USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

VARIOUS STEPS IN SOLVING OR PROBLEM USING SIMPLEX METHOD

Step I. Formulate the problem

The problem must be put in the form of a mathematical model. The standard form of the LP model has the following properties.

a)     An objective function, which has tc be maximized or minimized.

b)    All the constraints can be put in the form of equations.

c)     All the variables are non-negative.

Step II. Set up the initial simplex table with slack variable or surplus variables in the solution,

Step III. Determine the decision variables which are to be brought in the solution.

Step IV. Determine which variables to replace.

Step V. Calculate new row values for entering variables.

Step VI. Revise remaining rows.

Repeat step III to VI till an optimal solution is obtained. This procedure can best be explained with the help of a suitable example,

Sol.

Step 1 Formulate the problem,

Problem is already stated in the mathematical model.

Step 2. Set up the initial simplex table with the slack variables in solution. By introducing the slack variables, the equations in step I, i.e., the mathematical model can be rewritten as follows.

3X1 + 2X2 + S1 = 1,200

2X1 + 6X2 + S2 = 1,500

X1 + S3 = 350

X2 + S4 = 200

where S1, S2 , S3 and S4 are the slack variables. Let us re-write the above equation in a symmetrical manner so that all the four slacks S1, S2, S3 and S4 appear in all the equations.

3X1 + 2X2 + 1S1 + 0S2 + 0S3 + 0S4 = 1,200

2X1 + 6X2 + 0S1 + 1S2 + 0S3 + 0S4 = 1,500

1X1 + 0X2 + 0S1 + 0S2 + 1S3 + 0S4 = 350

0X1 +1X2 + 0S1 + 0S2 + 0S3 + 1S4 = 200

Let us also write the objective function Z by introducing the slacks in it.

Z = 10X1 + 20X2 + 0S1 + 0S2 + 0S3 + 0S4

The first simplex table can now be written as.

Table 3.1

Cj

Solution Mix

Rs. 10

Rs. 20

0

0

0

0

Contribution unit quantity

X1

X2

S1

S2

S3

S4

0

S1

3

2

1

0

0

0

1200

0

S2

2

6

0

1

0

0

1500

0

S3

1

0

0

0

1

0

350

0

S4

0

1

Key element

0

0

0

1

200 Key Row

Zj

(Cj-Zj)

0

0

0

0

0

0

0

10

20

Key column

0

0

0

0

 

The first simplex table is shown in Table 3-.1. The table is explained as below:-

  1. Row 1 contains Cj or the contribution to total profit with the production of one unit of each product X1 and X2. This row gives the coefficients of the variables in the objective function which will remain the same. Under column 1 (Cj) is provided profit per unit of 4 variables S1, S2, S3, S4 which is zero.
  2. All the variables S1, S2, S3, S4 are listed under Solution Mix. Their profit is zero and written under column 1 (Cj) as explained above.
  3. The constraint variables are written to the right of solution mix. These are X1, X2, S1, S2 L3 and S4.Under these are written coefficient of variables and under each are written the coefficients of particular variable as they appear in the constraint equations. For example, the coefficients X1, X2, S1, S2, S3 and S4 in first constraints equation are 3, 2, 1, 0, 0 and 0, respectively which are written under these variables in the first level. Similarly, the remaining 3 rows represent the coefficients of the variables as they appear in the other 3 constraint equations. The entries in the quantity column represent the right hand side of each constraint equation. These values are 1,200, 1,500, 350 and 200 respectively, for the given problem.
  4. The Zj values in the second row from the bottom refer to the amount of gross profit that is given up by the introducing one unit of that variable into the solution. The subscript j refers to the specific variable being considered. The Zj value under the quantity column is the total profit for their solution. In the initial column all the Zj values will be zero because no real product is being manufactured and hence there is no gross profit to be lost if they are replaced.
  5. The bottom row of the table contains net profit per unit obtained by introducing one unit of a given variable into the solution. This row is designated as the Cj – Zj row. The procedure for calculating Zj and Cj- Zj values is given below:

Calculation of Zj,

Cj × X1

0 × 3 = 0

+

0 × 2 = 0

+

0 × 1 = 0

+

0 × 0 =0

Cj × X2

0 × 2 =0

+

0 × 6 = 0

+

0 × 0 = 0

+

0 × 1 = 0

Cj × S1

0 × 1 = 0

+

0 × 0 = 0

+

0 × 0 = 0

+

0 × 0 = 0

ZX1=0

ZX2=0

ZS1=0

 

Similarly, ZS2, ZS3 and ZS4 can be calculated as 0 each.

Calculation of Cj – Zj

CX1-ZXI =10-0 =10

CX2 – ZX2 = 20 – 0 = 20

CS1 – ZS1 = 0 – 0 = 0

CS2 – ZS2 = 0 – 0 = 0

CS3 – ZS3 = 0 – 0 = 0

CS4 – ZS4 = 0 – 0 = 0

The total profit for this solution is Rs. zero.

Step 3. Determine the variable to be brought into the solution. An improved solution is possible if there is a positive value in Cj – Zj row. The variable with the largest positive value in the Cj – Zj row is subjected as the objective is to maximize the profit. The column associated with this variable is referred to as ‘key column’ and is designated by a small arrow beneath this column. In the given example, 20 is the largest possible value corresponding to X2 which is selected as the key column.

Step 4. Determine which variable is to be replaced. To make this determination, divide each amount in the contribution quantity column by the amount in the comparable row of key column, X2 and choose the variable associated with smallest quotient as the one to be replaced. In the given example, these values are calculated as

for the S1 row – 1200/2 = 600

for the S2 row – 1500/6 = 250

for the S3 row – 350/0 = ∞

for the S4 row – 200/1 = 200

Since the smallest quotient is 200 corresponding to S4, S4 will be replaced, and its row is identified by the small arrow to the right of the table as shown. The quotient represents the maximum value of X which could be brought into the solution.

Step 5. Calculate the new row values for entering the variable. The introduction of X2 into the solution requires that the entire S4 row be replaced. The values of X2, the replacing row, are obtained by dividing each value presently in the S4 row by the value in column X2 in the same row. This value is termed as the key or the pivotal element since it occurs at the intersection of key row and key column.

0/1 = 0; 1/1 = I ; 0/1 = 0; 0/1 = 0; 0/1 = 0; – 1/1 = 1 ; 200/1 = 200

Step 6. Update the remaining rows. The new S2 row values are 0, 1, 0, 0, 1 and 200 which are same as the previous table as the key element happens to be 1. The introduction of a new variable into the problem will affect the values of remaining variables and a second set of calculations need to be performed to update the initial table. These calculations are performed as given here:

Updated S1 row = old S1 row – intersectional element of old S1 row X corresponding element of new X2 row

= 3 – [2 × 0] = 3

= 2 – [2 × 1] = 0

= 1 – [2 × 0] = 1

= 0 – [2 × 0] = 0

= 0 – [2 × 0] = 0

= 0 – [2 × 1] = -2

=1200 – [2 × 200] = 800

Similarly, the updated elements of S2 and S3 rows can be calculated as follows:

Elements of updated S2 row

Elements of updated S3 row

2–[6×0]=2

6-[6×1]=0

0-[6×0]=0

1-[6×0]=1

0-[6×0]=0

0-[6×1]=-6

1500-[6×200]=300

1-[0×0]=1

0-[0×1]=0

0-[0×0]=0

0-[0×0]=0

1-[0×0]=1

0-[0×1]=0

350-[0×200]=350

Rewriting the second simplex table with the updated elements as shown in Table 3.2 below:

Solution Mix

Rs.10

Rs.20

0

0

0

0

Contribution

Ratio

Cj

X1

X2

S1

S2

S3

S4

Quantity

0

S1

3

0

1

0

0

-2

800

266.7

0

S2

2

0

0

1

0

-6

300

150

0

S3

1

0

0

0

1

0

350

350

20

X2

0

1

0

0

0

1

200

Zj

0

20

0

0

0

20

4000

(Cj-Zj)

10

0

0

0

0

-20

 

The new variable entering the solution would be X1. It will replace the S2 row which can be shown as follows:

For the S1 row 800/3 = 266·7

For the S2 row 300/2 = 150

For the S3 row 350/1 = 350

For the S4 row 200/0 = 00

As the quotient 150 corresponding to S2 row is the minimum, it will be replaced by X, in the new solution. The corresponding elements of S2 row can be calculated as follows:

 

New elements of S2 row to be replaced by X1 are

2/2 = 1; 0/2 = 0; 0/2 = 0; 1/2 = 1/2; 0/2 = 0; – 6/2 = – 3; 300/2 = 150;

The updated elements of S1 and S3 rows can be calculated as follows:

Elements of updated S1 row

3 – [3 × 1] = 0

0 – [3 × 0] = 0

1 – [3 × 1/2] = 1

1 – [3 × 0] = 0

0 – [3 × -3] = -7

800 – [3 × 150] = 350

Elements of updated S3 row

1 – [1 × 1] = 0

0 – [1 × 0] = 0

0 – [1 × 0] = 0

0 – [1 × 1/2] = -1/2

1 – [1 × 0] = 1

0 – [1 × -3] = 3

350 – [1 × 150] =200

Elements of updated X2 row

0-[0 ×1] =0

1- [0 × 0] = 1

0- [0 × 0] = 0

0-[0 × 1/2] = 0

0-[0 × 0] = 0

1- [0 × - 3] = 1

200 – [0 × 150] = 200

Revised simplex table can now be written as shown in Table 3.3 below:

CJ

Solution

Rs.10

Rs.20

0

0

0

0

Contribution

Min Ratio

Mix

X1

X2

S1

S2

S3

S4

Quantity

0

S1

0

0

1

-3/2

0

7

350

50

10

X1

1

0

0

1/2

0

-3

150

-50

0

S3

0

0

0

-1/2

1

3

200

66.7

20

X2

0

1

0

0

0

1

200

200

Zj

10

20

0

5

10

-10

5500

(Cj-Zj)

0

0

0

-5

0

10

 

Now the new entering variable will be S4 and it will replace S1 as shown below:

350/7 = 50

150/- 3 =- 50

200/3 = 66.7

200/1 = 200

In these figures, 50 represent the minimum quotient which corresponds to row S1 .

The new elements of S1 row to be replaced by S4 can be calculated as follows:

The new elements of S1 row would be

0/7 =0; 0/7 =0; 1/7 = 1/7; (-3/2) × (1/7) =-3/14; 0/7=0; 1; 7/7 = 1; 350/7=50

The updated elements of the other rows can be calculated as follows:

Elements of updated X1 row  

1- [- 3 × 0] = 1

0- [- 3 × 0] = 0

0-[-3 × 1/7] =3/7

½ [- 3 × 3/14] = – 1/7

0-[-3 × 0] =0

- 3 – [- 3 × 1] = 0

150 – [- 3 × 50] = 300

Elements of updated S3 row

0-[3 × 0] =0

0- [3 × 0] = 0

0- [3 × 1/7] =-3/7

- ½ [3 × - 3/14] = – 1/7

1 – [3 × 0] = 1

3 – [3 × -1] = 0

200 – [3 × 50] = 50

Elements of Updated X2 row

0-[1×0] = 0

1- [1 × 0] = 1

0- [1 × 1/7] = 1/7

0-[1 ×-3/14] =3/14

0-[1×0]=0

1-[1×1]=0

200 – [1 × 50] = 150

The new simplex table can now be written as shown in Table 3.4.

Table 3.4

Solution Mix

Rs.10

Rs.20

0

0

0

0

Contribution Quantity

Cj

X1

X2

S1

S2

S3

S4

0

S4

0

0

1/7

-3/14

0

1

50

10

X1

1

0

3/7

-1/7

0

0

300

0

S3

0

0

-3/7

1/7

1

0

50

20

X2

0

1

-1/7

3/14

0

0

150

Zf

10

20

10/7

40/14

0

0

6,000

(Cj-Zf)

0

0

-10/7

-40/14

0

0

6,000

 

As there is no positive value in Cj – Zj row it represents the optimal solution, which is given as:

X1 = 300 units: X2 = 150 units

And the maximum profit Z = Rs 6,000