Different Types of Linear Programming Problems

Classification of Linear Programming Problems

Linear Programming can be applied to a wide range of real-world situations. The basic mathematical idea remains the same: we define decision variables, write a linear objective function, impose linear constraints, and then optimize the objective.

In the standard school curriculum, LPPs are often grouped into the following broad categories:

1. Manufacturing / Production Problems
2. Diet / Nutrition Problems
3. Transportation / Allocation Problems

This classification is useful because each category has a recurring pattern in the way the objective function and constraints are formed. Recognizing these patterns helps students translate word problems into mathematical form much faster and more accurately.

Manufacturing Problems

Objective

Determine the number of units of different products that should be produced and sold so as to maximize profit (or sometimes minimize cost).

Characteristics

• Decision Variables: Usually, $x$ and $y$ denote the number of units of Product A and Product B.
• Constraints: These usually arise from limited resources such as:
• Machine Time: e.g. "Machine 1 is available for at most 12 hours" gives a $\le$ type constraint.
• Labour Hours: e.g. "At most 500 labour hours are available" also gives a $\le$ constraint.
• Raw Material: e.g. "Only 50 kg of raw material is available" again gives a $\le$ constraint.
• Non-negativity: Since production quantities cannot be negative, we always take $x \ge 0, y \ge 0$.

Diet Problems

Objective

Determine the quantities of different foods to be included in a diet so as to minimize the total cost, while still meeting nutritional requirements.

Characteristics

• Decision Variables: Usually, $x$ and $y$ denote the amounts of Food I and Food II.
• Constraints: These arise from minimum required nutrient levels.
• Example: "The diet must contain at least 80 units of Vitamin A" gives a $\ge$ constraint.
• Since the requirements are usually minimum requirements, diet problems most often involve $\ge$ type inequalities.
• Feasible Region: Because of these $\ge$ constraints, the feasible region is very often unbounded.

Transportation Problems

Objective

Determine the transportation plan that minimizes the total transportation cost when goods must be shipped from a set of origins to a set of destinations.

Characteristics & Formulation Strategy (for 2 origins and 3 destinations)

Let the origins be factories $A$ and $B$, and the destinations be depots $D, E, F$.

• Supply: Factory $A$ has $S_A$ units and factory $B$ has $S_B$ units.
• Demand: Depots require $d_D, d_E, d_F$ units respectively.
• In standard textbook problems, total supply usually equals total demand.
• Decision Variables: For a 2-variable graphical formulation, we may let:
• $x$ = units sent from $A$ to $D$
• $y$ = units sent from $A$ to $E$
• Then the other shipments are written in terms of $x$ and $y$:
• From $A$ to $F$: $S_A - x - y$
• From $B$ to $D$: $d_D - x$
• From $B$ to $E$: $d_E - y$
• From $B$ to $F$: $d_F - (S_A - x - y)$
• Constraints: Every shipment must be non-negative, which gives the inequalities that define the feasible region.

Example 1: Manufacturing Problem

A company manufactures two types of novelty souvenirs made of plywood. Souvenir of type A requires 5 minutes each for cutting and 10 minutes each for assembling. Souvenir of type B requires 8 minutes each for cutting and 8 minutes each for assembling. There are 3 hours and 20 minutes available for cutting and 4 hours available for assembling. The profit is Rs 50 each for type A and Rs 60 each for type B. How many souvenirs of each type should the company manufacture in order to maximize profit?

Solution: Step 1: Let the number of type A souvenirs be $x$ and the number of type B souvenirs be $y$.

Step 2: Since profit on A is Rs 50 and on B is Rs 60, the objective function is $$Z = 50x + 60y$$ and we have to maximize $Z$.

Step 3: Cutting time available is 3 hours 20 minutes = 200 minutes. Each A requires 5 minutes and each B requires 8 minutes, so $$5x + 8y \le 200.$$

Step 4: Assembling time available is 4 hours = 240 minutes. Each A requires 10 minutes and each B requires 8 minutes, so $$10x + 8y \le 240,$$ which simplifies to $$5x + 4y \le 120.$$

Step 5: Since numbers of souvenirs cannot be negative, $$x \ge 0, \quad y \ge 0.$$

Step 6: Find the corner points of the feasible region.

• From $5x + 4y \le 120$, x-intercept is $(24,0)$.
• From $5x + 8y \le 200$, y-intercept is $(0,25)$.
• Intersection of the two lines: $$5x + 8y = 200, \quad 5x + 4y = 120.$$ Subtracting gives $$4y = 80 \implies y = 20.$$ Substituting into $5x + 4y = 120$, $$5x + 80 = 120 \implies 5x = 40 \implies x = 8.$$ So the corner points are $(0,0), (24,0), (8,20), (0,25)$.

Step 7: Evaluate $Z$ at these points:

• $(0,0)$: $Z = 0$
• $(24,0)$: $Z = 50(24) = 1200$
• $(8,20)$: $Z = 50(8) + 60(20) = 400 + 1200 = 1600$
• $(0,25)$: $Z = 60(25) = 1500$

Step 8: The maximum value is 1600 at $(8,20)$.

Answer: The company should manufacture 8 souvenirs of type A and 20 souvenirs of type B for a maximum profit of Rs 1600.

Example 2: Diet Problem

A diet is to contain at least 80 units of vitamin A and 100 units of minerals. Two foods $F_1$ and $F_2$ are available. Food $F_1$ costs Rs 4 per unit and $F_2$ costs Rs 6 per unit. One unit of food $F_1$ contains 3 units of vitamin A and 4 units of minerals. One unit of food $F_2$ contains 6 units of vitamin A and 3 units of minerals. Formulate this as an LPP to find the minimum cost of the diet.

Solution: Step 1: Let $x$ units of food $F_1$ and $y$ units of food $F_2$ be used.

Step 2: Since the costs are Rs 4 and Rs 6 per unit, the objective function is $$Z = 4x + 6y$$ and we have to minimize $Z$.

Step 3: Vitamin A requirement is at least 80 units. Food $F_1$ contributes $3x$ units and food $F_2$ contributes $6y$ units, so $$3x + 6y \ge 80.$$

Step 4: Mineral requirement is at least 100 units. Food $F_1$ contributes $4x$ and food $F_2$ contributes $3y$, so $$4x + 3y \ge 100.$$

Step 5: Non-negativity constraints are $$x \ge 0, \quad y \ge 0.$$

Step 6: Find important boundary corner points.

• On x-axis, for feasibility both inequalities must hold. This gives $$3x \ge 80 \Rightarrow x \ge \frac{80}{3}, \quad 4x \ge 100 \Rightarrow x \ge 25.$$ So the x-axis boundary point is $\left(\frac{80}{3},0\right)$.
• On y-axis, feasibility requires $$6y \ge 80 \Rightarrow y \ge \frac{40}{3}, \quad 3y \ge 100 \Rightarrow y \ge \frac{100}{3}.$$ So the y-axis boundary point is $\left(0,\frac{100}{3}\right)$.
• Intersection of the two lines: $$3x + 6y = 80, \quad 4x + 3y = 100.$$ Multiply the second equation by 2: $$8x + 6y = 200.$$ Subtract the first: $$5x = 120 \Rightarrow x = 24.$$ Then $$3(24) + 6y = 80 \Rightarrow 72 + 6y = 80 \Rightarrow 6y = 8 \Rightarrow y = \frac{4}{3}.$$ So the intersection point is $\left(24,\frac{4}{3}\right)$.

Step 7: Evaluate the cost function:

• At $\left(\frac{80}{3},0\right)$: $$Z = 4\left(\frac{80}{3}\right) = \frac{320}{3} \approx 106.67$$
• At $\left(24,\frac{4}{3}\right)$: $$Z = 4(24) + 6\left(\frac{4}{3}\right) = 96 + 8 = 104$$
• At $\left(0,\frac{100}{3}\right)$: $$Z = 6\left(\frac{100}{3}\right) = 200$$

Step 8: Minimum value is 104, obtained at $\left(24,\frac{4}{3}\right)$.

Answer: Minimum cost is Rs 104 when 24 units of $F_1$ and $\frac{4}{3}$ units of $F_2$ are used.

Example 3: Transportation Problem (Formulation)

Two factories A and B have production capacities of 50 and 40 units respectively. They supply to three depots D, E, F which have demands of 20, 30, and 40 units respectively. The transportation cost per unit (in Rs) from factories to depots are given below. Formulate an LPP to minimize total transportation cost. A to D: 5, A to E: 3, A to F: 4 B to D: 4, B to E: 2, B to F: 6

Solution: Step 1: Total supply is $50 + 40 = 90$ and total demand is $20 + 30 + 40 = 90$, so the problem is balanced.

Step 2: Let

• $x$ = units sent from A to D
• $y$ = units sent from A to E

Step 3: Express the remaining shipments:

• A to F = $50 - x - y$
• B to D = $20 - x$
• B to E = $30 - y$
• B to F = $40 - (50 - x - y) = x + y - 10$

Step 4: Since each shipment must be non-negative, the constraints are: $$x \ge 0, \quad y \ge 0,$$ $$50 - x - y \ge 0 \Rightarrow x + y \le 50,$$ $$20 - x \ge 0 \Rightarrow x \le 20,$$ $$30 - y \ge 0 \Rightarrow y \le 30,$$ $$x + y - 10 \ge 0 \Rightarrow x + y \ge 10.$$

Step 5: Form the cost function: $$Z = 5x + 3y + 4(50-x-y) + 4(20-x) + 2(30-y) + 6(x+y-10).$$ Now simplify: $$Z = 5x + 3y + 200 - 4x - 4y + 80 - 4x + 60 - 2y + 6x + 6y - 60$$ $$Z = (5-4-4+6)x + (3-4-2+6)y + (200+80+60-60)$$ $$Z = 3x + 3y + 280.$$

Answer: Minimize $$Z = 3x + 3y + 280$$ subject to $$x + y \le 50, \quad x + y \ge 10, \quad x \le 20, \quad y \le 30, \quad x \ge 0, \quad y \ge 0.$$

Example 4: Allocation Problem

A farmer has a supply of chemical fertilizer of type I which contains 10% nitrogen and 6% phosphoric acid and type II fertilizer which contains 5% nitrogen and 10% phosphoric acid. After testing the soil conditions, he finds that he needs at least 14 kg of nitrogen and 14 kg of phosphoric acid for his crop. If type I fertilizer costs Rs 6/kg and type II costs Rs 5/kg, determine how many kilograms of each fertilizer should be used so that nutrient requirements are met at a minimum cost.

Solution: Step 1: Let $x$ kg of type I and $y$ kg of type II fertilizer be used.

Step 2: Objective function: $$Z = 6x + 5y$$ which is to be minimized.

Step 3: Nitrogen requirement: Type I gives 10% nitrogen and type II gives 5% nitrogen, so $$0.10x + 0.05y \ge 14.$$ Multiply by 100: $$10x + 5y \ge 1400 \Rightarrow 2x + y \ge 280.$$

Step 4: Phosphoric acid requirement: Type I gives 6% and type II gives 10%, so $$0.06x + 0.10y \ge 14.$$ Multiply by 100: $$6x + 10y \ge 1400 \Rightarrow 3x + 5y \ge 700.$$

Step 5: Non-negativity: $$x \ge 0, \quad y \ge 0.$$

Step 6: Find the intersection of the two boundary lines: $$2x + y = 280, \quad 3x + 5y = 700.$$ Multiply the first by 5: $$10x + 5y = 1400.$$ Subtract the second: $$7x = 700 \Rightarrow x = 100.$$ Then $$2(100) + y = 280 \Rightarrow y = 80.$$ So the intersection point is $(100,80)$.

Step 7: Find the axis boundary corner points of the feasible region.

• On x-axis, $y=0$: $$2x \ge 280 \Rightarrow x \ge 140,$$ $$3x \ge 700 \Rightarrow x \ge \frac{700}{3}.$$ So the feasible x-axis boundary point is $\left(\frac{700}{3},0\right)$.
• On y-axis, $x=0$: $$y \ge 280, \quad 5y \ge 700 \Rightarrow y \ge 140.$$ So the feasible y-axis boundary point is $(0,280)$.

Step 8: Evaluate the objective function:

• At $\left(\frac{700}{3},0\right)$: $$Z = 6\cdot\frac{700}{3} = 1400$$
• At $(100,80)$: $$Z = 6(100) + 5(80) = 600 + 400 = 1000$$
• At $(0,280)$: $$Z = 5(280) = 1400$$

Step 9: The minimum cost is Rs 1000 at $(100,80)$.

Answer: Minimum cost is Rs 1000 when the farmer uses 100 kg of type I and 80 kg of type II fertilizer.

Example 5: Investment Problem

A merchant plans to sell two types of personal computers: a desktop model and a portable model that will cost Rs 25000 and Rs 40000 respectively. He estimates that the total monthly demand of computers will not exceed 250 units. Determine the number of units of each type of computer which the merchant should stock to get maximum profit if he does not want to invest more than Rs 70 lakhs and if his profit on the desktop model is Rs 4500 and on the portable model is Rs 5000.

Solution: Step 1: Let $x$ be the number of desktop models and $y$ be the number of portable models.

Step 2: Objective function: $$Z = 4500x + 5000y$$ which is to be maximized.

Step 3: Demand constraint: $$x + y \le 250.$$

Step 4: Investment constraint: $$25000x + 40000y \le 7000000.$$ Divide by 5000: $$5x + 8y \le 1400.$$

Step 5: Non-negativity: $$x \ge 0, \quad y \ge 0.$$

Step 6: Find the corner points.

• x-axis intercepts: from $x+y \le 250$ gives $(250,0)$; from $5x+8y \le 1400$ gives $(280,0)$. So the feasible x-axis boundary point is $(250,0)$.
• y-axis intercepts: from $x+y \le 250$ gives $(0,250)$; from $5x+8y \le 1400$ gives $(0,175)$. So the feasible y-axis boundary point is $(0,175)$.
• Intersection of $$x+y=250, \quad 5x+8y=1400.$$ Multiply the first by 5: $$5x+5y=1250.$$ Subtract from the second: $$3y=150 \Rightarrow y=50.$$ Hence $$x=200.$$ So the intersection point is $(200,50)$.

Step 7: Evaluate $Z$:

• At $(250,0)$: $$Z = 4500(250) = 1125000$$
• At $(200,50)$: $$Z = 4500(200) + 5000(50) = 900000 + 250000 = 1150000$$
• At $(0,175)$: $$Z = 5000(175) = 875000$$

Step 8: Maximum profit is Rs 11,50,000 at $(200,50)$.

Answer: The merchant should stock 200 desktop models and 50 portable models.

Example 6: Production Problem with Three Constraints

A company produces two different products. One of them needs 1/4 of an hour of assembly work per unit, 1/8 of an hour in quality control work, and Rs 1.2 in raw materials. The other requires 1/3 of an hour of assembly work per unit, 1/3 of an hour in quality control, and Rs 0.9 in raw materials. Given the current availability of staff, there are at most 90 hours for assembly and 80 hours for quality control available each day. The daily raw material budget is Rs 600. The profit for the first product is Rs 9, and the second is Rs 8. Find the optimal production to maximize profit.

Solution: Step 1: Let $x$ and $y$ denote the daily units of product 1 and product 2 respectively.

Step 2: Objective function: $$Z = 9x + 8y$$ which is to be maximized.

Step 3: Assembly time constraint: $$\frac{1}{4}x + \frac{1}{3}y \le 90.$$ Multiply by 12: $$3x + 4y \le 1080.$$

Step 4: Quality control constraint: $$\frac{1}{8}x + \frac{1}{3}y \le 80.$$ Multiply by 24: $$3x + 8y \le 1920.$$

Step 5: Raw material budget: $$1.2x + 0.9y \le 600.$$ Multiply by 10: $$12x + 9y \le 6000 \Rightarrow 4x + 3y \le 2000.$$

Step 6: Non-negativity: $$x \ge 0, \quad y \ge 0.$$

Step 7: Check important boundary intersections.

• Intersection of $3x+4y=1080$ and $4x+3y=2000$ gives a negative y-value, so that point lies outside the feasible region.
• x-axis intercepts:
• $3x+4y=1080 \Rightarrow x=360$
• $3x+8y=1920 \Rightarrow x=640$
• $4x+3y=2000 \Rightarrow x=500$ Hence the tightest x-axis bound is $(360,0)$.
• y-axis intercepts:
• $3x+4y=1080 \Rightarrow y=270$
• $3x+8y=1920 \Rightarrow y=240$
• $4x+3y=2000 \Rightarrow y=\frac{2000}{3}$ Hence the tightest y-axis bound is $(0,240)$.
• Intersection of $3x+4y=1080$ and $3x+8y=1920$: Subtracting gives $$4y = 840 \Rightarrow y = 210.$$ Then $$3x + 4(210) = 1080 \Rightarrow 3x = 240 \Rightarrow x = 80.$$ So this intersection point is $(80,210)$.
• Check budget constraint at $(80,210)$: $$4(80) + 3(210) = 320 + 630 = 950 \le 2000.$$ So it is feasible, and the budget constraint is not active in the optimal region.

Step 8: Evaluate $Z$ at the corner points $(0,0), (360,0), (80,210), (0,240)$:

• $(0,0)$: $Z=0$
• $(360,0)$: $Z = 9(360)=3240$
• $(80,210)$: $Z = 9(80)+8(210)=720+1680=2400$
• $(0,240)$: $Z = 8(240)=1920$

Step 9: Maximum profit is 3240 at $(360,0)$.

Answer: The optimal production is 360 units of product 1 and 0 units of product 2, giving a maximum profit of Rs 3240.

Example 7: Aeroplane Ticket Allocation

An aeroplane can carry a maximum of 200 passengers. A profit of Rs 1000 is made on each executive class ticket and a profit of Rs 600 is made on each economy class ticket. The airline reserves at least 20 seats for executive class. However, at least 4 times as many passengers prefer to travel by economy class than by the executive class. Determine how many tickets of each type must be sold in order to maximize the profit for the airline.

Solution: Step 1: Let $x$ be the number of executive class tickets and $y$ be the number of economy class tickets.

Step 2: Objective function: $$Z = 1000x + 600y$$ which is to be maximized.

Step 3: Capacity constraint: $$x + y \le 200.$$

Step 4: Reserved executive seats imply $$x \ge 20.$$

Step 5: Economy demand is at least 4 times executive demand: $$y \ge 4x.$$

Step 6: Non-negativity: $$x \ge 0, \quad y \ge 0.$$

Step 7: Corner points of the feasible region:

• Intersection of $x=20$ and $y=4x$ gives $(20,80)$.
• Intersection of $x=20$ and $x+y=200$ gives $(20,180)$.
• Intersection of $y=4x$ and $x+y=200$ gives $$x+4x=200 \Rightarrow 5x=200 \Rightarrow x=40, y=160.$$ So point $(40,160)$.

Step 8: Evaluate $Z$:

• $(20,80)$: $Z = 1000(20)+600(80)=20000+48000=68000$
• $(20,180)$: $Z = 1000(20)+600(180)=20000+108000=128000$
• $(40,160)$: $Z = 1000(40)+600(160)=40000+96000=136000$

Step 9: Maximum profit is Rs 1,36,000 at $(40,160)$.

Answer: The airline should sell 40 executive class tickets and 160 economy class tickets.

Example 8: Transportation Problem

An oil company has two depots A and B with capacities of 7000 L and 4000 L respectively. The company is to supply oil to three petrol pumps, D, E and F whose requirements are 4500L, 3000L and 3500L respectively. The distances (in km) between the depots and the petrol pumps is given below: A to D: 7, A to E: 6, A to F: 3. B to D: 3, B to E: 4, B to F: 2. Assuming the transportation cost of 10 litres of oil is Re 1 per km, how should the delivery be scheduled to minimize total transportation cost?

Solution: Step 1: Total supply is $7000+4000=11000$ L and total demand is $4500+3000+3500=11000$ L, so the problem is balanced.

Step 2: Let

• $x$ litres be transported from A to D,
• $y$ litres be transported from A to E.

Step 3: Then the remaining shipments are:

• A to F = $7000 - x - y$
• B to D = $4500 - x$
• B to E = $3000 - y$
• B to F = $3500 - (7000 - x - y) = x + y - 3500$

Step 4: Cost of carrying 10 litres for 1 km is Re 1, so cost per litre per km is Rs 0.1. Hence the transportation cost is $$Z = 0.7x + 0.6y + 0.3(7000-x-y) + 0.3(4500-x) + 0.4(3000-y) + 0.2(x+y-3500).$$ Now simplify: $$Z = 0.7x + 0.6y + 2100 - 0.3x - 0.3y + 1350 - 0.3x + 1200 - 0.4y + 0.2x + 0.2y - 700$$ $$Z = (0.7-0.3-0.3+0.2)x + (0.6-0.3-0.4+0.2)y + (2100+1350+1200-700)$$ $$Z = 0.3x + 0.1y + 3950.$$

Step 5: Non-negativity of all shipments gives the constraints: $$x \ge 0, \quad y \ge 0,$$ $$7000 - x - y \ge 0 \Rightarrow x+y \le 7000,$$ $$4500 - x \ge 0 \Rightarrow x \le 4500,$$ $$3000 - y \ge 0 \Rightarrow y \le 3000,$$ $$x+y-3500 \ge 0 \Rightarrow x+y \ge 3500.$$

Answer: Minimize $$Z = 0.3x + 0.1y + 3950$$ subject to $$x+y \le 7000, \quad x+y \ge 3500, \quad x \le 4500, \quad y \le 3000, \quad x \ge 0, \quad y \ge 0.$$

Example 9: Furniture Manufacturing (Time Constraint)

A manufacturer makes two products: desks and chairs. A desk requires 4 hours of woodworking and 2 hours of finishing. A chair requires 3 hours of woodworking and 1 hour of finishing. The manufacturer has 240 hours of woodworking and 100 hours of finishing available. Profit on a desk is Rs 40 and on a chair is Rs 25. Formulate LPP.

Solution: Step 1: Let $x$ be the number of desks and $y$ be the number of chairs.

Step 2: Profit function: $$Z = 40x + 25y$$ which is to be maximized.

Step 3: Woodworking hours: Each desk uses 4 hours and each chair uses 3 hours, so $$4x + 3y \le 240.$$

Step 4: Finishing hours: Each desk uses 2 hours and each chair uses 1 hour, so $$2x + y \le 100.$$

Step 5: Non-negativity: $$x \ge 0, \quad y \ge 0.$$

Answer: Maximize $$Z = 40x + 25y$$ subject to $$4x + 3y \le 240, \quad 2x + y \le 100, \quad x \ge 0, \quad y \ge 0.$$

Example 10: Diet Problem with Budget Constraint

A person wants to decide the constituents of a diet which will fulfill his daily requirements of proteins, fats, and carbohydrates at the minimum cost. The choice is to be made from four different types of foods. (For simplicity, we reduce to 2 foods A and B). Food A yields 3 units of protein, 2 of fats, and 6 of carbs per unit. Food B yields 2 of protein, 2 of fats, and 4 of carbs per unit. Minimum requirements are 800 proteins, 200 fats, and 700 carbs. Cost of A is Rs 2, cost of B is Rs 1. Formulate.

Solution: Step 1: Let $x$ units of food A and $y$ units of food B be consumed.

Step 2: Objective function: $$Z = 2x + y$$ which is to be minimized.

Step 3: Protein requirement: $$3x + 2y \ge 800.$$

Step 4: Fat requirement: $$2x + 2y \ge 200 \Rightarrow x + y \ge 100.$$

Step 5: Carbohydrate requirement: $$6x + 4y \ge 700 \Rightarrow 3x + 2y \ge 350.$$

Step 6: Non-negativity: $$x \ge 0, \quad y \ge 0.$$

Step 7: Observe redundancy. Since the protein constraint is $$3x + 2y \ge 800,$$ it automatically implies $$3x + 2y \ge 350.$$ Therefore the carbohydrate constraint is weaker and is redundant.

Answer: Minimize $$Z = 2x + y$$ subject to $$3x + 2y \ge 800, \quad x + y \ge 100, \quad x \ge 0, \quad y \ge 0.$$