2020 Mathematics 340 Homework 4 Due Friday, October 9th
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.
Only part of the problems may be graded. But, you have to submit all the problems. Submit only pdf files.
Remember to use
Is there a pair (x,y), with x,y ≥ 0, that satisfy the following three inequalities simultaneouly?
5 marks
Justify your answer.
−x + 2y ≤ −2 2x + y ≥ 1 − 3x + y ≥ −4.
Solution: The three inequalities −x+2y ≤ −2, 2x+y ≥ 1, −3x+y ≥ −4 have no solution x, y with x, y ≥ 0. Below is the justification.
We first transform the inequalities to standard form −x + 2y ≤ −2, −2x − y ≤ −1, +3x − y ≤ 4. Then apply Phase One of the two phase method:
w= −x0 x1 =−2 +x −2y+x0 x2 =−1+2x +y +x0 x3 = 4 −3x +y +x0
Fake pivot to feasibility, x0 enters and x1 leaves.
w = −2 +x −2y −x1 x0 = 2 −x +2y +x1 x2 = 1 +x +3y +x1 x3 = 6 −4x+3y+x1
(I used the standard pivoting rule with x before y) x enters and x3 leaves.
w = −1/2 −(1/4)x3 −(5/4)y −(3/4)x1 x0 = 1/2 +(1/4)x3 +(5/4)y +(3/4)x1 x2 = 5/2 −(1/4)x3 +(15/4)y +(5/4)x1
x = 3/2 −(1/4)x3 +(3/4)y +(1/4)x1
We are at optimality with w = −1/2. This means that the original constraints (with x0 = 0) is feasible. This exactly, mean that the three inequalities cannot be satisfied for any x, y ≥ 0.
Page 1 of 4
2020 Mathematics 340 Homework 4 Due Friday, October 9th
2.
Consider the m × n-matrix A and the vector ⃗b ∈ Rm that are given by A = [aij], ⃗b = [bi]
5 marks
where
aij =(−2)i+j(i2−j2), bi =(−2)i fori=1,···mandj=1,···,n. Note that aij is the entry of A at the i-th row and the j-th column.
Consider the following condition on vectors ⃗x ∈ Rn:
(Condition1) A⃗x ≤ ⃗b & ⃗x ≥ ⃗0.
Write and run a python Jupyter notebook using the PuLP package, to check whether there is a vector ⃗x ∈ Rn that satisfies (Condition1),
whenm=n=10,
and if it exists, find one. Submit your screenshots.
[For credits, you must write a python Jupyter notebook to solve this problem.]
Python Hint: Start with giving M=10
N=10
You may want to use Python lists combined with ‘forloop’. For example,
column=[j+1 for j in range(N)]
row=[i+1 for i in range(M)]
Then, one can define the matrix A and the vector ⃗b, using Python dictionaries combined with ‘forloop’ as
a= {i:{j:(-1)**(i+j)*(i-j) for j in column} for i in row}
b = {i: (-1)**(i) for i in row}
In this way, the entry aij can be written in the later part of the Jupyter notebook code as a[i][j]. Similarly, b[i] for bi.
For more instruction on the Python ‘forloop’, see https://wiki.python.org/moin/ForLoop
Solution: See the file in the Canvas. There is a feasible point that is all zeros except for x4 = 0.00096 and x9 = 3.00(10−5).
Page 2 of 4
2020 Mathematics 340 Homework 4 Due Friday, October 9th
3.
5.1-1 From Hillier/Lieberman Consider the following problem.
5 marks
subject to
and
Maximize Z = 3×1 + 2×2 2×1 + x2 ≤ 6
x1 + 2×2 ≤ 6 x1≥0, x2≥0.
(a) Solve this problem graphically. Identify the CPF solutions by circling them on the graph.
(b) Identify all the sets of two defining equations for this problem (corresponding to choice of basic and nonbasic variables). For each set, solve (if a solution exists) for the corresponding corner-point solution (vertex), and classify it as feasible or infeasible.
(c) Introduce slack variables in order to write the functional constraints in augmented form. Use the slack variables to identify the basic solution that corresponds to each corner-point solution found in part (b).
Solution: The graph looks like:
Page 3 of 4
2020 Mathematics 340 Homework 4 Due Friday, October 9th
There are six sets of two defining equations corresponding to when two of the inequalites are equalitites:
2×1 + x2 = 6 and x1 + 2×2 = 6
defines the point (x1, x2) = (2, 2). The slack variables (part c) are (w1, w2) = (0, 0).
Since all variables, including the slack variables, are nonnegative the point is feasible. 2×1 + x2 = 6 and x1 = 0
defines the point (x1,x2) = (0,6). In this case w2 is basic with w2 +(0)+2(6) = 6 so (w1, w2) = (0, −6). The point is infeasible because w2 < 0 or equivalently x1+2x2 > 6.
2×1 + x2 = 6 and x2 = 0
defines the point (x1,x2) = (3,0). In this case w2 is basic with w2 +(3)+2(0) = 6 so
(w1, w2) = (0, 3). The point is feasible.
x1 + 2×2 = 6 and x1 = 0
defines the point (x1,x2) = (0,3). In this case w1 is basic with w1 +2(0)+(3) = 6 so (w1, w2) = (3, 0). The point is feasible.
x1 + 2×2 = 6 and x2 = 0
defines the point (x1,x2) = (6,0). In this case w1 is basic with w1 +2(6)+(0) = 6 so
(w1, w2) = (−6, 0). The point is infeasible.
x1 =0andx2 =0
defines the point (x1,x2) = (0,0). In this case both w1 and w2 are basic with (w1, w2) = (6, 6). The point is feasible.
Page 4 of 4