4
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Commented Dec 18, 2022 at 5:50

1 Answer 1

Reset to default
-1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Community Bot
    Commented Dec 19, 2022 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.