- #1
catcherintherye
- 47
- 0
hello,I have been given the transportation problem (T)
defined by the cost matrix
<br /> \left(\begin{array}{ccccccc}5&3&9&3&8&2\\5&6&3&15&7&16\\9&20&10&22&17&25\\3&7&3&14&9&14\end{array}\right)<br />
the demand vector q=(2,8,9,4,6,2)
the supply vector p=(3,13,6,9)
the problem is as follows
a) use the northwest vertex rule to find a basic feasible solution of (T)
...this i found to be
<br /> \left(\begin{array}{ccccccc}2&1&0&0&0&0\\0&7&6&0&0&0\\0&0&3&3&0&0\0&0&0&1&6&2\end{array}\right)<br />
(b) write down the linear program for the dual program (T*)
...this i found to be
(T*)
<br /> maximize \sum_{i=1}^{4}p_i y_i + \sum_{j=1}^{6}q_j z_j <br />
subject to
<br /> \\ y_i + z_j \leq c_ij, y_1,...,y_4,z_1,...z_6,<br />
(c) use the complementary slackness conditions to show that the shipping matrix
<br /> \left(\begin{array}{ccccccc}0&0&0&1&0&2\\0&7&0&0&6&0\\2&0&4&0&0&0\\0&1&5&3&0&0\end{array}\right)<br /> [\tex]<br /> <br /> solves (T)<br /> <br /> now since i have <br /> x_i_j &gt; 0 <br /> <br /> for (i,j) = (1,4), (1,6), (2,2), (2,5), (3,1), (3,3), (4,2), (4,3), (4,4) complementary slackness implies that the associated dual constraints are binding and we have a system of nine equations in 10 unknowns. Now here is the rub. I would usually progress by substituting the above values (from the shipping matrix) into the primal constraints and derive that one of them is non binding, then deduce that the associated dual variable is zero by complementary slackness. However since we have here supply=demand, no such constraint will occur. I have done a similar problem where the next progression was to assume that one of the dual variables say y_1 is 0 and then the system of nine equalities from above are solvable, however if as an example i take y_1 =0, this implies that z_3 =-8 which is infeasible. In fact as it turned out assuming any dual variable y_1, ...y_4, z_1,...,z_6 to be zero will lead to another dual vaiable in the system being negative. What am I missing<img src="https://cdn.jsdelivr.net/joypixels/assets/8.0/png/unicode/64/1f615.png" class="smilie smilie--emoji" loading="lazy" width="64" height="64" alt=":confused:" title="Confused :confused:" data-smilie="5"data-shortname=":confused:" />
defined by the cost matrix
<br /> \left(\begin{array}{ccccccc}5&3&9&3&8&2\\5&6&3&15&7&16\\9&20&10&22&17&25\\3&7&3&14&9&14\end{array}\right)<br />
the demand vector q=(2,8,9,4,6,2)
the supply vector p=(3,13,6,9)
the problem is as follows
a) use the northwest vertex rule to find a basic feasible solution of (T)
...this i found to be
<br /> \left(\begin{array}{ccccccc}2&1&0&0&0&0\\0&7&6&0&0&0\\0&0&3&3&0&0\0&0&0&1&6&2\end{array}\right)<br />
(b) write down the linear program for the dual program (T*)
...this i found to be
(T*)
<br /> maximize \sum_{i=1}^{4}p_i y_i + \sum_{j=1}^{6}q_j z_j <br />
subject to
<br /> \\ y_i + z_j \leq c_ij, y_1,...,y_4,z_1,...z_6,<br />
(c) use the complementary slackness conditions to show that the shipping matrix
<br /> \left(\begin{array}{ccccccc}0&0&0&1&0&2\\0&7&0&0&6&0\\2&0&4&0&0&0\\0&1&5&3&0&0\end{array}\right)<br /> [\tex]<br /> <br /> solves (T)<br /> <br /> now since i have <br /> x_i_j &gt; 0 <br /> <br /> for (i,j) = (1,4), (1,6), (2,2), (2,5), (3,1), (3,3), (4,2), (4,3), (4,4) complementary slackness implies that the associated dual constraints are binding and we have a system of nine equations in 10 unknowns. Now here is the rub. I would usually progress by substituting the above values (from the shipping matrix) into the primal constraints and derive that one of them is non binding, then deduce that the associated dual variable is zero by complementary slackness. However since we have here supply=demand, no such constraint will occur. I have done a similar problem where the next progression was to assume that one of the dual variables say y_1 is 0 and then the system of nine equalities from above are solvable, however if as an example i take y_1 =0, this implies that z_3 =-8 which is infeasible. In fact as it turned out assuming any dual variable y_1, ...y_4, z_1,...,z_6 to be zero will lead to another dual vaiable in the system being negative. What am I missing<img src="https://cdn.jsdelivr.net/joypixels/assets/8.0/png/unicode/64/1f615.png" class="smilie smilie--emoji" loading="lazy" width="64" height="64" alt=":confused:" title="Confused :confused:" data-smilie="5"data-shortname=":confused:" />