0

For a homework problem I am asked to implement the dual simplex algorithm on the following linear program:

$$ \min -25x_1 -30x_2 \\ \\ s.t. 5x_1 +4x_2 \leq 120 \\ \\ 20x_1 +30x_2 \leq 690 \\ \\ x_i \geq 0$$

Now the issue that I am having is that once this problem is converted to standard form by adding the variables $x_3, x_4$, the initial solution using the third and fourth columns to obtain the basis matrix $I_2$ yields the "optimal" solution according to the algorithm since $B^{-1}b = I_2(120, 690)^T = (120, 690)^T \geq 0$.

I feel like there is something I am missing in the setup to this problem because clearly this is not a solution to the original LP, but according to the dual simplex algorithm I should terminate immediately.

Any help would be appreciated. 

AnotherPerson
  • 5,842
  • The termination condition you're using is wrong. If you form the tableau, you have that the entries in the last row are negative. So you must pivot. – V.S.e.H. Nov 13 '23 at 00:37
  • What kind of tableau are you considering? I've seen the represented multiple ways. – AnotherPerson Nov 22 '23 at 19:21
  • Here's how the initial tableau would look like: $$ \begin{pmatrix} 5 & 4&1&0&120\ 20 & 30 &0&1&690\ -25 & -30 & 0 & 0&0 \end{pmatrix} $$ The last row, with the exception of the last element, must contain nonnegative numbers after pivoting. – V.S.e.H. Nov 22 '23 at 20:03
  • So then how is this the dual simplex algorithm? All you did was write the tableau for the simplex algorithm. – AnotherPerson Nov 22 '23 at 23:45
  • You've asked me what kind of tableau I'm using, and here it is. I assumed that you already know how the algorithm works, and specifically what pivoting is. In this answer I use the algorithm to solve an LP. – V.S.e.H. Nov 22 '23 at 23:52
  • So I understand the simplex algorithm, what I am not understanding is the DUAL simplex algorithm. In particular for this problem we did not even consider anything regarding solutions of the dual LP. – AnotherPerson Nov 22 '23 at 23:58
  • Then you would know that you'd be working with the DUAL of the primal problem, and performing the standard simplex algorithm as usual on the dual, see this – V.S.e.H. Nov 23 '23 at 00:09

0 Answers0