Mathematics 340 Homework 6 Due Friday, March 12th
Only part of the problems may be graded. But, you have to submit all the problems. Submit only pdf files.
Remember to use
Anstee’s rule:
– Choose the entering variable with the largest positive coefficient.
– If there is a tie, then choose the one with the smaller subscript.
– If there is a choice of leaving variable, then choose the one with the smallest subscript.
1. There are six independent questions below. What can you say about the dual if you already know: (answer for each of the following considered individually)
a) a feasible solution to the primal exists?
b) an optimal solution to the primal exists?
c) an optimal solution to the primal exists with x1 > 0? d) an optimal solution to the primal exists with x1 = 0? e) there is no feasible solution to the primal?
f) the primal is unbounded?
Solution: a) If a feasible solution to the primal exists, the dual has to be bounded by weak duality.
b) If an optimal solution to the primal exists, then by Strong Duality, there is an optimal solution to the dual with the same value of the objective function.
c) If an optimal solution to the primal exists with x1 > 0, then we have the same conclusion as b), but using the Theorem of Complementary Slackness, we deduce that any optimal solution to the dual has the first constraint being equality (first dual slack is 0).
d) If an optimal solution to the primal exists with x1 = 0, then we cannot make any grander observations than that of b). In some instances, x1 = 0 may force other facts.
e) If there is no feasible solution to the primal, then by Strong Duality, the dual cannot have an optimal solution. Thus the dual is either unbounded or is infeasible.
f) If the primal is unbounded then the dual is infeasible, which follows from weak duality.
Page 1 of 7
Mathematics 340 Homework 6 Due Friday, March 12th 2. 6.1-14 from Hillier-Lieberman
For any linear programming problem in standard form and its dual problem, label each of the following statements as true or false and then justify your answer.
1. 2.
3.
The sum of the number of decision variables and constraints is the same for both the primal and the dual problems.
At each iteration, the simplex method simultaneously identify a basic feasible so- lution for the primal problem and a solution for the dual problem that satisfies complementary slackness such that the objective values are the same.
If the primal problem has an unbounded objective function then the optimal value of the objective function for the dual problem must be zero.
Solution:
1. True. If there are n decision variables and m constraints for the primal, then there are m decision variables and n constraints for the dual, and the sum m+n is the same.
2. True. This can be seen by transforming to the dual dictionary using the nega- tive transpose property. Complementary slacness is satisfied because the basic variables correspond to non-basic variables in the dual. The object value is the same as it remains the same in the upper left hand corner of the dictionary.
3. False. If the primal problem is unbounded then the dual problem is infeasible by weak duality.
3.
Consider the following dictionary from a standard form LP problem.
Z = −3×1 −x2 −x3 x4 = 5 −x1 −2×2
x5 = 0 −x1 −x2 +x3 x6 = 20 −7×1 −3×2 +5×3
6 marks
Find all the optimal dual solutions.
Solution: This dictionary is feasible and is in fact an optimal dictionary as the coefficients for z are all negative. Note that the for the optimal solution ⃗x∗ = (0, 0, 0) is the unique optimal solution. but it is degenerate because of the constant 0 in the second row of the above dictionary.
The dual dictionary is
Page 2 of 7
Mathematics 340 Homework 6
Due Friday, March 12th
−W = −5z4 z1 = 3 +z4 z2 = 1 +2z4 z3=1
+0z5 −20z6 +z5 +7z6 +z5 +3z6 −z5−5z6
One basic optimal solution for the dual problem is z1 = 3, z2 = 1, z3 = 1. To find another we can do the simplex method with z5 as an entering variable. The leaving variable is z3. The new dictionary is
−W = −5z4 z1 = 4 +z4 z2 = 2 +2z4 z5=1
+0z3 −20z6 −z3 +2z6 −z3 −2z6 −z3−5z6
Another basic optimal solution is z1 = 4, z2 = 2 and z5 = 1. Choosing z3 as entering will make z5 leaving and return us to the starting dictionary, so we have found all basic optimal solutions.
All optimal dual solutions are then on the line segmant connecting these points, so are given by t ∈ [0, 1] and
z1 = 3(1−t)+4t = 3+t z2 = 1(1−t)+2t = 1+t z3 = 1(1−t) = 1−t z4 = 0 z5 =0+1t=t z6 = 0.
Recall,thedualdecisionvariablesarey1 =z4 =0,y2 =z5 =tandy3 =z6 =0.
4. Your colleague is working on the following LP problem:
Maximize z = −x1 +x2 +2×3 subject to x1 +2×2 −x3 2×1 +3×2 +x3 −2×1 +4×2 +2×3 x1, x2, x3
≤2 ≤ 6 ≤ 8 ≥ 0.
He tells you that he has found an optimal solution when x2,x5,x6 are non-basic and x1, x3, x4 are basic.
(a) Write down the initial dictionary and the dictionary that is thought to be optimal, both as in the Revised Simplex Method: Give B,N,c⃗ ,⃗c ,⃗x ,⃗x ,⃗b, write
in the basis headings (that is, label the columns of matrices with the corresponding variables).
NNBN
Page 3 of 7
Mathematics 340 Homework 6 Due Friday, March 12th
Solution:
The original dictionary is given by
1 0 0 B=0 1 0,
0 0 1 x4 2
⃗x B = ⃗b =
So if we make x2,x5,x6 non-basic and the other variables basic, we get
x 5 = 6 ,
x6 8 x3 0
1 2 −1 N=2 3 1
−2 4 2 x1 0
⃗x N = x 2 = 0 2 0
−1 ⃗c N = 1
6 , ⃗c B = 0 , 802
1 −1 1 B=2 1 0,
2 0 0 N=3 1 0
−2 2 0
2 0
4 0 1 ⃗xB =B−1⃗b=14, ⃗xN =0
60
−1 1
⃗cB=2 , ⃗cN=0 0
3 3
(b) What is the basic solution of your colleague’s dictionary? Is this a feasible solution?
Solution:
The current basic feasible solution is given by ⃗xN = 0 and ⃗x∗B = B−1⃗b. To
find the latter we solve B⃗x∗B = ⃗b
1 − 1 1 x ∗1 2
2 1 0 x ∗3 = 6 −220x∗4 8
which gives x∗ = 6,x∗ = 14,x∗ = 2. The other variables are zero. 43313
Since all the variables are non-negative, it follows that the dictionary is feasible.
Page 4 of 7
Mathematics 340 Homework 6 Due Friday, March 12th (c) Is your colleague’s dictionary optimal?
Solution:
To check optimality we need to verify that ⃗cN −⃗cBB−1N ≤ 0.
First compute ⃗y = ⃗cB B−1 by solving ⃗yB = ⃗cB :
1 −1 1
y1 y2 y32 1 0=−1 2 0
−2 2 0
Thisgivesy1 =0,2y2 −2y3 =−1,y2 +2y3 =2. Hence⃗y=[0,1,5]
36
So ⃗cN − ⃗yN is:
1 0 0−0 1 53 1 0=−10 −1 −5
2 0 0
36 336
401 Hence the current dictionary is optimal.
(d) What is the optimal value?
5. 5.2-2 Hillier-Lieberman
Work through the matrix form of the simplex method (revised simplex method) step by step to solve the following problem.
Solution:
Theobjectivefunctionisthereforez=−1×2 +0+2×14 =26. 333
subject to
and xj ≥ 0, j = 1,2,3,4,5.
Maximize Z = 5×1 + 8×2 + 7×3 + 4×4 + 6×5
2×1 +3×2 +3×3 +2×4 +2×5 ≤ 20 3×1 +5×2 +4×3 +2×4 +4×5 ≤ 30
Page 5 of 7
Mathematics 340 Homework 6 Due Friday, March 12th
Solution: To begin, B = {x6, x7}, N = {x1, x2, x3, x4, x5}, and 1 0 2 3 3 2 2
B=01, N=35424,
20 ⃗xB= 30,
The dual solution is.
Entering variable is x2.
The step size is
and the leaving variable is x7. The dual direction is
6
The dual step is s = 8 . 5
−3
−5 ∆⃗zN = −N⊤B−⊤⃗e7 = −4 .
−2 −4
′ 2 ⃗x B = ⃗x B − t ∆ ⃗x B = 0 .
−5+83 9 55
5 0 8
⃗cB=0, ⃗cN=7. 4
−5
−8 ⃗zN = N⊤B−⊤⃗cB − ⃗cN = −7 .
−4 −6
−1 3 ∆ ⃗x B = B N ⃗e 2 = 5 .
t = 1/ max{3/20, 5/30} = 6
00 ⃗z′ =⃗z −s∆⃗z =−7+84=−3.
NNN55 −4+82 −4
55
−6 + 8 4 2 55
Page 6 of 7
Mathematics 340 Homework 6 Due Friday, March 12th
Solution: We update the basis. B = {x6, x2}, N = {x1, x7, x3, x4, x5}, and
1 3 2 0 3 2 2 B=05, N=31424,
2 ⃗xB= 6,
The dual solution is.
Entering variable is x4.
5 0 0
⃗cB=8, ⃗cN=7. 4
9 5
8
53
6
⃗z N = − . 5
5 −4
−12 4 ∆⃗xB=BN⃗e4=B 2=52.
5
t = 1/ max{(4/5)/2), (2/5)/6} = 5 2
−1
5 3
⊤ −⊤ ⊤1 53 ∆⃗zN=−NB ⃗e6=−N −3 =−.
Thedualstepiss=−4/−4 =1. 55
′ 0 ⃗x B = ⃗x B − t ∆ ⃗x B = 5 .
−1
2 5
The step size is
and the leaving variable is x6. The dual direction is
5 −4
55 2
5
9 −1 2 55
8 3 1 NNN55
⃗z′ =⃗z −s∆⃗z =−53−−53=0.
− 4 − 4 0 55
22 55
0
This is optimal. The final solution has x1 = 0, x2 = 5, x3 = 0, x4 = 5 , x5 = 0. 2
Page 7 of 7