Minimization problems. An identical procedure is followed for solving the minimization problems. Since the objective is to minimize rather than maximize, a negative (C_{j} – Z_{j}) value indicates potential improvement. Therefore, the variable associated with largest negative (C_{j} – Z_{j}) value would be brought into the solution first. Additional variables are brought in to set up such problems. However, such problems involve greater than or equal to constraints, which need to be treated separately from less than or equal to constraints, which are typical of maximization problems. In order to convert such inequalities, the following procedure may be adopted.
Where S_{1} is a slack variable. However, this will create a difficulty in the simplex method because of the fact that the initial simplex solution starts with slack variables and a negative value (1S_{1}) would be in the solution, a condition which is not permitted in linear programming. To overcome this problem, the simplex procedure requires that another variable known as artificial variable be added to each equation in which a slack variable is subtracted. An artificial variable may be thought of as representing a fictitious product having very high cost which though permitted in the initial solution to a simplex problem, would never appear in the final solution. Defining A as an artificial variable, the constraint equation can be written as:
3X_{1} + 2X_{2}S_{1} + 1A_{1} = 1200
Assuming the objective function is to minimize cost, it would be written as :
10X_{1} + 20X_{2} + 0S_{1} + MA_{1} to be minimised
Where M is assumed to be very large cost (say, 1 million). Also S_{1} is added to the objective function even though it is negative in constraint equation. An artificial variable is also added to constraint equations equality signs, e.g. if the constraint equation is
3X_{1} + 2X_{2} = 1200
then, in simplex it would change to
3X_{1} + 2X_{2} + 1A_{1} = 1200
to satisfy simplex requirement and would be reflected as MA in the objective unction.
Example 3.2 ABC company manufactures and sells two products P_{1} and P_{2}. Each unit of P_{1} requires 2 hours of machining and 1 hour of skilled labour. Each unit of P_{2} requires 1 hour of machining and 2 hours of labour. The machine capacity is limited to 600 machine hours and skilled labour is limited to 650 man hours. Only 300 units of product P_{1} can be sold in the market. You are required to
a) Develop a suitable model to determine the optimal product mix.
b) Find out the optimal product mix and the maximum contribution. Unit contribution from product P_{1} is Rs 8 and from product P_{2} is Rs 12.
c) Determine the incremental contribution/unit of machinehours, per unit of labour and per unit of product P_{1}.
Sol.
Step 1. Formulation of LP model
Let X_{1} and X_{2} be the number of units to be manufactured of the two products P_{1} and P_{2} respectively. We are required to find out the number of units of the two products to be manufactured to maximise contribution, i.e., profits when individual contribution of the two products are given. LP model can be formulated as follows:
Step 2. Converting constraints into equations
LP problem has to be written in a standard form, for which the inequalities of the constraints have to be converted into equations. For this purpose, we add a slack variable to each constraint equation. Slack is the unused or spare capacity for the constraints to which it is added. In less than (≤)
type of constraint, the
slack variable denoted by S, is added to convert inequalities into equations. S is always a nonnegative figure or 0. If S is negative, it may be seen that the capacity utilised will exceed the total capacity, which is absord. The above inequalities of this problem can be rewritten by adding suitable slack variables and converted into equations as shown below.
2X_{1} + X_{2} + S_{1}= 600
X_{1} + 2X_{2} + S_{2} = 650
X_{1}+S_{3}=300
X_{1}, X_{2}, S_{1}, S_{2}, S_{3} > 0
Slack variables S_{1}, S_{2} and S_{3} contribute zero to the objective function since they represent only unused resources. Let us include these slack variables in the objective function. Then maximize
2 = 8X_{1} + 12X_{2} + 0S_{1} + 0S_{2}+ 0S_{3}
Step 3. Set up the initial solution
Let us recollect that the computational procedure in the simplex method is based on the following fundamental property.
“The optimal solution to a Linear Programming problem always occurs at one of three comer points of the feasible solution space”.
It means that the comer points of the feasible solution region can provide the optimal solution. Let the search start with the origin which means nothing is produced at origin (0, 0) and the value of decision variable X_{1} and X_{2} is zero. In such a case, S_{1} = 600, S_{2} = 650, S_{3} = 300 are the spare capacities as nothing (0) is being produced. In the solution at origin we have two variables X_{1} and X_{2} with zero value and three variables (S_{1}, S_{2} and S_{3}) with specific values of 600, 650 and 300. The variables with nonzero values, i.e., S_{1}, S_{2} and S_{3} are called the basic variables where as the other variables with zero values i.e. X_{1}, X_{2} and X_{3} are called nonbasic variables. It can be seen that the number of basic variables is the same as the number of constraints equations (three in the present problem). The solution with basic variables is called basic solution which can be further divided into Basic Feasible Solution and Basic Infeasible Solution. The first type of solutions are those which satisfy all the constraints. In Simplex Method, we search for basic feasible solution only.
Step 4 Developing initial simplex table
The initial decision can be put in the form of a table which is called a Simplex Table or Simplex Matrix. The details of the matrix are as follows.
 Row I contains C_{j} or the contribution to total profit with the production of one unit of each product P_{1} and P_{2} Under column I (C_{j}) are listed the profit coefficients of the basic variables. In the present problem, the profit coefficients of S_{1}, S_{2} and S_{3} are zero.
 In the column labeled Solution Mix or Product Mixare listed the variables S_{1}, S_{2} and S_{3} their profits are zero and written under column I (C_{j}) as explained above.
 In the column labeled ‘contribution unit quantity’ are listed the values of basic variables included in the solution. We have seen in the initial solution S_{1} = 600, S_{2} = 650 and S_{3} = 300. These values are listed under this column on the right side as shown in table 3.5. Any variables not listed under the solutionmix column are the nonbasic variables and their values are zero.
 The total profit contribution can be calculated by multiplying the entries in column C_{j} and column ‘contribution per unit quantity’ and adding them up. The total profit contribution in the present case is 600 × 0 + 650 × 0 + 300 × 0 = 0.
 Numbers under X_{1} and X_{2} are the physical ratio of substitution. For example, number 2 under X_{1} gives the ratio of substitution between X_{1} and S_{1}. In simple words if we wish to produce 2 units of product P_{1} i.e., X_{1}, 2 units of S_{1} must be sacrificed. Other numbers have similar interpretation. Similarly, the number in the ‘identity matrix’ columns S_{1}, S_{2} and S_{3} can be interpreted as ratios of
exchange. Hence the numbers under the column S_{1} represents the ratio of exchange between S_{1} and the basic variables S_{1}, S_{2} and S_{3}.  Z_{j} and C_{j} – Z_{j} are the two final rows. These two rows provide us the total profit and help us in finding out whether the solution is optimal or not Z_{j} and C_{j} – Z_{j} can be found out in the following
Z_{j} = C_{j} of S_{1} (0) × coefficients of X_{1} in S_{1} row (2) + C_{j} of S_{2} (0) × coefficients of X_{1} in S_{2} row(1)+C_{j }of S_{3}(0) × coefficient X_{1} in S_{j} row(1)=0 × 2+0 × 1 +0 × l =0
C_{j} 
Solution mix 
8 
12 
0 
0 
0 
Contribution unit quantity 
X_{1} 
X_{2} 
S_{1} 
S_{2} 
S_{3} 
(Solution values) 

0 
S_{1} 
2 
1 
1 
0 
0 
600 
0 
S_{2} 
1 
2 
0 
1 
0 
650 
0 
S_{3} 
1 
0 
0 
0 
1 
300 
C_{j} 
0 
0 
0 
0 
0 

(C_{j}Z_{j}) 
8 
12 
0 
0 
0 
Using the same procedure Z_{j} for all the other variable columns can be worked out as shown in the completed first Simplex Table given in Table 3.5.
The number in the (C_{j} – Z_{j}) row represent the net profit that will result from introducing 1 unit of each product or variable into the solution. This can be worked out by subtracting, Z_{j} total for each column from the C_{j} values at the top of that variable’s column. For example, C_{j} – 2_{j} number in the X_{1} column will 8 – 0 = 8, in the X_{2} column it will be 12 – 0 = 12 etc.
The value of the objective function can be obtained by multiplying the elements in C_{j} column with the corresponding elements in the C_{j} rows i.e. in the present case Z = 8 × 0 + 12 × 0 = 0
Table 3.6
C_{j} 
Solution mix 
8 
12 
0 
0 
0 
Contribution unit quantity (Solution values) 
X_{1} 
X_{2} 
S_{1} 
S_{2} 
S_{3} 

0 
S_{1} 
2 
1 
1 
0 
0 
600 
0 
S_{2} 
1 
2 
0 
1 
0 
650 
0 
S_{3} 
1 
0 
0 
0 
1 
300 
C_{j} 
0 
0 
0 
0 
0 

(C_{j}Z_{j}) 
8 
12 
0 
0 
0 
By examining the number in the (C_{j} – Z_{j} ) row, we can see that total profit can be increased by Rs 8 for each unit of product X_{1} added to the product mix or by Rs 12 for each unit of product X_{2} added to the product mix. A positive (C_{j} – Z_{j}) indicates that profits can still be improved. A negative number of (C_{j} _ Z_{j}) would indicate the amount by which the profits would decrease, if one unit of the variable was added to the solution. Hence, optimal solution is reached only when there are no positive numbers in (C_{j} – Zj) row.
Step 5 Test for optimality
Now we must test whether the results obtained are optimal or it is possible to carry out any improvements. It can be done in the following manner.
 Selecting the entering variable. We have to select which of the variables, out of the two nonbasic variables X_{1} and X_{2}, will enter the solution. We select the one with maximum value of C_{j} – Zj. Variable X_{1} has a (C_{j} – Z_{j}) value of 8 and X_{2} has a (C_{j} – Z_{j}) value of 12. Hence, we select variable X_{1} as the variable to enter the solution mix and identify the column in which it occurs as the key column with help of a small arrow.
 Selecting the variable that leaves the solution. As a variable is entering the solution, we have to select a variable which will leave the solution. This can be done as follows:
 Divide each number in the solution value or contribution unit quantity column by corresponding number in the key column i.e., divide 600, 650 and 300 by 1, 2, 0.
C_{j} 0 0 0 
Solution mix S_{1} S_{2} S_{3} 
8 X_{1} 2 1 1 
12 X_{2} 1 2 0 
0 S_{1} 1 0 0 
0 S_{2} 0 1 0 
0 S_{3} 0 0 1 
Solution values 600 650 300 
Minimum ratio 600 325

Z_{f} 
0 
0 
0 
0 
0 

(C_{j}Z_{j}) 
8 
12 
0 
0 
0 
 Select the row with smallest non negative ratio as the row to be replaced, in present example the ratios are
S_{1} row, 600/1 = 600 unit of X_{2}
S_{2} row, 650/2 = 325 units of X_{2}
S_{3} row, 300/0 = units of X_{2}
It is clear that S_{2} (with minimum ratio) is the departing variable. This row is called the key row.
 The number at the intersection of key row and key column is called the key number which is 2 in the present case and is circled in the table.
Step 6 Developing second simplex table
Now we can develop the second simplex table by the following method.
(a) Determine new values for the key row. To revise the key rows, divide the values in the key row (S_{2}) by the value of the key element (2) and replace departing variable (S_{2}) by the entering variable
(X_{2}).
(b) Determine new values for other remaining rows. This is done as follows:
New row = old raw number – [Corresponding number in key row] × [corresponding fixed ratio] where fixed ratio = old row number in key column key number.
Now the new S_{1} and S_{3} rows are
Row S_{1} = 600 – 650 × 1/2 = 275
21×1/2=1.5
12×1/2=0
10×1/2=1
01×1/2=0
Row S_{2} = 300 – 650 × 0/2 = 300
11×0/2=1
02×0/2=0
00×0/2=0
01×0/2=0
10×0/2=1
Key row S_{2} is replaced by X_{2} with the following elements
1/2, 1,0, 1/2, 0, 325
Value of C_{j} and C_{j} – Zj rows can be calculated as explained earlier. The new revised and improved solution table is shown below.
Table 3.8
Second simplex Table
C_{j} 
Solution mix 
8 
12 
0 
0 
0 
Solution values 
Minimum ratio 
X_{1} 
X_{2} 
S_{1} 
S_{2} 
S_{3} 

0 
S_{1} 
1.5 
0 
1 
0 
0 
275 

0 
X_{2} 
½ 
1 
0 
½ 
0 
325 
325 
0 
S_{3} 
1 
0 
0 
0 
1 
300 

Z_{j} 
0 
0 
0 
0 
0 

(C_{j}Z_{j}) 
8 
12 
0 
0 
0 
Zj values are Z = 0 × 1.5 + 0 × ½ × 0 × 1 = 0 etc.
Minimum ratios by dividing 275, 325 and 300 by corresponding element in the key column i.e., 0, 1, 0.
We find that the value of objective function has been improved from 0 to . But the correct solution is not optimal as there are positive values (12) and (8) in the (C_{j} – Z_{j}) row. Also, since minimum ratio is 325, we select X_{2} row to leave the solution as X_{2} (key column) will enter the solution. The new X_{2} (key) row will remain same as its elements 1/2, 1, 0, 1/2, 0 and 325 have to be divided by key element, i.e., (shown circled in the above table). However, row S_{1} and S_{3} elements will undergo change Row S_{1} = old row number – [corresponding number in key row 1 × [corresponding fixed ratio]
Fixed ratio = old row number in key column key number = 0
It can be concluded that this problem does not have a optimal solution as X_{2} row is to be replaced by X_{2} row.
Example 3.3. Following data is available for a manufacturing company engaged in production of three items X. Y and Z
Product 
Time required in hours 
Total contribution (Rs.) 

Machining 
Finishing 

X 
12 
3 
1000 
Y 
6 
8 
800 
Z 
8 
6 
400 
Conpany’s capacity 
3000 
1500 
You are required to present the above data in the form of LPP to maximize the profit from the production and solve the problem using simplex method.
Now let us construct the first Simplex table as below
Table 3.9
Solution mix 
1000 
800 
400 
0 
0 
Solution values 
Min ratio 
X_{1} 
X_{2} 
X_{3} 
S_{1} 
S_{2} 

S_{1} 
12 
6 
8 
1 
0 
3000 
250 
S_{2} 
3 
8 
6 
0 
1 
1500 
500 
Z_{j} 
0 
0 
0 
0 
0 
0 

(C_{j}Z_{j}) 
1000 
800 
400 
X_{1} is the key column S_{1} is the key row and 12 is the key element (circled in the table).
Also it can be seen X_{1} is the entering variable and S_{1} is the variable leaving the solution.
Row (1) new = 1/12 Row (1) old, i.e., 1, 1/2, 2/3, 1/12, 0, 250
Row (2) new = Row (2) old – 3 row (1) new
First element =33×1=0
Second element =63×1/2=13/2
Third element =63×2/3=4
Fourth element = 03×1/12=1/4
Fifth element = 13 × 0 = 1
Sixth element = 1500 – 3 × 250 = 750
Hence row 1 (S_{1}) will be replaced by 1, 1/2, 2/3, 1/12, 0, 250 and row 2 (S_{2}) will be replaced by 0, 13/2, 4, 1/4, 1, 750.
Second simplex table can now be constructed
Table 3.10
Second simplex table
C_{j} 
Solution mix 
1000 
800 
400 
0 
0 
Solution values 
Minimum Ratio 
X_{1} 
X_{2} 
X_{3} 
S_{1} 
S_{2} 

1000 
x_{1} 
1 
0 
250 
500 

0 
S_{2} 
0 
4 
1 
750 
115.4 

Z_{j} 
1000 
500 
667 
83.3 
0 
2,50,000 

(C_{j}Z_{j}) 
0 
300 
267 
83.3 
0 
It may be seen that the value of objective function has increased from 0 to 2,50,000. But there is a positive entry (300) in the (C_{j} – Z_{j}) hence this solution is not optimal.
It can also be seen that entering variable is X_{2} and departing variable is S_{2}.
Third simplex table can now be constructed as follows:
Table 3.11
Third simplex table (optimal solution)
C_{j} 
Solution mix 
1000 
800 
400 
0 
0 
Solution value 
X_{1} 
X_{2} 
X_{3} 
S_{1} 
S_{2} 

1000 
x_{1} 
1 
0 

800 
x_{2} 
0 
1 

Z_{j} 
2,84,615 
1000 
800 

(C_{j}Z_{j}) 
0 
0 
Since all the entries in (C_{j} – Z_{j}) row are either zero or negative, this is the optimal solution.
Maximum value of Z, 2,84,615 occurs at x_{1} = 192 x_{2} = 115 and x_{3} = 0.
Example 3.4 ABC Ltd produces four products P_{1}, P_{2}, P_{3} and P_{4}. Each one of these products has to be processed on three machines X, Y, Z. The capacity of the machines and the time required to manufacture one of each type of products are shown in the table below:
The profit contribution/unit of products P_{1}, P_{2}, P_{3} and P_{4} are Rs. 8, 6, 4, 2 respectively.
You are required to formulate the above as a LPP and determine the optimal product mix by using simplex method.
Let X_{1}, X_{2}, X_{3} and X_{4} be the number of units of product P_{1}, P_{2}, P_{3} and P_{4} respectively.
The mathematical model is as follows
Maximise Z = 8x_{1} + 6x_{2} + 4x_{3} + 2x_{4}
After introducing slack variables S_{1}, S_{2} and S_{3} the problem can be rewritten as
Maximise Z = 8x_{1} + 6x_{2} + 4x_{3} + 2x_{4} + 0S_{1} + 0S_{2} + 0S_{3}
Subject to the constraints
2x_{1}+3x_{2}+4x_{3} +3x_{4}+S_{1}=800
4x_{1} + 2x_{2} + x_{3} + 2x_{4} + S_{2} = 600
3x_{1} + x_{2} + 2x_{3} + x_{4} + S_{3} = 420
x_{1}, x_{2}, x_{3}, x_{4}, S_{1}, S_{2} , S_{3} 0
Initial feasible solution can be obtained by purring
x_{1}=x_{2}=x_{3}=x_{4}=0 so that S_{1}=800, S_{2}=600, S_{3}=420 and Z=0.
Now first simplex table can be constructed.
Table 3.12
C_{j} 
Solution mix 
8 
6 
4 
2 
0 
0 
0 
Solution value 
Minimum Ratio 
x_{1} 
x_{2} 
x_{3} 
x_{4} 
S_{1} 
S_{2} 
S_{3} 

0 
S_{1} 
2 
3 
4 
3 
1 
0 
0 
800 
400 
0 
S_{2} 
4 
2 
1 
2 
0 
1 
0 
600 
150 
0 
S_{3} 
3 
1 
2 
1 
0 
0 
1 
420 
140 Key row 
Z_{j} 
0 
0 
0 
0 
0 
0 
0 

(C_{j}Z_{j}) 
8 
6 
4 
2 
0 
0 
0 
x_{1} is the key column.
S_{3} is the key row.
and 3 is the key number (circled in the table)
Also x_{1} is the entering variable and S_{3} is the outgoing variable.
We use the following row operations to get second simplex table by entering x_{1} in to the solution and removing S_{3} variable.
C_{j} 
Solution mix 
8 
6 
4 
2 
0 
0 
0 
Solution value 
Minimum Ratio 
x_{1} 
x_{2} 
x_{3} 
x_{4} 
S_{1} 
S_{2} 
S_{3} 

0 
S_{1} 
1 
3 
2 
2 
1 
0 
1 
380 
126.7 
0 
S_{2} 
2 
0 
1 
320 
240 

8 
x_{1} 
1 
0 
0 
140 
46.7 

Z_{j} 
1120 
8 
0 
0 

(C_{j}Z_{j}) 
0 
0 
0 
It can be seen that Z has improved from 0 to 1120 but since there is still a positive value in (C_{j} – Zj) it is not optimal solution.
It is now clear that x_{2} is the entering variable and x_{1} the departing variable.
Now the third simplex table is to be constructed
We now use the following row operations to get a new solution by entering variable x_{2} and removing x_{1} variable.
Table 3.14
Third simplex table
C_{j} 
Solution mix 
8 
6 
4 
2 
0 
0 
0 
Solution Mix 
x_{1} 
x_{2} 
x_{3} 
x_{4} 
S_{1} 
S_{2} 
S_{3} 

0 
S_{1} 
1 
2 
2 
2 
1 
0 
1 
380 
0 
S_{2} 
0 

Z_{j} 
10 
4 
0 

(C_{j}Z_{j}) 
2 
4 
0 
The student should further attempt this problem to get the optimal solution. The present solution is not the optimal solution as positive values exist in C_{j} Z_{j}.
Recent Comments