• Practice
  • About 18 min
  • 5 practice questions

Transportation and allocation problems

Reduce a two-source, three-destination transportation problem to two variables, write every shipment's non-negativity as a constraint, simplify the cost, and solve allocation problems such as hiring vehicles.

If something looks wrong, please tell us.

Transportation problems look as if they need six or more variables, one for each route. With supplies and demands fixed, only two of the amounts can be chosen freely and the rest follow from them. That turns the problem into a two-variable LPP that the corner-point method can solve. These problems are long, so a clean routine matters more than speed.

The routine

  1. Check that total supply equals total demand (if not, the problem says what happens to the surplus).
  2. Choose two shipments from the first source as x and y.
  3. Write every other shipment in terms of x and y using the supplies and demands.
  4. Every shipment is ≥ 0: this gives all the constraints.
  5. Write the cost as the sum of amount × unit cost over all routes and simplify.
  6. Solve by the corner-point method and translate back into all six shipments.

Worked example 1: two godowns, three markets

Godown A holds 80 tonnes and godown B holds 70 tonnes. Markets D, E and F need 50, 60 and 40 tonnes (total 150, equal to the supply). The cost per tonne in rupees is: A to D 5, A to E 4, A to F 3, B to D 4, B to E 2, B to F 5. Let A send x tonnes to D and y tonnes to E.

RouteAmountCost per tonne (₹)Condition from amount ≥ 0
A to Dx5x ≥ 0
A to Ey4y ≥ 0
A to F80 − x − y3x + y ≤ 80
B to D50 − x4x ≤ 50
B to E60 − y2y ≤ 60
B to F40 − (80 − x − y) = x + y − 405x + y ≥ 40

Cost: Z = 5x + 4y + 3(80 − x − y) + 4(50 − x) + 2(60 − y) + 5(x + y − 40). Collect terms: x has 5 − 3 − 4 + 5 = 3, y has 4 − 3 − 2 + 5 = 4, and the constant is 240 + 200 + 120 − 200 = 360. So Z = 3x + 4y + 360.

The feasible region has corners (40, 0), (50, 0), (50, 30), (20, 60), (0, 60) and (0, 40), giving Z = 480, 510, 630, 660, 600 and 520. The minimum is ₹480 at x = 40, y = 0: A sends 40 to D, 0 to E, 40 to F; B sends 10 to D, 60 to E, 0 to F. Check: 40 × 5 + 40 × 3 + 10 × 4 + 60 × 2 = 480.

Speed tip: read the reduced cost

Once the cost is Z = 3x + 4y + 360 with both coefficients positive, you want x and y small. The only constraint pushing them up is x + y ≥ 40, and x is the cheaper of the two, so the answer is x = 40, y = 0. Use the corner table to confirm, but this reasoning tells you where to look first.

Worked example 2: hiring vehicles

At least 360 people must be carried in one trip. A bus seats 60 and costs ₹4000; a minibus seats 30 and costs ₹2500. Only 8 drivers are available and only 5 buses. With x buses and y minibuses: minimise Z = 4000x + 2500y subject to 60x + 30y ≥ 360 (that is 2x + y ≥ 12), x + y ≤ 8, x ≤ 5, x, y ≥ 0. The corners are (4, 4), (5, 2) and (5, 3), costing ₹26,000, ₹25,000 and ₹27,500. Hire 5 buses and 2 minibuses for ₹25,000. A bus costs ₹66.67 a seat against ₹83.33 for a minibus, so the cheaper seat is used as far as the limit of 5 buses allows.

Transportation: let two shipments be x and y, express all the others through supplies and demands, make every shipment ≥ 0, then simplify the total cost before finding corners.

Key takeaways: a balanced 2 × 3 transportation problem has two free variables. All six non-negativity conditions are constraints, and the last route is the one most often forgotten. Simplify the cost to px + qy + constant before evaluating corners, and always state the answer as the full shipping plan.

Check your understanding

  1. 1. Godown P holds 30 units and godown Q holds 20 units. Shops R, S and T need 15, 20 and 15 units. P sends x units to R and y to S, and everything is delivered. Which of these is one of the constraints?

    1. x + y ≤ 15
    2. x + y ≥ 15
    3. x ≥ 15
    4. x + y ≥ 30
    Show answer

    Answer: B. P sends 30 − x − y to T, so Q must send 15 − (30 − x − y) = x + y − 15 to T. This amount cannot be negative, so x + y ≥ 15. (The other constraints are x, y ≥ 0, x + y ≤ 30, x ≤ 15 and y ≤ 20.)

  2. 2. In that problem the cost per unit is ₹3 from P to R, ₹3 from P to S, ₹1 from P to T, ₹4 from Q to R, ₹2 from Q to S and ₹3 from Q to T. What is the total cost in terms of x and y?

    1. Z = 3x + 3y + 30
    2. Z = x + 3y + 130
    3. Z = x + 3y + 85
    4. Z = 7x + 5y + 85
    Show answer

    Answer: C. Z = 3x + 3y + 1(30 − x − y) + 4(15 − x) + 2(20 − y) + 3(x + y − 15). The x terms: 3 − 1 − 4 + 3 = 1. The y terms: 3 − 1 − 2 + 3 = 3. Constants: 30 + 60 + 40 − 45 = 85. So Z = x + 3y + 85.

  3. 3. Minimise Z = x + 3y + 85 for that problem (x, y ≥ 0, x + y ≤ 30, x ≤ 15, y ≤ 20, x + y ≥ 15). What is the least cost?

    1. ₹100
    2. ₹85
    3. ₹130
    4. ₹115
    Show answer

    Answer: A. Z grows with both x and y, and y costs three times as much, so use x to meet x + y ≥ 15: x = 15, y = 0 gives 100. Checking the corners (15, 0), (15, 15), (10, 20), (0, 20) and (0, 15) gives 100, 145, 155, 145 and 130. ₹85 needs x = y = 0, which breaks x + y ≥ 15.

  4. 4. At least 240 students must be carried in x large buses (48 seats) and y minibuses (24 seats). After simplifying, the constraint is:

    1. x + 2y ≥ 10
    2. 2x + y ≤ 10
    3. 48x + 24y ≥ 10
    4. 2x + y ≥ 10
    Show answer

    Answer: D. Seats: 48x + 24y ≥ 240. Divide by 24: 2x + y ≥ 10. The number of seats must be at least the number of students, hence ≥.

  5. 5. In the transport problem of this lesson, why must every one of the six shipments be written in terms of x and y and kept ≥ 0?

    1. Because the cost must be positive
    2. Because a negative shipment is meaningless, and these conditions give the constraints of the problem
    3. Because it makes the region unbounded
    4. Because x and y must be equal
    Show answer

    Answer: B. Only two shipments are chosen freely; the other four are fixed by the supplies and demands. Each of the six must be non-negative, and those six conditions are exactly the constraints that bound the feasible region. Forgetting one (often the last route, here B to F giving x + y ≥ 40) is the commonest error.

Privacy · Terms · Refunds · Delivery