Note on the problem statement
In the second constraint, the last term appears to be written as − 2 y 2 -2y_2 − 2 y 2 y 4 y_4 y 4
− y 1 − y 2 − y 3 − 2 y 4 ≥ − 3 -y_1-y_2-y_3-2y_4\geq -3 − y 1 − y 2 − y 3 − 2 y 4 ≥ − 3
was intended. We first solve this intended version. The literal reading with − 2 y 2 -2y_2 − 2 y 2
1. Conversion to a maximization problem
Multiplying the objective and the constraints by − 1 -1 − 1
max 10 y 1 + 6 y 2 + 12 y 3 + 8 y 4 s.t. 2 y 1 + y 2 + 3 y 3 + y 4 ≤ 4 , y 1 + y 2 + y 3 + 2 y 4 ≤ 3 , y 1 , y 2 , y 3 , y 4 ≥ 0. \begin{aligned}
\max\quad &10y_1+6y_2+12y_3+8y_4\\
\text{s.t.}\quad
&2y_1+y_2+3y_3+y_4\leq4,\\
&y_1+y_2+y_3+2y_4\leq3,\\
&y_1,y_2,y_3,y_4\geq0.
\end{aligned} max s.t. 10 y 1 + 6 y 2 + 12 y 3 + 8 y 4 2 y 1 + y 2 + 3 y 3 + y 4 ≤ 4 , y 1 + y 2 + y 3 + 2 y 4 ≤ 3 , y 1 , y 2 , y 3 , y 4 ≥ 0. The optimal value of the original minimization problem is the negative of the optimal value of this maximization problem.
2. The dual problem
Each of the two constraints gets a dual variable x 1 x_1 x 1 x 2 x_2 x 2
min 4 x 1 + 3 x 2 s.t. 2 x 1 + x 2 ≥ 10 , x 1 + x 2 ≥ 6 , 3 x 1 + x 2 ≥ 12 , x 1 + 2 x 2 ≥ 8 , x 1 , x 2 ≥ 0. \begin{aligned}
\min\quad &4x_1+3x_2\\
\text{s.t.}\quad
&2x_1+x_2\geq10,\\
&x_1+x_2\geq6,\\
&3x_1+x_2\geq12,\\
&x_1+2x_2\geq8,\\
&x_1,x_2\geq0.
\end{aligned} min s.t. 4 x 1 + 3 x 2 2 x 1 + x 2 ≥ 10 , x 1 + x 2 ≥ 6 , 3 x 1 + x 2 ≥ 12 , x 1 + 2 x 2 ≥ 8 , x 1 , x 2 ≥ 0. The feasible region lies above the drawn lines.
Graphical solution of the dual
The relevant corner points and objective values are
( x 1 , x 2 ) 4 x 1 + 3 x 2 ( 0 , 12 ) 36 ( 2 , 6 ) 26 ( 4 , 2 ) 22 ( 8 , 0 ) 32 \begin{array}{c|c}
(x_1,x_2)&4x_1+3x_2\\ \hline
(0,12)&36\\
(2,6)&26\\
(4,2)&22\\
(8,0)&32
\end{array} ( x 1 , x 2 ) ( 0 , 12 ) ( 2 , 6 ) ( 4 , 2 ) ( 8 , 0 ) 4 x 1 + 3 x 2 36 26 22 32 Hence the optimal dual solution is
x ∗ = ( 4 , 2 ) \boxed{x^*=(4,2)} x ∗ = ( 4 , 2 )
with optimal value
4 x 1 ∗ + 3 x 2 ∗ = 22 . \boxed{4x_1^*+3x_2^*=22}. 4 x 1 ∗ + 3 x 2 ∗ = 22 .
3. Complementary slackness
Since
x 1 ∗ = 4 > 0 , x 2 ∗ = 2 > 0 , x_1^*=4>0,\qquad x_2^*=2>0, x 1 ∗ = 4 > 0 , x 2 ∗ = 2 > 0 ,
both primal constraints must be active:
2 y 1 + y 2 + 3 y 3 + y 4 = 4 , y 1 + y 2 + y 3 + 2 y 4 = 3. \begin{aligned}
2y_1+y_2+3y_3+y_4&=4,\\
y_1+y_2+y_3+2y_4&=3.
\end{aligned} 2 y 1 + y 2 + 3 y 3 + y 4 y 1 + y 2 + y 3 + 2 y 4 = 4 , = 3. Now consider the slacks of the dual constraints:
2 x 1 ∗ + x 2 ∗ − 10 = 0 , x 1 ∗ + x 2 ∗ − 6 = 0 , 3 x 1 ∗ + x 2 ∗ − 12 = 2 , x 1 ∗ + 2 x 2 ∗ − 8 = 0. \begin{aligned}
2x_1^*+x_2^*-10&=0,\\
x_1^*+x_2^*-6&=0,\\
3x_1^*+x_2^*-12&=2,\\
x_1^*+2x_2^*-8&=0.
\end{aligned} 2 x 1 ∗ + x 2 ∗ − 10 x 1 ∗ + x 2 ∗ − 6 3 x 1 ∗ + x 2 ∗ − 12 x 1 ∗ + 2 x 2 ∗ − 8 = 0 , = 0 , = 2 , = 0. The third dual constraint has positive slack. Complementary slackness therefore implies
y 3 ∗ = 0 . \boxed{y_3^*=0}. y 3 ∗ = 0 .
This leaves the equations
2 y 1 + y 2 + y 4 = 4 , y 1 + y 2 + 2 y 4 = 3. \begin{aligned}
2y_1+y_2+y_4&=4,\\
y_1+y_2+2y_4&=3.
\end{aligned} 2 y 1 + y 2 + y 4 y 1 + y 2 + 2 y 4 = 4 , = 3. Setting y 4 = t y_4=t y 4 = t
y 1 = 1 + t , y 2 = 2 − 3 t , y 3 = 0. y_1=1+t,\qquad y_2=2-3t,\qquad y_3=0. y 1 = 1 + t , y 2 = 2 − 3 t , y 3 = 0.
Nonnegativity gives
0 ≤ t ≤ 2 3 . 0\leq t\leq\frac23. 0 ≤ t ≤ 3 2 .
So there is not just one optimal solution, but a whole line segment of optimal solutions:
y ∗ ( t ) = ( 1 + t , 2 − 3 t , 0 , t ) , 0 ≤ t ≤ 2 3 . \boxed{
y^*(t)=
\left(1+t,\;2-3t,\;0,\;t\right),
\qquad
0\leq t\leq\frac23
}. y ∗ ( t ) = ( 1 + t , 2 − 3 t , 0 , t ) , 0 ≤ t ≤ 3 2 . Set of optimal primal solutions in the (y₄,y₂)-plane
For example, one particularly simple solution is
y ∗ = ( 1 , 2 , 0 , 0 ) \boxed{y^*=(1,2,0,0)} y ∗ = ( 1 , 2 , 0 , 0 )
Its original objective value is
− 10 ⋅ 1 − 6 ⋅ 2 − 12 ⋅ 0 − 8 ⋅ 0 = − 22. -10\cdot1-6\cdot2-12\cdot0-8\cdot0=-22. − 10 ⋅ 1 − 6 ⋅ 2 − 12 ⋅ 0 − 8 ⋅ 0 = − 22. So for the intended problem statement the result is
min = − 22 . \boxed{\min=-22}. min = − 22 .
If − 2 y 2 -2y_2 − 2 y 2
Then the second rewritten constraint becomes
y 1 + 3 y 2 + y 3 ≤ 3. y_1+3y_2+y_3\leq3. y 1 + 3 y 2 + y 3 ≤ 3.
In particular, the dual then includes
x 1 ≥ 8. x_1\geq8. x 1 ≥ 8.
Its optimal solution is
x ∗ = ( 8 , 0 ) , 4 x 1 ∗ + 3 x 2 ∗ = 32. x^*=(8,0),\qquad 4x_1^*+3x_2^*=32. x ∗ = ( 8 , 0 ) , 4 x 1 ∗ + 3 x 2 ∗ = 32.
Complementary slackness yields
y ∗ = ( 0 , 0 , 0 , 4 ) , \boxed{y^*=(0,0,0,4)}, y ∗ = ( 0 , 0 , 0 , 4 ) ,
and the original minimal objective value under this literal reading would be
min = − 32 . \boxed{\min=-32}. min = − 32 .
Alternative under the literal reading with −2y₂
