Linear Programming  Minimization of Cost  Simplex Method:
Linear programming simplex method can be used in problems whose objective is to
minimize the
variable cost.
An example can help us explain the procedure of
minimizing cost using linear programming simplex method.
Example:
Assume that a pharmaceutical firm is to produce
exactly 40 gallons of mixture in which the basic ingredients, x and y, cost
$8 per gallon and $15 per gallon, respectively, No more than 12 gallons of x
can be used, and at least 10 gallons of y must be used. The firm wants to
minimize cost.
The cost function objective can be written as:
C = 8x + 15y
C = Cost
The problem illustrates the three types of
constraints, =, ≤, and ≥, as follows:
x + y = 40
x ≤ 12
y ≥ 10
The optimum solution is obvious. Since x is
cheaper, as much of it as possible should be used, i.e., 12 gallons. Then
enough y, or 28 gallons, should be used to obtain the desired total quantity
of 40 gallons.
Simplex Method:
In more realistic problems, a solution may not
be obvious, especially if there are many ingredients each having
constraints. A simple procedure is needed to generate an optimal solution no
matter how complex the problem. The steps towards a solution in the cost
minimization problem are similar to those taken in the
contribution margin maximization example where the simplex method is
used and slack variables are introduced in order to arrive at the first
feasible solution which give a zero
contribution margin.
I addition to the slack variables, a different
type of variable known as and artificial variable is introduced. Artificial
variables allow two types of restrictions or constraints to be treated: the
equalto type and the greaterthanorequalto type. Artificial variables
are of value only as computational devices in maximization and minimization
problems.
In this minimization problem, an artificial
variable, a1, is introduced in the first constraint, which is of the
equalto type. A new equality is written as follow:
x + y + a1 = 40 gallons
The new ingredient, a1, must be thought of as a
very expensive item which would not be part of the optimum solution. I a
costs $999 per gallon, for example, 40 gallons would cost $39,960. This high
cost is noted by the coefficient m in the objective function. (For a
maximization problem, the notion of a very low contribution margin is
denoted by the symbol m.) This symbol is added merely to intimate the
simplex method, since the constraint is already an equality.
The second constraint is the
lessthanorequalto type, and a slack variable, s1, is added to form an
equation: x + s1 = 12 gallons. The s1 represents the difference between 12
gallons of x and the actual number of gallons of x in the final solution.
The third constraint is the
greaterthanorequalto type, and a variable s2, is introduced to form and
equation: y  s2 = 10 gallons. The variable s2 must be thought of as the
amount by which the actual number of gallons of y in the final solution must
be reduced to arrive at 10 gallons. For example, if y should be 18 gallons,
than s2 would be 8 gallons (18  8 = 10 gallons). However, if y appears in
the first solution as 0, than 0  s2 = 10 or s2 = 10. This equation is not
feasible because 10 gallons of an ingredient is not possible. To prevent s2
from entering the first solution, in which only slack and artificial
variables are introduced, a second artificial variable, a2, is utilized.
Thus, y  s2 +a2 +10 gallons. Similar to a1, a high cost (m) is assigned to
a2 in the objective function.
As a rule, there must be the same number of
entries in the variable (mix) column as there are constraints. Before a2 is
introduced in this example, there are three constraints, one artificial
variable (a1), and two slack variables (s1 ands2), of which s2 has a
negative coefficient. The introduction of the artificial variable, a2, gives
a set of four variables, from which the three with positive coefficients
(s1, a1, and a2) can be chosen to enter into the variable column of the
first tableau.
The new cost equation is:
C = 8x + 15y  0s2 + ma1 +0s1 + ma2
For minimizing cost, the objective function must
be multiplied by 1. This transformed function enters the first tableau as
the objective row. the resulting equation is:
C =  8x  15y + 0s2  ma1  0s1  ma2
The new constraints for the simplex solution
are:

x + y +a1
x + s1
y  s2 + a2 
=
=
= 
40
12
10 
The first tableau can be set up as shown below:

Mix 
0 
8 
15 
0 
m 
0 
m 
Quantity 
x 
y 
s2 
a1 
s1 
a2 
m 
a1 
40 
1 
1 
0 
1 
0 
0 
0 
s1 
12 
1 
0 
0 
0 
1 
0 
m 
a2 
10 
0 
1 
1 
0 
0 
1 


50m 
m+8 
2m+15 
m 
0 
0 
0 
First simplex tableau and
first solution 
Explanation and Computations for the First Tableau:
The explanation of the arrangement is identical
with that given for the first tableau of the
maximization model. Observe that variables not included in a constraint
are assigned zero coefficients in the problem rows. The index row is
computed as follows:
Steps 1
and 2 
Step 3 
m (40) + 0
(12) + (m) (10) = 50m 
50m  0 =
50m 
m (1) + 0
(1) + (m) (0) = m 
m  (8) =
m + 8 
m (1) + 0
(0) + (m) (1) = 2m 
2m  (15) =
2m + 15 
m (0) + 0
(0) + (m) (1) = m 
m  0 = m 
m (1) + 0
(0) + (m) (0)= m 
m  (m) = 0 
m (0) + 0
(1) + (m) (0) = 0 
0  0 = 0 
m (0) + 0
(0) + (m) (1)= m 
m  (m) = 0 
In the simplex method the optimum solution has not been reached if the index
row carries any negative values (except for the quantity column which
denotes total cost of this solution) at the completion of an iteration.
Consequently, since negative values appear in the index row, the optimum
solution has not been found, and a second tableau must be set up.
Explanation and Computation for the Second Tableau:
Since the objective is to minimize cost, the key
column is found by selecting that column with the negative value having the
highest absolute value in the index row, i.e., that variable whose value
will most decrease cost. The index row shows only two negative values: m +
8 and 2m + 15. Observe that the quantity column value in the index row,
50m, is not considered. This figure denotes total cost of this solution and
is negative by convention. The negative number with the highest absolute
value in the index row is 2m + 15; therefore, y is the key column. The row
to be replaced, the key row, is a2, determined as follows:
a1 row, 40/1 = 40
s1 row, 12/0 is not considered (not defined
mathematically)
a2 row, 10/1 = 10
Again, as in the maximization discussion, the
smallest positive ratio identifies the equation which operates as the
limiting constraint.
Since the key number (the crossing cell of the
key column y and the key row a2) is 1, the values of the main row (y) do not
change, as indicated by the following computations: 10/1 = 10; 0/1 = 0; 1/1
= 1; 1/1 = 1; 0/1 = 0; 0/1 = 0; and 1/1 = 1.
The values in the other rows are determined as
follows:
a1 Row 
s1 Row 
40
 1 (10) = 30 
12
 0 (10) = 12 
1
 1 (0) = 1 
1
 0 (0) = 1 
1
 1 (1) = 0 
0
 0 (1) = 0 
0
 1 (1) = 1 
0
 0 (1) = 0 
1
 1 (0) = 1 
0
 0 (0) = 0 
0
 1 (0) = 0 
1
 0 (0) = 1 
0
 1 (1) = 1 
0
 0 (1) = 0 

Index Row 
Step 1
and 2 
Step 3 
m (30) + 0
(12) + (15) (10) = 30m  150 
(30m  150)
 0 = 30m  150 
m (1) + 0
(1) + (15) (0) = m 
(m)  (8) =
m + 8 
m (0) + 0
(0) + (15) (1) =  150 
(15)  (15)
= 0 
m (1) + 0
(0) + (15) (1) = m + 15 
(m + 15)  0
= m + 15 
m (1) + 0
(0) + (15) (0) = m 
(m)  (m) =
0 
m (0) + 0
(1) + (15) (0) = 0 
(0)  0 = m
+ 0 
m (1) + 0
(0) + (15) (1) = m  15 
(m  15) 
(m) = 2m  15 

Mix 
0 
8 
15 
0 
m 
0 
m 
Quantity 
x 
y 
s2 
a1 
s1 
a2 
m 
a1 
30 
1 
0 
1 
1 
0 
1 
0 
s1 
12 
1 
0 
0 
0 
1 
0 
15 
y 
10 
0 
1 
1 
0 
0 
1 


30m  150 
m + 8 
0 
m + 15 
0 
0 
2m  15 
Second simplex tableau and
second solution 
Since negative values appear in the index row,
excluding the quantity column, the optimum solution has not yet been found,
and a third tableau must be set up.
Explanation and Computations for the Third Tableau:
Since m + 8 is the negative number with the
highest absolute value in the index row of the second tableau, x is the key
column.
The row to be replaced, the key row, is s1,
determined as follows:
a1 row, 30/1 = 30
s1 row, 12/1 = 12
y row, 10/0 not defined mathematically
The following computations determine the values
in the x row that replaces the s1 row, as well as the values in the other
rows:
x Row 
a1 Row 
y Row 
12/1 = 12 
30  1 (12) =
18 
10  0 (12) =
10 
1/1 = 1 
1  1 (1) = 0 
0  0 (1) = 0 
0/1 = 0 
0  1 (0) = 0 
1  0 (0) = 1 
0/1 = 0 
1  1 (0) = 1 
1  0 (0) =
1 
0/1 = 0 
1  1 (0) = 1 
0  0 (0) = 0 
1/1 = 0 
0  1 (1) =
1 
0  0 (1) = 0 
0/1 = 0 
1  1 (0) =
1 
1  0 (0) = 0 


Index Row 
m (18) + (8) (12) + (15) (10) = 18m  246 
(18m  246)  0 = 18m  246 
m (0) + (8) (1) + (15) (0) = 8 
8  (8) = 0 
m (0) + (8) (0) + (15) (1) = 15 
15  (15) = 0 
m (1) + (8) (0) + (15) (1) = m + 15 
(m + 15)  0 = m + 15 
m (1) + (8) (0) + (15) (0) = m 
m  (m) = 0 
m (1) + (8) (1) + (15) (0) = m  8 
(m  8)  0 = m  8 
m (1) + (8) (0) + (15) (1) = m  15 
(m  15)  (m) = 2m  15 


Mix 
0 
8 
15 
0 
m 
0 
m 
Quantity 
x 
y 
s2 
a1 
s1 
a2 
m 
a1 
18 
0 
0 
1 
1 
1 
1 
8 
x 
12 
1 
0 
0 
0 
1 
0 
15 
y 
10 
0 
1 
1 
0 
0 
1 


18m  246 
0 
0 
m + 15 
0 
m  8 
2m  15 
Third simplex tableau and
third solution 
Since a negative value, m + 15 appears in the
index row, excluding the quantity column, the optimum solution has not been
found, and a fourth tableau must be set up.
Explanation and Computations for the Fourth Tableau:
Since m +15 is the only negative number in the
index row of the third tableau, excluding the quantity column, s2 is the key
column.
The smallest positive ratio in the following
computation identifies the row to be replaced as a1
a1 row, 18/1 = 18
x row, 12/0 is not defined mathematically
y row, 10/1 = 10
The values in the s2 row (replacing the a1 row),
the x row, and the index row are determined as follows:
s2 Row 
x Row 
y Row 
18/1 = 18 
12  0 (18) =
12 
10  (1)
(18) = 28 
0/1 = 0 
1  0 (0) = 1 
0  (1) (0)
= 0 
0/1 = 0 
0  0 (0) = 0 
1  (1) (0)
= 1 
1/1 = 1 
0  0 (1) = 0 
1  (1) (1)
= 0 
1/1 = 1 
0  0 (1) = 0 
0  (1) (1)
= 1 
1/1 = 1 
1  0 (1) =
1 
0  (1) (1)
= 1 
1/1 = 1 
0  0 (1) =
0 
1  (1) (1)
= 0 


Index Row 
Step 1 and 2 
Step 3 
0
(18) + (8) (12) + (15) (28) = 516 
516  0 = 516 
0
(0) + (8) (1) + (15) (0) = 8 
8  (8) = 0 
0
(0) + (8) (0) + (15) (1) = 15 
15  (15) = 0 
0
(1) + (8) (0) + (15) (0) = 0 
0
 0 = 0 
0
(1) + (8) (0) + (15) (1) = 15 
15  (m) = m  15 
0
(1) + (8) (1) + (15) (1) = 7 
7
 0 = 7 
0
(1) + (8) (0) + (15) (0) = 0 
0
 (m) = m 

Mix 
0 
8 
15 
0 
m 
0 
m 
Quantity 
x 
y 
s2 
a1 
s1 
s2 
0 
s2 
18 
0 
0 
1 
1 
1 
1 
8 
x 
12 
1 
0 
0 
0 
1 
0 
15 
y 
28 
0 
1 
0 
1 
1 
0 


516 
0 
0 
0 
m  15 
7 
m 
Fourth simplex tableau and
the optimal solution 
No negative values remain in the index row of the fourth tableau, except the
minimum cost figure which is negative (516) by convention. The following
optimum solution has been reached:
12 gals. of x @ $ 8 per gal.
= 
$96 

28 gals. of y @ $15 per gal.
= 
420 

 
 

40 gals. of mixture 
$516

The lowest
cost combination 

===== 

