DASE7034 Chap.4 Simplex Edge Cases and Artificial Variables
Simplex Edge Cases and Artificial Variables
Terminal tableaus can describe alternate optimal solutions, unbounded improvement or infeasibility.
A zero reduced cost for an eligible non-basic variable can reveal another optimum; an improving column with no leaving row reveals an unbounded direction; and a positive artificial variable after the feasibility phase proves that the original constraints have no common feasible point.
Distinguish algebraic symptoms from conclusions
A tableau feature has meaning only after the current basis and sign convention are established.
At an optimal tableau, an eligible non-basic variable with zero reduced cost can enter without changing the objective, revealing another optimal basis and possibly an optimal edge. Degeneracy is different: a basic variable is zero, so a pivot may change the basis without moving to a different geometric point.
The objective can remain unchanged in both cases, but only the reduced-cost and feasible-direction evidence establishes alternate optimality.
Recognise an unbounded improving direction
If a non-basic variable can improve the objective and its pivot column has no strictly positive entry eligible for the ratio test, the variable can increase without forcing a basic variable below zero.
This is evidence that the objective is unbounded in that direction. It is not the same as an unbounded feasible set, because an open feasible region can still have a finite optimum when the objective points elsewhere.
In an applied model, unboundedness often exposes a missing capacity, balance or demand constraint.
Use artificial variables only to obtain feasibility
Greater-than and equality constraints may not supply an obvious starting basis. Surplus variables remove excess from a greater-than relationship but do not create a unit column, so an artificial variable can temporarily provide a basis.
In a two-phase method, Phase I minimises the sum of artificial variables or an equivalent objective. If the best Phase I value remains positive, the original constraints cannot be satisfied together. If it reaches zero, remove artificial variables correctly before restoring the original objective.
Give the right operational diagnosis
Each exceptional outcome needs a different response.
With alternate optima, compare secondary considerations such as robustness or implementation cost. With unboundedness, identify the missing limitation instead of reporting an infinite operating recommendation. With infeasibility, locate conflicting requirements, data errors or policy combinations and quantify a useful relaxation where possible.
When degeneracy appears, preserve careful pivot bookkeeping and consider an anti-cycling rule. The closing explanation should connect the tableau evidence to the geometry and to the model revision it motivates.
What this chapter covers
- 01
Alternate optimal bases
- 02
Unbounded improving directions
- 03
Artificial starting variables
- 04
Infeasibility certificates
- 05
Degenerate pivots
Worked example · free
Diagnose three tableau endings
- 3Match each signal to the model property.
- 3State the modelling implication.
- 3Name the appropriate repair or next step.
Key terms
- Artificial Variable
- A temporary variable introduced to create a starting basis when no natural slack basis exists.
- Unbounded Model
- A model whose objective can improve without limit along a feasible direction.
- Alternate Optimum
- A distinct feasible solution attaining the same best objective value.
Simplex Edge Cases and Artificial Variables FAQ
What does a zero reduced cost mean at optimum?
For an eligible non-basic variable, it means the variable can enter without changing the objective, potentially producing another optimal corner. Pivoting reveals a second endpoint of an optimal edge or confirms degeneracy.
Why does no leaving row indicate unboundedness?
If an improving entering variable has no strictly positive coefficient in any constraint row, increasing it never forces a current basic variable below zero. The objective can therefore improve indefinitely within the modeled constraints.
Should an artificial variable appear in the final recommendation?
No. It has no physical interpretation and exists only to construct a starting basis. If it remains positive after the feasibility phase, the original model is infeasible and must be revised.
Exam move
Create three flash cards with the signal on one side and the conclusion plus repair on the other. For every unusual tableau, test feasibility first, boundedness second and uniqueness third. This order prevents a secondary signal from hiding a more fundamental failure. Practise the transition from Phase I to Phase II separately.
Verify that the auxiliary objective is zero, inspect every artificial variable, pivot a zero-valued artificial variable out when possible and justify removal of any redundant row. Rebuild the original objective using the retained basis before continuing. For each diagnostic answer, use three sentences: identify the symptom, cite the exact tableau evidence and state the operational consequence.
Alternate optimality needs an eligible zero reduced cost and a feasible alternative direction; unboundedness needs an improving column with no positive ratio entry; infeasibility needs a positive minimum artificial residue. Then name the repair: apply a secondary selection criterion, add or correct a missing limit, or reconcile conflicting requirements.
Compare degeneracy with alternate optimality in a small example so that an unchanged objective after a pivot is not treated as sufficient evidence of multiple optima.
Working through Simplex Edge Cases and Artificial Variables in DASE7034? Sia is AskSia’s AI Mathematics tutor — ask any DASE7034 Simplex Edge Cases and Artificial Variables question and get a clear, step-by-step explanation grounded in how DASE7034 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.