Past exam of the Probability, statistics and options II course of the University of Oxford / 2011 / T (Linear Programming)

With nonnegative production amounts $x_1,x_2,x_3$, the primal linear programme isIntroduce slacks $s_R,s_S\ge 0$. The initial basic variables are the slacks, and the reduced profits of the goods are $5,6,3$. The greatest is six, so $x_2$ enters. The ratio test compares $6/2=3$ and $11/3$, so $s_R$ leaves. The resulting dictionary iswith profit $18-7x_1+3x_3-3s_R$. The greatest positive reduced profit is now three, so $x_3$ enters; its only positive pivot coefficient is two in the second row, and $s_S$ leaves. The final tableau, expressed as equations, isAll nonbasic reduced profits are nonpositive, proving optimality atThe ordered optimal basis is $(x_2,x_3)$, henceThe inverse is read from the two slack columns of the final basic equations.

The dual prices $u,v\ge 0$ solveThe optimal tableau gives $(u,v)=c_B^T{B}^{-1}=(6,3)B^{-1}=(3/4,3/2)$. This vector is dual feasible and has objective $21$, equal to the primal value, proving optimality.

Thus an extra unit of R is worth $3/4$ while the current basis stays feasible. Increasing its supply by $\delta$ changes the basic values toFor increases, feasibility is retained exactly up to $\delta =4/3$. Therefore the firm can buy up to $4/3$ extra units at a marginal value of $3/4$ per unit. The reduced profits do not change during this right-hand-side variation.

For the proposed fourth good, the reduced profit is $8-(4u+4v)=8-9=-1$. Its profit is below the resource opportunity cost, so it is not worth producing at the current optimum. The old dual solution also satisfies the new good's inequality, certifying that introducing it cannot improve the optimum.

In the $(u,v)$ plane the feasible set lies in the first quadrant above the three lines $v=3/2$, $v=5/2-2u$ and $v=2-(2/3)u$. Its lower boundary has verticesand the region is unbounded upward and to the right. The objective at these vertices is respectively $21$, $43/2$ and $55/2$, so $A$ is optimal for the original supply.

Let the available amount of R be $r\ge 0$. Comparing the three dual vertex objectives gives the optimal valueThus the marginal shadow price of R is $3/4$ below $22/3$, then $3/8$ between $22/3$ and $22$, and zero beyond $22$. At the two breakpoints, optimal dual prices range between the adjacent one-sided prices: $[3/8,3/4]$ and $[0,3/8]$ respectively. At zero supply the right marginal value is $3/4$; dual multipliers on the zero resource can be nonunique. These slope changes describe why the first extra $4/3$ units from the original supply six have the original price, but subsequent units do not.