Linear Programming Problems from Words: Quick Revision

A brief note on Linear Programming Problems from Words. Read it before a test. Try each question at the end before you open its answer.

The four steps

• Name the unknowns: $x$ and $y$, with what they count and the unit.
• Write the objective: the profit or the cost as a formula in $x$ and $y$.
• Write the constraints: one inequality for each limit or need, and also $x \ge 0$, $y \ge 0$.
• Solve and read: find the corners, work out the objective at each, pick the best. Say the plan and its value in words, with units.

The three kinds of problem

• Manufacturing: maximise a profit. Each resource limit gives a $\le$ rule.
• Diet and mixing: minimise a cost. Each need gives a $\ge$ rule, so the region is unbounded. With positive prices the smallest corner cost is the minimum. Check it with the half-plane test.
• Transport: choose two shipments $x$ and $y$. The needs of the shops give the other shipments. All four shipments are at least $0$, and each depot sends at most its stock.
• Allocation: split a fixed amount between two uses, such as an investment, by the same steps.

Reading the answer

• A price changes: the cheapest or best corner changes where two corner values are equal.
• A tie: if two corners give the same best value, the whole edge between them is optimal.
• Whole numbers: if the best corner is fractional, test the whole-number plans near it against every rule. Rounding may break a rule.
• Check: put the plan back into every limit.

A worked example

A factory makes chairs and desks. A chair needs $2$ hours of machine time and $3$ hours of labour. A desk needs $1$ hour of machine time and $4$ hours of labour. There are $20$ hours of machine time and $60$ hours of labour. A chair earns $30$ pounds and a desk earns $50$ pounds. Find the best plan.

1. The model. Maximise $Z = 30x + 50y$ pounds subject to $2x + y \le 20$, $3x + 4y \le 60$, $x \ge 0$, $y \ge 0$.
2. The corners. The lines meet where $y = 20 - 2x$ and $3x + 80 - 8x = 60$, so $x = 4$ and $y = 12$. The other corners are $(0, 0)$, $(10, 0)$ and $(0, 15)$.
3. The values. $Z = 0$, $300$, $120 + 600 = 720$ and $750$ pounds.
4. The answer. The best plan is $15$ desks and no chairs, for $750$ pounds. Check: labour is $4(15) = 60$ hours and machine time is $15$ hours.

Practice with new numbers

A program to try

The program works out the profit at the corners of the worked example and asks linprog for the best plan.

Mistakes to avoid

• Swapping the numbers in a rule, so the chairs get the hours of the desks.
• Using $\le$ for a need in a diet problem.
• Forgetting the shipments that are left in a transport problem.
• Rounding a fractional corner without testing the plan.
• Answering in numbers only. Give the plan and the profit with units.

Check yourself

1. A bag of seed needs $3$ kg of soil and a pot needs $2$ kg. There are $60$ kg of soil. Write the rule for $x$ bags and $y$ pots.

2. The corners of a diet region are $(0, 10)$, $(4, 3)$ and $(9, 0)$. Food A costs $3$ rupees and food B costs $2$ rupees a kilogram. Find the lowest cost.

3. Shop S1 needs $40$ crates and depot D1 sends it $x$. How many does depot D2 send to S1?

4. Two plans have the same cost at a certain price of food A. What happens to the cheapest plan if the price rises above it?

5. The best corner is $(2.4, 5.6)$ and the items are whole. What do you do?

Sources

• NCERT, Mathematics Textbook for Class XII, Part II, Chapter 12, Linear Programming.
• SciPy documentation, scipy.optimize.linprog.