Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the following linear program:
maximize $\sum\limits_{j = 1}^n {{p_j}{x_j}}$
subject to $\sum\limits_{j = 1}^n {{q_j}{x_j}} \le \beta$
$\begin{array}{*{20}{c}} {{x_j} \le 1}&{j = 1,2, \ldots ,n} \end{array}$
$\begin{array}{*{20}{c}} {{x_j} \ge 0}&{j = 1,2, \ldots ,n} \end{array}$
Here, the numbers ${p_j},j = 1,2, \ldots ,n$ are positive and sum to one. The same is true of the ${q_j}$ ’s:
$\sum\limits_{j = 1}^n {{q_j} = 1}$
${q_j} > 0$
Furthermore, assume that
$\frac{{{p_1}}}{{{q_1}}} < \frac{{{p_2}}}{{{q_2}}} < \cdots < \frac{{{p_n}}}{{{q_n}}}$
and that the parameter $\beta$ is a small positive number. Let $k = \min \{ j:{q_{j + 1}} + \cdots + {q_n} \le \beta \}$. Let ${y_0}$ denote the dual variable associated with the constraint involving $\beta$, and let ${y_j}$ denote the dual variable associated with the upper bound of 1 on variable ${x_j}$. Using duality theory, show that the optimal values of the primal and dual variables are given by
${x_j} = \left\{ {\begin{array}{*{20}{l}} 0&{j < k}\\ {\frac{{\beta - {q_{k + 1}} - \cdots - {q_n}}}{{{q_k}}}}&{j = k}\\ 1&{j > k} \end{array}} \right.$
${y_j} = \left\{ {\begin{array}{*{20}{l}} {\frac{{{p_k}}}{{{q_k}}}}&{j = 0}\\ 0&{0 < j \le k}\\ {{q_j}\left( {\frac{{{p_j}}}{{{q_j}}} - \frac{{{p_k}}}{{{q_k}}}} \right)}&{j > k} \end{array}} \right.$.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

This is a fairly famous problem. It's the linear programming relaxation of the 0-1 knapsack problem. The problem here is to show that the greedy solution is optimal. Part of what makes that interesting is that the 0-1 knapsack problem itself is NP-complete: Not only is the greedy solution not guaranteed to be optimal for 0-1 knapsack, there's not even a known "fast" optimal algorithm for solving it!

To show what you're trying to show, first you have to construct the dual problem. This is

$$\begin{align} \text{minimize } &\beta y_0 + \sum_{j=1}^n y_j, \\ \text{subject to } &q_j y_0 + y_j \geq p_j, \ \ j = 1, 2, \ldots, n, \\ & y_j \geq 0. \end{align}$$

Then, verify that the primal solution given and the dual solution given have the same objective function value (by substituting them into their respective objective functions). The primal solution has objective function value $$p_k \frac{{\beta - {q_{k + 1}} - \cdots - {q_n}}}{{{q_k}}} + \sum_{j > k} p_j.$$ The dual solution has objective function value $$\beta \frac{p_k}{q_k} + \sum_{j > k} q_j \left(\frac{p_j}{q_j} - \frac{p_k}{q_k}\right).$$ A little algebra shows that they are equal.

Finally, verify that both the primal solution given and the dual solution given are feasible. I'll let you do that. By weak duality, then, the given primal and dual solutions are both optimal.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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