# Verifying optimality for given primal and dual solutions to a linear program

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

-

\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.