How to calculate minimax value with simplex method?

Question

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?

Answer 1

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.$$

Answer 2

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$