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 equal-to type and the greater-than-or-equal-to 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 equal-to 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 less-than-or-equal-to 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 greater-than-or-equal-to 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

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

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
	=====

 

You may also be interested in other relevant articles: Linear Programming-Maximization of Contribution Margin-Graphical Method Linear Programming-Maximization of Contribution Margin-Simplex Method Linear Programming-Minimization of Cost-Graphical Method Linear Programming-Minimization of Cost-Simplex Method Shadow Prices Dynamic Programming Linear Programming Techniques-General Observations Linear Programming Questions and Answers Linear Programming Problems, Graphical and Simplex Method

 

Dear visitor! Do you like this article? If you like, then please bookmark this page and also share with your friends. Thank you for your support.   [Report Errors and Omissions]

Back to Home Page | Linear Programming Technique