Assignment 2 — LPP Special Cases

Objective: Max Z = 4X₁ + 6X₂ + 5X₃ + 0S₁ + … — all slacks, so the origin is the starting basis.

The final table is optimal (every Cⱼ − Zⱼ ≤ 0) but the basic variable S₂ has value 0. That is degeneracy. It came from a tie in the ratio test, and it happens because all four constraints pass through the optimal corner: at (2, 2, 2) each one is exactly satisfied (6, 8, 8, 8). The solution is still optimal; degeneracy only means the simplex method could cycle.

Objective: Max Z = 7X₁ + 5X₂ + 6X₃ + 0S₁ + … — all slacks, so the origin is the starting basis.

Every non-basic Cⱼ − Zⱼ is strictly negative (−1.75, −1.75, −0.75), no basic variable is 0 and no artificial variable exists. So the optimum is unique. Constraints 1–3 are fully used; constraint 4 has 0.45 spare and constraint 5 has 1.65 spare.

Objective: Max Z = 4X₁ + 7X₂ + 5X₃ + 0·(slacks/surpluses) − M·(artificials)

The optimality condition is met, yet the artificial variable A₃ is still basic at 25/6 ≈ 4.17. A positive artificial variable at the end means no point satisfies every constraint. The reason: X₁ + X₂ ≥ 10, but X₁ + 2X₂ + X₃ ≤ 9 forces X₁ + X₂ ≤ 9. The ≥ constraint can never be met — the "solution" Z = 32.83 is meaningless.

Objective: Min Z = 5X₁ + 4X₂ + 6X₃ + 0·(slacks/surpluses) + M·(artificials)

This is a Min problem, so the optimality test is every Cⱼ − Zⱼ ≥ 0: X₂ = 1.5 and X₃ = 6 for the non-basic variables, both strictly positive. No artificial is left and no basic variable is zero. The optimum uses X₁ = 7 only, for a minimum Z = 35; constraint 2 (2X₁ + X₂ ≥ 14) is exactly met, constraints 1 and 3 have 3 and 1 units spare.

Objective: Max Z = 5X₁ + 5X₂ + 3X₃ + 0S₁ + … — all slacks, so the origin is the starting basis.

The table is optimal, but the non-basic slack S₃ has Cⱼ − Zⱼ = 0. Bringing S₃ into the basis gives a different corner with the same Z = 42. Pivoting on S₃ (ratio row S₄, θ = 6) gives X₁ = 1.5, X₂ = 4.5, X₃ = 4 — also Z = 42. The reason is visible in the data: the objective 5X₁ + 5X₂ is parallel to the binding constraint 2X₁ + 2X₂ ≤ 12, so every point on that edge between (4.5, 1.5) and (1.5, 4.5) is optimal.

Objective: Min Z = 5X₁ + 5X₂ + 3X₃ + 0·(slacks/surpluses) + M·(artificials)

Two signals at once. The basic variable S₂ = 0 (degenerate: X₁ ≥ 2 is exactly met at the same corner as other constraints), and the non-basic S₅ has Cⱼ − Zⱼ = 0 (multiple optima). The cost 5X₁ + 5X₂ is parallel to X₁ + X₂ ≥ 10, so any X₁ from 2 to 7 with X₂ = 10 − X₁ and X₃ = 4 costs the same Z = 62 — e.g. (2, 8, 4) or (7, 3, 4).

Objective: Min Z = −6X₁ + 4X₂ + 5X₃ + 0·(slacks/surpluses) + M·(artificials)

After 3 iterations the variable S₁ should enter (its Cⱼ − Zⱼ still improves Z), but every entry in its column is ≤ 0. With no positive divisor there is no replacement ratio — the simplex cannot continue.

The table reaches a point where a variable should enter (it would still reduce Z) but its column has no positive entry, so there is no replacement ratio and no leaving variable. Reason in the data: X₁ carries cost −6, so every extra unit lowers Z by 6, and X₁ appears only in ≥ constraints (X₁ − X₂ ≥ 2, X₁ + X₂ + X₃ ≥ 6), which a bigger X₁ only satisfies more. Z → −∞. The model is missing an upper limit on X₁.

Objective: Max Z = 6X₁ + 8X₂ + 5X₃ + 0·(slacks/surpluses) − M·(artificials)

After 4 iterations the variable S₁ should enter (its Cⱼ − Zⱼ still improves Z), but every entry in its column is ≤ 0. With no positive divisor there is no replacement ratio — the simplex cannot continue.

Same signal: the entering column has no positive entry, so there is no ratio test. X₁ has profit +6 and appears only in the ≥ constraints X₁ − X₂ ≥ 3 and X₁ + X₂ + X₃ ≥ 6. Nothing stops X₁, so Z → +∞. A real business problem cannot earn infinite profit — a capacity constraint on X₁ has been left out.