#### Sample Assignments of Simplex Method

Worked Examples

Solve with the help of simplex method

Example 1

Maximize Z = 80x1 + 55x2

Subject to

4x1 + 2x2 ≤ 40

2x1 + 4x2 ≤ 32

&     x1 ≥ 0, x≥ 0

SLPP

Maximize Z = 80x1 + 55x2 + 0s1 + 0s2

Subject to

4x1 + 2x2+ s1= 40

2x1 + 4x2 + s2= 32

x1 ≥ 0, x≥ 0, s1 ≥ 0, s2 ≥ 0

Cj →    80               55            0                0

 Basic Variables CB       XB X1              X2                S1                   S2 Min ratio  XB /Xk s1    s2 0         40    0         32 4                2              1                0     2                4              0                1 40 / 4 = 10→ outgoing   32 / 2 = 16 Z= CB XB = 0 ↑incoming Δ1= -80      Δ2= -55      Δ3=0        Δ4=0 x1                        s2 80       10                    0         12 (R1=R1 / 4)     1                1/2          1/4              0   (R2=R2- 2R1)   0                 3           -1/2             1 10/1/2 = 20                  12/3 = 4→ outgoing Z = 800 ↑incoming Δ1=0       Δ2= -15      Δ3=40        Δ4=0 x1                        x2 80         8                    55         4 (R1=R1- 1/2R2)  1                0             1/3              -1/6   (R2=R2 / 3)  0                1            -1/6              1/3 Z = 860 Δ1=0      Δ2=0       Δ3=35/2       Δ4=5

As all Δj ≥ 0, optimal basic feasible solution is achieved. Hence the solution is Max Z = 860, x1 = 8 and x2 = 4

Example 2

Maximize Z = 5x1 + 3x2

Subject to

3x1 + 5x2 ≤ 15

5x1 + 2x2 ≤ 10

&     x1 ≥ 0, x≥ 0

SLPP

Maximize Z = 5x1 + 3x2 + 0s1 + 0s2

Subject to

3x1 + 5x2+ s1= 15

5x1 + 2x2 + s2= 10

x1 ≥ 0, x≥ 0, s1 ≥ 0, s2 ≥ 0

Cj →     5                3               0                0

 Basic Variables CB       XB X1               X2                 S1                 S2 Min ratio  XB /Xk s1    s2 0         15    0         10 3                5              1                0     5                2              0                1 15 / 3 = 5   10 / 5 = 2 → outgoing Z= CB XB = 0 ↑incoming Δ1= -5       Δ2= -3       Δ3=0        Δ4=0 s1                        x1 0          9                    5          2 (R1=R1- 3R2)     0               19/5           1             -3/5   (R2=R2 /5)  1               2/5             0                1/5 9/19/5 = 45/19 →                 2/2/5 = 5 Z = 10 ↑ Δ1=0         Δ2= -1        Δ3=0        Δ4=1 x2                        x1 3         45/19                    5         20/19 (R1=R1 / 19/5)  0                1              5/19         -3/19   (R2=R2 -2/5 R1)  1               0             -2/19          5/19 Z = 235/19 Δ1=0      Δ2=0      Δ3=5/19     Δ4=16/19

As all Δj ≥ 0, optimal basic feasible solution is attained. So the solution is Max Z = 235/19, x1 = 20/19 and x2 = 45/19

Example Sample Assignments 3

Maximize Z = 5x1 + 7x2

Subject to

x1 + x2 ≤ 4

3x1 - 8x2 ≤ 24

10x1 + 7x2 ≤ 35

&     x1 ≥ 0, x≥ 0

SLPP

Maximize Z = 5x1 + 7x2 + 0s1 + 0s2 + 0s3

Subject to

x1 + x2 + s1= 4

3x1 - 8x2 + s2= 24

10x1 + 7x2 + s3= 35

x1 ≥ 0, x≥ 0, s1 ≥ 0, s2 ≥ 0, s3 ≥ 0

Cj →   5             7            0           0          0

 Basic Variables CB       XB X1          X2             S1             S2           S3 Min ratio  XB /Xk s1    s2    s3 0         4   0                  24    0         35 1             1           1            0          0     3            -8           0            1          0    10            7           0            0          1 4 /1 = 4→outgoing   -    35 / 7 = 5 Z= CB XB = 0 ↑incoming  -5            -7           0            0          0 ←Δj x2      s2      s3 7              4     0         56      0          7 1             1           1            0          0     (R2 = R2 + 8R1)   11           0           8            1          0     (R3 = R3 - 7R1)   3             0          -7            0          1 Z = 28 2             0           7            0          0 ←Δj

Because all Δj ≥ 0, optimal basic feasible solution is achieved

Thus the solution is Max Z = 28, x1 = 0 and x2 = 4

Sample Assignment 4

Maximize Z = 2x - 3y + z

Subject to

3x + 6y + z ≤ 6

4x + 2y + z ≤ 4

x - y + z ≤ 3

&     x  ≥ 0, y  ≥ 0, z ≥ 0

Solution

SLPP

Maximize Z = 2x - 3y + z + 0s1 + 0s2 + 0s3

Subject to

3x + 6y + z + s1= 6

4x + 2y + z + s2= 4

x - y + z + s3= 3

x ≥ 0, y  ≥ 0, z ≥ 0 s1 ≥ 0, s2 ≥ 0, s3 ≥ 0

Cj →     2             -3              1           0            0           0

 Basic Variables CB       XB X             Y                 Z              S1              S2             S3 Min ratio  XB /Xk s1    s2    s3 0         6   0                  4   0         3 3              6             1             1            0          0       4              2            1             0             1          0     1              -1            1             0             0         1 6 / 3 = 2   4 / 4 =1→ outgoing   3 / 1 = 3 Z = 0 ↑incoming -2               3             -1             0             0         0 ←Δj s1                     x    s3 0          3            2          1     0          2 0             9/2            1/4            1         -3/4        0   1              1/2            1/4            0         1/4          0   0             -3/2            3/4           0         -1/4         1 3/1/4=12   1/1/4=4              8/3 = 2.6→ Z = 2 ↑incoming    0                4               1/2          0           1/2        0 ←Δj s1               x      z 0                  7/3       2         1/3     1         8/3 0                5                0            1         -2/3      -1/3   1                1                0            0          1/3       -1/3   0              -2                 1            0         -1/3        4/3 Z = 10/3 0                3                 0            0         1/3        2/3 ←Δj

As all Δj ≥ 0, optimal basic feasible solution is achieved. Consequently the solution is Max Z = 10/3, x = 1/3, y = 0 and z = 8/3

Example 5

Maximize Z = 3x1 + 5x2

Subject to

3x1 + 2x2 ≤ 18

x1 ≤ 4

x2 ≤ 6

&     x1 ≥ 0, x≥ 0

SLPP

Maximize Z = 3x1 + 5x2 + 0s1 + 0s2 + 0s3

Subject to

3x1 + 2x2 + s1= 18

x1 + s2= 4

x2 + s3= 6

x1 ≥ 0, x≥ 0, s1 ≥ 0, s2 ≥ 0, s3 ≥ 0

Cj →   3              5             0            0            0

 Basic Variables CB XB X1 X2 S1 S2 S3 Min ratio  XB /Xk s1 0 18 3 2 1 0 0 18 / 2 = 9 s2 0 4 1 0 0 1 0 4 / 0 = ∞ (neglect) s3 0 6 0 1 0 0 1 6 / 1 = 6→ Z = 0 -3 ↑ -5 0 0 0 ←Δj (R1=R1-2R3) s1 0 6 3 0 1 0 -2 6 / 3 = 2 → s2 0 4 1 0 0 1 0 4 / 1 = 4 x2 5 6 0 1 0 0 1 -- Z = 30 ↑ -3 0 0 0 5 ←Δj (R1=R1 / 3) x1 3 2 1 0 1/3 0 -2/3 (R2=R2 - R1) s2 0 2 0 0 -1/3 1 2/3 x2 5 6 0 1 0 0 1 Z = 36 0 0 1 0 3 ←Δj

As find that, all Δj ≥ 0, optimal basic feasible solution is achieved. As a result the solution is Max Z = 36, x1 = 2, x2 = 6

Example 6

Minimize Z = x1 - 3x2 + 2x3

Subject to

3x1 - x2 + 3x3 ≤ 7

-2x1 + 4x2 ≤ 12

-4x1 + 3x2 + 8x3 ≤ 10

&     x1 ≥ 0, x≥ 0, x3 ≥ 0

SLPP

Min (-Z) = Max Z? = -x1 + 3x2 - 2x3 + 0s1 + 0s2 + 0s3

Subject to

3x1 - x2 + 3x3 + s1 = 7

-2x1 + 4x2 + s2 = 12

-4x1 + 3x2 + 8x3 + s3 = 10

x1 ≥ 0, x≥ 0, x3 ≥ 0 s1 ≥ 0, s2 ≥ 0, s3 ≥ 0

Cj →      -1           3          -2           0            0            0

 Basic Variables CB XB X1 X2 X3 S1 S2 S3 Min ratio XB /Xk s1 0 7 3 -1 3 1 0 0 - s2 0 12 -2 4 0 0 1 0 3→ s3 0 10 -4 3 8 0 0 1 10/3 Z' = 0 1 ↑ -3 2 0 0 0 ←Δj (R1 = R1 + R2) s1 0 10 5/2 0 3 1 1/4 0 4→ (R2 = R2 / 4) x2 3 3 -1/2 1 0 0 1/4 0 - (R3 = R3 - 3R2) s3 0 1 -5/2 0 8 0 -3/4 1 - Z' = 9 ↑ -5/2 0 0 0 3/4 0 ←Δj (R1 = R1 / 5/2) x1 -1 4 1 0 6/5 2/5 1/10 0 (R2 = R2 + 1/2 R1) x2 3 5 0 1 3/5 1/5 3/10 0 (R3 = R3 + 5/2R1) s3 0 11 0 1 11 1 -1/2 1 Z' = 11 0 0 3/5 1/5 1/5 0 ←Δj

As all Δj ≥ 0, optimal basic feasible solution is achieved

Thus the solution is Z' =11 which means Z = -11, x1 = 4, x2 = 5, x3 = 0

Example 7

Max Z = 2x + 5y

x + y ≤ 600

0 ≤ x ≤ 400

0 ≤ y ≤ 300

SLPP

Max Z = 2x + 5y + 0s1 + 0s2 + 0s3

x + y + s1 = 600

x + s2 = 400

y + s3 = 300

x1 ≥ 0, y  ≥ 0, s1 ≥ 0, s2 ≥ 0, s3 ≥ 0

Cj →    2                5              0               0                0

 Basic Variables CB XB X Y S1 S2 S3 Min ratio XB /Xk s1 0 600 1 1 1 0 0 600 / 1 = 600 s2 0 400 1 0 0 1 0 - s3 0 300 0 1 0 0 1 300 /1 = 300→ Z = 0 -2 ↑ -5 0 0 0 ←Δj (R1 = R1 - R3) s1 0 300 1 0 1 0 -1 300 /1 = 300→ s2 0 400 1 0 0 1 0 400 / 1 = 400 y 5 300 0 1 0 0 1 - Z = 1500 ↑ -2 0 0 0 5 ←Δj x 2 300 1 0 1 0 -1 (R2 = R2 - R1) s2 0 100 0 0 -1 1 1 y 5 300 0 1 0 0 1 Z = 2100 0 0 2 0 3 ←Δj

As given that, all Δj ≥ 0, optimal basic feasible solution is achieved. Thus the solution is Z = 2100,   x = 300, y = 300