Chapter 6.5, Problem 6P

Explanation of Solution

Duals of LP:

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

a.

• To find the dual of the above LP proceed as follows:
• Step 1:

Max z
min w	($x_1\ge 0$)	($x_2\ge 0$)
	$x_1$	$x_2$
$\left(y_1\ge 0\right)$	$y_1$	1	1	$\le 1$
	$y_2$	-1	1	$\ge 2^{*}$
	$\ge 3$	$\ge 1$

• Step 2:
  • In this case, the second primal constraint is $\ge$ and therefore dual variable $y_2$ must satisfy $y_2\le 0$.
  • The asterisk (*) sign represents the places where rules must be applied to determine part of the dual

Explanation of Solution

b.

• As the above linear programming problem is not a normal max problem, therefore the following steps are to be performed to convert it into a normal form.
• Step 1: Multiply each $\ge$ constraint by -1 as mentioned below:
  • $-x_1+x_2\ge 2$
  • $-1(-x_1+x_2)\le -2$
  • $x_1-x_2\le -2$
• Step 2:
  • Replace the equality constraint by two inequality constraints as,
  • There is no equality constraint in this LP.
• Step 3:
  • Now replace each urs variable x_i by $x_i=x_i^{\text{'}}-x_i^{\text{'}\text{'}}$ as there is no urs variable in the given LP.
• Now write the transformed LP as,
• max z= $3x_1+x_2$
• Subject to constraints:
  • $x_1+x_2\le 1$
  • $x_1-x_2\le -2$
  • $x_1,x_2\ge 0$
• Construct the following table according to the given LP,

Min W

$(x_1\ge 0$

Explanation of Solution

c.

• Now put ${\overline{y}}_2=-y_2$ in the part (b) answer. So that,
• min w= $y_1+2y_2\mathrm{.....}(2)$
• Subject to constraints
  • $y_1-y_2\ge 3$
  • $y_1+y_2$