Dual Problem
In the solution of linear programming, there are times when the solution is not unique, or degenerate solution. Multisolutions correspond to infinite solutions, while degenerate solution corresponds to basic variables which equal to 0. It seemly that there bears no relation between them. However, derived from the iterations of simplex table, the column of b and the row of test number represent a basic solution of the primal problem and the dual problem respectively.
If the primal problem has multisolutions, then:
(1)
all the test numbers are less than or equal to 0, while one of nonbasic variables equals to 0.
(2) one of the basic variables in the basic solution of the dual problem equals to 0, that is to say: a degenerated optimal solution.
Based on the analysis aforementioned, a conclusion can be reasonably drawn that : If the primal problem has multisolutions, then its dual problem has a degenerated optimal solution; If the dual problem has multisolutions, then the primal problem has a degenerated optimal solution.
