USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

MINIMISATION PROBLEMS (ALL CONSTRAINTS OF THE TYPE ) BIG ‘M’ METHOD

We have till now seen in this chapter, the type of problems where profit had to be maximised and the constraints were of the type ≤. However, there could be problems where the objective function has to be minimised (like the availability of funds, raw material or the costs of operations have to be minimised) and the constraints involved may be of the type ≥ or =. In such cases, the simplex method is somewhat different and is discussed in the form of following steps.

Step 1. Formulation of mathematical model

Now we subtract the surplus variables S1, S2, …. Sn etc to convert the inequalities into equations.

i.e., Minimise Z = C1 x1 + C2 x2 + C3 x3 + …. + Cn Xn + 0S1 + 0S2 + …. + 0Sn

Subject to the constraints

As in the maximisation problem, initial basic solution is obtained by putting x1 = x2 = xn = 0

So –S1=b1 or S1=-b1

- S2 = b2 or S2 = – b2

- Sm = bm or Sm = – bm

It may be seen that S1, S2, …. Sm being negative violate the non-negativity constraint and hence is not feasible. Hence, in the system of constraints we introduce m new variables A1, A2 …. Am known as artificial variable. By introducing these variables the equations are

a11 x1 + a12 x2 + a13 x3 + …. + a1n xn – S1 + A1 = b1

a21 x1 + a22 x2 + a23 x3 + …. + a2n xn – S2 + A2 = b2

am1 x1 + am2 x2 + am3 x3 + …. + amn xn – Sm + Am = bm

where xj ≥ 0 (i = 1, 2, 3, …. n)

Sj  ≥0 (j=1,2,3, …. m)

Aj ≥ 0(j=1,2,3, …. m)

As we have introduced artificial variables A1, A2 …. Am this has to be taken out of the solution. For this purpose, we introduce a very large value (M) assigned to each of artificial variable and zero to each of the surplus variables as the coefficient values in the objective function. The problem now becomes

Minimise Z=C1x1 + C2x2 + C3x3 + …. + Cnxn

+ 0S1 + 0S2 + …. + 0Sm +

MA1 + M A2 + …. + M Am

Subject to the constraints

a11 x1 + a12 x2 + a13 x3 + …. + a1n xn – S1 + A1 = b1

a21 x1 + a22 x2 + a23 x3 + …. + a2n xn – S2 + A2 = b2

am1 x1 + am2 x2 + am3 x3 + …. + amn xn – Sm + Am = bm

Step 2. Setting up of initial simplex table

Here, we allot 0 values to variables x1 = x2 = x3 =…. = xn = 0 so that A1 = b1, A2 = b2 …. Am=bm.

Table 3.15

Initial simplex table

CB

Solution mix

Cj

C1, C2, C3, …. Cn, 0 0 M … M  Minimum ratio

Solution values

x1, x2, x3 …. xS1, S2, S3 …. Sn

CB1

CB2

CBn

A1

A2

An

b1

b2

bn

a11 + a12 …. + a1n -1 0 0 1 0 … 0

a21 + a22 …. + a2n 0 -1 0 0 1 … 0

am1 + am2 …. + amn 0 0 -1 0 0 1

 

Zj

(Cj-Zj)

0 0 0 0 0 0 0 0 … 0

C1 C2 … Cn 0 0 0 M M … M

 

Step 3. Test for optimality

Calculate the elements of (Cj – Zj) row

 

(a)             If all (Cj – Zj) ≥ 0 then the basic feasible solution is optimal.

(b)             If anyone (Cj – Zj) ≥ 0 then pick up the largest negative number in this row. This is the key column and determines the variable entering the solution,

Now the second simplex table can be constructed.

Step 4. Test for feasibility

Determine the key row and key number (element) in the same manner as is done in the maximisation problem.

Example 3.5. A special diet for a patient in the hospital must have at least 8000 units of vitamins, 100 units of minerals and 2800 units of calories. Two types of foods X and Y are available in the market at the cost of Rs. 8 and Rs. 6 respectively. One unit of X contains 400 units of vitamins, 2 units of minerals and 80 units of calories. One unit of food B contains 200 units of vitamins, 4 units of minerals and 80 units of
calories. What combination of foods X and Y be used so that the minimum requirement of vitamins, minerals and calories is maintained and the cost incurred by the hospital is minimised? Use simplex method.

Sol. Mathematical model of the problem is as follows

Minimise Z = 8x1 + 6x2

Subject to the constraints

400x1 + 200x2 ≥ 8000 (Constraint of minimum vitamins)

2x1 + 4x2 ≥ 100 (Constraint of minimum minerals)

80x1 + 80x2 ≥ 2800 (Constraint of minimum calories)

x1, x2 ≥ 0 (Non-negativity constraint)

where x1 and x2 are the number of units of food X and food Y. Now the constraint inequalities can be converted into equations. Here, we take an initial solution with very high cost, as opposed to the maximisation problem where we had started with an initial solution with no profit. We subtract surplus variables S1, S2, and S3.

400x1 + 200x2 – S1 = 8000

2x1+4x2 -S2=100

80x1 + 80x2 – S3 = 2800

The surplus variables S1, S2 and S3 introduced in these equations represent the extra unit of vitamins, minerals and calories over 8000 units, 100 units and 2500 units in the least cost combination.

Let x1, x2 be zero in the initial solution.

Hence S1 = – 8OOO

S2 =- 100

S3 =-2500

This is not feasible as S1, S2 and S3 ≥  0 and cannot be negative. We have to see that S1, S2 and S3 do not appear (as they are – ve) in the initial solution. So if x1, x2 and S1, S2, S3 are all zero, new foods which can substitute food X and Y must be introduced. A1, A2 and A3 are the artificial variables to be introduced. Let the artificial variables (foods) be of are very large price, M per unit

400x1 + 200x2 – S1 + A1 = 8000

2xI+4x2-S2+A2 =100

80x1 + 80x2 – S3 + A3 = 2800

and Z objective function

Minimise Z = 8x1 + 6x2 + 0S1 + 0S2 + 0S3 + MA1 + MA2 + MA3

where x1, x2, S1, S2, S3 ,A1, A2, A3  0

Now, it is possible to set up initial solution by putting x1 = x2 = S1 = S2 = S3 = 0 in such a manner that = 8000, A2 = 100 and A3 = 2800.

Table 3.16

First simplex table

Cj

8

6

0

0

0

M

M

M

CB

B

Solution mix variables

B (=xB)

Solution values

x1

x2

S1

S2

S3

A1

A2

A3

Min ratio

M

A1

8000

400

200

-1

0

0

1

0

0

20

M

A2

100

2

4

0

-1

0

0

1

0

50

M

A3

2800

80

80

0

0

-1

0

0

1

35

Zj

482M

284M

-M

-M

-M

M

M

M

(Cj-Zj)

8-482M

6-284M

M

M

M

0

0

0

x1 is the key column entering the solution, A is the departing row and 400 (circled) in the table is the key number (element).

Now apply the row operations

Table 3.17 second simplex table

 

Cj

8

6

0

0

0

M

M

M

Minimum ratio

Ca

Solution mix variable (=B)

Solution values (b=XB)

x1

x2

S1

S2

S3

A1

A2

A3

8

x1

20

1

0

0

0

0

40

M

A2

60

0

3

-1

0

1

0

20

M

A3

1200

0

40

0

-1

0

1

30

Zj

8

4+43

M

-4+41

M/200

-M

-M

M

M

(Cj-Zj)

0

2-43 M

4-41 M/200

M

M

0

0

 

Value of Z calculated as follows

Zj (S2) =- M

Zj (S3) =- M

Zj (A2) = M

Zj(A3) = M

It is clear from the above table, that x2 enters the solution and A2 deports, using the following row operations, we introduce x2 and remove A1.

Table 3.18 Third simplex table

 

Cj

8

6

0

0

0

M

M

M

Minimum ratio

CB

Solution Mix variable (=B)

Solution values b(=xB)

x1

x2

S1

S2

S3

A1

A2

A3

8

x1

10

1

0

0

-

-

0

60

6

x2

20

0

1

0

-

-

0

-60

M

A3

400

0

0

-1

-

-

1

30

Zj

8

6

-M

-

-

M

(Cj-Zj)

0

0

M

-

-

0

 

It can be seen S2 has to be introduced and A3 has to depart. This procedure can be adopted for further improving the solution by constructing fourth simplex table and so on.