4

I have a Dantzig-Wolfe decomposition question with the following questions

\begin{align} &Maximize: 2x_1 +3x_2+4x_3+2x_4 \\ s.t. \quad & x_1 +x_2+2x_3+x_4 \le 15\\ & x_1 +x_2+2x_3+x_4 \le 10\\ &x_1 +2x_2 \le 8\\ &x_1 \le 3\\ &x_3+3x_4 \le 6\\ &x_4 \le 4\\ &x_1,x_2,x_3,x_4 \ge 0\\ \end{align}

a) Find the extreme point of the diagonal blocks (e.g., using the graphical method) and reformulate this optimization problem in terms of that extreme points using the representation theorem.

b) Assuming that the dual variable for the binding constraints (the one with ≤ 15 and ≤ 10) are equal to 1 and 2, respectively. Formulate the corresponding sub-problems and find the vectors Vih to be added as the columns in the master problem

I posted the solutions but am unsure how to solve part (b). Is the solution optimal since the z of both subproblems is zero?

enter image description here

enter image description here

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Romio Rodriguez
  • 41
  • 2
  • 2
    Are you sure your constraint coefficients are correct? The first two constraints are parallel, so they cannot both be active. Your second plot needs axis labels. Also, you have mistakenly omitted $\mu_1$ from the first convexity constraint. – RobPratt Dec 18 '22 at 05:50

1 Answers1

-1

Please read this book Bazaraa et al. Linear Programming and Network Flows, 3rd edition, page 345 the numericalenter image description here example 7.2.

Max
  • 27
  • 3
  • Your answer could be improved with additional supporting information. Please [edit] to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Community Dec 19 '22 at 22:05