0
$\begingroup$

For the LP problems with only inequality constraints, I know how to use simplex method to give an optimal solution.

However, when I want to calculate the minimax value, how should I use the simplex method? For example, in the following LP problem,

\begin{align} &\max & v \\ &s.t. & 5x_1 + 3x_2 \geq v \\ & & 2x_1 + 6x_2 \geq v \\ & & 4x_1 + 5x_2 \geq v \\ & & x_1 + x_2 = 1 \\ & & x_1, x_2 \geq 0 \end{align}

How should we build up an initial tableau for this problem?

$\endgroup$
  • $\begingroup$ Either replace $x_2$ with $1-x_1$ everywhere, or write $x_1+x_2\geq 1$ and $-x_1-x_2\geq 1$ instead of the equality. $\endgroup$ – 5xum Apr 16 at 9:41
  • $\begingroup$ Thanks! I could solve it with graphical method. I don't how to establish an initial tableau for this problem. $\endgroup$ – Shawn Guo Apr 16 at 9:59
1
$\begingroup$

Now, I see how to establish an initial tableau for LP problems with >= or = constraints. The following 2 videos are really helpful!

How to Solve a Linear Programming Problem Using the Big M Method

How to Solve a Linear Programming Problem Using the Two Phase Method

Take the LP problem in my question and Big M method for example. We need first convert it to standard form, which is given as follow:

\begin{align} &\max & v = x_3 - Ma \\ &s.t. & -5x_1 - 3x_2 + x_3 + s_1 = 0\\ & & -2x_1 - 6x_2 + x_3 + s_2 = 0\\ & & -4x_1 - 5x_2 + x_3 + s_3 = 0\\ & & x_1 + x_2 + a = 1 \\ & & x_1, x_2, s_1, s_2, s_3, a \geq 0 \end{align}

where $s_1,s_2,s_3$ are slack variables and $a$ is the artificial variable.

Rewriting $v=x_3-Ma$ as $v-x_3+Ma=0$, we can establish the following initial tableau:

\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline Basis & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & a & RHS \\ \hline s_1 & -5 & -3 & 1 & 1 & 0 & 0 & -1 & 0 \\ \hline s_2 & -2 & -6 & 1 & 0 & 1 & 0 & 0 & 0 \\ \hline s_3 & -4 & -5 & 1 & 0 & 0 & 1 & 0 & 0 \\ \hline a & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline \tilde{v}& 0 & 0 & -1 & 0 & 0 & 0 & M & 0 \\ \hline v & -M & -M & -1 & 0 & 0 & 0 & 0 & -M \\ \hline \end{array}

Note that, the $\tilde{v}$ row is temporary and not a part as the initial tableau, as it needs to be pivoted (the coefficient of $a$ is not $0$).

Then, we can see from the above tableau, the entering variable can be $x_1$, and the departing variable can be $a$. After pivoting, we get the following tableau,

\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline Basis & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & a & RHS \\ \hline s_1 & 0 & 2 & 1 & 1 & 0 & 0 & 5 & 5 \\ \hline s_2 & 0 & -4 & 1 & 0 & 1 & 0 & 2 & 2 \\ \hline s_3 & 0 & -1 & 1 & 0 & 0 & 1 & 0 & 4 \\ \hline x_1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline v & 0 & 0 & -1 & 0 & 0 & 0 & M & 0 \\ \hline \end{array}

The next entering variable is $x_3$ and the departing variable is $s_2$. After another pivoting, we get the following tableau,

\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline Basis & x_1 & x_2 & x_3 & s_1 & s_2 & s_3 & a & RHS \\ \hline s_1 & 0 & 6 & 0 & 1 & 0 & 0 & 3 & 3 \\ \hline x_3 & 0 & -4 & 1 & 0 & 1 & 0 & 2 & 2 \\ \hline s_3 & 0 & 3 & 0 & 0 & -1 & 1 & -2 & 2 \\ \hline x_1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline v & 0 & -4 & 0 & 0 & 1 & 0 & M+2& 2 \\ \hline \end{array}

Now, the entering variable is $x_2$ and the deparing varible is $s_1$. Thus, we can get the next-step tableau,

\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline Basis &x_1&x_2&x_3& s_1 & s_2 & s_3 & a & RHS \\ \hline x_2 & 0 &1 &0 &\frac{1}{6}& 0 & 0 &\frac{1}{2}&\frac{1}{2}\\ \hline x_3 & 0 & 0 & 1 &\frac{2}{3}& 1 & 0 & 4 & 4 \\ \hline s_3 & 0 & 0 & 0 &-\frac{1}{2}& -1 & 1 &-\frac{5}{2}&\frac{1}{2}\\ \hline x_1 & 1 & 0 & 0 &-\frac{1}{6}& 0 & 0 &\frac{1}{2}&\frac{1}{2}\\ \hline v & 0 & 0 & 0 &\frac{2}{3}& 1 & 0 & M+2 & 4 \\ \hline \end{array}

As all the coefficients in $v$ row are positive now and $a$ is not in the basis, we get the optimal solution for the original LP problem. That is,

$$x_1=\frac{1}{2}, x_2=\frac{1}{2}, v=4.$$

$\endgroup$
0
$\begingroup$

As 5xum has said, just replace $x_2$ by $1-x_1$

$\texttt{max} \ v$

$2x_1+3\geq v$

$-4x_1+6\geq v$

$-x_1+5\geq v$

Now you put the numbers on the RHS and $v$ on the LHS.

$\texttt{max} \ v$

$2x_1-v\geq -3$

$-4x_1-v\geq -6$

$-x_1-v\geq -5$

We can handle $v$ as an ordinary variable, $v\geq 0$

Multiplying the inequalities by (-1). The inequality signs of the constraints are turning around.

$\texttt{max} \ v$

$-2x_1+v\leq 3$

$4x_1+v\leq 6$

$x_1+v\leq 5$

$x_1,v\geq 0$

Therefore the initial table is

$$\begin{array}{|c|c|c|c|c|} \hline x_1&v&s_1&s_2&s_3&\textrm{RHS} \\ \hline 0&-1&0&0& 0&0 \\ \hline -2&\color{red}1&1&0&0& 3\\ \hline 4&1&0&1&0&6 \\ \hline 1&1&0&0&1&5 \\ \hline \end{array}$$

The first line is the objective function. According to the simplex algorithm the red marked element is the pivot element. Hint: The optimal solution is $(x_1^*,v^*)=(0.5,4)\Rightarrow x_2=0.5$

$\endgroup$
  • $\begingroup$ Thanks very much! Yes, we could replace x_2 with (1-x_1) in this specific LP problem. However, it isn't a general method to deal with LP problems containing >2 decision variables. $\endgroup$ – Shawn Guo Apr 17 at 9:31
  • $\begingroup$ @ShawnGuo The problem is not that there a two, maybe three, variables . That is trivial.. The difficulty is that the right hand side is variable. I´ve posted a way to obtain a standard form. $\endgroup$ – callculus Apr 17 at 12:15
  • $\begingroup$ @ShawnGuo Btw, could you go on and finish the calculation? $\endgroup$ – callculus Apr 17 at 12:26
  • $\begingroup$ Yes, of course. I'll finish them later. $\endgroup$ – Shawn Guo Apr 18 at 10:52
  • $\begingroup$ @ShawnGuo I´m looking forward to hear wether you could finish it or not. $\endgroup$ – callculus Apr 18 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.