Formulation Drill Set
Formulation Drill Set
These are exam-style LP modeling drills. Each solution gives the model, not the numerical optimum.
1. Mutual funds
An investor has €50,000. Funds A, B, C are bonds with unit prices $4.5,4,2.5$ and return rates $7\%,8\%,6\%$. Funds D, E, F are balanced with prices $3,4.5,5$ and return rates $6\%,9\%,9\%$. Funds G, H are equity with prices $6,5.5$ and return rates $10\%,12\%$. At least €15,000 must be in bonds, at least €20,000 in balanced funds, and at most €5,000 in equity.
Solution
Let $x_A,\ldots,x_H$ be units purchased.
\[\max 0.07(4.5)x_A+0.08(4)x_B+0.06(2.5)x_C+0.06(3)x_D+0.09(4.5)x_E+0.09(5)x_F+0.10(6)x_G+0.12(5.5)x_H\]subject to
\[4.5x_A+4x_B+2.5x_C+3x_D+4.5x_E+5x_F+6x_G+5.5x_H\le50000,\] \[4.5x_A+4x_B+2.5x_C\ge15000,\] \[3x_D+4.5x_E+5x_F\ge20000,\] \[6x_G+5.5x_H\le5000,\] \[x_j\ge0.\]2. Farm allocation
Let $x_L,x_T$ be hectares for lettuce and tomatoes. Lettuce yields 20 quintals/ha, tomato yields 30 quintals/ha. Labor is 18 and 24 hours/ha. Required production is at least 45 and 50 quintals. Total labor is at most 100 hours. Prices are €100 and €150 per quintal.
Solution
\[\max 100(20)x_L+150(30)x_T\]subject to
\[20x_L\ge45,\] \[30x_T\ge50,\] \[18x_L+24x_T\le100,\] \[x_L,x_T\ge0.\]3. Diet problem
Let $x_P,x_M,x_V,x_C$ be kilograms of pasta, meat, vegetables, and cheese per day. Nutrients are given per 100g. Costs per kg are €1, €9, €0.8, €12. Vegetables are at most 0.5 kg. Requirements: at least 70g protein, 50g fats, 250g sugar.
Solution
Since the nutrient table is per 100g and variables are kg, multiply nutrient values by 10.
\[\min x_P+9x_M+0.8x_V+12x_C\]subject to
\[99x_P+208x_M+20x_V+220x_C\ge70,\] \[12x_P+11x_M+2x_V+260x_C\ge50,\] \[753x_P+40x_V\ge250,\] \[x_V\le0.5,\] \[x_P,x_M,x_V,x_C\ge0.\]4. Two mines
Mine X costs €180/day and produces 6 high, 3 medium, 4 low tons/day. Mine Y costs €160/day and produces 1 high, 1 medium, 6 low tons/day. Requirements are 12 high, 8 medium, 24 low tons/week.
Solution
Let $x,y$ be operating days of mines X and Y.
\[\min 180x+160y\]subject to
\[6x+y\ge12,\] \[3x+y\ge8,\] \[4x+6y\ge24,\] \[x,y\ge0.\]5. Vehicle production
Let $x_A,x_B,x_C$ be weekly production of vehicles A, B, C. Capacities and hours per vehicle are: motors $3,2,1$ with capacity 120; bodies $1,2,3$ with capacity 80; finishing A $2$ with capacity 96; finishing B $3$ with capacity 102; finishing C $2$ with capacity 40. Profits are 840, 1120, 1200.
Solution
\[\max 840x_A+1120x_B+1200x_C\]subject to
\[3x_A+2x_B+x_C\le120,\] \[x_A+2x_B+3x_C\le80,\] \[2x_A\le96,\] \[3x_B\le102,\] \[2x_C\le40,\] \[x_A,x_B,x_C\ge0.\]6. Research hiring
Let $x_1,x_2,x_3$ be first-, second-, and third-level researchers. Salaries are €40k, €30k, €25k. Budget is €3M. Spending on second level cannot exceed 80% of spending on first level. Second-level hires must be at least double third-level hires. Each level must have at least 6 positions. Maximize hires.
Solution
\[\max x_1+x_2+x_3\]subject to
\[40000x_1+30000x_2+25000x_3\le3000000,\] \[30000x_2\le0.8(40000x_1),\] \[x_2\ge2x_3,\] \[x_1,x_2,x_3\ge6.\]If integer hiring is required, add $x_1,x_2,x_3\in\mathbb Z$.
7. Transportation
Factories P and C can supply 10,000 and 8,000 units. Warehouses R and N need 11,000 and 4,600 units. Costs are $P\to R=10$, $P\to N=30$, $C\to N=5$, $C\to R=35$.
Solution
Let $x_{PR},x_{PN},x_{CN},x_{CR}$ be shipped units.
\[\min 10x_{PR}+30x_{PN}+5x_{CN}+35x_{CR}\]subject to
\[x_{PR}+x_{PN}\le10000,\] \[x_{CN}+x_{CR}\le8000,\] \[x_{PR}+x_{CR}\ge11000,\] \[x_{PN}+x_{CN}\ge4600,\] \[x\ge0.\]8. Battery production
Let $x_A,x_B,x_G$ be boxes of Alef, Beth, and Ghimel. Copper is needed only for Beth and Ghimel: 1kg and 2kg. At most 4000kg copper. Profits after labor/copper are 13, 9, 16. Alef boxes must be at least double Beth and no more than Ghimel.
Solution
\[\max 13x_A+9x_B+16x_G\]subject to
\[x_B+2x_G\le4000,\] \[x_A\ge2x_B,\] \[x_A\le x_G,\] \[x_A,x_B,x_G\ge0.\]9. Campsite
Let $x$ be caravans and $y$ tents. Area is 1800 m². Caravans use 200 m² and tents 90 m². At most 6 caravans. People limit: 4 per caravan, 3 per tent, at most 48. Nightly charges are £2 and £1.
Solution
\[\max 2x+y\]subject to
\[200x+90y\le1800,\] \[x\le6,\] \[4x+3y\le48,\] \[x,y\ge0.\]If whole caravans/tents are required, add $x,y\in\mathbb Z$.
10. Binary knapsack
A bag can carry weight 15. Items have values $(10,7,12,8)$ and weights $(6,4,8,5)$.
Solution
Let $x_i\in{0,1}$ indicate whether item $i$ is selected.
\[\max 10x_1+7x_2+12x_3+8x_4\]subject to
\[6x_1+4x_2+8x_3+5x_4\le15,\] \[x_i\in\{0,1\}.\]Exam checkpoint
Practice under exam timing. Write the full pipeline: model, standard form if needed, BFS/reduced costs if asked, simplex iterations if asked, final objective value and interpretation.