Math 407
Linear Optimization
Simplex Algorithm for Problems in Standard Form and having Feasible Origin
Solve the following LPs using the simplex algorithm in simplex tableau form. At each stage
of the simplex algorithm identify the BFS identified by the current tableau and give the
associated objective vale z. All of the problems below are in standard form and have feasible
origin.
1.
maximize
4x + 3y + 2z
subject to
x
+
z
2
x
y +
z
1
x +
y +
z
3
0
x, y,
z
Solution: (2, 1, 0), optimal value = 11.
2.
maximize
4x + 2y + 2z
subject to
x + 3y
2z
3
4x + 2y
4
x +
y +
z
2
0
x, y,
z
Solution: (1, 0, 1), optimal value = 6.
3.
maximize
7x
+ 9x
+
3x
1
2
3
subject to
5x
4x
x
10
1
2
3
x
x
4
1
2
3x
+ 4x
+
x
1
1
2
3
0
x
, x
,
x
.
1
2
3
Solution: (4, 0, 13), optimal value = 11.
4.
maximize
7x
+ 6x
+
5x
2x
+
3x
1
2
3
4
5
subject to
x
+ 3x
+
5x
2x
+
2x
4
1
2
3
4
5
4x
+ 2x
2x
+
x
+
x
3
1
2
3
4
5
2x
+ 4x
+
4x
2x
+
5x
5
1
2
3
4
5
3x
+
x
+
2x
x
+
2x
1
1
2
3
4
5
0
x
,
x
, x
,
x
, x
.
1
2
3
4
5
Solution: (0, 4/3, 2/3, 5/3, 0), optimal value = 8.
1