1. (a)
Solve the following linear programming problem, using our standard two phase method and using Anstee’s rule. It will take three pivots in phase 1 (including special pivot to feasibility) and one pivot in phase 2.
Solution.
Phase 1 initial dictionary:
x4 = 4 −x2 x5 = −3 −x1 +x2 x6 = −1 −x1
Phase 1 ends, initial dictionary for phase 2:
x2=3+x1 +x5 x3=1 +x1 +x6 x4 = 2 −x5 +x6
z = 4 −3×1 +2×5 −2×6 Then x5 enters, x4 exits:
x2 = 5 +x1 −x4 +x6
Math 340 Practice problems. Solutions.
Maximize −3×1 +2×2 x2 x1 −x2
x1
−2×3
−x3 ≤ 4
≤ −3 −x3 ≤ −1
x1,x2,x3 ≥0
+x3 +x0 +x0 +x3 +x0 w= −x0
Special pivot to feasibility, x0 enters, x5 its:
x0= 3+x1 −x2 +x5 x4 = 7 +x1 −2×2 +x3 +x5 x6= 2 −x2 +x3 +x5
w= −3 −x1 +x2 −x5 Now x2 enters, x6 exits:
x0 = 1 +x1 −x3 +x6 x2=2 +x3+x5−x6 x4 = 3 +x1 −x3 −x5 +2×6
ex-
w= −1 −x1 +x3 Next x3 enters, x0 exits:
x2=3+x1 +x5 x3=1+x1
x4=2 −x5 +x6 +x0
z= 8 −3×1 −2×4
And we’ve reached optimality. The opti- malsolutionisx1 =0,×2 =5,×3 =1, x4 =0,×5 =2,×6 =0whichmakesz=8.
−x0 +x6 −x0
−x6
w= −x0
(b) Either give two optimal solutions or show the optimal solution is unique.
Solution. In any optimal solution x1 = x4 = 0 because they appear with negative coefficient in the z-row of the final dictionary (recall the argument: since x1,x4 ≥ 0, wehavez=8−3×1−2×4 ≤8;equalitycanonlyholdifx1 =x4 =0). Butx6 isa non-basic variable with zero coefficient in the z-row, this has the potential for multiple solutions. Looking at the top part of the dictionary, we see that x6 can take any non- negative value without any other variable becoming zero, so all solutions are given by (x1,x2,x3,x4,x5,x6) = (0,5+t,1+t,0,2+t,t) for t ≥ 0. (The problem, of course, just asks for one additional solution, so we could have just set x6 = 3 or whatever.)
1
x3=1 +x1 x5=2
+x6 −x4 +x6
2. Consider the following linear program:
Maximize −2×1 +3×2 +x2 −x1 +x2 x1 +x2
+7×3
+2×3 ≤2 +4×3 ≤3 +4×3 ≤4
x1,x2,x3 ≥0 (a) Give the Dual Linear Program of the above Primal Linear Program.
Solution.
y1,y2,y3 ≥0
(b) You are given that an optimal primal solution has x∗ = 0, x∗ = 1, x∗ = 1 . Determine
an optimal dual solution (without pivoting), stating which theorems you have used.
Solution. We will use Complementary Slackness: since x∗2,x∗3 > 0, the second and third constraint of dual have no slack:
y 1∗ + y 2∗ + y 3∗ = 3 2y1∗ +4y2∗ +4y3∗ =7
Minimize 2y1 +3y2 +4y3
−y2 +y3 ≥ −2
y1 +y2 +y3 ≥3 2y1 +4y2 +4y3 ≥ 7
Now we check the primal constraints for slack. Only the third constraint has slack, so again by Complementary Slackness, we have y3∗ = 0.
Solving the equations we have found, we get that there is only one optimal dual solution, namely: y∗ = 5 , y∗ = 1 , y∗ = 0
1232
12223
(c) Consider changing the objective function of the primal by raising the coefficient of x1
from −2 to −1. Does the primal solution x∗ = 0, x∗ = 1, x∗ = 1 and the optimal dual 1232
solution determined in b) remain optimal to their new LP’s? Explain.
Solution. Yes, they remain optimal. One way we can check is by using weak duality: if you have feasible primal and dual solutions which have equal objective function values, both must be optimal. So consider the old optimal primal and dual solutions for the new primal and new dual. The old optimal primal soltion remains feasible for the new primal because the primal’s constraints haven’t changed. The old optimal dual solution remains feasible because the only dual constraint that changes is the first one, which becomes −y2∗ + y3∗ ≥ −1 and is still true. Finally, the objective functions agree: the one for the dual hasn’t changed; the primal objective function has changed, but the only change is in the coefficient of x1 and since x∗1 = 0 the value doesn’t change.
3. Given Aaug,b,caug, current basis (and A−1 for your computational ease), use our Revised B
Simplex method and Anstee’s rule to determine the next entering variable (if there is one), the next leaving variable (if there is one), and the new basic feasible solution after the pivot as well as the new basis matrix AB (if there is both an entering and leaving variable). The current basis is {x7, x3, x2}.
x1 x2 x3 x4 x5 x6 x7 x5 x6 x7
x52 −1 0 −1 1 0 0 x5−3 x7−3 1 1
Aaug= x61 −1 1 1 0 1 0,b= x6−2,A−1= x3−1 1 0 B
x7 0 −2 −1 1 0 0 1 x7 −5 2
x2 −1 0 0
x1 x2 x3 x4 x5 x6 x7 (caug)⊤=1 −1 1 2 0 0 0
Solution. The coefficients in the z-row are given by c⊤ − c⊤A−1AN , which is: NBB
x5 x6 x7 x1 x4 x5 x6 x1 x4 x5 x6 x7 x3 x2 x7−3 1 1x52 −1 1 0
1 2 0 0−0 1 −1x3−1 1 0x61 1 0 1= x2 −1 0 0 x7 0 1 0 0
x1 x4 x5 x6 x1 x4 x5 x6 x5 x6 x7 x52 −1 1 0
1 2 0 0−0 1 0x61 1 0 1= x7 0 1 0 0
x1 x4 x5 x6 x1 x4 x5 x6 x1 x4 x5 x6 1 2 0 0−1 1 0 1=0 1 0 −1.
So the entering variable is x4. To determine the exiting variable we need to find the largest t≥0suchthatA−1b−tA−1A4 ≥0.
BB
x72 x75 x72−5t We have: A−1b = x31 and A−1A4 = x32, so A−1b−tA−1A4 = x31−2t,
BBBB
x2 3 x2 1 x2 3−t which is ≥ 0 for t ≤ 2/5. The exiting variable is x7, and the next basic solution is x4 = maxt=2/5,×3 =1−2(2/5)=1/5,×2 =3−2/5=13/5.
x4 x3 x2 x5−1 0 −1
By simply consulting Aaug, we see the new AB will be x6 1 1 −1. If the question x7 1 −1 −2
had asked instead for the new A−1, probably the best way to get it is from (new A−1) = BB
5 0 0
E−1(old A−1), where E = 2 1 0 (the first column is A−1A4), whose inverse is E−1 =
BB
101
1/500
−2/5 1 0 . MultiplyingoutgivesnewA−1 = x3 1 3 −1 .
x5 x6 x7 x4−3 1 1
555 B555
−1/5 0 1 x2 −2 −1 −1 555
4. A student wants to take on extra curricular activities that will boost their chance of finding a job after graduation. We quantify the boost in terms of career points. There are limits on the students time, money and loss of self esteem. The activities of networking, taking professional exams and doing sports will all contribute to landing a job after graduation; each unit of the activities will result in some number of career points. The student wishes to maximize the number of career points. The activities (for this student) have different costs in terms of time, money and self esteem. The student has 34 hours to spend on these activities and has $1800 to spend (the costs are given in units of $100 below). A student can only lose 9 units of self esteem before affecting their success in UBC courses.
3
1
= 45 −2x −x 56
hours
money
self esteem career points
networking exams sports available 34 18 9
= 2 +x −2x x4 x5 x6 45 x1−120
A−1=x2−1 1 2 B
= 2 +x4 −x5 −2×6
= 3 −3×4 +4×5 +3×6
x3 3 −4 −3 NOTE: All questions are independent of one another.
NBBB
7
8
5
Let x1 denote the units of networking, x2 denote the units of professional exams and x3 denote the units of sports and let x3+i denote the ith slack for i = 1, 2, 3. The final dictionary is:
x x2 x3
z
(a) Give the marginal values for each of the resources: hours, money and esteem. What are the units for the marginal values?
Solution. The marginal values are minus the coefficients of the slack variables x4, x5 and x6 in the z-row:
Hours: 0 career points per hour.
Money: 2 career points per hundred dollars (you could also say 0.02 career points per
dollar).
Self esteem: 1 career point per unit of self esteem.
(b) Give the range on c1 (career points for unit of networking) so that the current solution remains optimal.
Solution. We need c⊤ − c⊤A−1AN to stay ≤ 0. Let’s calculate! Since the basis in the NBB
final dictionary is x1,x2,x3, we have cN = 0,cB = c,AN = I.
We have c⊤ − c⊤A−1AN = −c⊤A−1 = c1 −7 −2c1 +12 −1, which is ≤ 0 for
6≤c1 ≤7.
(c) Consider the possibility of changing maximum loss of esteem to 9+p and the maximum money to 18 + p. Determined the range on p so that the current basis {x1, x2, x3} remains optimal and report the profit as a function of p.
Solution. The basis remains optimal as long as A−1(b + ∆b) ≥ 0, where ∆b =
0 p p⊤. We get:
A−1(b+∆b)=A−1b+A−1∆b=2+ 3p =2+3p.
BBB
2 2p 2+2p 3 −7p 3−7p
This is ≥ 0 for −2/3 ≤ p ≤ 3/7. In that range the objective function is 0 0
z∗ +y∗ ·∆b=45+2·p=45+3p. 1p
4
564 332 121
B
(d) Change the availability of hours, money and esteem to 13, 6 and 4 respectively Deter- mine the new optimal solution using the Dual Simplex method. Report the new solution as well as the new marginal values.
such that 0 −2 −1+t1 −2 The next dictionary is then:
x2 = x3 = x4 =
z=
0 ≤ 0. This is t = 0, so x4 is the entering variable.
13 −1 B B
Solution. The new x∗ = A−1 6 = 1 , so the optimal basis of the old problem 43
is not feasible for the new one. The new z is (−1)(7) + (1)(8) + (3)(5) = 16.
We perform a dual simplex pivot. Since x1 = −1 < 0 is the only negative variable, it is the one that exits the basis. To fidn the entering variable, we want the largest t ≥ 0
2
1 16
+x1 +x5 −2x6 −3x1 −2x5 +3x6
+x1 +2x5
−2x5 −x6
So an optimal solution for these
which produces z = 16. In words, under these limits, you’re best bet is to forgo networking and sports and just take exams until you simultaneously run out of money and self esteem. The marginal values happen to be the same as before: 0, 2, 1 for hours, money and self esteem, respectively.
5. Let A be a given m×n matrix. Let b be a m×1 vector. Show that either i) There exist an x with Ax = b, x ≥ 0,
or
ii) There exists y with AT y ≥ 0, b · y < 0,
but not both.
Solution.
Consider the following pair of LPs:
Dual max0·x minb·y
new resource limits is given by x1 = 0 = x3, x2 = 2
Primal
subject to subject to
Ax = b x≥0
A⊤y ≥ 0 y free
They are dual to each other: the variables in the vector y correspond to the equality con- straints Ax = b, so they are free.
Notice that the primal cannot be unbounded because it’s objective function is 0 for any feasible solution. So, by the fundamental theorem of linear programming, the primal is either infeasible or has an optimal solution.
5
Case of an infeasible primal. Here i) does not occur, let’s show ii) does. Notice that the dual is feasible, because y = 0 satisfies the constraints. But the dual cannot have an optimal solution since then, by strong duality, so would the primal. This means that the dual must be unbounded and so, in particular, must have some feasible solution with b · y < 0.
Case where the primal has an optimal solution. Then i) does occur, lets show ii) does not. By weak duality any feasible dual solution satisfies 0 · x ≤ b · y, so we cannot have b · y < 0.
6. Let a, b be given numbers with a, b > 0. Consider the game given by payoff matrix A below (the payoff to the row player).
a −a A= −b b
Give optimal strategies (which may involve expressions in a, b) for both the row player and the column player and indicate how they give bounds on the value of the game v(A) and show that v(A) = 0.
Solution. To confirm that the value of the game is 0, we just need to produce stochastic vectors x and y such that the smallest entry of x⊤A and the largest entry of Ay are both 0. It’s easy to spot that y⊤ = 1/2 1/2⊤ gives Ay = 0 0⊤. This shows that player two can ensure that player one wins no more than 0 on average per round, so v(A) ≤ 0.
Forx,wehavex⊤A=ax1−bx2 −ax1+bx2and,ofcourse,x1+x2=1.Solvingweget x⊤ = b a andthenx⊤A=0 0. Thisshowsthatplayeronecanensureshegetsat
a+b a+b
least 0 on average per round, so that v(A) ≥ 0 and therefore v(A) = 0 as desired.
7. Let A, b and c be given. Assume that our standard LP: max c·x subject to Ax ≤ b and x≥0hasanoptimalsolution. AssumetheLP:max(−c)·xsubjecttoAx≤bandx≥0 has an optimal solution. Show that for any u satisfying Au ≤ 0 and u ≥ 0 that we may deduce that u also satisfies c · u = 0.
Solution. AssumethatusatisfiesAu≤0andu≥0. Weneedtoprovethatc·u=0. Let x be some optimal solution for the LP max c · x subject to Ax ≤ b, x ≥ 0. Consider the
vector x + u. It is also feasible for this LP:
Addingx≥0andu≥0,wegetx+u≥0.
AddingAx≤bandAu≤0,wegetA(x+u)≤b.
Therefore the objective function for x+u must be less than or equal to the objective function
ontheoptimalsolutionx. Thatis,c·(x+u)≤c·x,whichtellsusthatc·u≤0.
An analogous argument with the other LP (the one whose objective function is (−c)·x) will
show that (−c) · u ≥ 0, that is, that c · u ≥ 0.
6