The Dual of a Linear Program

The other item on the Simplex menu is Dual. It computes the dual of a linear program.


$\blacktriangleright$ Simplex + Dual

x + y
4x + 3y≤6
3x + 4y≤4
x≥ 0
- y≤ 0
, Dual system is:
6s1 +4s2
1≤3s1 +4s2 - s4
1≤4s1 +3s2 - s3

Applying the simplex algorithm to these two linear programs yields the following results.

$\blacktriangleright$ Simplex + Maximize

x + y
4x + 3y≤6
3x + 4y≤4
x≥ 0
- y≤ 0
, Maximum is at: $\left\{\vphantom{ y=0,x=%
\frac{4}{3}}\right.$y = 0, x = ${\frac{{4}}{{3}}}$$\left.\vphantom{ y=0,x=%
\frac{4}{3}}\right\}$

$\blacktriangleright$ Simplex + Minimize

6s1 +4s2
1≤4s1 +3s2 - s4
1≤3s1 +4s2 - s3
s1≥ 0
s2≥ 0
s3≥ 0
s4≥ 0
, Minimum is at: $\left\{\vphantom{ s_{4}=0,s_{1}=0,s_{2}=\frac{1}{3},s_{3}=\frac{1}{3}}\right.$s4 = 0, s1 = 0, s2 = ${\frac{{1}}{{3}}}$, s3 = ${\frac{{1}}{{3}}}$$\left.\vphantom{ s_{4}=0,s_{1}=0,s_{2}=\frac{1}{3},s_{3}=\frac{1}{3}}\right\}$