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

 

Answer

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

 

Answer

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

 

Answer

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

 

Answer

 

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

Answer

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

 

Answer

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