Question

Write the dual to the following linear program.

$$\begin{gathered} maxx+y \\ 2x+y⩽3 \\ x+3y⩽5 \\ x,y⩾0 \end{gathered}$$

Find the optimal solutions to both primal and dual LPs

Short answer

Dual LP:

$Minimize3a+5b$

Subject to

$$\begin{gathered} 2a+b⩾1 \\ a+3b⩾1 \\ a,b⩾0 \end{gathered}$$

Solution of primal LP, $x=\frac{4}{5}$,$y=\frac{7}{5}$ .

Solution of dual LP is $a=\frac{2}{5}$ ,$b=\frac{1}{5}$

Step-by-step solution

Explain Duality in Linear programming.

Every linear maximization problem has a dual minimization problem, and they relate to each other. Any feasible value of the dual LP is an upper bound on the original primal LP. For any feasible solution of the dual is an upper bound on any feasible solution of the primal.

Step 2:Derive the dual LP and the optimal solutions of primal, dual LP. 

Consider the given Linear programming,

$$\begin{gathered} \max x+y \\ 2x+y⩽3 \\ x+3y⩽5 \\ x,y⩾0 \end{gathered}$$

To find the dual LP, minimize the maximum value with multipliers as follows,$\min 3a+5b$

Subject to

$$\begin{gathered} 2a+b⩾1 \\ a+3b⩾1 \\ a,b⩾0 \end{gathered}$$

Therefore, the above bound is the dual LP.

Consider the primal LP, and with the multipliers and Inequality,

For the value of X

$$\begin{gathered} 2x+y⩽3 \\ x+3y⩽5 \\ 5x⩾4 \end{gathered}$$

For the value of Y

$$\begin{gathered} 2x+y⩽3 \\ x+3y⩾5 \\ 5y⩾7 \end{gathered}$$

Therefore, the optimal solution of primal LP is $x=\frac{4}{5}$, $y=\frac{7}{5}$,

Consider the dual LP,

$\min 3a+5b$

$$\begin{gathered} 2a+b⩾1 \\ a+3b⩾1 \\ a,b⩾0 \end{gathered}$$

Compare, inequality as follows,

$$\begin{gathered} 2a+b⩾1 \\ a+3b⩾1 \\ 2a+5b⩽1 \\ a,b⩾0 \end{gathered}$$

Therefore, the optimal solution of dual LP is $a=\frac{2}{5}$ , $b=\frac{1}{5}$.