# knapsack problem using duality

I have this knapsack problem

\begin{align} \max {z}=10&x_1+8x_2-13x_3 +10x_4+10x_5 + 5x_6\\[0.4cm] \text{s.t. }\quad\,\,\,7&x_1+6x_2+10x_3+\,\,\,8x_4 +\,\,\,9x_5 + 5x_6\le39 \\[0.2cm]& x_i\ge0 \end{align}

and I want to solve it using duality. I have converted it to dual but I don't know what to do next. The (D) is:

\begin{cases} \text{min }w=&39y\\ &7y \ge 10\\ &6y \ge 8\\ &10y \ge 13\\ &8y \ge 10\\ &9y \ge 10\\ &5y \ge 5\\ \end{cases}

• just take the minimum admissible value of $y$. – Jimmy R. Feb 18 '16 at 11:47
• Don't you have an integrality constraint? – LinAlg Feb 3 '17 at 11:36

Once you have got the dual problem, you can see that each constraint is of the following form:
$\qquad a_iy >= c_i$

Now choose the minimum y such that all these constraints are satisfied, i.e., set y to
$\qquad max (c_i/a_i)\; ∀ i.$
$\qquad i.e.\;y = 10/7$

Since the objective function is a constant times y, your solution is optimal.
So the optimal solution is $39*10/7 = 390/7$.
Now a quick observation of the primal problem reveals that $x_1 = 39/7$ and other primal variables at $0$ achieves the optimal value z = 390/7 and satisfies the constraints as well.

• maybe add how to obtain $x$ from $y$ – LinAlg Feb 3 '17 at 11:37
• @LinAlg added that part too. – infobliss Feb 4 '17 at 11:31