MTH 208: Written Homework 3: LS simplex algorithm
MTH 208: Written Homework 3 – due Friday, 9/29 at 2pm on gradescope
Note: unless stated otherwise, when asked to “solve the LOP” you need to use the LS simplex algorithm, show your initial and final tableau, and list the sequence of pivots used in i → j form. If a problem is infeasible you need to show it by either providing a certificate of infeasibility or solving the auxiliary problem. If a problem is unbounded you need to provide a certificate of unboundedness.
(P1) Consider the LOP
-
(a) Solve the LOP above for ⃗y∗ and w∗.
-
(b) Write the dual problem for the LOP above.
Minimize such that
and
w=2y1−3y2, 2y1−4y2≥4, 2y1 + y2 ≥ 1, −3y1 + 8y2 ≥ 1, y1,y2≥0.
(c) Solve the dual from part (b) and verify that strong duality is satisfied. Also explain (very briefly) how the primal-dual correspondence theorem is satisfied (see the end of section 2.1 notes).
(P2) Consider the LOP
Maximize such that
and
z = 12x1 +3x2 +20x3,
x1 −x2 −10x3 ≤2,
7x1 − 4x3 ≤ 21,
8x1 − x2 ≤ 32,
2x2 − 4x3 ≤ 5, x1,x2,x3≥0.
(a) Solve the LOP.
(b) Write the dual LOP. Do you expect the dual to have an optimum? Explain.
(c) Solve the dual LOP. (according to the directions at the top of this page)
(P3) Consider the LOP P given below Maximize
such that
and
z=−12x1−11x2−13x3,
−x1+x2≤−2,
−x2 − x3 ≤ −3,
x1 + x3 ≤ 5,
x1,x2,x3≥0.
1
-
(a) For P above, write the dual problem D.
-
(b) Show that xˆ = (2, 0, 3)T is feasible in P and compute z(xˆ).
-
(c) Show that yˆ = (12, 13, 0)T is feasible in D and compute w(yˆ).
-
(d) Without using the simplex algorithm, find z∗ and w∗ and briefly explain how you know these are the optimal values.
(e) Show that yˆ = (13, 14, 1) D?
(P4) Consider the LOP below
is feasible in D and compute w(yˆ). What can you conclude about LOP
ˆTˆ
Maximize such that
z=3x1+4x2+5x3, 2x1 −7x2 +4x3 ≤6, x1 −2x2 −2x3 ≤−4, −5x1 +x2 +2x3 ≤5, x1,x2,x3≥0.
and
Note that basis sets are size 3 since there are 3 constraints, so there are 6 = 20 collections of 3 indices
to form a basis.
-
(a) Recall that an n × n matrix can be row reduced to an identity matrix if and only if the column vectors are linearly independent. Considering this, among the 20 collections of 3 indices, which can be chosen as bases to represent the tableau for this problem?
-
(b) Among the bases found in part (a), which are feasible and which are infeasible? Note: a “feasible basis” means the basic solution is feasible.
-
(P5) Create a standard form LOP with 2 variables and 2 constraints such that the feasible region is a quadrilateral and the LS simplex algorithm visits all 4 extreme points.
-
(P6) Complete each part below.
-
(a) Suppose2x+4y+6z≤10andx,y,z≥0. Howlargecanxbe? Whatabouty? Whataboutz?
-
(b) Let P be a standard form LOP with constraints A⃗x ≤ ⃗b having all entries of A and ⃗b strictly positive. Explain why the fundamental theorem of linear optimization (see section 1.4) implies that P has an optimum. Hint: Can P be infeasible? Unbounded? Why or why not?
-
