UPSC 2020 Maths Optional Paper 2 Q1e — Step-by-Step Solution

10 marks · Section A

LPP: standard form; basic, basic feasible, optimal solutions · Linear Programming · asked 6× in 13 yrs · Read the full method →

Question

The UPSC maintenance section has purchased sufficient curtain cloth pieces; the length of each piece is 17 feet. The requirement by curtain length is: length 5 ft → 700 required; length 9 ft → 400 required; length 7 ft → 300 required. The width of all curtains is the same as the available pieces. Form a linear programming problem in standard form that decides the number of pieces cut in different ways so that the total trim loss is minimum. Also give a basic feasible solution to it.

Technique

Cutting-stock (Gilmore–Gomory) formulation: decision variables = pieces cut per pattern; minimize $\sum(\text{trim}_j)x_j$ subject to demand $\ge$ constraints; standard form via surplus + artificial variables.

Solution

This is a classic cutting-stock / trim-loss problem. Each stock piece (17 ft) can be cut into curtains of length $5,7,9$ ft. A cutting pattern specifies how many of each length come from one piece.

Step 1 — Enumerate the (efficient) cutting patterns

A pattern $(n_5,n_7,n_9)$ must satisfy $5n_5+7n_7+9n_9\le 17$ . We keep the maximal patterns (those in which no further curtain of any length fits — otherwise the trim could be reduced):

Pattern	$5$ ft ( $n_5$ )	$7$ ft ( $n_7$ )	$9$ ft ( $n_9$ )	Length used	Trim loss (ft)
$P_1$	$0$	$1$	$1$	$16$	$1$
$P_2$	$0$	$2$	$0$	$14$	$3$
$P_3$	$1$	$0$	$1$	$14$	$3$
$P_4$	$2$	$1$	$0$	$17$	$0$
$P_5$	$3$	$0$	$0$	$15$	$2$

Let $x_j\ge 0$ = number of stock pieces cut according to pattern $P_j$ , $j=1,\dots,5$ .

Step 2 — Objective: minimize total trim loss

\min\; z = 1\,x_1 + 3\,x_2 + 3\,x_3 + 0\,x_4 + 2\,x_5.

Step 3 — Demand constraints

Number of each curtain produced must meet the requirement (5 ft: 700, 7 ft: 300, 9 ft: 400):

\begin{aligned} 5\text{-ft}:&\quad 0x_1+0x_2+1x_3+2x_4+3x_5 \ge 700,\\ 7\text{-ft}:&\quad 1x_1+2x_2+0x_3+1x_4+0x_5 \ge 300,\\ 9\text{-ft}:&\quad 1x_1+0x_2+1x_3+0x_4+0x_5 \ge 400,\\ &\quad x_1,\dots,x_5\ge 0. \end{aligned}

Step 4 — Standard form (surplus + artificial variables)

Convert each $\ge$ constraint to equality by subtracting a surplus variable $s_i\ge0$ . For a starting basis one also adds an artificial variable $A_i\ge0$ (penalised by $+M$ in the objective, Big-M method). The standard form is:

\min\; z = x_1+3x_2+3x_3+0x_4+2x_5+0(s_1+s_2+s_3)+M(A_1+A_2+A_3)

subject to

\begin{aligned} x_3+2x_4+3x_5 - s_1 + A_1 &= 700,\\ x_1+2x_2+x_4 - s_2 + A_2 &= 300,\\ x_1+x_3 - s_3 + A_3 &= 400,\\ x_j\ge0,\quad s_i\ge0,\quad A_i\ge0. \end{aligned}

Equivalently, in matrix form $\min\, c^\top x$ s.t. $Ax=b,\ x\ge0$ with

A=\begin{bmatrix}0&0&1&2&3\\1&2&0&1&0\\1&0&1&0&0\end{bmatrix},\quad b=\begin{bmatrix}700\\300\\400\end{bmatrix},\quad c=\begin{bmatrix}1\\3\\3\\0\\2\end{bmatrix}

(before adding surplus/artificial columns).

Step 5 — A basic feasible solution

The constraints are three $\ge$ inequalities in five nonnegative variables. A BFS in standard form has at most $3$ (= number of constraints) basic variables.

A convenient feasible point using only patterns that directly supply the larger curtains. Use $P_5$ (three 5-ft each) for the 5-ft demand, $P_2$ (two 7-ft each) for the 7-ft demand, $P_1$ (one 9-ft each) for the 9-ft demand:

x_5=\left\lceil\tfrac{700}{3}\right\rceil\!\Big|_{\text{LP}}=\tfrac{700}{3},\qquad x_2=\tfrac{300}{2}=150,\qquad x_1=400,\qquad x_3=x_4=0.

Check (LP allows fractional pieces):

5-ft produced $=3x_5=3\cdot\frac{700}{3}=700\ge700$ ✓ (surplus $s_1=0$ )
7-ft produced $=x_1+2x_2=400+300=700\ge300$ ✓ (surplus $s_2=400$ )
9-ft produced $=x_1+x_3=400\ge400$ ✓ (surplus $s_3=0$ )

The three basic structural variables $\{x_1,x_2,x_5\}$ together with the slack of the slack constraint give a basic feasible solution. Its trim loss is

z=1\cdot 400+3\cdot 150+2\cdot\tfrac{700}{3}=400+450+\tfrac{1400}{3}=850+\tfrac{1400}{3}=\tfrac{3950}{3}\approx 1316.7\text{ ft}.

Answer

\boxed{\;\text{BFS: } (x_1,x_2,x_3,x_4,x_5)=\big(400,\,150,\,0,\,0,\,\tfrac{700}{3}\big),\ \ z=\tfrac{3950}{3}\text{ ft of trim.}\;}