Linear Programming — Real-World Applications

• Translate diet problems into LP formulations and solve for minimum-cost nutrition plans
• Formulate manufacturing/allocation problems with multiple resource constraints
• Set up a basic transportation LP matrix (introductory level, without full simplex)
• Systematically extract decision variables, constraints, and objectives from word problems
• Apply the DOCF mnemonic to structure any LP word problem before solving
• Evaluate corner points for real-world LP problems and interpret the solution in context

Level 1 — Foundations

DOCF mnemonic for LP word problems:

Common problem types:

Reading word problems — key signal words:

Level 2 — JEE Depth

Diet problem structure: $\text{Minimise } Z = c_1 x + c_2 y$ $\text{subject to:}$ $a_1 x + b_1 y \geq P \quad \text{(protein requirement)}$ $a_2 x + b_2 y \geq C \quad \text{(calorie requirement)}$ $x \geq 0,\; y \geq 0$

Since constraints are $\geq$ type, the feasible region is unbounded. Minimum cost is found at a corner point and verified with the isocost line.

Manufacturing problem — shadow price intuition: The shadow price of a constraint is the rate of change of the optimal objective value per unit increase in the resource limit (right-hand side). At JEE Foundation level, this means: if the wood constraint relaxes from 60 to 61 m², by how much does the maximum profit increase? This is computed by re-solving the LP or by sensitivity analysis (introduced at higher levels).

Transportation LP (introductory): Two warehouses W1, W2 with supplies $s_1$, $s_2$. Two destinations D1, D2 with demands $d_1$, $d_2$. Cost of shipping one unit from $W_i$ to $D_j$ is $c_{ij}$.

Variables: $x_{ij}$ = units sent from $W_i$ to $D_j$.

$\text{Minimise } Z = \sum_{i,j} c_{ij} x_{ij}$ $\text{Supply:} \; x_{11} + x_{12} = s_1, \quad x_{21} + x_{22} = s_2$ $\text{Demand:} \; x_{11} + x_{21} = d_1, \quad x_{12} + x_{22} = d_2$ $x_{ij} \geq 0$

For a 2×2 case with balanced supply and demand ($s_1+s_2 = d_1+d_2$), this reduces to a 2-variable LP after substitution.

Example 1 (Diet Problem): Two foods F1 and F2. F1 contains 4 g protein, 2 g fat per unit, costs ₹10/unit. F2 contains 3 g protein, 5 g fat per unit, costs ₹8/unit. Minimum daily requirements: 20 g protein, 15 g fat. Minimise cost.

Step 1 — DOCF.
D: x = units of F1, y = units of F2.
O: Minimise Z = 10x + 8y.
C: Protein: 4x + 3y ≥ 20
   Fat:     2x + 5y ≥ 15
   x ≥ 0, y ≥ 0.
F: Check feasibility — origin (0,0): 0 ≥ 20? No. Constraints are ≥, so origin is not feasible.

Step 2 — Boundaries.
L1: 4x + 3y = 20  →  (5, 0) and (0, 20/3 ≈ 6.67)
L2: 2x + 5y = 15  →  (7.5, 0) and (0, 3)

Step 3 — Feasible region (above/right of both lines, first quadrant).

Step 4 — Corner points.
A: intersection of L1 with x-axis (y=0): 4x = 20 → x = 5. Point (5, 0).
   Check L2: 2(5) + 5(0) = 10 ≥ 15? NO. Not feasible.

B: intersection of L2 with x-axis (y=0): 2x = 15 → x = 7.5. Point (7.5, 0).
   Check L1: 4(7.5) + 3(0) = 30 ≥ 20 ✓. Feasible.

C: intersection of L1 with y-axis (x=0): 3y = 20 → y = 20/3. Point (0, 20/3).
   Check L2: 2(0) + 5(20/3) = 100/3 ≈ 33.3 ≥ 15 ✓. Feasible.

D: intersection of L1 and L2:
   4x + 3y = 20   …(1)
   2x + 5y = 15   …(2)
   Multiply (2) by 2: 4x + 10y = 30.
   Subtract (1): 7y = 10 → y = 10/7.
   Substitute in (1): 4x = 20 − 30/7 = 110/7 → x = 110/28 = 55/14.
   Point D = (55/14, 10/7) ≈ (3.93, 1.43).

Step 5 — Evaluate Z at feasible corners B, D, C.
B = (7.5, 0):      Z = 10(7.5) + 8(0) = 75
D = (55/14, 10/7): Z = 10(55/14) + 8(10/7) = 550/14 + 80/7 = 550/14 + 160/14 = 710/14 ≈ 50.71
C = (0, 20/3):     Z = 10(0) + 8(20/3) = 160/3 ≈ 53.33

Minimum Z ≈ 50.71 at D = (55/14, 10/7).

Step 6 — Verify with isocost line.
Draw 10x + 8y = 710/14. Check: no feasible point gives smaller Z (region extends outward from D). ✓

Answer: Buy 55/14 ≈ 3.93 units of F1 and 10/7 ≈ 1.43 units of F2, minimum cost ≈ ₹50.71.
(In practice, if integer units required, check adjacent integers — not part of standard LP.)

Example 2 (Manufacturing): A manufacturer makes products A and B. A needs 2 h machine time + 3 h assembly; B needs 3 h machine + 2 h assembly. Available: 12 h machine, 12 h assembly. Profit: ₹300/A, ₹200/B. Maximise profit.

Step 1 — DOCF.
D: x = units of A, y = units of B.
O: Maximise Z = 300x + 200y.
C: Machine:   2x + 3y ≤ 12
   Assembly:  3x + 2y ≤ 12
   x ≥ 0, y ≥ 0.

Step 2 — Boundaries.
L1: 2x + 3y = 12  →  (6, 0) and (0, 4)
L2: 3x + 2y = 12  →  (4, 0) and (0, 6)

Step 3 — Feasible region: below/on both lines, first quadrant.
Origin (0,0): 0 ≤ 12 ✓, 0 ≤ 12 ✓. Origin is feasible; shade toward origin.

Step 4 — Corner points.
O = (0, 0)
A: L1 meets x-axis: 2x = 12 → x = 6, but check L2: 3(6) = 18 > 12. Not feasible.
A: L2 meets x-axis: 3x = 12 → x = 4. Check L1: 2(4) = 8 ≤ 12 ✓. A = (4, 0).
B: L1 meets y-axis: 3y = 12 → y = 4. Check L2: 2(4) = 8 ≤ 12 ✓. B = (0, 4).
C: Intersection of L1 and L2:
   2x + 3y = 12   …(1)
   3x + 2y = 12   …(2)
   Multiply (1) by 3: 6x + 9y = 36
   Multiply (2) by 2: 6x + 4y = 24
   Subtract: 5y = 12 → y = 12/5.
   From (2): 3x = 12 − 2(12/5) = 12 − 24/5 = 36/5 → x = 12/5.
   C = (12/5, 12/5) = (2.4, 2.4).

Step 5 — Evaluate Z.
O = (0,0):     Z = 0
A = (4,0):     Z = 300(4) + 200(0) = 1200
B = (0,4):     Z = 300(0) + 200(4) = 800
C = (2.4,2.4): Z = 300(2.4) + 200(2.4) = 720 + 480 = 1200

Maximum Z = ₹1200 at both A=(4,0) and C=(2.4,2.4).
→ Multiple optimal solutions; all points on segment AC give Z = 1200.

Step 6 — Interpret.
The manufacturer can produce 4 units of A only (0 units of B), or any combination along the
line segment from (4,0) to (2.4, 2.4). The constraint boundary 3x+2y=12 (assembly) is binding
and the profit line 300x+200y=1200 is parallel to... let us check:
Slope of Z=1200: 200y = 1200−300x → y = 6 − 1.5x. Slope = −1.5 = −3/2.
Slope of L2: 3x+2y=12 → slope = −3/2. ✓ Parallel — confirms multiple optima on L2 segment.

Answer: Maximum profit ₹1200; achieved by producing 4 units of A (and 0 of B), or any 
(x,y) on the segment from (4,0) to (12/5, 12/5).

• Q1: A diet uses bread ($x$ slices) and milk ($y$ glasses). Bread: 2 g protein, 1 g fat, ₹2/slice. Milk: 1 g protein, 2 g fat, ₹5/glass. Need ≥ 4 g protein, ≥ 4 g fat. Write the LP formulation using DOCF.
• Q2: In Example 2, if the machine-time availability increases to 15 hours (keeping assembly at 12), re-compute all corner points and the new maximum profit.
• Q3: A company ships goods from two warehouses (W1: 30 units, W2: 20 units) to two shops (S1: 25 units, S2: 25 units). Costs: W1→S1 ₹2, W1→S2 ₹3, W2→S1 ₹4, W2→S2 ₹1. Let $x$ = units from W1 to S1. Express all other flows in terms of $x$ and write the objective function.
• Q4: In the diet problem (Example 1), which constraint is binding at the optimal point D? (A constraint is binding if it holds with equality at the optimum.)
• Stretch: Q5: A nutrition consultant wants to minimise the cost of a diet plan (two foods) while meeting three nutrient requirements (protein, fat, carbohydrates). Explain why a graphical 2D method is insufficient and suggest the appropriate extension (name the method used for 3+ variables).

NCERT Chapter 12 link: Section 12.4 (Different types of LP problems — diet, manufacturing, transportation); worked examples 12.9–12.11 and miscellaneous examples.

Exam connections: JEE Main: full word-problem LP (typically manufacturing or diet type, 4 marks); common error is constraint setup. JEE Advanced: LP appears occasionally as part of a larger optimisation or inequality problem.

Study strategy: Use DOCF every time — write it at the top of your solution sheet as a checklist. Read the word problem twice: first pass for variables, second pass for constraints. The most common source of marks lost in LP is a wrong constraint coefficient — double-check by reading "one unit of X needs Y resource" and confirming the coefficient is Y, not 1/Y.

• Diet optimiser world: students input their own nutritional requirements (protein, fat) and food costs; the system formulates and solves the LP, then displays which foods to buy and how much.
• Manufacturing profit simulator: adjust machine-time and assembly limits with sliders and watch the optimal production mix update live.
• AI mentor reflection: "If the cost of food F2 in Example 1 drops from ₹8 to ₹4, would the optimal diet change? Re-solve or reason graphically."

• "In the diet problem, we minimised cost. What if we instead wanted to minimise fat intake while meeting the protein requirement and staying within a ₹60 budget? Reformulate the LP."
• "In Example 2, the manufacturer found multiple optimal solutions. Suppose the assembly line can only produce whole units. How would you find the best integer solution near the fractional corner point (2.4, 2.4)?"
• Stretch: "Research the Simplex Method (one step beyond graphical): explain conceptually why it moves from corner point to corner point along edges of the feasible polytope and why this is efficient even for problems with hundreds of variables."

• Complete the core practice + one extension activity (photo, table, short reflection, or mini-project) for base XP + topic badge.
• 5-7 day streak or family discussion note = multiplier + visible artifact in parent/principal dashboard.
• Best real-world application stories (anonymised) featured on class or national leaderboard.

• Design a "meal plan robot": given a list of foods (protein, fat, cost per unit), the robot uses LP to suggest the cheapest diet meeting daily requirements; implement it in Python with scipy.optimize.linprog and display the meal plan on an LCD or terminal.
• Future Skill track: AI Mastery — LP underlies many AI resource allocation tasks: GPU scheduling, ad bidding, supply chain optimisation; connect the diet problem structure to how AI systems allocate compute resources across tasks under budget and latency constraints.
• Coding extension: Write a Python class DietOptimiser with methods add_food(name, nutrients, cost), set_requirement(nutrient, min_amount), and solve() that internally calls scipy.optimize.linprog and returns the optimal food quantities and minimum cost.

This material emphasises experiential "learning by doing", competency (apply/create/analyse), vocational exposure, critical thinking, and multidisciplinary connections. Designed to feed live worlds, AI Mentor (with memory), gamification, robotics, parent analytics, and future skills — not just exam prep.

Portfolio Evidence Idea: Your photo/table/reflection/project + one sentence on "How this helps me in real life or a possible future path."

Open the Practice tab for aligned questions (easy/medium/hard + case-based) with full AI scaffolding.

See curriculum for cross-links and the full future-skills/robotics chapters.