Example 1: The following tableau is optimal for a maximizing linear program with four \le constraints:
| x_1 | x_2 | s_1 | s_2 | s_3 | s_4 | |
|---|---|---|---|---|---|---|
| 0 | 0 | -2 | 1 | 0 | 3/4 | 50 |
| 0 | 1 | 1/2 | 0 | 0 | -1/4 | 40 |
| 1 | 0 | -1 | 0 | 0 | 7/4 | 25 |
| 0 | 0 | 4 | 0 | 1 | 2 | 30 |
| 0 | 0 | 20 | 0 | 0 | 30 | 525 |
- Determine the optimal values for all variables.
- In which constraints are the resources used completely?
- What are the optimal values of the variables in the dual minimizing linear program?
- What would be the value of an additional unit of resource in each of the constraints where all resources are used?
Solution: The optimal values are x_1 = 25, x_2 = 40, s_1 = 0, s_2 = 50, s_3 = 30, s_4 = 0.
Because s_1 = s_4 = 0, the resources in constraint 1 and constraint 4 are used completely.
Reading the values of slack / artificial variables in the objective row from left to right, we get the optimal solution to the dual mLP y_1 = 20, y_2 = 0, y_3 = 0, y_4 = 30.
The value of addition unit of resource in constraint 1 is 20 and the one in constraint 4 is 30.
Example 2: Determine the dual of the linear program:
| Minimize: | 4y_1 + 3y_2 + 8y_3 |
| Subject to: | y_1 + y_2 + y_3 \ge 12 |
| 5y_1 - 2y_2 + 4y_3 \le 20 | |
| 2y_1 + 3y_2 - y_3 = 12 | |
| y_1 \ge 0, y_2 \ge 0, y_3 unrestricted |
Solution: We use the dual formation rules and obtain the dual MLP.
| Maximize: | 12x_1 + 20x_2 + 12x_3 |
| Subject to: | x_1 + 5x_2 + 2x_3 \le 4 |
| x_1 - 2x_2 + 3x_3 \le 3 | |
| x_1 + 4x_2 - x_3 = 8 | |
| x_1 \ge 0, x_2 \le 0, x_3 unrestricted |
Example 3: Electra Manufacturing has decided to focus the next month of production on three related product lines. The per-unit profits on the lines are $120, $150 and $90. The first line has been the most popular, so they plan to make at least as many of it as they make of the other two combined. They want to make a total of at least 3,000 items. The respective lines require 1, 0.5 and 0.75 hours of production time. In the month they anticipate having 2,420 hours of production available. A particular component is in short supply – they have access to only 7,000. Lines 1 and 3 require two of the component: line 2 requires three. Assuming that they can sell all they make, how many of each product line should they make to maximize their profit?
The linear programming formulation, initial tableau, and optimal tableau for the problem follow:
| Maximize: | 120x_1 + 150x_2 + 90x_3 |
| Subject to: | -x_1 + x_2 + x_3 \le 0 |
| x_1 + x_2 + x_3 \ge 3,000 Minimal sales | |
| x_1 + 0.5x_2 + 0.75x_3 \le 2,420 Production hours | |
| 2x_1 + 3x_2 + 2x_3 \le 7,000 Component supply |
The initial tableau:
| x_1 | x_2 | x_3 | s_1 | s_2 | a_2 | s_3 | s_4 | |
|---|---|---|---|---|---|---|---|---|
| -1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | -1 | 1 | 0 | 0 | 3,000 |
| 1 | 1/2 | 3/4 | 0 | 0 | 0 | 1 | 0 | 2,420 |
| 2 | 3 | 2 | 0 | 0 | 0 | 0 | 1 | 7,000 |
| -120 | -150 | -90 | 0 | 0 | 0 | 0 | 0 | 0 |
| -1 | -1 | -1 | 0 | 1 | 0 | 0 | 0 | -3,000 |
The optimal tableau:
| x_1 | x_2 | x_3 | s_1 | s_2 | a_2 | s_3 | s_4 | |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | -8 | 8 | -4 | -2 | 320 |
| 0 | 1 | 0 | 0 | 2 | -2 | 0 | 1 | 1,000 |
| 1 | 0 | 0 | 0 | 5 | -5 | 4 | 1 | 1,680 |
| 0 | 0 | 0 | 1 | 11 | -11 | 8 | 2 | 360 |
| 0 | 0 | 0 | 0 | 180 | -180 | 120 | 90 | 380,400 |
- If Electra could find another source of the component in short supply, how much should they pay for it?
- The sales manager would like to slightly increase the number of items made. How would you advise him?
- What range of production hours would result in the same set of basic variables?
- What would the new basic solution be if 100 fewer components were available?
- What would be the value of an additional hour of production?
Solution: Note component supply constraint has slack variable s_4 and its value in the objective row is 90 in the optimal tableau. Electra should pay $90 for each component in short supply from another source if they could find one.
“Slightly increase number of items made” means changing 3000 on the right hand side of constraint 2 to 3000 + \delta. Imagine the sales manager tells you “Oops, our sales goal is not 3000, but 3000 + \delta“. You might be like “OMG, I have to do the optimization all over again.” However, there is a slick way to get the new optimal solution.
The current optimal solution is x_1 = 1680, x_2 = 1000, x_3 = 320, s_1 = 360. To get x_1 in the new optimal solution, we find, in the optimal tableau, the entry in the column of a_2 (the artificial variable of constraint 2) is in the same row of the 1 in the column of x_1. This entry is -5, and so x_1 in the new optimal solution is x_1 = 1680 - 5\delta. Similarly, in the new optimal solution, we have x_2 = 1000 - 2\delta, x_3 = 320 + 8\delta, s_1 = 360 - 11\delta.. Some entires in the optimal tableau are colored to help you understand where those coefficients in the new optimal solution come from.
Remark: Constraint 2 has a surplus variable s_2. However, to get the new optimal solution, one has to use the slack / artificial variable of the constraint.
Applying the same logic to 2420 on the right hand side of constraint 3 to 2420 + \delta, we obtain new optimal solution x_1 = 1680 + 4\delta, x_2 = 1000 + 0\delta, x_3 = 320 - 4\delta, s_1 = 360 + 8\delta. To maintain the non-negativities of the basic variables, -45 = -360/8 \le \delta \le 320/4 = 80.
A better way to find out the maximum and minimum of \delta, is to divide the last column (i.e., 320, 1000, 1680, 360) by the negation of column of s_3 (i.e., 4, 0, -4, -8). This yields 320 / 4 = 80, 1000 / 0 (skip), 1680 / -4 = -420, 360 / -8 = -45. The smallest among the positives, that is 80, is the maximum, while the biggest among the negatives, that is -45, is the minimum. The range of the production hours is hence 2420-45 = 2375 to 2420+80=2500.
Similarly, if we change 7000 on the right hand side of constraint 4 to 7000+\delta, where \delta = -100, new optimal solution will be x_1 = 1680 +\delta = 1580, x_2 = 1000 + \delta = 900, x_3 = 320 - 2\delta = 420, s_1 = 360 + 2\delta = 160.
Constraint 3 has slack variable s_3 and its value in the objective row in the optimal tableau is 120. The value of an additional hour of production is $120.