Math 484.1 October 23, 2003. Name:______L. Vaserstein__________________________
Midterm 2, 5 problems, 15 points each.
Solve linear programs where all x_{i} >= 0:
1.
2 
x_{2} 
3 
x_{3} 

1 
2 
3 
4 
= x_{1} 
5 
6 
7 
8 
= x_{4} 
0 
1 
2 
3 
> min 
combine two columns with constants on top together and multiply
a column by 1.
standard feasible tableau:
x_{2} 
x_{3} 
1 

2 
4 
7 
= x_{1} 
6 
8* 
11 
= x_{4} 
1 
3 
6 
> min 
pivot step according to Phase 2 of simplex method
x_{2} 
x_{4} 
1 

1* 
1/2 
3/2 
= x_{1} 
3/4 
1/8 
11/8 
= x_{3} 
5/4 
3/8 
15/8 
> min 
pivot step according to Phase 2 of simplex method
x_{1} 
x_{4} 
1 

1 
1/2 
3/2 
= x_{2} 
3/4 
1/4 
5/2 
= x_{3} 
5/4 
1/4 
0 
> min 
The x_{4}column is bad, so the program is unbounded.
2.
2 
x_{2} 
3 
x_{1} 

1 
2 
3 
4 
= x_{1} 
5 
6 
7 
8 
= x_{4} 
0 
1 
2 
3 
> min 
combine two columns with constants on top together
x_{2} 
x_{1} 
1 

2* 
4 
7 
= x_{1} 
6 
8 
11 
= x_{4} 
1 
3 
6 
> min 
pivot step
x_{1} 
x_{1} 
1 

1/2 
2 
7/2 
= x_{2} 
3 
4 
10 
= x_{4} 
1/2 
1 
5/2 
> min 
combine the first two columns. standard tableau:
x_{1} 
1 

5/2 
7/2 
= x_{2} 
7 
10 
= x_{4} 
1/2 
5/2 
> min 
x_{1}column is bad,. As x_{1}>
infinity, the objective function > infinity,
while x_{2} and x_{4 }become
positive.
The program is unbounded.
3.
2 
x_{2} 
3 
x_{3} 

1 
2 
3 
4 
= x_{1} 
5 
6 
7 
8 
= x_{1} 
0 
1 
2 
3 
> max 
combine two columns with constants on top together and multiply
a column by 1.
x_{2} 
x_{3} 
1 

2 
4 
7 
= x_{1} 
6 
8 
11 
= x_{1} 
1 
3 
6 
> max 
subtract the first row from the second row and multiply the third row by
1
x_{2} 
x_{3} 
1 

2 
4 
7 
= x_{1} 
4 
4* 
4 
= 0 
1 
3 
6 
> min 
pivot on 4 and drop the second column to obtain standard tableau
x_{2} 
1 

2 
3 
= x_{1} 
1 
1 
=x_{3} 
2 
3 
> min 
This is an optimal tableau, so min = 3 at x_{1 }=
3, x_{2 }= 0, x_{3}= 1. For the origional maximization
program,
max = 3 at x_{1 }= 3, x_{2 }= 0,
x_{3}= 1. (The optimal solution is unique.)
4.
x_{3} 
x_{2} 
3 
x_{3} 

1 
2 
3 
4 
= x_{1} 
5 
6 
7 
8 
= x_{4} 
0 
1 
2 
3 
> min 
combine the first and the last column and scale the third column to obtain
standard tableau
x_{3} 
x_{2} 
1 

3* 
2 
9 
= x_{1} 
3 
6 
21 
= x_{4} 
3 
1 
6 
> min 
pivot step according to Phase 2 of simplex method
x_{1} 
x_{2} 
1 

1/3 
2/3 
3 
= x_{3} 
1 
4 
12 
= x_{4} 
1 
1 
3 
> min 
x_{2}column is bad, so the program is unbounded.
5.
0 
x_{2} 
1 
x_{3} 

1 
2 
3 
4 
= x_{1} 
5 
6 
7 
8 
= x_{4} 
0 
1 
2 
3 
> min 
drop the first column, switch two columns, and multiply a column by 1
to obtain standard tableau
x_{2} 
x_{3} 
1 

2 
4* 
3 
= x_{1} 
6 
8 
7 
= x_{4} 
1 
3 
2 
> min 
pivot step according to Phase 2 of simplex method
x_{2} 
x_{1} 
1 

1/2 
1/4 
3/4 
=x_{3} 
2 
2 
1 
= x_{4} 
1/2 
3/4 
1/4 
> min 
x_{2}column is bad, so the program is unbounded.