Lesson 5 Simplex method -Problems

A farmer has 1,000 acres of land on which he can grow corn, wheat or soyabeans.  Each acre of corn costs Rs. 100 for preparation, requires 7 man-days of work and yields a profit of Rs. 30.  An acre of wheat costs Rs. 120 to prepare, requires 10 man-days of work and yields a profit of Rs. 40.  An acre of soyabeans costs Rs. 70 to prepare, requires 8 man-days of work and yields a profit of Rs. 20.  The farmer has Rs. 1,00,000 for preparation and 8,000 man-days of work.  Set-up the linear programming equation for the problem.

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.s1+0.s2+0.s3

Subject to

                   10x+12y+7z +s1 = 10000

                    7x +10y +8z +s2 = 8000

                    x + y +z +s3 =1000

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

Step 3: Identify a suitable initial feasible solution by putting x=y=z=0.Then s1=1000; s2=8000 and s3=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 CBXB. Also compute all the ‘Net Evaluations’ using

zj-cj = CBYj – cj

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 x2 (or Y2). So Y2 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 Y5. So Y5 leaves the basis. The row corresponding to Y5 is called ‘pivot row’ and the column corresponding to Y2 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

Y1 enters into the basis and Y4 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

 

 

Last modified: Saturday, 3 May 2014, 10:33 AM