Consider solving the following 4-variable LP by Dantzig-Wolfe Decomposition Algorithm 13D. Constraints 1 and 2 will constitute the linking problem, numbers 3-5 the first subproblem, and numbers 6-8 the second.

(a) Sketch the feasible set of the constraints for the first subproblem in a 2-dimensional plot, and establish that the feasible set is convex.

(b) Identify all the extreme points and extreme directions of that first subproblem feasible set.

(c) Do

(a) for the second subproblem.

(d) Do

(b) for the second subproblem.

(e) Show that Algorithm 13D can begin with extreme point 1x1, x22 = 10, 02 in the first subproblem, and 1x3, x42 = 10, 102 in the second subproblem. And construct the first partial master problem.

(f) Solve your partial master problem of (e)
with class optimization software.
(g) Use results of part

(f) to construct objective functions for the two subproblems and solve both graphically.
(h) Update the partial master with results from the two subproblems.

Transcribed Image Text:

max 52x +19x2 +41x3 + 9x4 s.t. 12x1 +20%2 +15x3 + 8x 90 9x1 +10x2 +13x3 +18x 180 +x1 7 +x1 -x2 3 x1,x20 + 1x3 8 +1x3 +1x410 X3, X40