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 = 4x_{1} + 6x_{2}
Subject to constraints
Subject to constraints
x_{1} + x_{2} = 120 (Total units of alloy)
x_{1≤} 60 (Ingradient A constraint)
x_{2} ≥ 40 (Ingradient B constraint)
x_{1}, x_{2} ≥ 0 (Nonnegativity constraint)
where x_{1} and x_{2} number of units of ingradient A and B respectively. Let x_{1} and x_{2} = 0 and let us introduce an artificial variable which represents a new ingradient with very high cost M.
x_{1}+ x_{2}+A_{1} =120
Also x_{1 }+ S_{1}= 60
Third constraint x_{2} – S_{2} + A_{2} = 40
Now the standard form of the problem is
Minimise Z = 4x_{1} + 6x_{2} + MA_{1} + 0S_{1} + 0S_{2} + MA_{2}
Subject to the constraints
x_{1} + x_{2} + A_{1} = 120
x_{1} + S_{1} = 60
x_{2} – S_{2} + A_{2} = 40
x_{1},x_{2}, S_{1}, S_{2}, A_{1}, A_{2} ≥ 0
Initial basic solution is obtained by putting x_{1} = x_{2} = 0 and S_{1} = S_{2} = 0 so that A_{1} = 100, S_{1} = 60, A_{2} = 40.
Table 3.19 First simplex table

C_{j} 
4 
6 
M 
0 
0 
M 
Minimum ratio 

C_{B} 
Solution mix 
Solution values 
x_{1} 
x_{2} 
A_{1} 
S_{1} 
S_{2} 
A_{2} 

M 0 M 
A_{1} S_{1} A_{2} 
120 60 40 
1 1 0 
1 0 1 
1 0 0 
0 1 0 
0 0 1 
0 0 0 
120 – 40 
Z_{f} 
M 
2M 
M 
0 
M 
M 

(C_{j}Z_{j}) 
4M 
62M 
0 
0 
M 
0 
6 – 2M is the largest negative number hence, x_{2} will enter the solution and since 40 is the minimum ratio A_{2} will depart.
R – 3 (New) → R – 3 (old) as key element is 1
R1 (New) → R1 (old) – R 3 (New)
Table 3.20 Second simplex table
C_{j} 
4 
6 
M 
0 
0 
M 
Minimum ratio 

C_{a} 
Solution mix 
Solution values 
x_{1} 
x_{2} 
A_{1} 
S_{1} 
S_{2} 
A_{2} 

M 0 6 
A_{1} S_{1} x_{2} 
80 60 40 
1 1 0 
0 0 1 
1 0 0 
0 1 0 
1 0 1 
80 60 – 

Z_{j} 
M 
6 
M 
0 
M6 

(C_{j}Z_{j}) 
4M 
0 
0 
0 
M+6 
R1 (new) = 10= 1; 11 =0, 10= 1,00=0,0(1)= 1
i.e., 0, 1, 1,0, 1, 10040=60
x_{1} will be introduced and S_{1} will depart.
Use the following row operations
(i) R – 2 (new) → R_{2} (old)
(ii) R – 1 (new) → R_{1} (old) – R_{2} (new)
R 2 (new) = 1, 0, 0, 1, 0
R1(new)=11=0, 00=0,10=1,01=1,10=1
i.e. 0, 0, 1, 1, 1
Table 3.21 Third simplex table
C_{j} 
4 
6 
M 
0 
0 
M 
Minimum ratio 

C_{B} 
Solution mix 
Solution values 
x_{1} 
x_{2} 
A_{1} 
S_{1} 
S_{2} 
A_{2} 

M 4 6 
A_{1} x_{1} x_{2} 
40 60 40 
0 1 0 
0 0 1 
1 0 0 
1 0 0 
1 0 1 
40 – 40 

Z_{j} 
4 
6 
M 
M+4 
M6 

(C_{j}Z_{j}) 
0 
0 
0 
M4 
M+6 
We now introduce S_{2} and take out A_{1} using following row operations
R1 (new) → R1 (old)
R 3 (new) → R 3 (old) + R1 (new)
Table 3.22 Fourth simplex table
C_{j} 
4 
6 
M 
0 
0 
M 

C_{B} 
Solution mix 
Solution values 
x_{1} 
x_{2} 
A_{1} 
S_{1} 
S_{2} 
A_{2} 
0 4 6 
S_{2} x_{1} x_{2} 
40 60 80 
0 1 0 
0 0 1 
1 1 1 
1 0 0 

Z_{j} 
4 
6 
– 
2 
0 

(C_{j}Z_{j}) 
0 
0 
– 
2 
0 
Since all the numbers in (C_{j} – Z_{j}) are either zero or positive, this is the optimal solution.
x_{1} = 60, x_{2} = 80 and Z = 40 × 60 + 6 × 80 = Rs. 720
Maximisation caseconstraints 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 = 2x_{1} + 4x_{2} – 3x_{3}
Subject to the constraints
x_{1}+ x_{2} + x_{3} ≥ 8
x_{1}– x_{2} ≥ 1
3 x_{1} + 4 x_{2} + x_{3} ≤ 40
Sol. The problem can be formulated in the standard form
Maximise Z = 2x_{1} + 4x_{2} – 3x_{3} + 0S_{1} + 0S_{2} – MA_{1} – MA_{2}
Subject to constraints
x_{1} + x_{2} + x_{3} + A_{1} =8
x_{1}–_{X2}S_{1}+A_{2}=1
3x_{1} + 4 x_{2} + x_{3} + S_{2} = 40
x_{1} ≥ 0, x_{2} ≥ 0, S_{1} ≥ 0, S_{2} ≥ 0, A_{1} ≥ 0; A_{2} ≥ 0
where A_{1} and A_{2} are the artificial constraints, S_{1} is the surplus variable, S_{2} is the slack variable and M is a very large quantity.
For initial basic solution
A_{1}=8, A_{2}=1, S_{2}=40
Table 3.23. First simplex table
C_{j}  2  4  3  0  0  M  M  Minimum ratio  
C_{B}  Solution mix variables (B)  Solution values b(=x_{B})  x_{1}  x_{2}  x_{3}  S_{1}  S_{2}  A_{1}  A_{2}  
M M 0 
A_{1} A_{2} C_{2} 
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

Z_{j} 
2M 
0 
M 
M 
0 
M 
M 

(C_{j}Z_{j}) 
22M 
4 
3+M 
M 
0 
0 
0 
This is a problem of maximisation, hence we select 2 + 2M, the largest positive number in (C_{j} _ Z_{j}) x_{1} will enter and A2 will depart. Use the following row operations.
R – 2 (New) → R – 2 (old)
R – 1 (New) → R – 1 (old) – R_{2} (new)
R – 3 (New) → R – 3 (old) – 3 R_{2} (new)
Table 3.24. Second simplex table
C_{B} 
Solution mix variables (B) 
C_{j} 
2 
4 
3 
0 
0 
M 
M 
Minimum ratio 
Solution values b(=x_{B}) 
x_{1} 
x_{2} 
x_{3} 
S_{1} 
S_{2} 
A_{1} 
A_{2} 

M 2 0 
A_{1} x_{1} S_{2} 
7 1 37 
0 1 0 
2 1 7 
1 0 0 
1 1 3 
0 0 1 
1 1 3 
1 

Z_{j} 
2 
2M2 
M 
M2 
0 
M+2 

(C_{j}Z_{j}) 
0 
6+2M 
3+M 
M+2 
0 
2 
R 2 (new) = R – 2(old)
R1 (new)=R1 (old)R2(new)
R3 (new)=403 × 1=37, 33×1=0, 43×1=7
03 × 0 = 0, 0 – 3 ×I = 3, 1 – 3 × 0 = 1, 0 – 3 × 1 = – 3
Now x_{2} 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
C_{j} 
2 
4 
3 
0 
0 
M 
M 

C_{B} 
Solution Mix variables (B) 
Solution values b(=x_{B}) 
x_{1} 
x_{2} 
x_{3} 
S_{1} 
S_{2} 
A_{1} 
A_{2} 
4 2 0 
x_{2} x_{1} S_{2} 
0 1 0 
1 0 0 
0 0 1 

Z_{j} 
2 
4 
3 
1 
0 

(C_{j}Z_{j}) 
0 
0 
6 
1 
0 
Since all the entries in C_{j} – Z_{j} are either 0 or negative, optimal solution has been obtained with
and Z=2x_{1}+4x_{2}3x_{3}+0S_{1}+0S_{2}
=9+140+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 x_{1}, x_{2} and x_{3} 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) x_{1} + (SP – CP) x_{2} + (SP – CP) x_{3}
=950 x_{1} +2375 x_{2}+2175 x_{3}
By introducing slack, surplus and artificial variables in the inequalities of the constraints, the LP problem in standard form becomes
Maximise Z = 95.0 x_{1} + 2375 x_{2} + 2175 x_{3} + 0S_{1} + 0S_{2} + 0S_{3} + 0S_{4} – MA_{1}
Subject to the constraints
5 x_{1} + 10 x_{2} + 15 x_{3} + S_{1} = 1,20,000
15 x_{1} + 15 x_{2} + 10 x_{3} + S_{2} = 1,60,000
10 x_{1} + 10 x_{2} + 10 x_{3} + S_{3} = 1,40,000
x_{1} – S_{4} + A_{1} =6000
and x_{1}, x_{2}, S_{1}, S_{2}, S_{3}, S_{4}, A_{0} ≥ 0
An initial basic feasible solution is obtained by setting x_{1} = x_{2} = x_{3} = S_{4} = 0 so that S_{1} = 1,20,000, S_{2} =1,60,000, S_{3} = 20,000, A_{1} = 6000 and maximum Z = – 6000 M
Now the first simplex table can be written
Table 3.27 First simplex table
C_{j} 
950 
2375 
2175 
0 
0 
0 
0 
M 
Minium ratio 

C_{B} 
Solution mix variables (B) 
Solution values b(=x_{B}) 
x_{1} 
x_{2} 
x_{3} 
S_{1} 
S_{2} 
S_{3} 
S_{4} 
A_{1} 

0 
S_{1} 
1,20,000 
5 
10 
15 
1 
0 
0 
0 
0 
24,000 
0 
S_{2} 
1,60,000 
15 
15 
10 
0 
1 
0 
0 
0 
10,667 
0 
S_{3} 
1,40,000 
10 
10 
10 
0 
0 
1 
0 
0 
14,000 
M 
A_{1} 
600 
1 
0 
0 
0 
0 
0 
1 
1 
6000 
Z_{j} 
M 
0 
0 
0 
0 
0 
1 
1 
6000 

(C_{j}Z_{j}) 
950+M 
2375 
2175 
0 
0 
0 
M 
0 
950 + M is the largest positive value in C_{j} – Z_{j} row and 6000 is the minimum ratio so x_{1} 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) R1(new) →R1(old) 5 R4(new)
(iii) R2(new) → R2(0ld)15 R4(new)
(iv) R – 3 (new) → R – 3 (old) – 1.0 R – 4 (new)
R – 1 (new) = 1,20,000 – 5 × 6000 = 90,000
55×5=0,
105×0=10,
155×0=15,
15 × 0= 1,
05 × 0=0,
0.5 × 0=0,
05 × 1 =5,
i.e., 90,000, 0, 10, 15, 1, 0, 0, 5
R – 2 (new) = 1,60,000 × 15 × 6000 = 70,000
1515×1=0
1515×0=15
1015×0=10,
015×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,
010 × 1 = 10
i.e., 80,000, 0, 10, 10, 0, 0, 1, 10
Table 3.28. Second simplex table
C_{j} 
950 
2375 
2175 
0 
0 
0 
0 
M 
Minimum ratio 

C_{B} 
Basic variables (B) 
Solution Values b(=x_{B}) 
x_{1} 
x_{2} 
x_{3} 
S_{1} 
S_{2} 
S_{3} 
S_{4} 
A_{1} 

0 
S_{1} 
90,000 
0 
10 
15 
1 
0 
0 
5 
9000 

0 
S_{2} 
70,000 
0 
15 
10 
0 
1 
0 
15 
4666 

0 
S_{3} 
80,000 
0 
10 
0 
0 
0 
1 
10 
8000 

950 
x_{1} 
6000 
1 
0 
0 
0 
0 
0 
1 
6000 

Z_{j} 
950 
0 
0 
0 
0 
0 
950 

(C_{j}Z_{j}) 
0 
2375 
2175 
0 
0 
0 
950 
Since 2375 is the largest positive number in (C_{j} – Z_{j}) row and 4666 is the minimum ratio, enter variable x_{2} and replace S_{2}. Following row operations will be applied for writing the third simplex table.
Table 3.29. Third simplex table
C_{j} 
950 
2375 
2175 
0 
0 
0 
0 
M 
Minimum ratio 

C_{B} 
Basic variables (B) 
Solution values b(x_{B}) 
x_{1} 
x_{2} 
x_{3} 
S_{1} 
S_{2} 
S_{3} 
S4_{1} 
A_{1} 

0 
S_{1} 
43,334 
0 
0 
1 
0 
5 
5200 

75 
x_{2} 
46,666 
0 
1 
0 
0 
1 
69,999 

0 
S_{3} 
33,340 
0 
0 
0 
1 
0 
– 

950 
x_{1} 
6,000 
1 
0 
0 
0 
0 
0 
1 
– 

Z_{j} 
950 
2375 
0 
0 
1425 

(C_{j}Z_{j}) 
0 
0 
0 
0 
1425 
Table 3.30 Fourth simplex table
C_{j} 
950 
2375 
2175 
0 
0 
0 
0 
M 
Minimum ratio 

C_{B} 
Basic variables (B) 
Solution Values b(=x_{B}) 
x_{1} 
x_{2} 
x_{3} 
S_{1} 
S_{2} 
S_{3} 
S_{4} 
A_{1} 

2175 
x_{3} 
5200 
0 
0 
1 
0 
ve 

2375 
x_{2} 
43199 
0 
1 
0 
0 
103202 

0 
S_{3} 
6807 
0 
0 
0 
1 
4 
ve 

950 
x_{1} 
6000 
1 
0 
0 
0 
0 
0 
1 
ve 

Z_{j} 
950 
2375 
2175 
0 
1305 

(C_{j}Z_{j}) 
0 
0 
0 
0 
1305 
The solution cannot be improved further and optimal solution is to produce 6000 tons of x_{1}, 43199 of x_{1} and 5200 of x_{3}.
Sol. Introducing slack variables, the problem becomes
Z = 3 x_{1} + 5 x_{2} + 4 x_{3} + 0S_{1} + 0S_{2} + 0S_{3}
Three slack variables have been introduced
Subject to
2x_{1} + 3 x_{2} + 0 x_{3} + S_{1} + 0S_{2} + 0S_{3} = 8
0 x_{1} + 2 x_{2} + 5 x_{3} + 0S_{1} + S_{2} + 0S_{3} = 10
3 x_{1} + 2 x_{2} + 4 x_{3} + 0S_{1} + 0S_{2} + S_{3} = 15
Drawing the first simplex table
Table 3.31 First simplex table
C_{j} 
3 
5 
4 
0 
0 
0 
Minimum ratio 

C_{B} 
Basic variables 
Solution values 
x_{1} 
x_{2} 
x_{3} 
S_{1} 
S_{2} 
S_{3} 

0 
S_{1} 
8 
2 
3 
0 
1 
0 
0 
2.6 
0 
S_{2} 
10 
0 
2 
5 
0 
1 
0 
5 
0 
S_{3} 
15 
3 
2 
4 
0 
0 
1 
7.5 
Z_{j} 
0 
0 
0 
0 
0 
0 
0 

(C_{j}Z_{j}) 
3 
5 
4 
0 
0 
0 
Since 5 is the maximum + ve value of (C_{j} – Z_{j}) in the maximising problem. 5 is the key column and S_{1} row has the minimum value, S_{1} will be replaced by x_{2}.
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 
x_{1} 
x_{2} 
x_{3} 
S_{1} 
S_{2} 
S_{3} 

5 
X_{2} 
1 
0 
0 
0 

0 
S_{2} 
0 
5 
1 
0 

0 
S_{3} 
0 
4 
0 
1 

Z_{j} 
5 
0 
0 
0 

(C_{j}Z_{j}) 
0 
4 
0 
0 
Since 4 is the maximum + ve value, x_{3} 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 S_{1} it will be replaced by X_{3}. New x_{3} 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 
x_{1} 
x_{2} 
x_{3} 
S_{1} 
S_{2} 
S_{3} 

5 
X_{2} 
1 
0 
0 
0 

0 
X_{3} 
0 
1 
0 

0 
S_{3} 
0 
0 
1 

Z_{j} 
5 
4 
0 

(C_{j}Z_{j}) 
0 
4 
0 
Sol. Since the problem is of minimisation nature, artificial variables are also introduced
Z = 5y_{1} + 6 y_{2} + 0S_{1} + OS_{2} + MA_{1} + MA_{2}
Subject to
2y_{1} + 5y_{2} – S_{1} + 0S_{2} + A_{1} + 0A_{1} = 15
3y_{1} + y_{2}+ 0S_{1}– S_{2} + 0A_{1} + 0A_{2} = 12
y_{1}, y_{2}, S_{1}, S_{2}, A_{1}, A_{2} ≥ 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
C_{j }→ 
5 
6 
0 
0 
M 
M 
Minimum ratio 

C ↓ 
Basic variables 
Solution values 
y_{1} 
y_{2} 
S_{1} 
S_{2} 
A_{1} 
A_{2} 

M 
A_{1} 
15 
2 
5 
1 
0 
1 
0 
3 
M 
A_{2} 
12 
3 
1 
0 
1 
0 
1 
12 
Z_{j} 
27M 
5M 
6M 
M 
M 
M 
M 

(C_{j}Z_{j}) 
55M 
66M 
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 y_{2} will replace A_{1} 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 x_{1} = Number of pages of magazine
x_{2} = Number of spots on TV
Maximise Z = 60,000 x_{1} + 1,20,000 x_{2}
9000 x_{1} + 12000 x_{2} ≤ 7,20,000
3x_{1} + 4x_{2} ≤ 240
x_{1} ≥ 2
x_{2} ≥ 3
x_{1}, x_{2} ≥ 0
Introducing slack and artificial variables, we have
Maximize Z = 6000 x_{1} + 1,20,000 x_{2} + 0S_{1} + 0S_{2} – MA_{1} – MA_{2}
3x_{1} +4x_{2} + S_{1} =240
x_{1}S_{2}+A_{1} =2
x_{2} – S_{3} + A_{2} = 3
x_{1}, x_{2}, S_{1}, S_{2}, A_{1}, A_{2} ≥ 0
Now the first Simplex table can be constructed as follows.
Table 3.38 First simplex table
C_{j} → 
60,000 
12,20,000 
0 
0 
0 
M 
M 
Minimum 

↓ 
Basic variables 
Solution values 
x_{1} 
x_{2} 
S_{1} 
S_{2} 
S_{3} 
A_{1} 
A_{2} 
Ratio 
0 
S_{1} 
240 
3 
4 
1 
0 
0 
0 
0 
60 
M 
A_{1} 
2 
1 
0 
0 
1 
0 
1 
0 

M 
A_{2} 
3 
0 
1 
0 
0 
1 
0 
1 
3 
Z_{j} 
5M 
M 
M 
0 
M 
M 
M 
M 

(C_{j}Z_{j}) 
60,000+ M 
1,20,000+ M 
0 
M 
M 
0 
0 
Since x_{2} column has the largest +ve value and minimum ratio is that of A – 2 row and (1) is the key element.
x_{2} will replace row A_{2}.
New elements of row A_{2} 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. 2404×3=228,
34×0=3,
44x_{1}=0,
14×0=1,
04×0=0
04×1= 0,
04×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 C_{j} – Z_{j}, x_{1} is the key column and since minimum ratio is that of A_{1}, row A_{1} will be replaced by column x_{1}. New row A_{1} is obtained by dividing all the elements of the row by key element i.e. 1.
New row S_{1} is obtained by the relationship already known.
228 – 3 × 2 = 222,
3 – 3 × 1=0,
0 – 3 × 0 = 0,
13 × 0 = 1,
0 – 3 × – 1 = 3
43×0=4
New row x_{2} 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

C_{j} → 
60,000 
1,20,000 
0 
0 
0 
Minimum Ratio 

↓ 
Basic variables 
Solution values 
x_{1} 
x_{2} 
S_{1} 
S_{2} 
S_{3} 

0 
S_{1} 
222 
0 
0 
1 
3 
4 
55.5 
60,000 
x_{1} 
2 
1 
0 
0 
1 
0 

1,20,000 
x_{2} 
3 
0 
1 
0 
0 
1 
ve 

Z_{j} 
4,80,000 
60,000 
1,20,000 
0 
60,000 
1,20,000 


(C_{j}Z_{j}) 
0 
0 
0 
60,000 
1,20,000 

S_{3} has the largest +ve value and S_{1} has the minimum ratio so S_{1} will be replaced by S_{3}. Key element is 4.
New row S_{1} is obtained by dividing all its elements by key element i.e., 4, 55· 5, 0, 0, ¼, ¾, 1.
New row x_{1} element will be the same as for this row 0 occurs in the key column.
Now row x_{2} is obtained by using the relationship already known.
Table 3.41 Fourth simplex table
C_{j} 
→ 
60,000 
1,20,000 
0 
0 
0 

↓ 
S_{3} 
55.5 
0 
0 
1 

60,000 
x_{1} 
2 
1 
0 
0 
1 
0 
1,20,000 
x_{2} 
58.5 
0 
1 
0 


Z_{j} 
71.40,000 
60,000 
1,20,000 
30,000 
30,000 
0 

(C_{j}Z_{j}) 
0 
0 
30,000 
30,000 
0 
Since all the elements of C_{j} – Z_{j} are ≤ 0
The optimal solution has been arrived
x_{1} =2
x_{2}=58.5
Z = 71,40,000
Sol.
Phase 1 It consists of the following steps.
Step I. Adding slack variables, the problem becomes
2x_{1} + x_{2} + S_{1} = 1
x_{1} + 4x_{2} – S_{2} = 6
Step II. Putting x_{1} = 0 and x_{2} = 0
S_{1} = 1
S_{2} = 6.
This gives the initial basic solution. However, it is not a basic feasible solution since S_{2} is – ve.
So, we will introduce artificial variable AI and the above constraint can be written as
2x_{1} + x_{2} + S_{1} = 1 … (i)
x_{1} +4x_{2}S_{2} + A_{1} = 6 … (ii)
Step III. Substituting x_{1} = x_{2} = S_{2} = 0 in the constraint equation we get S_{1} = 1 and A_{1} = 6 as the initial basic solution. This can be put in the form of a simplex table as follows.
As (C_{j} _ Z_{j}) is ve under some columns, the current basic feasible solution can be improved.
S_{1} will be replaced by x_{2} as x_{2} is the key column, and S_{1} is the key row, also CD is the key element.
New row x_{2} (old S_{1}) will be obtained by dividing all the elements by 1.
New row A_{1} 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
14×0=1,
14×0=1
New simplex table can be constructed as follows.
Table 3.45

C_{j} → 
0 
0 
0 
0 
1 

↓ 
Basic variables 
Solution variables 
x_{1} 
x_{2} 
S_{1} 
S_{2} 
A_{1} 
0 
x_{2} 
1 
2 
1 
1 
0 
0 
1 
A_{1} 
2 
7 
0 
4 
1 
1


Z_{j} 
2 
7 
0 
4 
1 
1 

(C_{j}Z_{j}) 
7 
0 
4 
1 
0 
Since all the elements are either +ve or zero, an optimal basic solution has been arrived.
However A_{1} = 2 which is > 0, the given LPP does not possess any feasible solution and the procedure stops.
Recent Comments