Practice: Transforming the Variables

Classify. $m$ is bounded below by $3$; $n$ is unrestricted; $k$ is nonpositive.

Substitutions. $m=u+3$ with $u\ge 0$; $n=n^{+}-n^{-}$ with $n^{\pm }\ge 0$; $k=-w$ with $w\ge 0$.

Objective.

Maximising this is maximising $6u+2n^{+}-2n^{-}+5w$ with the constant $18$ held aside. Negating for a minimisation:

First constraint. $(u+3)+(n^{+}-n^{-})+(-w)\le 25$, so $u+n^{+}-n^{-}-w\le 22$. With a slack: $u+n^{+}-n^{-}-w+s_1=22$, $s_1\ge 0$.

Second constraint. $(u+3)-(n^{+}-n^{-})\ge 4$, so $u-n^{+}+n^{-}\ge 1$. With a surplus: $u-n^{+}+n^{-}-e_1=1$, $e_1\ge 0$.

Discard the absorbed restrictions. $m\ge 3$ is gone into $u\ge 0$; the declarations that $n$ is free and $k$ nonpositive are replaced by nonnegativity on their substitutes.

Result.

subject to $u+n^{+}-n^{-}-w+s_1=22$, $u-n^{+}+n^{-}-e_1=1$, and $u,n^{+},n^{-},w,s_1,e_1\ge 0$.

Reading back. If the minimum is $z$, the original maximum is $-z+18$. The original variables are $m=u+3$, $n=n^{+}-n^{-}$, $k=-w$.

What the shift touched. Two places, not one: the constant $18$ in the objective, and the right-hand sides, which moved from $25$ to $22$ and from $4$ to $1$. Both come from the same substitution.

Recover the original variable in each run. Run A: $q=7-0=7$. Run B: $q=11-4=7$.

They are the same solution. Both runs set $q=7$. There is one plan here, reported in two different spellings of the same value.

Why both spellings are optimal. The split is not unique: for any $t\ge 0$, the pair $(q^{+}+t,q^{-}+t)$ gives the same difference. Run B is Run A with $t=4$. The objective contains $c(q^{+}-q^{-})$, so the $t$ cancels there too and the value is unchanged at $340$, which is exactly what the reports show.

So the converted program does have infinitely many optimal solutions. The entire ray $\{(7+t,t):t\ge 0\}$ is optimal. That is a property of the conversion, not a property of the original problem.

The error in the conclusion. 'Flexibility in how we set $q$' would mean several distinct values of $q$ attaining the optimum. Nothing here shows that; $q=7$ in both runs. The analyst has mistaken a redundancy in the representation for a choice in the plan.

What genuine flexibility would look like. Two reported solutions whose recovered values differ, say $q=7$ in one and $q=11$ in another, both with objective $340$. That would be multiple optima in the original problem, caused by the objective being parallel to a binding constraint, and it would be worth reporting.

The habit that prevents this. Always recover and report the original variables. The recovery rule is part of the conversion, and a solution expressed in converted variables has not yet been read back into the problem that was asked.

A basis cannot contain both. If $A_{q^{-}}=-A_{q^{+}}$, the two columns are linearly dependent. One is $(-1)$ times the other. A basis is a set of independent columns, so no basis contains both. At most one member of the pair is ever basic.

Consequently at most one is ever positive at a basic feasible solution. Nonbasic variables are zero, so if only one of the pair can be basic, the other is zero. A basic feasible solution therefore always has $q^{+}=0$ or $q^{-}=0$, and the split is unique at the corners even though it is not unique in general.

This is the reconciliation. Earlier the ray $\{(q^{+}+t,q^{-}+t)\}$ was all optimal, which suggested infinitely many optimal solutions. Those interior points of the ray are feasible but are not basic feasible solutions. They have both members positive and so cannot arise from any basis. The simplex method, which only ever visits basic feasible solutions, never reports one.

Why no difficulty arises in practice. The method returns a corner, where exactly one of the pair is positive, so the reported split is the tidy one: $q=7$ comes back as $(7,0)$ rather than $(11,4)$. The non-uniqueness is real and is invisible to an algorithm that walks corners.

What still requires care. Two different runs may return different corners, and any reported solution must still be read back through $q=q^{+}-q^{-}$ before it is a statement about the original problem. And if a solution arrives from a method that does not restrict itself to corners, an interior-point method, for instance, both members can be positive and the recovery step is the only thing that makes the answer intelligible.

Why this is the transfer. The substitution was introduced as bookkeeping performed once. It quietly changes the structure of the constraint matrix, and the consequence surfaces much later, in which column sets can be bases at all.