2021 Math 340:202. Midterm
Friday, 2021 February 26 IN CLASS ZOOM Exam Time: 45min
There are total of 5 problems each worth 5 points.
This is a closed-book examination.
Answers should be written on paper with all work shown.
Clearly legible photos of the written work should be submitted as a pdf file on Canvas, or if submission on Canvas is not possible then by email.
Pledge for integrity:
I pledge to uphold the standards of integrity expected of me in this course. I will not provide, seek, or receive any unauthorized assistance on this exam, and acknowledge that failure to abide by these conditions can result in serious disciplinary consequences, such as receiving a final grade of 0 in the course and being suspended from UBC.
Please write that you have read and understood the pledge for integrity and sign your name with todays date on the front page of your exam answers.
1. (5 points) Solve the following linear programming problem using the simplex method with Antsee’s rule.
Maximize: Z = 3×1 +10×2 Subjectto: x1 ≤ 30 x2 ≤ 6 x1 +2×2 ≤ 40
& x1,x2≥0.
Solution: The origin if feasible so we begin with a feasible dictionary:
Z = 0 +3×1 +10×2 w1 = 30 −x1
w2 = 6 −x2 w3 = 40 −x1 −2×2.
We choose x2 entering and w2 leaving to get:
Z = 60 +3×1 −10w2 w1 = 30 −x1
x2 = 6 −w2 w3 = 28 −x1 +2w2
We choose x1 entering and w3 leaving to get:
Z = 144 −3w3 −4w2 w1 = 2 +w3 −2w2 x2 = 6 −w2 x1 = 28 −w3 +2w2
This is optimal. The optimal solution is(x1, x2) = (28, 6).
Math340:202 Midterm
2. (5 points) Consider the following LP problem.
Maximize: Z = −6×1 +3×2
subject to: 2×1 −x2 ≤ −1 −x1 +2×2 ≤ 0
& x1,x2≥0.
(a) Express the auxiliary linear programming problem (phase one of the two phase simplex
method) in standard form.
(b) Find a basic feasible solution for the auxiliary linear programming problem with x1 = 0
and x2 = 0.
(c) After running the simplex method on the auxiliary problem you obtain the following
dictionary:
Z0 = −2 −2w1 −x1 −1w2 333
x0 = 2 +2w1 +x1 +1w2 333
x2 = 1 +1w1 +x1 −1w2. 333
What can you say about the original LP.
Solution:
(a) The auxiliary LP problem is
Maximize Z0 = −x0
subject to −x0 +2×1 −x2 ≤ −1
−x0 −x1 +2×2 ≤ 0 & x0,x1,x2≥0.
(b) To find a basic feasible solution we start with the infeasible dictionary:
Z0= −x0
w1 = −1 +x0 −2×1 +x2 w2 = 0 +x0 +x1 −2×2.
We choose x0 entering and w1 leaving to obtain a feasible dictionary:
Z0 = −1 −w1 −2×1 +x2 x0 = 1 +w1 +2×1 −x2 w2 = 1 +w1 +3×1 −3×2
This corresponds to the basic feasible solution: x0 = 1, w2 = 1, w1 = x1 = x2 = 0.
(c) The given dictionary is optimal. Since x0 > 0 this implies that the original LP is infeasible.
Math340:202 Midterm
3. (5 points) Show that the following problem is unbounded and find a feasible solution with Z ≥ 1000.
Maximize: Z = −2×1 +x2 +2×3 Subject to: x1 −2×2 +x3 ≤ 2 2×1 +x2 −3×3 ≤ 6
& x1,x2,x3≥0
Solution: The feasible dictionary corresponding to the point (x1, x2, x2) = (0, 0, 0) is:
Z = 0 −2×1 +x2 +2×3 w1=2−x1+2×2 −x3 w2 = 6 −2×1 −x2 +3×3.
Chood x3 entering and w1 leaving to get
Z= +2(
= x3 = w2 =
0 −2×1 +x2
2 −x1
4 −4×1
2 −x1 6−2×1 −x2
2 −x1
Now x2 is entering and there is no leaving variable so the LP is unbounded.
Setx2 =t,x1 =0,×3 =2+2t,Z=4+5t. Whent=200wegetx2 =200,×3 =402,and Z = 1004.
+3(
= 12 −5×1
+2×2 −w1 ) +5×2 −3w1 .
+2×2 −w1 ) +5×2 −2w1 +2×2 −w1
Math340:202 Midterm
4. (5 points) Jen has $5000 CAD to invest. She considers the following investments:
A Canada government bonds fund at a rate of 2% yearly interest (her investment is
multiplied by 1.02 after one year).
A Canada stock market index fund at a rate of 8% yearly interest.
An International (non-Canada) stock market index fund at a rate of 7% yearly interst.
A Balanced fund with 60% stocks and 40% bonds, 70% international (non-Canada) and 30% Canada, and 5% yearly interest.
Jen wishes to maximize her income with at most 90% of her money invested in stocks and at most 80% of her money invested in Canada (stocks or bonds). Express the linear optimization problem Jen should solve.
Solution: Decision variables:
x1: money invested in Canada bonds
x2: money invested in Canada stocks
x3: money invested in International stocks x4: money invested in Balanced fund
The objective function is
Z = 0.02×1 + 0.08×2 + 0.07×3 + 0.05×4, or, equivalent and also acceptable would be
Z = 1.02×1 + 1.08×2 + 1.07×3 + 1.05×4. x1 +x2 +x3 +x4 = 5000,
x2 + x3 + 0.6×4 ≤ 0.9(5000)
and
Along with nonnegativity: x1, x2, x3, x4 ≥ 0.
The constraints are
x1 + x2 + 0.3×4 ≤ 0.8(5000).
Math340:202 Midterm
5. (5 points) Answer whether the following statements are true of false. If true justify the answer. If false give a counter-example.
(a) If the simplex method using Antsee’s rule reaches the same (non-optimal) dictionary twice then it will never find an optimal solution.
(b) Consider the linear programming problem:
Maximize: Z = Subject to:
&
⃗c · ⃗x
A⃗x ≤⃗b
⃗0 ≤ ⃗x ≤ ⃗1
where A is an m × n matrix and all entries of A, ⃗b, and ⃗c are positive (⃗0 is the vector of all zeros and ⃗1 is the vector of all 1’s). This linear programming problem has an optimal solution.
(c) Consider the linear programming problem:
Maximize: Z = ⃗c · ⃗x Subject to: A⃗x ≤⃗b
& ⃗0≤⃗x
where A is an m × n matrix and all entries of A, ⃗b, and ⃗c are strictly positive.
then this linear program is unbounded.
If m < n
Solution:
(a) True: If the same dictionary is reached the simplex method will continue to cycle and reach the dictionary infinitely many times.
(b) True: The origin is feasible, and since ⃗x is bounded the LP is bounded. Thus the fundamental theorem of linear programming states that there is an optimal solution.
(c) False: Consider the standard simplex, which is given by the single constraint x1 + x2 + . . . + xn ≤ 1. With one constraint, m = 1 and any n this defines a bounded feasible region resulting in a bounded linear program.
Math340:202 Midterm