Linear Programming, Transportation and Assignment Problems — Practice

Question 1

According to the corner-point property, where does the optimal solution of a linear programme always occur?

Accepted Answer

At a corner (vertex) of the feasible region.

Question 2

What condition must hold for a transportation problem to be described as 'balanced'?

Accepted Answer

Total supply must exactly equal total demand.

Question 3

In an assignment problem, what is the supply at each source and the demand at each destination?

Accepted Answer

Exactly 1 at each (a strict one-to-one matching).

Question 4

A firm makes products A and B. Each unit of A needs 3 hours of a resource; each unit of B needs 2 hours. Only 60 hours are available. Formulate this single constraint as an inequality in A and B.

Accepted Answer

3A + 2B <= 60.

Question 5

A transportation problem has 2 sources with supplies 50 and 30, and 3 destinations with demands 20, 25 and 20. Is it balanced? If not, state the adjustment needed.

Accepted Answer

Total supply = 80. Total demand = 65. Unbalanced (supply exceeds demand); a dummy destination with demand of 15 units and zero cost must be added.

Question 6

In a transportation table, Source 1 has 20 units of supply and Destination 1 requires 35 units. Using the North-West Corner Method, what is the first allocation, and what happens next?

Accepted Answer

Allocate min(20, 35) = 20 units to (Source 1, Destination 1). Source 1's supply is now exhausted, so the method moves down to (Source 2, Destination 1) to allocate Destination 1's remaining unmet demand of 15 units.

Question 7

A feasible region for a maximisation problem has corner points (0,0), (0,40), (30,20) and (50,0). The objective function is Z = 40X + 30Y. Find the optimal solution.

Accepted Answer

Z at (0,0) = 0. Z at (0,40) = 30x40 = 1,200. Z at (30,20) = 40x30 + 30x20 = 1,200 + 600 = 1,800. Z at (50,0) = 40x50 = 2,000. The maximum is at (50,0), giving Z = 2,000, so X=50, Y=0 is optimal.

Question 8

Explain why reducing every row of a cost matrix by its row minimum, and then every column by its column minimum, does not change which assignment is actually optimal, even though every number in the matrix changes.

Accepted Answer

Subtracting a constant from every entry within a single row shifts the entire row's costs down by an identical amount, which preserves the RELATIVE cost differences between the cells in that row (cell A being, say, Rs. 5 cheaper than cell B in the same row remains true after both are reduced by the same amount). The same logic applies to column reductions. Since an assignment problem's optimal solution depends only on which combination of cells has the lowest TOTAL relative cost compared to other possible combinations, and these relative differences are preserved throughout the reduction process, the optimal assignment identified in the reduced matrix is exactly the same as the optimal assignment in the original matrix — the reductions merely reveal zero-cost cells that make spotting this optimal combination easier, without altering which combination is actually optimal.

Practice — Linear Programming, Transportation and Assignment Problems

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities