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

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.

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}$.