System Engineering 3(3+0)

Lesson 5 Simplex method -Problems

The given LPP is Max Z = 30x +40y +20z

 Subject to

                   10x+12y+7z ≤10000

                    7x +10y +8z ≤8000

                      x + y +z ≤1000

                           x,y,z ≥0

 

Step 1: Check up whether the objective function is of maximization type. Otherwise apply the equation Min(Z)=-Max(-Z) to convert the objective function to maximization type.

Step 2: Convert all the inequalities(≤ type)  into equalities by introducing slack Variables. Then the problem becomes 

           Max Z = 30x +40y +20z+0.s₁+0.s₂+0.s₃

Subject to

                   10x+12y+7z +s₁ = 10000

                    7x +10y +8z +s₂ = 8000

                    x + y +z +s₃ =1000

                    x, y, z , s₁, s₂, s₃  ≥ 0

Step 3: Identify a suitable initial feasible solution by putting x=y=z=0.Then s₁=1000; s₂=8000 and s₃=1000 and these are the basic variables and the original variables x,y,z are non-basic variables. p

 Step 4: Form the initial simplex table

			30	40	20	0	0	0
CB	YB	XB	Y1	Y2	Y3	Y4	Y5	Y6
0	Y4	10000	10	12	7	1	0	0
0	Y5	8000	7	10	8	0	1	0
0	Y6	1000	1	1	1	0	0	1
		0	-30	-40	-20	0	0	0

 

Step 5: Compute the value of the objection by using C_BX_B. Also compute all the ‘Net Evaluations’ using

z_j-c_j = C_BY_j – c_j

and write them in the last row.

 

Step 6: If all the net evaluations are ≥ 0, the the optimal solution is reached. In the above example, the net evaluations corresponding to x1,x2 and x3 are negative. So the  current solution is not optimal.

Step 7: Identify the most negative net evaluation and the variable corresponding to it will enter the basis. In the above problem, the most negative net evaluation is -40 and it corresponds to the variable x₂ (or Y₂). So Y₂ enters into the basis.

			30	40	20	0	0	0
CB	YB	XB	Y1	Y2	Y3	Y4	Y5	Y6
0	Y4	10000	10	12	7	1	0	0	10000/12=833…
0	Y5	8000	7	10	8	0	1	0	8000/10=800
0	Y6	1000	1	1	1	0	0	1	1000/1=1000
		0	-30	-40	-20	0	0	0	→

                                                                                                                            ↑                                                     ←↓

                                                                                                            Entering variable                                   leaving variable

Step 8: To find the ‘leaving variable’, select the variable for which the ratio  is a minimum (where j refers to the entering variable). So in the above example we have to find the minimum of the ratios (10000/12,8000/10,1000/1). The minimum ratio is 800 and it corresponds to the variable Y₅. So Y₅ leaves the basis. The row corresponding to Y₅ is called ‘pivot row’ and the column corresponding to Y₂ is called ‘pivot column’. The element at the intersection of ‘pivot row’ and ‘pivot column’ is known as ‘pivot element’ and in the above example the pivot element is 10.

Step9: Form the next simplex table. Dividing all the pivot row elements by the pivot element.

			30	40	20	0	0	0
CB	YB	XB	Y1	Y2	Y3	Y4	Y5	Y6
0	Y4	10000	10	12	7	1	0	0	10000/12=833…
40	Y2	8000	7	10	8	0	1	0	8000/10=800
0	Y6	1000	1	1	1	0	0	1	1000/1=1000
		0	-30	-40	-20	0	0	0

Step 10: Convert all the other elements in the pivot column to 0  as follows:

Pivot Row:   Row 2

800

7/10

1

8/10

0

1/10

0

 

Row 1:

10000	10	12	7	1	0	0
9600	84/10	12	96/10	0	12/10	0

 

Pivot Row X 12 

                  (-)

400

16/10

0

-26/10

1

-12/10

0

 

Row 3:      

1000	1	1	1	0	0	1
800	7/10	1	8/10	0	1/10	0

 

Pivot Row X 1

(-)     

200

3/10

0

2/10

0

-10/10

1

 

Step 10: Form the next Simplex table:Repeat steps 7 to 9.

			30	40	20	0	0	0
CB	YB	XB	Y1	Y2	Y3	Y4	Y5	Y6
0	Y4	400	16/10	0	-26/10	1	-12/10	0	250
40	Y2	800	7/10	1	8/10	0	1/10	0	8000/7
0	Y6	200	3/10	0	2/10	0	-1/10	1	2000/3
		32000	-2	0	12	0	4	0

                                                                                                                     ↑

                                                                                                     Entering variable

Y₁ enters into the basis and Y₄ leaves the basis.

			30	40	20	0	0	0
CB	YB	XB	Y1	Y2	Y3	Y4	Y5	Y6
30	Y1	250	1	0	-26/16	1	-12/16	0
40	Y2	800	7/10	1	8/10	0	1/10	0
0	Y6	200	3/10	0	2/10	0	-1/10	1
		32000

 

 

Pivot Row:

250

1

0

-26/16

0

-12/16

0

Row: 2

800	7/10	1	8/10	0	1/10	0
175	7/10	0	-182/160	0	-84/160	0

 

Pivot Row X 7/10

(-)

625

0

1

31/16

0

10/16

0

Row 3:

200	3/10	0	2/10	0	-1/10	1
75	3/10	0	-78/160	0	-36/160	0

 

 

Pivot row  X 3/10

(-)

125

0

0

11/16

0

20/160

1

 

Next Simplex Table:

			30	40	20	0	0	0
CB	YB	XB	Y1	Y2	Y3	Y4	Y5	Y6
30	Y1	250	1	0	-26/16	1	-12/16	0
40	Y2	625	0	1	31/16	0	10/16	0
0	Y6	125	0	0	11/16	0	20/160	1
		32500	0	0	120/16	0	40/16	0

All the net evaluations are ≥ 0. So optimal solution is reached. So

Optimal Area under Crop 1 = 250 acres;

Optimal Area Under crop 2 = 625 acres

Optimal Area Under crop 3 = 0 acres

Maximum Profit: 32,500

 

Resource utilization

Resource	Crop 1	Crop 2	Crop 3	Total Resource Used	Total Resource available	Slack
Optimal areas	250	625	0	--	--	--
Land	1	1	1	875	1000	125
Capital	10	12	7	10000	10000	0
Labour	7	10	8	8000	8000	0