MATH2070 Chap.3 Nonstandard Linear Programs
Nonstandard Linear Programs
Nonstandard constraints may lack the obvious slack-variable starting basis used by simplex. This chapter distinguishes slack, surplus and artificial variables, reverses inequalities correctly when a negative right-hand side is multiplied by minus one, and splits unrestricted variables into non-negative parts. Phase I minimises the artificial-variable total to find a feasible basis or prove infeasibility.
Phase II restores the original objective, while Big M provides a penalty-based alternative. A zero Phase I optimum establishes feasibility but does not by itself finish the transition: artificial columns must be removed, zero artificial basic variables handled and the genuine objective rebuilt for the current basis.
A positive auxiliary optimum proves that the original constraints cannot be satisfied without fictitious quantities. Equality rows, lower-bound constraints and free variables each require transformations that preserve the original feasible choices.
Keeping those roles explicit prevents auxiliary variables from leaking into the final decision interpretation and separates feasibility construction from later economic optimisation.
What this chapter covers
- 01
Equivalent transformations
- 02
Surplus variables
- 03
Artificial variables
- 04
Phase I feasibility
- 05
Phase II optimisation
- 06
Big M penalties
Worked example · free
Build an auxiliary feasibility problem
- 1Add surplus and artificial variables.
- 1Write the auxiliary objective.
- 1Find a zero-artificial feasible point.
- 1Restore the original objective.
Key terms
- Surplus variable
- A non-negative amount subtracted from a lower-bound constraint to form an equality.
- Artificial variable
- A temporary quantity used only to construct an initial basis.
- Phase I
- The auxiliary simplex problem that searches for a feasible basis.
- Big M method
- A single-phase method that penalises artificial variables with a dominating objective coefficient.
- Auxiliary objective
- The temporary Phase I objective that minimises the total artificial amount. A zero optimum supports feasibility of the original constraints, while a positive optimum proves that fictitious variables remain necessary.
- Redundant row
- An equation that adds no restriction beyond the remaining equations. During Phase I cleanup, a zero row with no usable genuine pivot coefficient may be removed after its redundancy is established.
Nonstandard Linear Programs FAQ
What does a positive Phase I optimum mean?
It means at least one artificial variable must remain positive, so no point satisfies every original constraint. The original linear programme is infeasible regardless of the apparent value of its objective.
Why is a surplus variable subtracted?
A greater-than constraint allows activity above a required minimum. Subtracting a non-negative surplus records how far the left side exceeds the lower bound while preserving equality.
When must the original objective be rebuilt?
After Phase I reaches zero and artificial variables are removed, replace the auxiliary objective with the original one and eliminate current basic-variable coefficients so reduced costs match the feasible Phase II basis.
Exam move
Create a conversion sheet with one row each for less-than, greater-than and equality constraints. For every form, record whether a slack or surplus variable is added, whether a natural basic column appears, and when an artificial variable is needed. Practise multiplying a negative right-hand side by minus one before adding variables, remembering that the inequality reverses.
Also rehearse replacing a free variable by the difference of two non-negative variables. When constructing Phase I, label artificial variables visually and write the auxiliary objective in words: minimise the total artificial amount needed to satisfy the enlarged system.
Build the starting basis, eliminate basic artificial coefficients from the auxiliary objective row and check that the initial dictionary represents the stated equations. This prevents Phase I from becoming a memorised row-operation ritual with no feasibility interpretation. Use three outcome drills. A positive auxiliary optimum proves the original constraints infeasible.
A zero optimum with all artificial variables non-basic permits their columns to be removed. A zero-valued artificial variable still in the basis requires either a pivot using a genuine coefficient or deletion of a redundant zero row. Explain which case holds before restoring the original objective, and never let an artificial variable re-enter Phase II.
During restoration, substitute the current basic variables into the original objective so its row is consistent with the feasible basis. Continue ordinary simplex only after that audit. Finish by translating the solution into original variables and checking every original equality and inequality, excluding all auxiliary quantities from the interpretation.
For spaced revision, alternate a standard-form conversion, a Phase I diagnosis and a short full two-phase problem. Keep an error log for sign reversal, variable role, auxiliary-objective setup and objective restoration; each category points to a different repair.
Working through Nonstandard Linear Programs in MATH2070? Sia is AskSia’s AI Mathematics tutor — ask any MATH2070 Nonstandard Linear Programs question and get a clear, step-by-step explanation grounded in how MATH2070 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
