Chapter 6, Problem 18RP

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}}$	4	3	$\ge 6$
${\text{y}}_2$	1	2	$\le 3$
${\text{y}}_3$	3	1	=3
	$\ge -\text{4}$	$\ge -1$

• The dual variable “${\text{y}}_1$” should satisfy the condition “${\text{y}}_{\text{1}}\le 0$” because the first 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}}\le 0$	${\text{y}}_{\text{1}}$	4	3	$\ge 6$
${\text{y}}_2\ge 0$	${\text{y}}_2$	1	2	$\le 3$
${\text{y}}_3$ urs	${\text{y}}_3$	3	1	=3
		$\ge -\text{4}$	$\ge -1$

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

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

b.

Explanation of Solution

“No”, the current optimal solution is no longer optimal.

Explanation:

Given:

The changed LP is,

$\begin{array}{l}\text{max z=}-{\text{4x}}_1-{\text{x}}_2-{\text{x}}_3\\ \text{s}\text{.t}\text{.}{\text{4x}}_1{\text{+3x}}_2{\text{+x}}_3\ge 6\\ {\text{x}}_1{\text{+2x}}_2{\text{+x}}_3\le 3\\ 3{\text{x}}_1{\text{+x}}_2{\text{+x}}_3=3\\ {\text{x}}_1\text{,}{\text{x}}_2\text{,}{\text{x}}_3\ge 0\end{array}$

To calculate “$\overline{{\text{c}}_{\text{j}}}$”:

“$\overline{{\text{c}}_{\text{j}}}$” is computed using the following formula,

$\overline{{\text{c}}_{\text{j}}}{\text{=c}}_{\text{BV}}{\text{B}}^{-\text{1}}{\text{a}}_{\text{j}}-{\text{c}}_{\text{j}}$

Price out “${\text{x}}_3$”   as follows,  

$\overline{{\text{c}}_3}{\text{=c}}_{\text{BV}}{\text{B}}^{-\text{1}}{\text{a}}_3-{\text{c}}_3$

Where,

${\text{a}}_3=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]$

${\text{c}}_{\text{BV}}\text{=}\left[\begin{array}{ccc}-\text{1}& -\text{4}& \text{0}\end{array}\right]$

${\text{B}}^{-1}\text{=}[\begin{array}{ccc}\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$5$}\right.& 0& \raisebox{1ex}{$-$}\!\left/ \!\raisebox{-1ex}{$$}\right.\end{array}$