Chapter 6, Problem 14RP

a.

Explanation of Solution

To find optimal solution of dual of LP:

• The given problem is a non normal max problem.
• To find the dual of LP follow the below steps,
  • The primal can be read as follows,

Minimize w	${\text{x}}_{\text{1}}$	max z ${\text{x}}_2$
${\text{y}}_{\text{1}}$	2	1	$\le 4$
${\text{y}}_2$	3	2	$\ge 6$
${\text{y}}_3$	4	2	=7
	$\ge 3$	$\ge 1$

• The dual variable “${\text{y}}_2$” should satisfy the condition “${\text{y}}_2\le 0$” because the second primal constraint is a “$\ge$” constraint.
• The inequality constraint is exist in third primal constraint and hence the dual variable “${\text{y}}_3$” will not be restricted to sign.
• The dual of the given LP is obtained by reading the following table,

	Minimize w	${\text{x}}_{\text{1}}$	max z ${\text{x}}_2$
${\text{y}}_{\text{1}}\ge 0$	${\text{y}}_{\text{1}}$	2	1	$\le 4$
${\text{y}}_2\le 0$	${\text{y}}_2$	3	2	$\ge 6$
${\text{y}}_3$ urs	${\text{y}}_3$	4	2	=7
		$\ge 3$	$\ge 1$

• The dual of Linear Programming (LP) is given as follows,

  $\begin{array}{l}{\text{minimize w = 4y}}_{\text{1}}{\text{+ 6y}}_{\text{2}}{\text{+ 7y}}_{\text{3}}\hfill \\ \text{ s}\text{.t}{}_{}\hfill \end{array}$

b.

Explanation of Solution

To determine the range of values:

• If the right hand side of the third constraint is changed to “$7+\Delta$”, then the right hand of the constraints will be as follows,

$\left[\begin{array}{ccc}1& 0& \frac{-1}{2}\\ 0& 2& \frac{-3}{2}\\ 0& -1& 1\end{array}\right]\left[\begin{array}{c}4\\ 6\\ 7+\Delta \end{array}\right]=\left[\begin{array}{c}\frac{1-\Delta }{2}\\ \frac{3-3\Delta }{2}\\ 1+\Delta \end{array}\right]$

• The current basis remains optimal for the values of “$\Delta$” in the range from “-1” to “1” or for the values of “${\text{b}}_{\text{3}}$” in the range from “6” to “8”.

New optimal solution when right hand side of third constraint is “$\raisebox{1ex}{$15$}\!\left/ \!\raisebox{-1ex}{$2$}\right.$”:

• The values of “$\Delta$” is “$\frac{1}{2}$”, if the value of “${\text{b}}_{\text{3}}$” is “$\frac{15}{2}$”