USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

MINIMISING CASE – CONSTRAINTS OF MIXED TYPE ( AND )

MINIMISING CASE – CONSTRAINTS OF MIXED TYPE ( AND ≥ )

We have seen the examples earlier where the constraints were either ≥ type or ≤ type. Both there are problems where the constraint equation could contain both types of constraints. This type of problem is illustrated with the help of an example.

Example 3.6. A metal alloy used in manufacture of rifles uses two ingradients A and B. A total of 120 units of alloy is used for production. Not more than 60 units of A can be used and at least 40 units of ingradient B must be used in the alloy. ingradient A costs Rs. 4 per unit and ingradient B costs Rs. 6 per unit. The company manufacturing rifles is keen to minimise its costs. Determine how much of A and B
should be used.

Sol. Mathematical formulation of the problem is

Minimise cost Z = 4x1 + 6x2

Subject to constraints

Subject to constraints

x1 + x2 = 120                        (Total units of alloy)

x1≤  60                       (Ingradient A constraint)

x2 ≥ 40                       (Ingradient B constraint)

x1, x2 ≥ 0                    (Non-negativity constraint)

where x1 and x2 number of units of ingradient A and B respectively. Let x1 and x2 = 0 and let us introduce an artificial variable which represents a new ingradient with very high cost M.

x1+ x2+A1 =120

Also x1 + S1= 60

Third constraint x2 – S2 + A2 = 40

Now the standard form of the problem is

Minimise Z = 4x1 + 6x2 + MA1 + 0S1 + 0S2 + MA2

Subject to the constraints

x1 + x2 + A1 = 120

x1 + S1 = 60

x2 – S2 + A2 = 40

x1,x2, S1, S2, A1, A2 ≥ 0

Initial basic solution is obtained by putting x1 = x2 = 0 and S1 = S2 = 0 so that A1 = 100, S1 = 60, A2 = 40.

Table 3.19 First simplex table

 

Cj

4

6

M

0

0

M

Minimum ratio

CB

Solution mix

Solution values

x1

x2

A1

S1

S2

A2

M

0

M

A1

S1

A2

120

60

40

1

1

0

1

0

1

1

0

0

0

1

0

0

0

-1

0

0

0

120

40

Zf

M

2M

M

0

-M

M

(Cj-Zj)

4-M

6-2M

0

0

M

0

 

6 – 2M is the largest negative number hence, x2 will enter the solution and since 40 is the minimum ratio A2 will depart.

R – 3 (New) → R – 3 (old) as key element is 1

R-1 (New) → R-1 (old) – R- 3 (New)

Table 3.20 Second simplex table

Cj

4

6

M

0

0

M

Minimum ratio

Ca

Solution mix

Solution values

x1

x2

A1

S1

S2

A2

M

0

6

A1

S1

x2

80

60

40

1

1

0

0

0

1

1

0

0

0

1

0

1

0

-1

80

60

Zj

M

6

M

0

M-6

(Cj-Zj)

4-M

0

0

0

-M+6

 

R-1 (new) = 1-0= 1; 1-1 =0, 1-0= 1,0-0=0,0-(-1)= 1

i.e., 0, 1, 1,0, 1, 100-40=60

x1 will be introduced and S1 will depart.

Use the following row operations

(i)                           R – 2 (new) → R2 (old)

(ii)                        R – 1 (new) → R1 (old) – R2 (new)

R- 2 (new) = 1, 0, 0, 1, 0

R-1(new)=1-1=0, 0-0=0,1-0=1,0-1=-1,1-0=1

i.e. 0, 0, 1, -1, 1

Table 3.21 Third simplex table

Cj

4

6

M

0

0

M

Minimum ratio

CB

Solution mix

Solution values

x1

x2

A1

S1

S2

A2

M

4

6

A1

x1

x2

40

60

40

0

1

0

0

0

1

1

0

0

-1

0

0

1

0

-1

40

40

Zj

4

6

M

-M+4

M-6

(Cj-Zj)

0

0

0

M-4

-M+6

 

We now introduce S2 and take out A1 using following row operations

R-1 (new) → R-1 (old)

R- 3 (new) → R- 3 (old) + R-1 (new)

Table 3.22 Fourth simplex table

Cj

4

6

M

0

0

M

CB

Solution mix

Solution values

x1

x2

A1

S1

S2

A2

0

4

6

S2

x1

x2

40

60

80

0

1

0

0

0

1

-1

1

-1

1

0

0

Zj

4

6

-2

0

(Cj-Zj)

0

0

2

0

 

Since all the numbers in (Cj – Zj) are either zero or positive, this is the optimal solution.

x1 = 60, x2 = 80 and Z = 40 × 60 + 6 × 80 = Rs. 720

Maximisation case-constraints of mixed type

A problem involving mixed type of constraints in which =, ≥  and ≤  are involved and the objective function is to be maximised. 

Example 3.7. Maximise Z = 2x1 + 4x2 – 3x3

Subject to the constraints

x1+ x2 + x3 ≥ 8

x1– x2 ≥ 1

3 x1 + 4 x2 + x3 ≤ 40

Sol. The problem can be formulated in the standard form

Maximise Z = 2x1 + 4x2 – 3x3 + 0S1 + 0S2 – MA1 – MA2

Subject to constraints

x1 + x2 + x3 + A1 =8

x1X2-S1+A2=1

3x1 + 4 x2 + x3 + S2 = 40

x1 ≥ 0, x2 ≥ 0, S1 ≥ 0, S2 ≥ 0, A1 ≥ 0; A2 ≥ 0

where A1 and A2 are the artificial constraints, S1 is the surplus variable, S2 is the slack variable and M is a very large quantity.

For initial basic solution

A1=8, A2=1, S2=40

Table 3.23. First simplex table

Cj 2 4 -3 0 0 -M -M Minimum ratio
CB Solution mix variables (B) Solution values b(=xB) x1 x2 x3 S1 S2 A1 A2

-M

M

0

A1

A2

C2

8

1

40

1

1

3

1

-1

4

1

0

1

0

-1

0

0

0

1

1

0

0

0

1

0

8

1

Zj

-2M

0

-M

M

0

-M

-M

(Cj-Zj)

2-2M

4

-3+M

-M

0

0

0

 

This is a problem of maximisation, hence we select 2 + 2M, the largest positive number in (Cj _ Zj) x1 will enter and A2 will depart. Use the following row operations.

R – 2 (New) → R – 2 (old)

R – 1 (New) → R – 1 (old) – R2 (new)

R – 3 (New) → R – 3 (old) – 3 R2 (new)

Table 3.24. Second simplex table

CB

Solution mix variables (B)

Cj

2

4

-3

0

0

-M

-M

Minimum ratio

Solution values b(=xB)

x1

x2

x3

S1

S2

A1

A2

-M

2

0

A1

x1

S2

7

1

37

0

1

0

2

-1

7

1

0

0

1

-1

3

0

0

1

-1

1

-3

-1

Zj

2

-2M-2

-M

-M-2

0

M+2

(Cj-Zj)

0

6+2M

-3+M

M+2

0

-2

 

R -2 (new) = R – 2(old)

R-1 (new)=R-1 (old)-R-2(new)

R-3 (new)=40-3 × 1=37, 3-3×1=0, 4-3×-1=7

0-3 × 0 = 0, 0 – 3 ×-I = 3, 1 – 3 × 0 = 1, 0 – 3 × 1 = – 3

Now x2 will enter as new variable and AI will depart. as shown. Third simplex table can be prepared using the following row operations.

Table 3.25 Third simplex table

Cj

2

4

-3

0

0

-M

-M

CB

Solution Mix variables (B)

Solution values b(=xB)

x1

x2

x3

S1

S2

A1

A2

4

2

0

x2

x1

S2

0

1

0

1

0

0

0

0

1

Zj

2

4

3

1

0

(Cj-Zj)

0

0

-6

-1

0

 

Since all the entries in Cj – Zj are either 0 or negative, optimal solution has been obtained with

and Z=2x1+4x2-3x3+0S1+0S2

=9+14-0+0+0= Rs. 23.

Example 3.8. A fertiliser manufacturing company produces three basic types of fertilisers A, B and C. It uses nitrate, phosphate and potash for this purpose. The following data is provided.

Ingredients

% in type A

% in type B

% in type C

Cost/ton (Rs.)

Availability (tons)

Nitrate

5

10

15

10,000

1200

Phosphate

15

15

10

4000

1600

Potash

10

10

10

6000

1400

Inert

The selling price of three fertilisers/ton is Rs. 3000, Rs. 4000 and Rs. 5000. The company must produce at least 6000 tons of type A fertiliser. The company wants to maximise its profits. Advise the company how much quantity of three fertilisers should they produce.

Sol. Let x1, x2 and x3 be the quantity of fertilisers A, B and C respectively the company should produce.

The data can be put in the form of following table.

Table 3.26

Fertilisers

Ingredients (%)

Selling price/ton (Rs.)

 

Nitrate

Phosphate

Potash

Inert

 

A

5

15

10

70

3000

B

10

15

10

65

4000

C

15

10

10

65

5000

Cost per ton (Rs.)

10,000

4000

6000

500

Availability (tons)

1200

1600

1400

 

Cost of A = 5% of 10,000 + 15% of 4,000 +10% × 6000 + 70% × 500

= 500 + 600 + 600 + 350 = 2050

Cost of B = 1000 + 600 + 600 + 325 = 1625

Cost of C = 1500 + 400 + 600 + 325 = 2825

Problem can be put in the mathematical formula

Maximise Z = (selling price – cost price) x1 + (SP – CP) x2 + (SP – CP) x3

=950 x1 +2375 x2+2175 x3

 

By introducing slack, surplus and artificial variables in the inequalities of the constraints, the LP problem in standard form becomes

Maximise Z = 95.0 x1 + 2375 x2 + 2175 x3 + 0S1 + 0S2 + 0S3 + 0S4 – MA1

Subject to the constraints

5 x1 + 10 x2 + 15 x3 + S1 = 1,20,000

15 x1 + 15 x2 + 10 x3 + S2 = 1,60,000

10 x1 + 10 x2 + 10 x3 + S3 = 1,40,000

x1 – S4 + A1 =6000

and x1, x2, S1, S2, S3, S4, A0 ≥ 0

 

An initial basic feasible solution is obtained by setting x1 = x2 = x3 = S4 = 0 so that S1 = 1,20,000, S2 =1,60,000, S3 = 20,000, A1 = 6000 and maximum Z = – 6000 M

Now the first simplex table can be written

Table 3.27 First simplex table

Cj

950

2375

2175

0

0

0

0

-M

Minium ratio

CB

Solution mix variables (B)

Solution values b(=xB)

x1

x2

x3

S1

S2

S3

S4

A1

0

S1

1,20,000

5

10

15

1

0

0

0

0

24,000

0

S2

1,60,000

15

15

10

0

1

0

0

0

10,667

0

S3

1,40,000

10

10

10

0

0

1

0

0

14,000

-M

A1

600

1

0

0

0

0

0

-1

1

6000

Zj

-M

0

0

0

0

0

-1

1

6000

(Cj-Zj)

950+M

2375

2175

0

0

0

-M

0

 

950 + M is the largest positive value in Cj – Zj row and 6000 is the minimum ratio so x1 is the entering variable and AI is the departing variable and 1 is the key number (circled in the table).

Following elementary operations are applied to prepare the second simplex table.

(i)                           R – 4 (new) → R – 4 (old)

(ii)                        R-1(new) →R-1(old)- 5 R-4(new)

(iii)                      R-2(new) → R-2(0ld)-15 R-4(new)

(iv)                      R – 3 (new) → R – 3 (old) – 1.0 R – 4 (new)

R – 1 (new) = 1,20,000 – 5 × 6000 = 90,000

5-5×5=0,

10-5×0=10,

15-5×0=15,

1-5 × 0= 1,

0-5 × 0=0,

0.5 × 0=0,

0-5 × -1 =5,

i.e., 90,000, 0, 10, 15, 1, 0, 0, 5

R – 2 (new) = 1,60,000 × 15 × 6000 = 70,000

15-15×1=0

15-15×0=15

10-15×0=10,

0-15×0=0

1 – 15 × 0 = 1,

0 – 15 × 0 = 0,

0 – 15 × 0 = 0,

0 – 15 ×-1 = 15

i.e., 70,000, 0, 15, 10, 0, 1, 0, 0, 15

R – 3 (new) = 1,40,000 – 10 × 6000 = 80,000

10 – 10 × 1 = 0,

10 – 10 × 0 = 10,

10, 0, 0, 1- 10 × 0 = 1,

0-10 × -1 = 10

i.e., 80,000, 0, 10, 10, 0, 0, 1, 10

Table 3.28. Second simplex table

Cj

950

2375

2175

0

0

0

0

-M

Minimum ratio

CB

Basic variables (B)

Solution Values b(=xB)

x1

x2

x3

S1

S2

S3

S4

A1

0

S1

90,000

0

10

15

1

0

0

5

9000

0

S2

70,000

0

15

10

0

1

0

15

4666

0

S3

80,000

0

10

0

0

0

1

10

8000

950

x1

6000

1

0

0

0

0

0

-1

6000

Zj

950

0

0

0

0

0

-950

(Cj-Zj)

0

2375

2175

0

0

0

950

 

Since 2375 is the largest positive number in (Cj – Zj) row and 4666 is the minimum ratio, enter variable x2 and replace S2. Following row operations will be applied for writing the third simplex table.

Table 3.29. Third simplex table

Cj

950

2375

2175

0

0

0

0

-M

Minimum ratio

CB

Basic variables (B)

Solution values b(xB)

x1

x2

x3

S1

S2

S3

S41

A1

0

S1

43,334

0

0

1

0

-5

5200

75

x2

46,666

0

1

0

0

1

69,999

0

S3

33,340

0

0

0

1

0

950

x1

6,000

1

0

0

0

0

0

-1

Zj

950

2375

0

0

1425

(Cj-Zj)

0

0

0

0

-1425

Table 3.30 Fourth simplex table

Cj

950

2375

2175

0

0

0

0

-M

Minimum ratio

CB

Basic variables (B)

Solution Values b(=xB)

x1

x2

x3

S1

S2

S3

S4

A1

2175

x3

5200

0

0

1

0

-ve

2375

x2

43199

0

1

0

0

103202

0

S3

6807

0

0

0

1

-4

-ve

950

x1

6000

1

0

0

0

0

0

-1

-ve

Zj

950

2375

2175

0

-1305

(Cj-Zj)

0

0

0

0

1305

 

The solution cannot be improved further and optimal solution is to produce 6000 tons of x1, 43199 of x1 and 5200 of x3.

Sol. Introducing slack variables, the problem becomes

Z = 3 x1 + 5 x2 + 4 x3 + 0S1 + 0S2 + 0S3

Three slack variables have been introduced

Subject to

2x1 + 3 x2 + 0 x3 + S1 + 0S2 + 0S3 = 8

0 x1 + 2 x2 + 5 x3 + 0S1 + S2 + 0S3 = 10

3 x1 + 2 x2 + 4 x3 + 0S1 + 0S2 + S3 = 15

Drawing the first simplex table

Table 3.31 First simplex table

Cj

3

5

4

0

0

0

Minimum ratio

CB

Basic variables

Solution values

x1

x2

x3

S1

S2

S3

0

S1

8

2

3

0

1

0

0

2.6

0

S2

10

0

2

5

0

1

0

5

0

S3

15

3

2

4

0

0

1

7.5

Zj

0

0

0

0

0

0

0

(Cj-Zj)

3

5

4

0

0

0

 

Since 5 is the maximum + ve value of (Cj – Zj) in the maximising problem. 5 is the key column and S1 row has the minimum value, S1 will be replaced by x2.

Now we can write the second simplex table as follows.

Table 3.32 Second simplex table

Cj→

3

5

4

0

0

0

Minimum ratio

Basic variables

Solution values

x1

x2

x3

S1

S2

S3

5

X2

1

0

0

0

0

S2

0

5

1

0

0

S3

0

4

0

1

Zj

5

0

0

0

(Cj-Zj)

0

4

0

0

 

Since 4 is the maximum + ve value, x3 is the key column. Minimum ratio is obtained by dividing each element of the three rows by their respective elements in the key column i.e., by 0, 5 and 4. Since minimum ratio is for S1 it will be replaced by X3. New x3 row is obtained by dividing it by key element i.e., 5.

Now the third simplex table can be written as

Table 3.33 Third simplex table

Cj→

3

5

4

0

0

0

Minimum ratio

Basic variables

Solution values

x1

x2

x3

S1

S2

S3

5

X2

1

0

0

0

0

X3

0

1

0

0

S3

0

0

1

Zj

5

4

0

(Cj-Zj)

0

4

0

 

Sol. Since the problem is of minimisation nature, artificial variables are also introduced

Z = 5y1 + 6 y2 + 0S1 + OS2 + MA1 + MA2

Subject to

2y1 + 5y2 – S1 + 0S2 + A1 + 0A1 = 15

3y1 + y2+ 0S1– S2 + 0A1 + 0A2 = 12

y1, y2, S1, S2, A1, A2 ≥ 0

using these the first Simplex table can be written as follows.

Now the third simplex table can be written as

Table 3.35 First simplex table

Cj

5

6

0

0

M

M

Minimum ratio

C

Basic variables

Solution values

y1

y2

S1

S2

A1

A2

M

A1

15

2

5

-1

0

1

0

3

M

A2

12

3

1

0

-1

0

1

12

Zj

27M

5M

6M

-M

M

M

M

(Cj-Zj)

5-5M

6-6M

M

M

0

0

 

Since M is a very large quantity and the problem is of minimisation, most negative value will be taken as key formula y2 will replace A1 row and key element is 5.

Example 3.11. A firm has an advertising budget of Rs. 7,20,000. It wishes to allocate this budget to two medias, magazine or TV so that total exposure is maximised. Each page of magazine advertising is estimated to result in 60,000 exposures whereas each spot on TV is estimated to result in 1,20,000 exposures. Each page of magazine advertising costs Rs. 900 and each spot on TV costs Rs.12,000. An additional condition that the firm has specified is that at least two pages of magazines advertising be used and at least 3 spots on TV. Determine the optimal media mix for this firm.

Sol. Let x1 = Number of pages of magazine

x2 = Number of spots on TV

Maximise Z = 60,000 x1 + 1,20,000 x2

9000 x1 + 12000 x2 ≤ 7,20,000

3x1 + 4x2 ≤ 240

x1 ≥ 2

x2 ≥ 3

x1, x2 ≥ 0

Introducing slack and artificial variables, we have

Maximize Z = 6000 x1 + 1,20,000 x2 + 0S1 + 0S2 – MA1 – MA2

3x1 +4x2 + S1 =240

x1-S2+A1 =2

x2 – S3 + A2 = 3

x1, x2, S1, S2, A1, A2 ≥ 0

Now the first Simplex table can be constructed as follows.

Table 3.38 First simplex table

Cj

60,000

12,20,000

0

0

0

-M

-M

Minimum

Basic variables

Solution values

x1

x2

S1

S2

S3

A1

A2

Ratio

0

S1

240

3

4

1

0

0

0

0

60

-M

A1

2

1

0

0

-1

0

1

0

-M

A2

3

0

1

0

0

-1

0

1

3

Zj

-5M

-M

-M

0

M

M

-M

-M

(Cj-Zj)

60,000+ M

1,20,000+ M

0

-M

-M

0

0

 

Since x2 column has the largest +ve value and minimum ratio is that of A – 2 row and (1) is the key element.

x2 will replace row A2.

New elements of row A2 are obtained by dividing by the key element i.e., 1

i.e., 3, 0, 1, 0, 0, – 1, 0, 1

New row – 1 is obtained by the relationship already known

i.e. 240-4×3=228,

3-4×0=3,

4-4x1=0,

1-4×0=1,

0-4×0=0

0-4×-1= 0,

0-4×0=0.

New row 2 will remain the same as old row 2 as 0 is to be multiplied with new elements of row 3.

Now the second simplex table can be constructed as follows.

Since 60,000 + M is the largest value of Cj – Zj, x1 is the key column and since minimum ratio is that of A1, row A1 will be replaced by column x1. New row A1 is obtained by dividing all the elements of the row by key element i.e. 1.

New row S1 is obtained by the relationship already known.

228 – 3 × 2 = 222,

3 – 3 × 1=0,

0 – 3 × 0 = 0,

1-3 × 0 = 1,

0 – 3 × – 1 = 3

4-3×0=4

New row x2 elements are as follows.

3 – 0 × elements of departing row, so all elements remain the same.

Third simplex table can be constructed as follows.

Table 3.40 Third simplex table

Cj

60,000

1,20,000

0

0

0

Minimum Ratio

Basic variables

Solution values

x1

x2

S1

S2

S3

0

S1

222

0

0

1

3

4

55.5

60,000

x1

2

1

0

0

-1

0

1,20,000

x2

3

0

1

0

0

-1

-ve

Zj

4,80,000

60,000

1,20,000

0

-60,000

-1,20,000

(Cj-Zj)

0

0

0

60,000

1,20,000

 

S3 has the largest +ve value and S1 has the minimum ratio so S1 will be replaced by S3. Key element is 4.

New row S1 is obtained by dividing all its elements by key element i.e., 4, 55· 5, 0, 0, ¼, ¾, 1.

New row x1 element will be the same as for this row 0 occurs in the key column.

Now row x2 is obtained by using the relationship already known.

Table 3.41 Fourth simplex table

Cj

60,000

1,20,000

0

0

0

S3

55.5

0

0

1

60,000

x1

2

1

0

0

-1

0

1,20,000

x2

58.5

0

1

0

Zj

71.40,000

60,000

1,20,000

30,000

30,000

0

(Cj-Zj)

0

0

-30,000

-30,000

0

 

Since all the elements of Cj – Zj are ≤ 0

The optimal solution has been arrived

x1 =2

x2=58.5

Z = 71,40,000

Sol.

Phase 1 It consists of the following steps.

Step I. Adding slack variables, the problem becomes

2x1 + x2 + S1 = 1

x1 + 4x2 – S2 = 6

Step II. Putting x1 = 0 and x2 = 0

S1 = 1

S2 =- 6.

This gives the initial basic solution. However, it is not a basic feasible solution since S2 is – ve.

So, we will introduce artificial variable AI and the above constraint can be written as

2x1 + x2 + S1 = 1                                         … (i)

x1 +4x2-S2 + A1 = 6                                          … (ii)

Step III. Substituting x1 = x2 = S2 = 0 in the constraint equation we get S1 = 1 and A1 = 6 as the initial basic solution. This can be put in the form of a simplex table as follows.

As (Cj _ Zj) is -ve under some columns, the current basic feasible solution can be improved.

S1 will be replaced by x2 as x2 is the key column, and S1 is the key row, also CD is the key element.

New row x2 (old S1) will be obtained by dividing all the elements by 1.

New row A1 can be obtained by using the relationship already known.

6 – 4 × 1 = 2,

1 – 4 × 2 = – 7,

4 – 4 × 1 = 0,

0 – 4 × 1 = – 4

-1-4×0=-1,

1-4×0=1

New simplex table can be constructed as follows.

Table 3.45

Cj

0

0

0

0

1

Basic variables

Solution variables

x1

x2

S1

S2

A1

0

x2

1

2

1

1

0

0

1

A1

2

-7

0

-4

-1

1

Zj

2

-7

0

-4

-1

1

(Cj-Zj)

7

0

4

1

0

 

Since all the elements are either +ve or zero, an optimal basic solution has been arrived.

However A1 = 2 which is > 0, the given LPP does not possess any feasible solution and the procedure stops.