Chapter 6, Problem 13RP

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

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

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

b.

Explanation of Solution

To determine the range of values:

• The basic variables are found from the optimal table.
• Here, the basic variables are “${\text{s}}_1$”, and “${\text{x}}_3$” and it is known from the table “58” of the textbook.
• “$\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}}$

• The matrix “${\text{B}}^{-\text{1}}$” is the columns for the slack variables in the optimal table constraints.

${\text{B}}^{-1}\text{=}\left[\begin{array}{cc}1& -1\\ 0& 1\end{array}\right]$

• To compute “${\text{c}}_{\text{BV}}{\text{B}}^{-\text{1}}$”, consider “${\text{c}}_{\text{j}}$” are the coefficients of the objective unction and hence “${\text{c}}_3=2+\Delta$”.
• The computation of “${\text{c}}_{\text{BV}}{\text{B}}^{-\text{1}}$” is as follows,

$\begin{array}{c}{\text{c}}_{\text{BV}}{\text{B}}^{-\text{1}}\text{=}\left[\begin{array}{cc}0& 2+\Delta \end{array}\right]\left[\begin{array}{cc}1& -1\\ 0& 1\end{array}\right]\\ =\left[\begin{array}{cc}0& 2+\Delta \end{array}\right]\end{array}$

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

$\begin{array}{c}\stackrel{}{{\text{c}}_1}\end{array}$

c.

Explanation of Solution

To determine the range of values:

• The basic variables are found from the optimal table.
• Here, the basic variables are “${\text{s}}_1$”, and “${\text{x}}_3$” and it is known from the table “58” of the textbook.
• Here, “${\text{B}}^{-\text{1}}$”, “b”, and “${\text{c}}_{\text{BV}}$” are unchanged as “${\text{x}}_1$” is a non basic variable.
• “$\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}}$

• To compute the new row “0” relate to “${\text{c}}_1=4+\Delta$”