The equality x₁−x₂=2 with nonnegative variables has feasible solutions, but setting both original variables to zero does not satisfy it. Introduce a nonnegative artificial variable a and write x₁−x₂+a=2. The artificial basis a=2 supplies a starting point for a temporary problem: minimize a. A solution with a=0 recovers original feasibility. The artificial variable is an algorithmic device, not an extra physical resource that may remain in the final model.
Predict
Predict why a negative right side must be handled before taking an artificial variable as a basic nonnegative coordinate. In x₁−x₂+a=−2, setting original variables to zero gives a=−2, which is infeasible. Multiply the equality by minus one first, then introduce an artificial variable with the appropriate sign. Also predict whether a basic artificial variable at value zero means Phase I failed. It does not; being basic is a coordinate-system choice, while a zero value may already satisfy the original constraints.
Experiment
Compare two one-dimensional systems after constructing feasible Phase I problems.
Original system
Phase I formulation
Minimum artificial sum
x=2, x≥0
x+a=2, x,a≥0
0, at x=2
x=−2, x≥0
−x+a=2, x,a≥0
2, at x=0
The second row is infeasible in the original variables. Its artificial sum cannot fall below two because a=2+x. This gives an exact positive Phase I optimum, not merely a stalled iterative trace. If a numerical solve stops early with a positive artificial objective, infeasibility is not certified unless a valid lower bound proves the optimum is positive.
Understand
For a correctly constructed feasible Phase I LP, minimize the sum of nonnegative artificial variables. If the original system is feasible, setting all artificials to zero supplies objective zero, the smallest possible value. Conversely, an attained zero sum forces every artificial variable to zero and leaves an original feasible point. Thus a strictly positive certified Phase I optimum proves infeasibility. Once zero is reached, remove artificial columns and restore the original objective. Any zero-valued basic artificial variable must be pivoted out when possible; if its row has no usable original coefficient, inspect the row for redundancy and remove it consistently.
Degeneracy occurs when a basic coordinate is zero. A pivot can then have zero length, changing the basis without changing the feasible point. Since there are finitely many bases, strict objective improvement at every pivot would prevent cycling, but degeneracy removes that argument. Bland’s rule chooses the smallest-index eligible entering variable and, among minimum-ratio ties, the smallest-index leaving variable. It prevents cycling in exact simplex arithmetic. The full combinatorial anti-cycling proof is a further theorem; this lesson states its guarantee and explains the failure mechanism it addresses rather than claiming that finiteness of bases alone proves termination.
Apply
Use basic values (0,4) and an entering direction that subtracts (1,1)t. The minimum ratio is zero, so the objective gain is zero even with positive reduced cost. Explain how the same geometric point can now acquire a different basis. Then change the first basic value to one: the allowable step becomes one and the objective can genuinely improve. These nearby cases show why numerical tolerances near zero need explicit handling.
In floating-point software, tiny negative coordinates, nearly singular bases and inconsistent feasibility tolerances can imitate or obscure degeneracy. Exact anti-cycling theory does not alone certify a floating-point implementation. Report residuals and tolerance policy, and verify a final feasible point and bound independently where possible.
Continue
Separate feasible, infeasible, unbounded and unfinished solver states. A time limit or failed pivot is not a mathematical infeasibility proof. Continue to Farkas’ alternative for an explicit separating-vector certificate that can prove an equality system has no nonnegative solution. This connects geometric impossibility with a short algebraic check independent of a long simplex trace.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
For x+a=−1 with x,a≥0, is this a valid artificial-variable start? Enter 1 for yes or 0 for no.
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Basic value s are(0,5) and the entering direction subtracts(1,2)t. What is the ratio-test step?
Integers, fractions and finite decimals are accepted. Expressions such as sqrt(2) are not parsed by this checker.
Explain why the minimum sum of nonnegative artificial variables is zero iff the original equality system has a nonnegative feasible solution.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A Phase I optimum is zero but an artificial variable remains basic at value zero. What should be checked before Phase II?
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Why does a positive entering reduced cost not always imply a strictly improved objective after a pivot?
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
State Bland’s rule and the scope of its termination guarantee.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
