Chapter 6, Problem 25RP

Program Plan Intro

Optimal solution:

• Consider the linear programming problem given below:
• max z= $2x_1+x_2+x_3$
• Subject to constraints:
  • $x_1+x_3\le 1$
  • $x_2+x_3\le 2$
  • $x_1+x_2\le 3$
  • $x_1,x_2,x_3\ge 0$

Explanation of Solution

b.

• The given LP is known as the primal. If the primal is a max problem, then the dual will be a min problem.
• Define the variables for the max problem to be $z,x_1,x_2,\mathrm{.........}{x}_n$ and the variables for the min problem to be $w,y_1,y_2,\mathrm{.........}{y}_n$
• max z= $c_1{x}_1+c_2{x}_2+\mathrm{......}+c_n{x}_n$
• subject to constraints:
  • $a_{11}{x}_1+a_{12}{x}_2+\mathrm{.....}+a_{1n}{x}_n\le b_1$
  • $a_{21}{x}_1+a_{22}{x}_2+\mathrm{.....}+a_{2n}{x}_n\le b_2$
  • $a_{m1}{x}_1+a_{m2}{x}_2+\mathrm{.....}+a_{mn}{x}_n\le b_m$
• The dual of the normal max problem is defined below:
• min w= $b_1{y}_1+b_2{y}_2+\mathrm{......}+b_n{y}_n$
• Subject to constraints:
  • $a_{11}{y}_1+a_{12}{y}_2+\mathrm{.....}+a_{1n}{y}_n\ge c_1$
  • $a_{21}{y}_1+a_{22}{y}_2+\mathrm{.....}+a_{2n}{y}_n\ge c_2$
  • $a_{m1}{y}_1+a_{m2}{y}_2+\mathrm{.....}+a_{mn}{y}_n\ge c_m$
• Given a max problem, the primal is read across the table and the dual is found by reading down.

min w		$\left(x_1\ge 0\right)$	$\left(x_2\ge 0\right)$	max z …	$\left(x_n\ge 0\right)$
		$x_1$	$x_2$		$x_n$
$\left(y_1\ge 0\right)$	$y_1$	$a_{11}$	$a_{12}$	$\dots$	$a_{1n}$	$\le b_1$
$(y_2\ge 0$

Explanation of Solution

c.

• Multiply the right-hand side of each constraint by a non-negative constant k.
  • $b=\left[\begin{array}{c}k\\ 2k\\ 3k\end{array}\right]$
• The right-hand side of the optimal table’s constraints can be found by calculating $B^{-1}b$
• $B^{-1}b=\left[\begin{array}{ccc}\frac{1}{2}& -\frac{1}{2}& \frac{1}{2}\\ -\frac{1}{2}& \frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& \frac{1}{2}& -\frac{1}{2}\end{array}\right]\left[\begin{array}{c}k\\ 2k\\ 3k\end{array}\right]$
• $B^{-1}b=[\begin{array}{c}k\\ \end{array}$