DD3, DD4 - Minimisation and tableau interpretation

Equivalent objectives

If $C=C_0-P$, with $C_0$ constant, then minimising $C$ is equivalent to maximising $P$ over the same transformed feasible choices. Recover $C_{\min}=C_0-P_{\max}$ and undo every variable substitution. This transformation is not supplied in the AQA formula booklet.

Worked example 1: maximise the saving

Question. Minimise $C=3x+2y$ subject to $0\leq x\leq4$, $0\leq y\leq3$, $x+y\geq5$. Real quantities are allowed.

Plan. Measure omitted quantities from $(4,3)$, then maximise the saving using simplex.

Let $u=4-x$, $v=3-y$. Substitution gives

The original lower bounds also require $u\leq4$, $v\leq3$. They follow already from $u+v\leq2$ and nonnegativity, so omitting these redundant rows loses no choices. Set $P=3u+2v$ and add slack $r$:

Enter $u$, pivot on 1, and add three times the constraint row to the objective row. The final equation $P+v+3r=6$ certifies $P_{\max}=6$, at $u=2,v=0$.

Answer. $x=4-2=2$, $y=3-0=3$, and $C_{\min}=18-6=12$.

Check. The original point satisfies all bounds and $x+y=5$. Also $C=2(x+y)+x\geq10+x$. Since $y\leq3$, feasibility forces $x\geq2$, giving $C\geq12$. Our point attains this independent lower bound.

Worked example 2: a higher requirement reduces the saving

Question. Minimise the same cost under the same variable bounds, but require $x+y\geq6$.

Plan. Repeat the exact substitution, changing only the transformed demand limit.

Now $u+v\leq1$, and $C=18-P$, $P=3u+2v$. The initial rows in columns $P,u,v,r,\text{value}$ are $(1,-3,-2,0\mid0)$, $(0,1,1,1\mid1)$. Pivoting on $u$ gives

Answer. Maximum saving $P=3$ occurs at $u=1,v=0$. Thus $x=3,y=3$, and the minimum cost is $18-3=15$.

Check. $C=2(x+y)+x\geq12+x$, and $y\leq3$ now forces $x\geq3$. Thus $C\geq15$, achieved at our point. Raising demand has increased the minimum cost, as expected.

Watch out

The final tableau contains a maximum saving, not the minimum original cost. Preserve the constant $C_0$, recover the original variables, and check every original constraint. Never add arbitrary upper bounds to make a transformation convenient.

Worked example 3: a supplied basis makes negation useful

Question. Minimise $C=3x+y$ subject to $x+y\geq4$, $x+2y\leq10$, $x,y\geq0$. Use the feasible basis $x=4,s=6$, with nonbasic $y=r=0$, where $r=x+y-4$, $s=10-x-2y$.

Plan. Maximise $Q=-C$, first eliminating basic $x$ from its objective row.

The canonical constraint equations are $x+y-r=4$ and $y+r+s=6$. The latter comes from substituting the first into $x+2y+s=10$. Start with $Q+3x+y=0$, then subtract three times the $x$-row:

Enter $y$. Ratios 4 and 6 choose the $x$-row. Add twice that row to the objective row and subtract it from the last row:

Answer. Nonbasic $x=r=0$ gives $y=4,s=2,Q=-4$. Thus $C_{\min}=4$. The final row proves $Q\leq-4$, equivalently $C\geq4$.

Check. In the original model, $(0,4)$ gives total 4, uses 8 of the capacity 10, and costs 4. Independently, $C=(x+y)+2x\geq4$, so the attained cost is minimal.