# How to calculate minimax value with simplex method?

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?

• 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. – 5xum Apr 16 at 9:41
• Thanks! I could solve it with graphical method. I don't how to establish an initial tableau for this problem. – Shawn Guo Apr 16 at 9:59

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

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

• 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. – Shawn Guo Apr 17 at 9:31
• @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. – callculus Apr 17 at 12:15
• @ShawnGuo Btw, could you go on and finish the calculation? – callculus Apr 17 at 12:26
• Yes, of course. I'll finish them later. – Shawn Guo Apr 18 at 10:52
• @ShawnGuo I´m looking forward to hear wether you could finish it or not. – callculus Apr 18 at 12:47