game theorylinear programmingsimplex
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?
Maybe it's worthwhile to talk through where the dual comes from. This will take a while, but hopefully the dual won't seem so mysterious when we're done.
Suppose we want to use the primal's constraints as a way to find an upper bound on the optimal value of the primal. If we multiply the first constraint by $9$, the second constraint by $1$, and add them together, we get $9(2x_1 - x_2) + 1(x_1 +3 x_2)$ for the left-hand side and $9(1) + 1(9)$ for the right-hand side. Since the first constraint is an equality and the second is an inequality, this implies $$19x_1 - 6x_2 \leq 18.$$ But since $x_1 \geq 0$, it's also true that $5x_1 \leq 19x_1$, and so $$5x_1 - 6x_2 \leq 19x_1 - 6x_2 \leq 18.$$ Therefore, $18$ is an upper-bound on the optimal value of the primal problem.
Surely we can do better than that, though. Instead of just guessing $9$ and $1$ as the multipliers, let's let them be variables. Thus we're looking for multipliers $y_1$ and $y_2$ to force $$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9).$$
Now, in order for this pair of inequalities to hold, what has to be true about $y_1$ and $y_2$? Let's take the two inequalities one at a time.
The first inequality: $5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$
We have to track the coefficients of the $x_1$ and $x_2$ variables separately. First, we need the total $x_1$ coefficient on the right-hand side to be at least $5$. Getting exactly $5$ would be great, but since $x_1 \geq 0$, anything larger than $5$ would also satisfy the inequality for $x_1$. Mathematically speaking, this means that we need $2y_1 + y_2 \geq 5$.
On the other hand, to ensure the inequality for the $x_2$ variable we need the total $x_2$ coefficient on the right-hand side to be exactly $-6$. Since $x_2$ could be positive, we can't go lower than $-6$, and since $x_2$ could be negative, we can't go higher than $-6$ (as the negative value for $x_2$ would flip the direction of the inequality). So for the first inequality to work for the $x_2$ variable, we've got to have $-y_1 + 3y_2 = -6$.
Here we have to track the $y_1$ and $y_2$ variables separately. The $y_1$ variables come from the first constraint, which is an equality constraint. It doesn't matter if $y_1$ is positive or negative, the equality constraint still holds. Thus $y_1$ is unrestricted in sign. However, the $y_2$ variable comes from the second constraint, which is a less-than-or-equal to constraint. If we were to multiply the second constraint by a negative number that would flip its direction and change it to a greater-than-or-equal constraint. To keep with our goal of upper-bounding the primal objective, we can't let that happen. So the $y_2$ variable can't be negative. Thus we must have $y_2 \geq 0$.
Finally, we want to make the right-hand side of the second inequality as small as possible, as we want the tightest upper-bound possible on the primal objective. So we want to minimize $y_1 + 9y_2$.
Putting all of these restrictions on $y_1$ and $y_2$ together we find that the problem of using the primal's constraints to find the best upper-bound on the optimal primal objective entails solving the following linear program:
$$\begin{align*} \text{Minimize }\:\:\:\:\: y_1 + 9y_2& \\ \text{subject to }\:\:\:\:\: 2y_1 + y_2& \geq 5 \\ -y_1 + 3y_2& = -6\\ y_2 & \geq 0. \end{align*}$$
And that's the dual.
Primal Problem Dual Problem
(or Dual Problem) (or Primal Problem)
Maximization Minimization
Sensible <= constraint paired with nonnegative variable
Odd = constraint paired with unconstrained variable
Bizarre >= constraint paired with nonpositive variable
Sensible nonnegative variable paired with >= constraint
Odd unconstrained variable paired with = constraint
Bizarre nonpositive variable paired with <= constraint
I post the Octave code for you to verify the optimal solution shown above.
octave:1> c = [2 -1 3]';
octave:2> A = [2 3 -5; -1 9 -1; 4 6 3];
octave:3> b = [4 3 8]';
octave:4> [x_max,z_max] = glpk(c,A,b,[0,0,0]',[],"UUL","CCC")
x_max =
1.28571
0.47619
0.00000
z_max = 2.0952
Best Answer
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.$$