2021 Mathematics 340 Homework 2 Due Friday, January 29th Only part of the problems may be graded. But, you have to submit all the problems.
1.
Submit one pdf file per question, unless otherwise stated 1(b).
Consider the problem [Vanderbei. Exercise 1.2]. “A small airline, Ivy Air,
flies between three cities …”
(a) Write this as a Linear Programming problem (in the standard inequality form). You must explain your notation and variables.
9 marks
Solution: Notice that the flight is to fly from Ithaca to Newark, then to Boston. Set the decision variables. First name the routes:
R1 Ithaca to Newark R2 Newark to Boston R3 Ithaca to Boston
We use the letters Y, B, M, for the available classes. Then, the decision variables are, for each i = 1,2,3
xiY = the number of Y class tickets for root i
xiB = the number of Y class tickets for root i xiM = the number of Y class tickets for root i
Notice that there are 9 such variables.
We want to maximize the objective function (the revenue in $)
300x1Y + 220x1B + 100x1M + 160x2Y + 130x1B + 80x2M + 360x3Y + 280x3B + 140x3M Now constraints. First, the obvious constraints: all variables are nonnegative
and integer. Then, the upper bounds from the forecasted maximum demand.
x1Y ≤ 4,x1B ≤ 8,x1M ≤ 22,x2Y ≤ 8,x2B ≤ 13,x2M ≤ 20,x3Y ≤ 3,x3B ≤ 10,x3M ≤ 18.
Now the constraint from not allowing overbooking. The aircraft has 30 seats. So, we have
x1Y +x1B +x1M +x3Y +x3B +x3M ≤30 x2Y +x2B +x2M +x3Y +x3B +x3M ≤30
The first line is from the route between Ithaca and Newark, where there are route 1 (Ithaca to Newark) route 3 (Ithaca to Boston) passengers are to be
Page 1 of 4
2021 Mathematics 340 Homework 2 Due Friday, January 29th
onboard. The second line is from the route between Newark and Boston, where there are route 2 (Newark to Boston) route 3 (Ithaca to Boston) passengers are to be onboard.
The final LP problem is
max
300x1Y + 220x1B + 100x1M + 160x2Y + 130x1B + 80x2M + 360x3Y + 280x3B + 140x3M subject to
x1Y ≤4,
x1B ≤ 8,
x1M ≤ 22,
x2Y ≤8,
x2B ≤ 13,
x2M ≤ 20,
x3Y ≤3,
x3B ≤ 10,
x3M ≤ 18,
x1Y +x1B +x1M +x3Y +x3B +x3M ≤30,
x2Y +x2B +x2M +x3Y +x3B +x3M ≤30,
x1Y ,x1B,x1M,x2Y ,x1B,x2M,x3Y ,x3B,x3M ≥ 0,
2.
(b) Solve the LP by writing down a code in the Python language using the Jupyter notebook; login to UBC syzygy website and the Jupyter notebook.
Attach the .pdf and .pynb [sic: .ipynb] files as separate files.
For given two nonempty sets S1, S2 ⊂ Rn, define the operation S1 + S2 as
follows:
S1+S2 :={z∈Rn |z=x+y forsomex∈S1, andforsomey∈S2},
that is, the points z ∈ S1 +S2 are those that can be expressed by the sum x+y for some x ∈ S1, and y ∈ S2.
(a) DefineBr ={x∈Rn ||x|≤r}. Forgivenr1,r2 >0,whatisBr1 +Br2? Justify your answer carefully.
( Hint. When justifying your answer you may need triangle inequality:
|x+y|≤|x|+|y|withequalityifandonlyifx=tyforanonnegativet≥0. )
9 marks
Page 2 of 4
2021 Mathematics 340 Homework 2 Due Friday, January 29th
Solution: We claim that
Br1 +Br2 =Br1+r2.
We first show that Br1 +Br2 ⊂ Br1+r2. If z ∈ Br1 +Br2 then there is x ∈ Br1 and y ∈ Br2 so that z = x+y. By the triangle inequality and that |x+y| ≤ |x|+|y| ≤ r1 +r2, so, z = x+y ∈ Br1+r2. This has proven that Br1 +Br2 ⊂Br1+r2.
WenextshowthatBr1 +Br2 ⊂Br1+r2.Ifz∈Br1+r2,then|z|≤r1+r2.Now,
letx=
and
r1 r1 +r2
z,y= r2 z. Then, r1 +r2
|x|= r1 |z|≤ r1 + r2
|y|= r2 |z|≤ r1 + r2
r1 (r1+r2)≤r1, sox∈Br1, r1 + r2
r1 (r1+r2)≤r2, soy∈Br2, r1 + r2
z = r1 + r2 z = r1
r1 + r2 r1 + r2
z + r2 z = x + y r1 + r2
So, z ∈ Br1 + Br2. As this holds for all z ∈ Br1+r2, we have that Br1+r2 ⊂ Br1 +Br2.
SinceBr1 +Br2 ⊂Br1+r2 andBr1+r2 ⊂Br1 +Br2,wehaveBr1+r2 =Br1 +Br2.
(b) Is it true that S1 + S2 must be convex for any nonempty convex sets S1 and S2? Justify your answer carefully.
Solution: Such a sum S1 + S2 is called the Minkovski sum of S1 and S2.
Let z1,z2 be two points in S1 + S2. Then, there are x1,x2 ∈ S1 and y1,y2 ∈ S2 so that z1 = x1 +y1 and z2 = x1 +y1. By convexity of S1, (1−t)x1 +tx2 ∈ S1 for any t ∈ [0,1]. Similarly, by convexity of S2, (1 − t)y1 + ty2 ∈ S2 for any t ∈ [0,1]. Therefore, for any t ∈ [0, 1], we see that
(1−t)z1 +tz2 = (1−t)(x1 +y1)+t(x2 +y2)
=(1−t)x +tx +(1−t)y +ty ∈S +S . 12 1212
This means that S1 + S2 is convex.
3. Consider Problem 3 from HW 1 about the Wyndor Window company. Page 3 of 4
7 marks
2021 Mathematics 340 Homework 2 Due Friday, January 29th (a) Introduce the slack variables w1, w2, w3 and express the problem in the augmented
simplex method form.
Solution:
z = 0 w1 = 6 w2 = 4 w3 = 48
+ 300 x1 − x1
− 6×1
+150 x2
−x2 −8×2
(b) Begin with the basic feasible solution, where no windows are produced. Choose the leaving [sic: entering] variable corresponding to the amount of wood-framed windows, x1, and compute a simplex method pivot.
Solution: Wearriveatz=1800,×1 =6,×2 =0,w1 =0,w2,=4,w3 =12.
z = 1800 x1 = 6
w2 = 4 w3 = 12
−300w1 +150×2 − w1
−x2 + 6w1 −8×2
(c) Complete the solution using the simplex method, showing each step.
Solution: We now choose x2 as the entering variable and w3 is the leaving variable.
z = 2025 x1 = 6
− 825 w1 −150 w3 28
− w1
+ 3w1 +1w3
w2 = 5 248
x2 = 3 − 3w1 −1w3 248
This is optimal! The optimal solution has z = 2025, x1 = 6, x2 = 3, w1 = 0,
w2,= 5, w3 = 0. 2
2
Page 4 of 4