212 Introduction to Linear Optimization and Extensions with MATLAB
R
minimize −2x
1
−3x
2
−5x
3
−4x
4
subject to x
1
+ 2x
2
+ 3x
3
≤ 8
x
2
+ x
3
+ x
4
≤ 7
3x
1
+ 2x
2
≤ 6
x
1
+ x
2
≤ 3
x
3
+ x
4
≤ 3
4x
3
+ 3x
4
≤ 6
x
1
≥ 0 x
2
≥ 0 x
3
≥ 0 x
4
≥ 0.
Exploit the structure of the linear program to solve for the optimal solution
without using Dantzig-Wolfe decomposition.
Exercise 5.2
Consider the following linear programming problem:
minimize −5x
1
− 3x
2
− x
3
subject to x
1
+ 2x
2
+ x
3
≤ 10
x
1
≤ 3
2x
2
+ x
3
≤ 8
x
2
+ x
3
≤ 5
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0.
Solve by using the Dantzig-Wolfe decomposition.
Exercise 5.3
Consider the following linear programming problem:
minimize −8x
1
− 7x
2
− 6x
3
− 5x
4
subject to 8x
1
+ 6x
2
+ 7x
3
+ 5x
4
≤ 80
4x
1
+ x
2
≤ 12
5x
1
+ x
2
≤ 15
7x
3
+ 2x
4
≤ 10
x
3
+ x
4
≤ 4
x
1
≥ 0, x
2
≥ 0, x
3
≥ 0, x
4
≥ 0.
(a) Solve by Dantzig-Wolfe decomposition. ...