We will assume that we have a mechanism for solving linear optimization models when they are formulated in the standard format. Indeed, linear programming computing codes for solving large linear programming problems are commonly available in both interactive mode (available from a time share terminal) and batch mode. In order to use either of these types of computing programs for the solution of linear optimization models, the problem must be presented to the “black box” in the precise form required. We shall use the software called LINDO to illustrate the solutions to the problems in this article.
Now, let us return to the chemical production problem for which we just formulated the linear optimization model in standard form. Figure below shows a portion of the computer printout for the problem.
The Chemical Production Problem: (a) Lindo Computer input and (b) Computer Solution
MAX 60 CHEMX + 50CHEMY
2)2 CHEM X + 4 CHEMY <=80
3)3 CHEMX + 2 CHEMY <=60
4) CHEMX <=16
5) CHEMY <=18
LP OPTIMUM FOUND AT STEP 3
OBJECTIVE FIUNCTION VALUE
VARIABLE VALUE REDUCED COST
CHEMX 10.000000 .000000
CHEMY 15.000000 .000000
ROW SLACK DUAL PRICES
2) .000000 3.750000
3) . 000000 17,500000
4) 6.000000 .000000
5) 3.000000 .000000
NO. ITERATIONS = 3
In Figure above we see the computer input for the linear optimization model, it is in almost the same from that we have been using. Unless your computer center has made the necessary conversion in the output, as is the case with the computer output we will show, the “<=” will mean “≤” in constraint statements. We need not enter the last constraints, x ≥0 and y ≥ 0, because the computer program assumes that none of the decision variables can take on negative values.
Figure above shows the solution output. ON the line labeled “1),” the optimum value of the objective function is shown, $1350. In other words, it states that Z= 1350 in the objective function for an optimal solution.
Next, the values of the variables in the optimum solution are shown under the column heading “VALUE”. The column labeled “REDUCED COST” lists the marginal amount by which the objective function coefficient of each variable must change before it would appear in the optimal solution. These are listed as zero in our example because the variables are already in the optimal solution.
Now let us consider variables listed in the solutions, CHEMX and CHEMY. The solutions states that their optimal values are 10 and 15 units, respectively. Note that this is point d in Figure, the point where the capacity constraints lines for machines A and B intersect, as we expected based on our graphical analysis of this problem. This is an important observation that we shall use in understanding how the linear programming algorithm actually works.
Using the solution values of CHEMX and CHEMY, we insert them in the objective function and compute Z:
Z= 60 X 10 + 50 X 15 =1350
This result checks with the optimum value of Z given by the computer solution.
Checking one further bit of logic, if the solution to our problem lies at the intersection of the lines of the two capacity constraint equations, then we should be able to solve the equations for the two lines simultaneously to determine the values of CHEMX and CHEMY that are common to both questions. First, let us use the equation for machine A and solve for x:
2x + 4y = 80
x = 80/2 – 4y/2
= 40 – 2y
We then substitute this value of x in the constraint equation for machines B:
3(40 – 2y) + 2y = 60
120 – 6y + 2y =60
This value of y checks with our computer solution. Now, we substitute y=15 in the machine A constraints equation to determine the value of x,
2x + 4(15) =80
x = (80 – 60)/2
Thus, we have verified that the solution to our problem lies at point d of Figure, where the two constraint equations intersect. Another interpretation of this fact is that machines A and B, our two productive resources, are completely utilized in this solution; there is no residual slack machine capacity. This fact is important because any of the other feasible solutions in the polygon abcdef of Figure would involve some slack capacity in one or both of the two machines. If there is slack capacity for either of the machines in the optimum solution that fact would have been indicated in the computer output for the optimum solution. In some more complex problems, there may be slack capacity for a productive resource in the optimum solution.
The computer output also gives us values for “SLACK” and “DUAL PRICES”. The nonzero slack values are for constraints 4 and 5, the market constraints. Constraints 4, CHEMX ≤ 16 was the market limit for that product. The solution simply points out to us that if we produce according to the optimum solution where CHEMX = 10, there will be unsatisfied demand (slack) of 6; this fits in with the market constraint because CHEMX + SLACK 4 = 10 + 6 = 16. Similarly, the value of SLACK 5 =3 agrees with the market constraint 5, CHEMY ≤ 18, because CHEMY + SLACK 4 = 15 + 3 = 18.
These interpretations of the optimum solution to the chemical production problem are rather simple. The important point is that equivalent interpretations of more complex problems are a straight forward extension of these ideas. The solution will state the combination of variables that optimizes the objective function. Some, but not necessarily all, of the constraints will be controlling constraints, and there will be slack in some of the resources; that is, all the resources will not be fully utilized. In our example, the slack is in the demand for the two products. Note, however, that if the demand for CHEMY drops to only 14, that is, y = 14, it would become one of the controlling (“tight”) constraints as may be seen in Figure, and there would be some slack capacity in machine A.