The University of Hong Kong · FACULTY OF MATHEMATICS

DASE7034 Chap.4 Simplex Edge Cases and Artificial Variables

- one subject, every graph, every model, every mark
5 Chapters3-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 4 of 12 · DASE7034

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.

In this chapter

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

Q [9 marks]. This example's weighting is not a University-published mark allocation. Classify a zero reduced cost, a missing leaving row and a positive artificial variable.
Three tableau signals lead to three different conclusions.Three tableau signals lead to three different conclusions. Zero reduced cost, a missing leaving row and a positive artificial variable must never be conflated.optimality testzero reduced costalternate optimumno leaving rowunboundedartificial > 0infeasible
Three tableau signals lead to three different conclusions. Zero reduced cost, a missing leaving row and a positive artificial variable must never be conflated.
  • 3Match each signal to the model property.
  • 3State the modelling implication.
  • 3Name the appropriate repair or next step.
An eligible zero reduced cost at optimum indicates a possible alternate optimal basis. An improving variable with no positive pivot-column entry gives an unbounded direction. A positive artificial variable after the feasibility phase proves infeasibility. Use a secondary criterion, find the missing limit or reconcile conflicting constraints respectively. The step weighting here was created for AskSia revision and is not the University's published marking scheme.
Sia tip — Label the signal before changing the tableau; different endings require different modelling repairs.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your DASE7034 tutor, unlimited, worked the way the exam marks it
The full 3-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works