← 2018 Paper 2

UPSC 2018 Maths Optional Paper 2 Q2b — Step-by-Step Solution

20 marks · Section A

Big-M / two-phase method (artificial variables) · Linear Programming · asked 5× in 13 yrs · Read the full method →

Question

Solve the following linear programming problem by Big M-method and show that the problem has finite optimal solutions. Also find the value of the objective function:

subject to

Technique

Big-M penalty method; surplus + artificial variables on the two $\ge$ constraints, slack on the $\le$ constraint; pivot until both artificials leave and all reduced costs are non-positive (minimization).

Solution

Step 1 — Standard form with slack/surplus and artificial variables

Convert each constraint to an equation. The two $\ge$ constraints need surplus variables $s_1,s_2\ge0$ (subtracted) and artificial variables $A_1,A_2\ge0$; the $\le$ constraint needs a slack $s_3\ge0$:

For minimization, artificials are penalized with $+M$ ($M$ a large positive number):

Initial basis: $A_1=8,\ A_2=12,\ s_3=60$ (all else $0$).

Step 2 — Initial tableau and reduced costs

With $c_B=(M,M,0)$ for the basis $(A_1,A_2,s_3)$, the reduced cost $z_j-c_j$ for each non-basic column is $c_B\cdot(\text{column})-c_j$:

(e.g. $x_1$: $M\cdot1+M\cdot3+0\cdot5-3=4M-3$). For minimization we improve while some $z_j-c_j>0$. The most positive is $x_1$ ($4M-3$) vs $x_2$ ($4M-5$); enter $x_1$ (largest coefficient of $M$ tie broken by constant: $4M-3>4M-5$).

Ratio test (RHS / positive entries in $x_1$ column $=(1,3,5)$): $8/1=8,\ 12/3=4,\ 60/5=12$. Minimum $=4$ at row 2 ⇒ $A_2$ leaves.

Step 3 — Pivot 1 (enter $x_1$, leave $A_2$), pivot element $3$

Row 2 $\div 3$: $\ x_1+\tfrac23x_2-\tfrac13s_2+\tfrac13A_2=4$. Eliminate $x_1$ elsewhere:

New basis $(A_1,x_1,s_3)=(4,4,40)$. Recompute reduced costs; the $x_2$ column still has a positive $z_j-c_j$ (coefficient of $M$ is $\tfrac43>0$), so enter $x_2$.

Ratio test ($x_2$ column entries in rows $(A_1,x_1,s_3)=(\tfrac43,\tfrac23,\tfrac83)$, RHS $(4,4,40)$): $4/\tfrac43=3,\ 4/\tfrac23=6,\ 40/\tfrac83=15$. Minimum $=3$ at row 1 ⇒ $A_1$ leaves.

Step 4 — Pivot 2 (enter $x_2$, leave $A_1$), pivot element $\tfrac43$

Row 1 $\div\tfrac43$: $\ x_2-\tfrac34 s_1+\tfrac14 s_2=3$. Update:

New basis $(x_2,x_1,s_3)=(3,2,32)$; both artificials are now non-basic (at $0$).

Step 5 — Optimality check

With both artificials expelled and the basis $(x_1,x_2,s_3)$, all reduced costs $z_j-c_j\le0$ for the non-basic variables $s_1,s_2,A_1,A_2$ (the surplus columns give $z_j-c_j\le0$ and artificials carry the $-M$ penalty). No entering variable improves $z$, so the current basic feasible solution is optimal:

Objective value:

Answer