Solved Simplex Problems PDF

Solve the following linear programming problems by Simplex Algorithm.
1. Minimize Z = -2x1 - 4x2 - x3 - x4

Subject to
x1 + 3x2
+ x4 4
2x1 + x2
3
x2 + 4x3 + x4 3
x1, x2, x3, x4 0
Standard Maximization Form:

Maximize Z* = 2x1 + 4x2 + x3 + x4 + 0x5 + 0x6 + 0x7
Subject to
Z* - 2x1 - 4x2 - x3 - x4 - 0x5 - 0x6 - 0x7 = 0
x1 + 3x2
+ x4 + x5
=4
2x1 + x2
+ x6
=3
x2 + 4x3 + x4
+ x7 = 3
x1, x2, x3, x4, x5, x6, x7 0
Basic
Variables
Z*
x5
x6
x7
Coefficients of
x3
x4
-1
-1
0
1
0
0
4
1
x5
0
1
0
0
x6
0
0
1
0
x7
0
0
0
1
Right
Side
0
4
3
3
Z*
1
0
0
0
x1
-2
1
2
0
x2
-4
3
1
1
Z*
x2
x6
x7
1
0
0
0
-2/3
1/3
5/3
-1/3
0
1
0
0
-1
0
0
4
1/3
1/3
-1/3
2/3
4/3
1/3
-1/3
-1/3
0
0
1
0
0
0
0
1
16/3
4/3
5/3
5/3
Z*
x2
x6
x3
1
0
0
0
-3/4
1/3
5/3
-1/12
0
1
0
0
0
0
0
1
1/2
1/3
-1/3
1/6
5/4
1/3
-1/3
-1/12
0
0
1
0
1/4
0
0
1/4
23/4
4/3
5/3
5/12
Z*
x2
x1
x3
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
11/60
11/10
2/5
-1/5
-1/10
9.20
1/5
3/5
1/20
1/4
0
0
1/4
13/2
1
1
1/2
4/15
-1/5
3/20
Ratio
4/3
3/1
3/1
5/12
4
1
Optimal solution is x1 = 1, x2 = 1, x3 = , x4 = 0 and Z*max = 13/2, i.e., Zmin = -13/2
2. Maximize Z = 2x1 + 3x2

Subject to
x1 + x2 8
x1 + 2x2 = 5
2x1 + x2 8
x1, x2 0
Standard Form:
Maximize Z = 2x1 + 3x2 + 0x3 - Mx4 + 0x5
Subject to
Z - 2x1 - 3x2 - 0x3 + Mx4 - 0x5 = 0
x1 + x2 + x3 + 0x4 + 0x5 = 8
x1 + 2x2
+ x4
=5
2x1 + x2
+ x5 = 8
x1, x2, x3, x4, x5 0, x4 is an artificial variable
...(1)
...(2)
...... (3)
...(4)
The row operation (1) - M(3) gives

Z (2+M)x1 (3+2M)x2 + 0x3 + 0x4 + 0x5 = -5M
Basic
Variables
Z
x3
x4
x5
Z
1
0
0
0
x1
-(2+M)
1
1
2
Coefficients of
x2
x3
-(3+2M)
0
1
1
2
0
1
0
Z
x3
x2
x5
1
0
0
0
-1/2
1/2
1/2
3/2
0
0
1
0
0
1
0
0
Z
x3
x2
x1
1
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
x4
0
0
1
0
Right Side
Ratio
x5
0
0
0
1
-5M
8
5
8
8/1
5/2
8/1
0
0
0
1
15/2
11/2
5/2
11/2
11
5
11/3
1/3
-1/3
-1/3
2/3
28/3
11/3
2/3
11/3
Optimal solution is x1 = 11/3, x2 = 2/3 and Zmax = 28/3

*Once an artificial variable leaves, it is not required to perform the calculations
corresponding to that variable.
3. Maximize Z = -2x1 + x2 + 3x3

Subject to
x1 - 2x2 + 3x3 = 2
3x1 + 2x2 + 4x3 = 1
x1, x2, x3 0
Standard Form:
Maximize Z = -2x1 + x2 + 3x3 - Mx4 - Mx5
Subject to
Z + 2x1 - x2 - 3x3 + Mx4 + Mx5 = 0
x1 - 2x2 + 3x3 + x4
=2
3x1 + 2x2 + 4x3 + x5 = 1
x1, x2, x3, x4, x5 0
(1)
(2)
(3)
Z + (2 4M)x1 x2 (3 + 7M)x3 + 0x4 + 0x5 = -3M

(By the operation, (1) - M(2)) - M(3))
Basic
Variables
Z
x4
x5
Z
1
0
0
x1
2- 4M
1
3
x4
x3
0
0
5M/4 +
17/4
-5/4
3/4
Coefficients of
x2
x3
-1
-3 7M
-2
3
2
4
7M/2
+1/2
-7/2
1/2
x4
0
1
0
x5
0
0
1
Right Side
Ratio
-3M
2
1
2/3
1/4
4M+3
0
1
1
0
5/4
1/4
Optimality has been reached. However, one of the artificial variables, i.e., x4 appears as a basic
variable in the final table with a positive value equal to 5/4.
This implies that there does not exist any feasible solution to the given LPP.
4. Maximize Z = 2x1 + 3x2 + x3

Subject to
-3x1 + 2x2 + 3x3 = 8
-3x1 + 4x2 + 2x3 = 7
x1, x2, x3 0
Standard Form:
Maximize Z = 2x1 + 3x2 + x3 - Mx4 - Mx5
Subject to
Z - 2x1 - 3x2 - x3 + Mx4 + Mx5 = 0
-3x1 + 2x2 + 3x3 + x4
=8
-3x1 + 4x2 + 2x3
+ x5 = 7
x1, x2, x3, x4, x5 0
Z + (6M 2)x1 (3 + 6M)x2 (1 + 5M)x3 + 0x4 + 0x5 = -15M
Basic
Variables
Z
x4
x5
Coefficients of
x2
x3
-3-6M -5M - 1
2
3
4
2
Z
1
0
0
x1
-2+6M
-3
-3
x4
x2
0
0
-17/4 +
3M/2
-3/2
-3/4
0
1
-2M +
1/2
2
1/2
Z
x3
x2
1
0
0
-31/8
-3/4
-3/8
0
0
1
0
1
0
x4
0
1
0
0
1
0
x5
0
0
1
Right Side
Ratio
-15M
8
7
4
7/4
-9M/2 +
21/4
92
7/4
9/4
7/2
33/8
9/4
5/8
In the last table, x1 is the entering variable as the corresponding element in the first row is
negative. But all the elements in the pivot column are negative, indicating that the
problem has an unbounded solution.
5. Maximize Z = 4x1 + 6x2

Subject to
2x1 + 3x2 6
x1 - x2 1
x1, x2 0
Standard Form:
Maximize Z = 4x1 + 6x2 + 0x3 + 0x4
Subject to
Z - 4x1 - 6x2 - 0x3 - 0x4 = 0
2x1 + 3x2 + x3
=6
x1 - x2
+ x4 = 1
x1, x2, x3, x4 0
Basic
Variables
Coefficients of
Right
Side
Z
x3
x4
Z
1
0
0
x1
-4
2
1
x2
-6
3
-1
x3
0
1
0
x4
0
0
1
0
6
1
Z
x2
x4
1
0
0
0
2/3
5/3
0
1
0
2
1/3
1/3
0
0
1
12
2
3
Ratio
6/3
3
9/5
As all the elements in the first row of the final table are 0, optimality has been reached.
x1 = 0 and x2 = 2 is an optimal solution and the maximum value of Z is 12.
For one of the non-basic variables, i.e., x1, the corresponding element in the first row is
zero. This indicates that there exists an alternate optimal solution. We can find the
alternate optimal solution by considering x1 as an entering variable.
Z
x2
x1
1
0
0
0
0
1
0
1
0
2
1/5
1/5
0
-2/5
3/5
12
4/5
9/5
An alternate optimal solution is x1 = 9/5 and x2 = 4/5. Also any convex combination of
the above two optimal solutions will also be an optimal solution.

Solved Simplex Problems PDF

Uploaded by

Copyright:

Available Formats

Solved Simplex Problems PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Solved Simplex Problems PDF

Uploaded by

Copyright:

Available Formats

Solve the following linear programming problems by Simplex Algorithm.

1. Minimize Z = -2x1 - 4x2 - x3 - x4

Standard Maximization Form:

Optimal solution is x1 = 1, x2 = 1, x3 = , x4 = 0 and Z*max = 13/2, i.e., Zmin = -13/2

2. Maximize Z = 2x1 + 3x2

The row operation (1) - M(3) gives

Optimal solution is x1 = 11/3, x2 = 2/3 and Zmax = 28/3

3. Maximize Z = -2x1 + x2 + 3x3

Z + (2 4M)x1 x2 (3 + 7M)x3 + 0x4 + 0x5 = -3M

4. Maximize Z = 2x1 + 3x2 + x3

5. Maximize Z = 4x1 + 6x2

You might also like