|
2.1
Simplex method
|
1. Use the simplex method to solve the following LP problem.
Maximize Z = 3x1 + 5x2 + 4x3
subject to the constraints
2x1 + 3x2 ≤ 8
2x2 + 5x3 ≤ 10
3x1 + 2x2 + 4x3 ≤ 15
and x1, x2, x3 ≥ 0
2. Use the simplex method to solve the following LP problem.
Maximize Z = 4x1 + 3x2
subject to the constraints
2x1 + x2 ≤ 1000
x1 + x2 ≤ 800
x1 ≤ 400
x2 ≤ 700
and x1, x2 ≥ 0
|
|
|
2.2
BigM method
|
1. Use the penalty (Big - M) method to solve the following LP problem.
Minimize Z = 5x1 + 3x2
subject to the constraints
2x1 + 4x2 ≤ 12
2x1 + 2x2 = 10
5x1 + 2x2 ≥ 10
and x1, x2 ≥ 0
2. Use the penalty (Big - M) method to solve the following LP problem.
Minimize Z = x1 + 2x2 + 3x3 - x4
subject to the constraints
x1 + 2x2 + 3x3 = 15
2x1 + x2 + 5x3 = 20
x1 + 2x2 + x3 + x4 = 10
and x1, x2, x3, x4 ≥ 0
|
|
|
|
|
2.3
Two-Phase method
|
1. Solve the following LP problem by using the Two-Phase method.
Minimize Z = x1 + x2
subject to the constraints
2x1 + 4x2 ≥ 4
x1 + 7x2 ≥ 7
and x1, x2 ≥ 0
2. Solve the following LP problem by using the Two-Phase method.
Minimize Z = x1 - 2x2 - 3x3
subject to the constraints
-2x1 + 3x2 + 3x3 = 2
2x1 + 3x2 + 4x3 = 1
and x1, x2, x3 ≥ 0
|
|
|
2.4
Dual Simplex method
|
1. Solve the following LP problem by using the Two-Phase method.
Minimize Z = x1 + x2
subject to the constraints
2x1 + 4x2 ≥ 4
x1 + 7x2 ≥ 7
and x1, x2 ≥ 0
2. Solve the following LP problem by using the Two-Phase method.
Minimize Z = x1 - 2x2 - 3x3
subject to the constraints
-2x1 + 3x2 + 3x3 = 2
2x1 + 3x2 + 4x3 = 1
and x1, x2, x3 ≥ 0
|
|
|
|
|
2.5
Gomorys Integer Cutting method
|
1. Solve the following integer programming problem using Gomory's cutting plane algorithm.
Maximize Z = x1 + x2
subject to the constraints
3x1 + 2x2 ≤ 5
x2 ≤ 2
and x1, x2 ≥ 0 and are integers.
2. Solve the following integer programming problem using Gomory's cutting plane algorithm.
Maximize Z = 2x1 + 20x2 - 10x3
subject to the constraints
2x1 + 20x2 + 4x3 ≤ 15
6x1 + 20x2 + 4x3 ≤ 20
and x1, x2, x3 ≥ 0 and are integers.
|
|
|
2.6
Graphical method
|
1. Use graphical method to solve following LP problem.
Maximize Z = x1 + x2
subject to the constraints
3x1 + 2x2 ≤ 5
x2 ≤ 2
and x1, x2 ≥ 0
2. Use graphical method to solve following LP problem.
Maximize Z = 2x1 + x2
subject to the constraints
x1 + 2x2 ≤ 10
x1 + x2 ≤ 6
x1 - x2 ≤ 2
x1 - 2x2 ≤ 1
and x1, x2 ≥ 0
|
|
|
|
|
2.7
Primal to dual conversion
|
1. Write the dual to the following LP problem.
Maximize Z = x1 - x2 + 3x3
subject to the constraints
x1 + x2 + x3 ≤ 10
2x1 - x2 - x3 ≤ 2
2x1 - 2x2 - 3x3 ≤ 6
and x1, x2, x3 ≥ 0
2. Write the dual to the following LP problem.
Minimize Z = 3x1 - 2x2 + 4x3
subject to the constraints
3x1 + 5x2 + 4x3 ≥ 7
6x1 + x2 + 3x3 ≥ 4
7x1 - 2x2 - x3 ≤ 10
x1 - 2x2 + 5x3 ≥ 3
4x1 + 7x2 - 2x3 ≥ 2
and x1, x2, x3 ≥ 0 |
|
|
2.8
Branch and Bound method
|
1. Solve the following LP problem by using Branch and Bound method
Max Z = 7x1 + 9x2
subject to
-x1 + 3x2 ≤ 6
7x1 + x2 ≤ 35
x2 ≤ 7
and x1,x2 ≥ 0
2. Solve the following LP problem by using Branch and Bound method
Max Z = 3x1 + 5x2
subject to
2x1 + 4x2 ≤ 25
x1 ≤ 8
2x2 ≤ 10
and x1,x2 ≥ 0
|
|
|
|
|
2.9
0-1 Integer programming problem
|
1. Solve LP using zero-one Integer programming problem method
Max Z = 300x1 + 90x2 + 400x3 + 150x4
subject to
35000x1 + 10000x2 + 25000x3 + 90000x4 ≤ 120000
4x1 + 2x2 + 7x3 + 3x4 ≤ 12
x1 + x2 ≤ 1
and x1,x2,x3,x4 ≥ 0
2. Solve LP using 0-1 Integer programming problem method
MAX Z = 650x1 + 700x2 + 225x3 + 250x4
subject to
700x1 + 850x2 + 300x3 + 350x4 ≤ 1200
550x1 + 550x2 + 150x3 + 200x4 ≤ 700
400x1 + 350x2 + 100x3 ≤ 400
x1 + x2 ≥ 1
-x3 + x4 ≤ 1
and x1,x2,x3,x4 ≥ 0
|
|
|
2.9
Revised Simplex method
|
1. Solve the following LP problem by using Revised Simplex method
MAX Z = 3x1 + 5x2
subject to
x1 ≤ 4
x2 ≤ 6
3x1 + 2x2 ≤ 18
and x1,x2 ≥ 0
2. Solve the following LP problem by using Revised Simplex method
MAX Z = 2x1 + x2
subject to
3x1 + 4x2 ≤ 6
6x1 + x2 ≤ 3
and x1,x2 ≥ 0
|
|
