Simplex Method: Self Test Questions
Theory
1. Write the general mathematical formulation of a linear programming problem.
2. Define the following:
- Slack variable
- Surplus variable
- Artificial variable
3. What do you mean by an optimal basic feasible solution to a linear programming problem?
4. Explain various steps of the simplex method involved in the computation of an optimal solution to a linear programming problem.
5. Fill up the blanks:
- .. variables are introduced to make type inequalities equations.
- A basic solution with m equation and n variables has variables equal to zero.
- A basic feasible solution is a basic solution whose variables are ..
- The maximum number of basic feasible solutions in a system with m equations and n variables is
- In a linear programming problem every . point of the Convex set of feasible solutions is a .solution of the problem.
- The objective function of a linear programming problem is maximized or minimized at a . solution.
Practical
1. Maximize z = 5x + 3y
subject to the constraints:
x + y ≤ 2
5x + 2y ≤ 10
3x + 8y ≤ 12
x, y ≥ 0
2. Maximize z = 2x1 + 4x2 + x3 + x4
subject to
x1 + 3x2 + x4 ≤
4
2x1 + x2 ≤ 3
x2 + 4x3 + x4 ≤
3
x1, x2, x3, x4 ≥ 0
3. Maximize z = 2x + 5y
subject to
x + y ≤ 600
0 ≤ x ≤
400
0 ≤ y ≤
300
4. Maximize z = 5x1 + 3x2
subject to
3x1 + 5x2 ≤ 15
5x1 + 2x2 ≤ 10
x1, x2 ≥ 0
5. Maximize z = x1 - x2 + 3x3subject to
x1 + x2 + x3 ≤
10
2x1 - x3 ≤ 2
2x1 - 2x2 + 3x3 ≤
0
x1, x2, x3 ≥ 0
6. Maximize z = x1 - 3x2 + 2x3
subject to
3x1 - x2 + 2x3 ≤
7
-2x1 + 4x2 ≤ 12
-4x1 + 3x2 + 8x3 ≤
10
x1, x2, x3 ≥ 0
7. Maximize z = -2x1 - x2
subject to
x1 + 2x2 + x3 = 10
x1 + x2+ x4 = 6
x1 - x2 + x5 = 2
x1 - 2x2 + x6 = 1
x1, x2, x3, x4, x5, x6 ≥ 0
8. Minimize z = x1 + x2 + 3x3
subject to
3x1 + 2x2 + x3 ≤
3
2x1 + x2 + 2x3 ≥
2
x1, x2, x3 ≥ 0
9. Minimize z = x2 - 3x3 + 2x5
subject to
x1 + 3x2 - x3 + 2x5 = 7
-2x2 + 4x3 + x4 = 12
-4x2 + 3x3 + 8x5 + x6 =
10
x1, x2, x3 ≥ 0
10. Maximize z = 2x1 + 5x2 + 7x3
subject to
3x1 + 2x2 + 4x3 ≤
100
x1 + 4x2 + 2x3 ≤
100
x1 + x2 + 3x3 ≤
100
x1, x2, x3 ≥ 0
11. Maximize z = 6x + 5y - 3z - 4w
subject to
2x + 3y + 2z - 4w = 24
x + 2y ≤ 10
x + y + 2z + 3w ≤ 15
y+ z + w ≤ 8
x, y, z, w ≥ 0
12. Maximize z = 5x - 2y + 3z
subject to
2x + 2y - z ≥ 2
3x - 4y ≤3
y + 3z ≤ 5
x,y,z ≥ 0
13. Maximize z = 8x1 + 19x2 + 7x3
subject to
3x1 + 4x2 + x3 ≤
25
x1 + 3x2 + 3x3 ≤
50
x1, x2, x3 ≥ 0
14. Maximize: z = x1 + x2 + x3
subject to
4x1 + 5x2 + 3x3 ≤
15
10x1 + 7x2 + x3 ≤
12
x1, x2, x3 ≥ 0
15. Maximize: z = 3x1 + 4x2
subject to
x1 - x2 ≤ 1
-x1 + x2 ≤ 2
x1, x2 ≥ 0
16. Maximize z = 3x1 + 5x2 + 4x3
subject to
2x2 + 3x3 ≤ 18
2x2 + 5x3 ≤ 18
3x1 + 2x2 + 4x3 ≤
25
x1, x2, x3 > 10
17. Maximize z = 3x1 + 2x2
subject to
2x1 + x2 ≤ 40
x1 + x2 ≤ 24
2x1 + 3x2 ≤ 60
x1, x2 ≥ 0
18. Maximize z = 2x1 + 4x2
subject to
2x1 + 3x2 ≤ 48
x1 + 3x2 ≤ 42
x1 + x2 ≤ 21
x1, x2 ≥ 0
19. Minimize z = 4x1 + 8x2 + 3x3
subject to
x1 + x2 ≥ 2
2x1 + x3 ≥ 5
x1, x2, x3 ≥ 0
20. Minimize z = x1 + x2 + x3
subject to
x1 - x4 - 2x6 = 5
x2 + 2x4 - 3x5 + x6 = 3
x3 + 2x4 - 5x5 + 6x6 = 5
x1, x2, x3, x4, x5, x6≥ 0
21. Minimize z = 2x1 + 9x2 + x3
subject to
x1 + 4x2 + 2x3 ≥ 5
3x1 + x2 + 2x3 ≥ 4
x1, x2, x3 ≥
0
22. Minimize z = 10x + 12y
subject to
2x + 5y ≥ 150
3x + y ≥ 120
x, y≥ 0
23. Maximize z = 12x1 + 15x2 + 9x3
subject to
8x1 + 16x2 + 12x3 ≤
250
4x1 + 8x2 + 10x3 ≥
80
7x1 + 9x2 + 8x3 =
105
x1, x2, x3≥
0
24. Maximize z = 4x1 + 14x2
subject to
2x1 + 7x2 ≤ 21
7x1 + 2x2 ≤ 21
x1, x2 ≥ 0
25. Maximize z = 3x1 + 2x2
subject to
2x1 + x2 ≤ 2
3x1 + 4x2 ≥ 12
x1, x2 ≥ 0
26. Maximize z = x1 + x2
subject to
x1 + x2 ≤ 1
-3x1 + x2 ≥ 3
x1, x2 ≥ 0
27. Maximize z = 3x1 + 2x2
subject to
x1 - x2 ≤ 1
x1 + x2 ≥ 3
x1, x2 ≥ 0
28. Consider the constraints
-x1 + x2 ≤ 1
6x1 + 4x2 ≥ 24
x1 ≥ 0, x2 ≥ 2.
| (a) Minimize x1. |
| (b) Minimize x2. |
| (c) Maximize x1. |
| (d) Maximize x2. |
| (e) Minimize x1 + x2. |
| (f) Maximize x1 + x2. |
| (g) Maximize -x1 + 2x2. |
| (h) Maximize x1 - 2x2. |
| (i) Maximize -3x1 -2x2. |
29. Consider the constraints
-10x1 - 15x2 ≥
-150
5x1 + 10x2 ≥ 50
x1 - x2 ≥ 0
x1 ≥ 2, x2 ≥ 0.
| (a) Maximize x1 + x2. |
| (b) Minimize x1 + x2. |
| (c) Maximize x1 + 3x2. |
| (d) Maximize -2x1 + x2. |
| (e) Maximize -x1 - 3x2. |
| (f) Maximize -x1 - 2x2. |
