Past exam of the Probability, statistics and options II course of the University of Oxford / 2007 / T / 2

Let $x_j\ge 0$ be the production amounts of the three distinct products; the repeated first-product labels in the printed table are interpreted using the surrounding text and the three separate columns. The linear program is

Introduce nonnegative slack variables $s_1,s_2$ and use a simplex tableau with the last row representing $z-c^{\mathsf{T}}x=0$. The starting tableau isEnter $x_3$ and let $s_2$ leave. Dividing the second row by three and eliminating its column givesEnter $x_1$ and let $s_1$ leave. The next simplex tableau isThusThe pivot choices and the optimality certificate are justified in the following parts.

For this tableau sign convention, a negative coefficient in the objective row means the corresponding nonbasic variable can increase profit. Initially $x_3$ has the most negative coefficient. The simplex ratio test gives $33/5$ in row one and $18/3=6$ in row two, so row two leaves to preserve feasibility. Next $x_1$ is the only column with a negative objective coefficient. The ratios are $3/(1/3)=9$ and $6/(1/3)=18$, so row one leaves. All resulting basic variables remain nonnegative.

The last objective row is $z+x_2+s_1+s_2=51$. Every feasible solution has nonnegative $x_2,s_1,s_2$, so $z\le 51$. The displayed basic feasible solution has all three zero and attains 51, proving optimality. Equivalently, the resource dual prices $(1,1)$ give the same upper bound $33+18=51$ and satisfy complementary slackness.

In the usual linear programming sensitivity within a fixed optimal basis, retain the optimal basis $\{x_1,x_3\}$ while allowing its values to adjust. If the second resource amount is $b$, thenThe dual prices remain $(1,1)$, so optimality persists exactly while both basic variables are nonnegative:The optimal profit on that range is $33+b$. At the endpoints the basis is degenerate but remains optimal. If the wording is instead read as requiring the exact numerical production vector $(9,0,3)$ to remain unchanged and optimal, only $b=18$ does so; the standard allowable range concerns the basis and its adjusted solution.

Let the third profit coefficient be $c_3$. For the same basis, the resource dual prices solve $2y_1+y_2=3$ and $5y_1+3y_2=c_3$, givingDual feasibility requires $y_1,y_2\ge 0$ and $3y_1+2y_2\ge 4$. These inequalities are $c_3\le 9$, $c_3\ge 15/2$ and $c_3\ge 7$, respectively. HenceThe production vector is unchanged because the resource constraints are unchanged. Equality at a boundary can allow additional optimal solutions.

Changing only the second profit coefficient leaves the dual prices at $(1,1)$, because the basic products remain one and three. The nonbasic product has nonpositive reduced cost exactly when $c_2\le 3(1)+2(1)=5$. ThereforeThere is no mathematical lower bound; if profit coefficients are additionally restricted to be nonnegative, intersect this range with $[0,\infty )$. At $c_2=5$, alternate optimal solutions are possible.

At the current dual prices $(1,1)$, the new product has reduced cost $5-(1+2)=2>0$, so it can increase profit. Its transformed resource column isIncreasing $x_4$ by $t$ changes the old basic variables to $x_1=9+7t$ and $x_3=3-3t$. Thus $x_3$ leaves at $t=1$, givingFor a certificate, take dual prices $(1/3,7/3)$. They price the four products at $3,17/3,26/3,5$, respectively, each at least its profit. Their resource total is $33/3+18(7/3)=53$, equal to the achieved profit. Weak duality proves optimality, and the profit has increased by two.