1. Given the following linear programs with feasible basis B, do the following:
(i) solve the linear program without tableau, give an appropriate certi cate
(you should include the canonical form. for each basis you are working on)
(ii) solve the linear program with tableau
(a) maximize x1 x2 + 2x3 3x5 + 6x6
subject to x1 + x2 + 2x3 x4 2x5 + 3x6 = 4
x1 x2 4x3 + x4 + 4x5 5x6 = 8
2x2 + x3 x4 2x5 + 2x6 = 5
x1;x2;x3;x4;x5;x6 0
Basis B =f1;3;5g
(b) maximize 2x1 + x2 x3 + 3x4 + 2x5 x6
subject to x1 x2 + x4 + x5 2x6 = 1
x1 + x2 2x3 + x5 + x6 = 2
x1 + x2 + x3 + x4 x5 + x6 = 1
x1;x2;x3;x4;x5;x6 0
Basis B =f1;2;5g
2. For the following linear programs, use an auxiliary LP to determine if it is feasible.
If the LP is infeasible, nd and verify a certi cate of infeasibility.
If the LP is feasible, nd a feasible basis.
(a) maximize 12x1 + x2 + 5x4 9x5
subject to x1 x2 + x3 2x4 3x5 = 3
2x1 + 3x3 2x4 + x5 = 4
x1 3x2 + x4 3x5 = 1
x1;x2;x3;x4;x5 0
(b) maximize 2x1 + x2 x3 + 4x4 + x5
subject to x1 + 3x2 x3 + 2x4 + 3x5 = 0
2x1 2x2 x3 + 2x4 3x5 = 5
2x1 x2 + x3 2x5 = 2
x1;x2;x3;x4;x5 0
For this question, you must use the following rule when you perform. the Simplex
Method on the auxiliary LP: If there are multiple choices of which variable be-
comes basic, choose the one whose coe cient is smallest in the objective function
of the canonical form.
3. Consider the given LP:
maximize x1 x2 + x3 + 5x4 + 2x5
subject to x1 + 2x2 + x3 + 3x4 + x5 = 6
2x1 + 2x2 x3 + 8x4 + x5 = 5
x1 4x2 x4 + 2x5 = 1
x1;x2;x3;x4;x5 0
Determine if the following tableaux, which are in canonical form, correspond to a
tableau of the given LP.
(a)1 0 2 0 1 0 7
0 1 2 0 3 0 3
0 0 1 0 1 1 1
0 0 1 1 1 0 2
3775
(b)
1 2 1 0 0 0 11
0 2 1 1 0 0 2
0 1 1 0 1 0 1
0 1 1 0 0 1 2
(c)
1 5=3 16=3 0 0 0 10
0 1=3 2=3 0 1 0 1
0 1=3 5=3 0 0 1 0
0 1=3 5=3 1 0 0 3
For further practice:
By the time this assignment is due, you will know how to show an LP in SEF is feasible or
not and how to nd a starting feasible basis for the simplex method. You should try making
up a "random" LP with some number of constraints (2 or 3) and variables (say around 3 to
4), and do the following:
1. Convert the LP to SEF.
2. Show the LP is infeasible or has a feasible basis.
3. If the LP is feasible, solve it or show it is unbounded, trying BOTH with and without
tableau.
4. Find the appropriate certi cate to prove your result. Verify it satis es the properties
of a certi cate.
Its recommended you try a couple of these every week until the nal to make sure you are
not "rusty" when it comes to dealing with LPs.
Additional study ideas:
Try to change some of the values in the examples you have worked on before (the coe cients
in the constraints, or the objective function, or both) to change the type of LP you are
dealing with (infeasible, optimal solution exists, unbounded). You might gain some further
insight into the structure of LPs. (This is actually analyzed in detail in CO 327.)