Scribd
Upload
12 views2 pages

Dual Simplex Method Example Explained

This document describes using the dual simplex method to solve a linear programming problem with four variables (x1, x2, x3, x4) and three inequality constraints. It shows the steps of setting up the initial tableau and pivoting to solve the problem. When a new constraint is added, it demonstrates how to extend the existing optimal tableau to include the new constraint and variable without restarting from scratch. Pivoting again yields a feasible solution that satisfies all constraints.

Uploaded by

Amit Kankarwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views2 pages

Dual Simplex Method Example Explained

This document describes using the dual simplex method to solve a linear programming problem with four variables (x1, x2, x3, x4) and three inequality constraints. It shows the steps of setting up the initial tableau and pivoting to solve the problem. When a new constraint is added, it demonstrates how to extend the existing optimal tableau to include the new constraint and variable without restarting from scratch. Pivoting again yields a feasible solution that satisfies all constraints.

Uploaded by

Amit Kankarwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

An example of the dual simplex method

Suppose we are given the problem


Minimize z = 2x
1
+ 3x
2
+ 4x
3
+ 5x
4
subject to

x
1
x
2
+x
3
x
4
10,
x
1
2x
2
+3x
3
4x
4
6,
3x
1
4x
2
+5x
3
6x
4
15
x
1
, x
2
, x
3
, x
4
0.
(1)
If we would have inequalities instead of , then the usual simplex would work
nicely. The two-phase method is more tedious. But since all coecients in z =
2x
1
+ 3x
2
+ 4x
3
+ 5x
4
are non-negative, we are ne for the dual simplex.
Multiply the equations by 1 and add to each of the equations its own variable.
Then we get the following tableau.
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
0
= z 0 2 3 4 5 0 0 0
x
5
10 1 1 1 1 1 0 0
x
6
6 1 2 3 4 0 1 0
x
7
15 3 4 5 6 0 0 1
Choose Row 1 to pivot on. The ratio for x
1
is better than for x
3
, so pivot on a
1,1
.
After pivoting, we get
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
0
= z 20 0 5 2 7 2 0 0
x
1
10 1 1 1 1 1 0 0
x
6
4 0 1 2 3 1 1 0
x
7
15 0 1 2 3 3 0 1
Now every a
i,0
for i > 0 is nonnegative. So, the tableau is optimal. But suppose
that the boss adds now the new restriction:
x
1
+ 2x
2
+ 3x
3
4x
4
8.
With the dual simplex, we do not need to start from scratch. We simply add the
new row and one more column to our nal tableau.
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
0
= z 20 0 5 2 7 2 0 0 0
x
1
10 1 1 1 1 1 0 0 0
x
6
4 0 1 2 3 1 1 0 0
x
7
15 0 1 2 3 3 0 1 0
x
8
8 1 2 3 4 0 0 0 1
Excluding from the last row x
1
, x
6
and x
7
, we get the tableau
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
0
= z 20 0 5 2 7 2 0 0 0
x
1
10 1 1 1 1 1 0 0 0
x
6
4 0 1 2 3 1 1 0 0
x
7
15 0 1 2 3 3 0 1 0
x
8
2 0 3 2 3 1 0 0 1
Note that if in the last row there were no 3, then the LP would be infeasible.
Now we pivot on x
4
:
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
0
= z 74/3 0 12 20/3 0 13/3 0 0 7/3
x
1
32/3 1 2 1/3 0 4/3 0 0 1/3
x
6
2 0 4 0 0 0 1 0 1
x
7
13 0 4 0 0 2 0 1 1
x
4
2/3 0 1 2/3 1 1/3 0 0 1/3
Thus we got a solution again.

You might also like