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}

  • $\begingroup$ just take the minimum admissible value of $y$. $\endgroup$ – Jimmy R. Feb 18 '16 at 11:47
  • $\begingroup$ Don't you have an integrality constraint? $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.