Chapter 6, Problem 1RP

a.

Explanation of Solution

Dual linear problem and its optimal solution

• The dual of a given linear program is another linear program that is derived from the original linear program in following ways:
  • Each variable in the original linear program becomes a constraint in the dual linear program.
  • Each constraint in the original linear program becomes a variable in the dual linear program.
  • The objective direction is inversed which becomes maximum in the original and minimum in the dual.
• Hence the dual of the linear problem is

  ${\text{Min w = 6y}}_{\text{1}}{\text{+ 3y}}_{\text{2}}{\text{+ 10y}}_{\text{3}}$

  Subject to

  $\begin{array}{l}{\text{y}}_{\text{1}}{\text{+ y}}_{\text{2}}{\text{+ 2y}}_{\text{3}}\text{>= 4}\hfill \\ {\text{2y}}_{\text{1}}{\text{– y}}_{\text{2}}{\text{+ y}}_{\text{3}}\text{>= 1}\hfill \end{array}$

• The formulas for computing the optimal table include:
  • ${\text{x}}_{\text{j}}$ column in optimal table’s constraints = ${\text{B}}^{\text{-1}}{\text{a}}_{\text{j}}$
  • Right hand side of optimal table’s constraints = ${\text{B}}^{\text{-1}}\text{b}$
  • Coefficient of slack variable in row 0 = (ith element of ${\text{c}}_{\text{BV}}{\text{B}}^{\text{-1}}$).
  • Coefficient of excess variable in row 0 = -(ith element of ${\text{c}}_{\text{BV}}{\text{B}}^{\text{-1}}$) .
  • Coefficient of artificial variable in row 0 = (ith element of ${\text{c}}_{\text{BV}}{\text{B}}^{\text{-1}}$) + $\text{M}$ (max problem).
  • Right hand side of row 0 = ${\text{c}}_{\text{BV}}{\text{B}}^{\text{-1}}\text{b}$
• Hence the optimal solution is

  $\text{w = 58/3}$, ${\text{y}}_{\text{1}}\text{= -2/3}$, ${\text{y}}_{\text{2}}\text{= 0}$, ${\text{y}}_{\text{3}}\text{= 7/3}$

b.

Explanation of Solution

New Optimal solution

• For a maximization problem, the new optimal value = (old optimal value) + (Constraint i’s shadow price).
• For a minimization problem, the new optimal value = (old optimal value) – (Constraint i’s shadow price).
• Here the $\text{new optimal value = 58/3 + row 3 shadow price = 65/3}\text{.}$