Question $2.(20$PTS$)$

This answer should fit on: $2$ page$($s$).$

Follow the Rules on how to write solutions to assignments and exams posted on the course page!!!

Consider the following knapsack linear program,

max$\{{\displaystyle \underset{j=1}{\overset{n}{}}}{w}_j{x}_j$:${\displaystyle \underset{j=1}{\overset{n}{}}}{}_j{x}_j,x0\},$

where all parameters ${}_j,w_j$ and $$ are positive values.

$($a$)$ Write the dual $($D$)$ of $($P$).$

$($b$)$ Write the Complementary Slackness $($CS$)$ conditions for $($P$)$ and $($D$).$

Assume now that that for all $j=2,$dots,$n$ the following inequality holds:

$\frac{w_1}{{}_1}\frac{w_j}{{}_j}.$

$($c$)$ Find an pair of optimal solutions $x$ and $y$ for $($P$)$ and $($D$)$ respectively.

$($d$)$ Prove using the CS theorem, that $x$ and $y$ are indeed optimal.