# Recitation 6

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.