Transport and allocation problems

What you will be able to do

• reduce a transport problem with four shipments to two unknowns;
• write the extra constraints that come from the other shipments;
• solve an allocation problem in the same way;
• handle a best corner whose coordinates are not whole numbers.

Four shipments, two unknowns

Depot D1 holds $40$ crates and depot D2 holds $50$ crates. Shop S1 needs $30$ crates and shop S2 needs $45$ crates. The cost of one crate, in rupees, is $5$ from D1 to S1, $5$ from D1 to S2, $7$ from D2 to S1 and $6$ from D2 to S2. How should the crates be sent at the least cost?

There are four routes. Let $x$ crates go from D1 to S1 and $y$ crates from D1 to S2. Each shop gets exactly what it needs, so D2 sends the rest:

• D2 to S1: $30 - x$ crates;
• D2 to S2: $45 - y$ crates.

Now write the rules. No shipment can be negative.

• $x \ge 0$ and $y \ge 0$;
• $30 - x \ge 0$, which is $x \le 30$;
• $45 - y \ge 0$, which is $y \le 45$;
• D1 holds $40$, so $x + y \le 40$;
• D2 holds $50$, so $(30 - x) + (45 - y) \le 50$, which is $x + y \ge 25$.

The total cost in rupees is

Solve it

The region has five corners: $(25, 0)$, $(30, 0)$, $(30, 10)$, $(0, 40)$ and $(0, 25)$. The rule $y \le 45$ never touches the region.

The costs are $Z = 430$, $420$, $410$, $440$ and $455$. The smallest is $410$ at $(30, 10)$.

In words: D1 sends $30$ crates to S1 and $10$ to S2. D2 sends $0$ to S1 and $35$ to S2. The total cost is $410$ rupees. Check the shops: S1 gets $30$ and S2 gets $10 + 35 = 45$. Check the depots: D1 sends all $40$ and D2 sends $35$, which is less than $50$.

Why this plan? Depot D1 is cheaper than D2 for both shops, so it sends all it can. Its crates save more at S1, where D1 is $2$ rupees cheaper, than at S2, where it is $1$ rupee cheaper. So D1 serves S1 first.

Allocation problems

An allocation problem splits a fixed amount between two uses. A trust has up to $80$ thousand pounds. Account A pays $5\%$ a year and account B pays $8\%$. At least $20$ thousand must go in A and at most $50$ thousand in B. Let $x$ and $y$ be the amounts, in thousands of pounds.

The return in pounds a year is $Z = 50x + 80y$, since $5\%$ of $1000$ pounds is $50$ pounds. The rules are $x + y \le 80$, $x \ge 20$ and $y \le 50$. The corners are $(20, 0)$, $(80, 0)$, $(30, 50)$ and $(20, 50)$. The returns are $1000$, $4000$, $5500$ and $5000$ pounds. The best plan is $30$ thousand pounds in A and $50$ thousand pounds in B, for a return of $5500$ pounds a year.

When the best corner is not a whole number

A shop makes vases and bowls in whole numbers. Say $x$ vases and $y$ bowls. The shelf holds $x + y \le 8$ items and the oven allows $3x + y \le 11$ hours. The profit is $Z = 5x + 3y$ pounds.

The corners are $(0, 0)$, $\left(\dfrac{11}{3}, 0\right)$, $(0, 8)$ and $\left(\dfrac{3}{2}, \dfrac{13}{2}\right)$. The best corner is $\left(\dfrac{3}{2}, \dfrac{13}{2}\right)$, with $Z = 27$. But we cannot make half a vase.

Rounding to the nearest whole numbers gives $(2, 6)$, and $3(2) + 6 = 12$ is more than $11$. That plan is not allowed. Rounding down gives $(1, 6)$ with $Z = 23$. But the whole-number plan $(1, 7)$ is allowed and gives $Z = 26$. This is the best whole-number plan.

So when whole numbers are needed, list the whole-number plans near the best corner, test each against every rule, and compare. The corner theorem does not promise that the best whole-number plan is near the rounded corner. The board problems in this chapter are chosen so that the best corner is already a whole number.

Practise with new numbers

Try it in Python

The program tries every whole-number plan $(x, y)$ for the delivery problem and keeps the cheapest. It then prints what each depot sends.

Common mistakes

• Forgetting the shipments that are left. The amounts $30 - x$ and $45 - y$ must also be at least $0$.
• Counting a depot's stock once. A depot sends to both shops, so its two shipments together must fit its stock.
• Rounding a fractional corner. The rounded plan may break a rule, or may not be the best whole-number plan.
• Dropping the units. Say crates, rupees or thousand pounds.

Remember these

• Choose two unknowns. The needs of the shops give the other shipments.
• The other shipments, and the stocks of the depots, give more constraints. Then find the corners and the best one.
• An allocation problem splits a fixed amount between two uses by the same steps.
• If whole numbers are needed, test the whole-number plans near the best corner.

References

• NCERT, Mathematics Textbook for Class XII, Part II, Chapter 12, Linear Programming (transportation problems and the exercises on allocation).

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. Shop S1 needs $50$ crates. Depot D1 sends it $x$ crates. How many does depot D2 send to S1?

2. Depot D2 holds $60$ crates. Its shipments are $50 - x$ to S1 and $45 - y$ to S2. Write its stock rule.

3. The costs per crate are $5$ from D1 to S1 and $7$ from D2 to S1. How many rupees does the shop save for each crate that comes from D1 instead of D2?

4. A fund of $40$ thousand pounds is split between plans paying $4\%$ and $7\%$. What is the return of $10$ thousand pounds in the first and $30$ thousand in the second?

5. The best corner of a problem about whole boxes is $(2.5, 3.5)$. Why is $(3, 4)$ not an automatic answer?