Complementary slackness and the transportation problem

  • Thread starter catcherintherye
  • Start date
In summary, the conversation discusses a transportation problem with a cost matrix, demand vector, and supply vector. The first part of the problem asks for a basic feasible solution using the northwest vertex rule. The second part involves writing down the linear program for the dual program and using complementary slackness conditions to show that the given shipping matrix solves the problem. However, the speaker is unsure about how to proceed with finding a feasible solution due to the equal supply and demand. They have attempted to assume one of the dual variables to be zero, but this leads to another dual variable being negative. They are seeking help and need a prompt answer for their upcoming referral.
  • #1
catcherintherye
48
0
hello,I have been given the transportation problem (T)

defined by the cost matrix
[tex]
\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)
[/tex]


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

[tex]
\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)
[/tex]



(b) write down the linear program for the dual program (T*)

...this i found to be

(T*)

[tex]
maximize \sum_{i=1}^{4}p_i y_i + \sum_{j=1}^{6}q_j z_j
[/tex]

subject to
[tex]
\\ y_i + z_j \leq c_ij, y_1,...,y_4,z_1,...z_6,
[/tex]

(c) use the complementary slackness conditions to show that the shipping matrix

[tex]
\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)
[\tex]

solves (T)

now since i have
[tex] x_i_j > 0 [/tex]

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 [tex] y_1 [/tex] 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 [tex] y_1, ...y_4, z_1,...,z_6 [/tex] to be zero will lead to another dual vaiable in the system being negative. What am I missing:confused:
 
Physics news on Phys.org
  • #2
btw, i really need a prompt answer if at all possible, this is for my referal which has to be in next week!
 
  • #3

Hello,

Thank you for sharing your progress on the transportation problem. It seems like you have a good understanding of the problem and have made significant progress in solving it.

To answer your question about the complementary slackness conditions, it is important to note that in this case, the primal and dual variables are not independent. This means that if one primal variable is fixed at a certain value, it will determine the values of other primal and dual variables. Therefore, we cannot simply assume that one dual variable is zero and solve the system of equations.

Instead, we can use the complementary slackness conditions to show that the shipping matrix you have found is a feasible solution to the primal problem. This means that the primal constraints are satisfied, and therefore, the associated dual variables must also satisfy their constraints. In this case, we can see that the shipping matrix satisfies the primal constraints and also satisfies the complementary slackness conditions. This proves that it is a feasible solution to the primal problem.

I hope this helps clarify any confusion you may have had. Keep up the good work!
 

1. What is the concept of complementary slackness in the context of the transportation problem?

Complementary slackness is a fundamental concept in the transportation problem that refers to the relationship between the supply and demand constraints. It states that for an optimal solution, the amount allocated from a particular source must be equal to the amount demanded at the corresponding destination. In other words, the unused supply at a source must be equal to the excess demand at a destination.

2. How does complementary slackness help in solving the transportation problem?

Complementary slackness helps in simplifying the solution process for the transportation problem by reducing the number of variables and constraints that need to be considered. It allows us to focus on the variables with non-zero values and eliminates the need for solving a large number of linear equations. This makes the solution process more efficient and manageable.

3. Can complementary slackness be applied to any transportation problem?

Yes, complementary slackness can be applied to any transportation problem as long as it satisfies the assumptions of the model, such as a fixed supply and demand, and the cost of transportation is linear and constant. It is a general principle that can be used to find optimal solutions for a variety of transportation problems.

4. What happens if complementary slackness does not hold in an optimal solution?

If complementary slackness does not hold in an optimal solution, it indicates that the solution is not feasible or that it is not the optimal solution. In such cases, the problem needs to be re-evaluated and a new solution must be found by adjusting the parameters or constraints.

5. Can complementary slackness be used to find the optimal solution for a transportation problem with multiple sources and destinations?

Yes, complementary slackness can be applied to solve transportation problems with multiple sources and destinations. However, it may become more complex as the number of variables and constraints increases. In such cases, complementary slackness can still be used, but additional methods and techniques may also be required to find the optimal solution.

Similar threads

  • Linear and Abstract Algebra
Replies
3
Views
780
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Linear and Abstract Algebra
Replies
6
Views
2K
  • Linear and Abstract Algebra
Replies
4
Views
3K
Replies
3
Views
577
  • MATLAB, Maple, Mathematica, LaTeX
Replies
3
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
21
Views
2K
  • General Math
Replies
4
Views
761
  • Calculus and Beyond Homework Help
Replies
8
Views
535
Back
Top