Dual Simplex Method
Dual Simplex Method
Introduction
Primal Problem
Maximize
Z
=
3
x
1
+
5
x
2
Z=3 x_{1}+5 x_{2}
Z=3x1+5x2
subject to
x
1
≤
4
2
x
2
≤
12
3
x
1
+
2
x
2
≤
18
\begin{aligned} x_{1} & \leq 4 \\ 2 x_{2} & \leq 12 \\ 3 x_{1}+2 x_{2} & \leq 18 \end{aligned}
x12x23x1+2x2≤4≤12≤18
and
x
1
≥
0
,
x
2
≥
0
x_{1} \geq 0, \quad x_{2} \geq 0
x1≥0,x2≥0
Graphical Analysis
Solve primal problem using simplex method
Dual Problem
Maximize
Z
=
−
4
y
1
−
12
y
2
−
18
y
3
\text { Maximize } \quad Z=-4 y_{1}-12 y_{2}-18 y_{3}
Maximize Z=−4y1−12y2−18y3
subject to
y
1
+
3
y
3
≥
3
2
y
2
+
2
y
3
≥
5
\begin{array}{r} y_{1}+3 y_{3} \geq 3 \\ 2 y_{2}+2 y_{3} \geq 5 \end{array}
y1+3y3≥32y2+2y3≥5
and
y
1
≥
0
,
y
2
≥
0
,
y
3
≥
0
y_{1} \geq 0, \quad y_{2} \geq 0, \quad y_{3} \geq 0
y1≥0,y2≥0,y3≥0
Solve dual problem using dual simplex method
Compare simplex method and dual simplex method
- The simplex method deals directly with basic solutions in the primal problem that are primal feasible( B − 1 b ≥ 0 B^{-1} b \geq 0 B−1b≥0) but not dual feasible. It then moves toward an optimal solution by striving to achieve dual feasibility (optimality test, C − C B B − 1 A ≤ 0 C-C_{B} B^{-1} A \leq 0 C−CBB−1A≤0) providing primal feasible(minimum ratio, B − 1 b ≥ 0 B^{-1} b \geq 0 B−1b≥0).
- The dual simplex method deals with basic solutions in the primal problem that are dual feasible( C − C B B − 1 A ≤ 0 C-C_{B} B^{-1} A \leq 0 C−CBB−1A≤0) but not primal feasible. It then moves toward an optimal solution by striving to achieve primal feasibility (optimality test, B − 1 b ≥ 0 B^{-1} b \geq 0 B−1b≥0) providing dual feasible(minimum ratio, C − C B B − 1 A ≤ 0 C-C_{B} B^{-1} A \leq 0 C−CBB−1A≤0).
- According to the strong duality, both primal problem and dual problem approaches optimal solution when both are feasible.