Manufacturing and transportation problems

A second standard class of LPPs is the manufacturing problem: a factory produces multiple products, each requiring resources (machine time, raw materials, labour) of which the supply is limited. The objective is usually to maximise profit.

Closely related is the transportation problem: goods are shipped from sources to destinations at known per-unit costs; the goal is to minimise total cost subject to supply and demand constraints.

Structure of a manufacturing problem

Decision variables: units of each product to produce.

Objective: maximise profit $Z = p_1 x_1 + p_2 x_2 + \cdots$, where $p_i$ is profit per unit of product $i$.

Constraints:

• Resource limits: $a_{i1} x_1 + a_{i2} x_2 + \cdots \le b_i$ for each resource (machine hours, kg of material, etc.).
• Demand limits (sometimes): $x_i \le d_i$ or $x_i \ge m_i$.
• Non-negativity: $x_j \ge 0$.

The feasible region is typically bounded (all $\le$ constraints) , corner-point method works directly.

Standard form

Let $x$ = units of A, $y$ = units of B.

Maximise $Z = p_1 x + p_2 y$ subject to:

• $a_1 x + a_2 y \le m_1$
• $b_1 x + b_2 y \le m_2$
• $x, y \ge 0$.

Transportation problem (simple form)

A two-warehouse, one-destination problem. Warehouse 1 has $S_1$ units, ships at cost $c_1$ per unit. Warehouse 2 has $S_2$ units, ships at $c_2$ per unit. Destination needs $D$ units total.

Variables: $x$ from W1, $y$ from W2. Constraints: $x \le S_1$, $y \le S_2$, $x + y \ge D$, $x, y \ge 0$. Minimise $Z = c_1 x + c_2 y$.

This is bounded if you also have supply caps; corner-point method again.

Worked examples

Example 1. A factory makes two products A and B. A needs $3$ hours on machine 1 and $4$ hours on machine 2; B needs $5$ hours on machine 1 and $3$ on machine 2. Machine 1 available $15$ hours, machine 2 available $12$ hours. Profit ₹$8$ per A, ₹$10$ per B.

$x$ = A, $y$ = B. $Z = 8x + 10y$. $3x + 5y \le 15$, $4x + 3y \le 12$, $x, y \ge 0$.

Corners: $(0, 0): 0$. $(3, 0)$ (on $y = 0$, $4x \le 12$ gives $x \le 3$): check $3(3) + 0 \le 15$ ✓. $(0, 3)$: check $0 + 15 \le 15$ ✓, $0 + 9 \le 12$ ✓. Intersection of $3x + 5y = 15, 4x + 3y = 12$: multiply first by 3, second by 5: $9x + 15y = 45, 20x + 15y = 60$. Subtract: $11x = 15, x = 15/11, y = (12 - 60/11)/3 = (72/11)/3 = 24/11$.

Values: $(3, 0): 24$. $(0, 3): 30$. $(15/11, 24/11)$: $120/11 + 240/11 = 360/11 \approx 32.7$. Max $Z \approx 32.7$ at $(15/11, 24/11)$.

Example 2. A bookbinder makes two types of books: A uses $2$ hours of finishing and $3$ hours of binding; B uses $4$ hours finishing and $2$ hours binding. Available: $20$ hours finishing, $24$ hours binding. Profit ₹$30$ for A, ₹$50$ for B.

$x$ = A, $y$ = B. $Z = 30x + 50y$. $2x + 4y \le 20$ (finishing, simplify $x + 2y \le 10$), $3x + 2y \le 24$, $x, y \ge 0$.

Corners: $(0, 0): 0$. $(10, 0)$: check $30 + 0 \le 24$? $30 > 24$, infeasible. So use $x = 8$ on binding line: $(8, 0)$. $(0, 5)$: check $0 + 10 \le 24$ ✓. Intersection $x + 2y = 10, 3x + 2y = 24$: subtract first from second: $2x = 14, x = 7, y = 3/2$.

Values: $(8, 0): 240$. $(7, 3/2): 210 + 75 = 285$. $(0, 5): 250$. Max $Z = 285$ at $(7, 3/2)$.

Example 3. A garment shop produces shirts and pants. Shirts use $1$ m of fabric, $1$ button, profit ₹$50$. Pants use $2$ m fabric, $0$ buttons (just zippers), profit ₹$80$. Available: $20$ m fabric, $12$ buttons (so number of shirts at most 12).

$x$ = shirts, $y$ = pants. $Z = 50x + 80y$. $x + 2y \le 20$, $x \le 12$, $x, y \ge 0$.

Corners: $(0, 0)$, $(12, 0)$ ($x + 0 = 12 \le 20$ ✓), $(12, 4)$ ($x = 12$, $12 + 2y = 20$, $y = 4$). $(0, 10)$.

Values: $(0, 0): 0$. $(12, 0): 600$. $(12, 4): 600 + 320 = 920$. $(0, 10): 800$. Max $Z = 920$ at $(12, 4)$.

Example 4. A trucker has two trucks. Truck A: capacity $5$ tonnes, fuel cost ₹$200$/trip. Truck B: capacity $3$ tonnes, fuel cost ₹$100$/trip. Need to move at least $24$ tonnes. Truck A can do at most $6$ trips, truck B at most $10$. Minimise total fuel cost.

$x$ = trips of A, $y$ = trips of B. $Z = 200x + 100y$. $5x + 3y \ge 24$, $x \le 6$, $y \le 10$, $x, y \ge 0$.

Corners: $(6, 0)$: check $30 + 0 \ge 24$ ✓; $z = 1200$. $(0, 8)$: check $0 + 24 \ge 24$ ✓; $z = 800$. $(0, 10)$: $z = 1000$ (also feasible). $(6, 10)$: $z = 2200$. Intersection of $5x + 3y = 24$ and $x = 6$: $y = -2$, not in first quadrant. Intersection with $y = 10$: $5x + 30 = 24$, $x = -1.2$, infeasible. Intersection with axes: covered. Try the line itself crossing the box: from $(6, -2)$ to $(-1.2, 10)$ , clipping to feasibility we get $(6, 0)$ on $x = 6$ and $(0, 8)$ on $y$-axis.

Min: $(0, 8): 800$. So $0$ trips of A, $8$ trips of B.

Example 5. A jewellery shop produces two types of necklaces. N1 uses $5$ g silver and $20$ minutes of labour; N2 uses $4$ g silver and $30$ minutes labour. Available: $150$ g silver, $1200$ minutes. Profit: ₹$500$ per N1, ₹$800$ per N2.

$x$ = N1, $y$ = N2. $Z = 500x + 800y$. $5x + 4y \le 150$, $20x + 30y \le 1200$ (simplify $2x + 3y \le 120$), $x, y \ge 0$.

Corners: $(0, 0)$. $(30, 0)$ ($5(30) = 150 \le 150$ ✓, $60 + 0 \le 120$ ✓). $(0, 37.5)$ , check $0 + 4(37.5) = 150 \le 150$ ✓, $0 + 112.5 \le 120$ ✓. So $(0, 37.5)$.

Intersection: $5x + 4y = 150$, $2x + 3y = 120$. From first: $y = (150 - 5x)/4$. Sub: $2x + 3(150 - 5x)/4 = 120$, multiply by 4: $8x + 450 - 15x = 480$, $-7x = 30$, $x = -30/7$ , infeasible.

So just the two axis corners (and origin) and we use simpler analysis: the line $5x + 4y = 150$ ends at $(30, 0)$ and $(0, 37.5)$. The line $2x + 3y = 120$ ends at $(60, 0)$ and $(0, 40)$. They are both upward-sloping (or downward-sloping) constraints in the same direction; the tighter one binds. At each axis: silver constraint binds (smaller intercept).

Values: $(30, 0): 15000$. $(0, 37.5): 30000$. Max $Z = 30000$ at $(0, 37.5)$.

Example 6. A transporter has $20$ trucks. Each "Type 1" trip earns ₹$1000$, uses $1$ truck-day. Each "Type 2" trip earns ₹$1500$, uses $1.5$ truck-days. Available: $25$ truck-days per week. Each Type 1 needs at least $5$ trips/week (to maintain a contract). Maximise revenue.

$x$ = Type 1, $y$ = Type 2 trips/week. $Z = 1000x + 1500y$. $x + 1.5y \le 25$, $x \ge 5$, $x, y \ge 0$.

Corners: $(5, 0)$: $1.5y = 20$, so $y = 0$ works, $z = 5000$. $(25, 0)$ on $x = 25$ axis but then $x + 0 = 25 \le 25$ and $x \ge 5$, OK: $z = 25000$. $(5, 40/3)$: $5 + 1.5(40/3) = 5 + 20 = 25$, OK: $z = 5000 + 20000 = 25000$.

So two corners both give $25000$ , tie along the edge from $(5, 40/3)$ to $(25, 0)$. Max $Z = 25000$ along that edge.

Try it yourself

1. Factory makes two TVs. A: ₹$2000$ profit, $3$ h machine 1, $2$ h machine 2. B: ₹$3000$ profit, $4$ h machine 1, $1$ h machine 2. Available: $50$ h, $24$ h.
2. Carpenter makes chairs (₹$25$ profit each, $2$ h work, $1$ kg wood) and tables (₹$100$ profit, $4$ h work, $3$ kg wood). Available: $30$ h, $20$ kg.
3. Bakery makes biscuits and cookies. Biscuit: $1$ kg flour, $2$ kg sugar, ₹$5$ profit. Cookie: $2$ kg flour, $1$ kg sugar, ₹$4$. Flour: $10$ kg, sugar: $12$ kg.
4. Two product factory: P1 uses $2$ kg material, $1$ h time, ₹$30$. P2 uses $1$ kg, $3$ h, ₹$40$. Available: $20$ kg, $30$ h.
5. A clothing maker. Shirts: ₹$50$, $1$ m fabric, $0.5$ h. Pants: ₹$80$, $2$ m, $1$ h. Available: $30$ m, $15$ h.
6. Cement plant: types $C_1$ and $C_2$. $C_1$ uses $4$ h crusher, $2$ h mixer, ₹$2000$ profit. $C_2$ uses $2$ h crusher, $5$ h mixer, ₹$2500$ profit. Available $20$ h crusher, $25$ h mixer.
7. A craftsman makes two articles X and Y. Both need molding and finishing. X: $2$ min mold, $3$ min finish, profit ₹$50$. Y: $4$ min mold, $1$ min finish, profit ₹$30$. Available: $60$ min mold, $40$ min finish.
8. Trucking: Truck 1 carries $4$ tonnes/trip, ₹$50$/trip. Truck 2 carries $3$ tonnes/trip, ₹$30$/trip. Need to move $36$ tonnes. Truck 1 can do $\le 8$, Truck 2 $\le 6$. Min cost.
9. Two cosmetics products. C1: $3$ hours mixing, $1$ hour packing, profit ₹$200$. C2: $2$ h mixing, $2$ h packing, profit ₹$150$. Available: $24$ h mixing, $18$ h packing.
10. A printing press has $80$ hours of machine time and $100$ kg ink. Magazines: $4$ h, $2$ kg, profit ₹$15$. Books: $6$ h, $4$ kg, profit ₹$25$.
11. Two chemicals A and B. A: ₹$5000$ profit, $2$ raw materials, $1$ man-day. B: ₹$4000$, $1$ raw, $2$ man-days. Available: $200$ raw, $150$ man-days.
12. A computer assembly: laptops use $4$ h labour, $1$ board, profit ₹$3000$. Desktops: $2$ h labour, $1$ board, profit ₹$2000$. $40$ h labour, $15$ boards.
13. A logistics: trucks of capacity $10$ and $15$ tonnes, costs ₹$100$ and ₹$150$/trip. Need to move $90$ tonnes. Available: $6$ small, $4$ large trucks. Min cost.
14. A multi-product factory: $3$ products P, Q, R with constraints , but for 2D restrict to $P + Q + R \le 100$ and similar...

Pitfalls and tricks

• Identify the bottleneck resource. The constraint that binds at the optimum is the "scarce" resource.
• Check integer feasibility separately if the problem demands integer units (you produce whole biscuits, not 2.7 biscuits). For Class XII problems, fractional answers are often acceptable.
• Profit problems are usually maximisation with $\le$ constraints → bounded region → corner-point method directly.
• Transportation problems are minimisation with mixed constraints ($\le$ on supply, $\ge$ on demand) , may give bounded or unbounded region.
• Sketch and verify that each corner you compute is in the feasible region. A common error is to include an infeasible intersection.