LINEAR PROGRAMMNG QUESTIONS (With Comprehensive solution)

Linear Programming Problems

Problem 1

A man owns a field of area 1000m². He wants to plant trees in it. He has a sum of Tsh 1400 to purchase young trees. He has the choice of two types of trees:

• Type A requires 10m² of ground per tree and costs Tsh 20 per tree
• Type B requires 20m² of ground per tree and costs Tsh 25 per tree

When fully grown:

• Type A produces an average of 20kg of fruits which can be sold at a profit of Tsh 2 per kg
• Type B produces an average of 40kg of fruits which can be sold at a profit of Tsh 1.5 per kg

How many trees of each type should be planted to achieve maximum profit when the trees are fully grown? What is the maximum profit?

Problem 2

Kurwa has 20,000/= to invest in three funds:

• Fund F1 offers a return of 2% and has low risk
• Fund F2 offers a return of 4% and has medium risk
• Fund F3 offers a return of 5% but has high risk

Investment constraints:

• No more than 3,000/= in F3
• At least twice as much in F1 than in F2

Assuming that the rates hold till the end of the year, what amount should he invest in each fund in order to maximize the year-end return?

Problem 3

A company produces two types of ornaments A and B that require gold and silver:

• Each unit of type A requires 4 grams of silver and 8 grams of gold
• Each unit of type B requires 8 grams of silver and 4 grams of gold

Available resources:

• 400 grams of silver
• 640 grams of gold

Profit per unit:

• Type A brings a profit of 1,000 Tsh
• Type B brings a profit of 1,600 Tsh

How should the company produce ornaments to obtain the maximum profit?

Problem 4

A retail shop receives orders from customers C1 and C2 for food packages:

• Package for C1 contains: 50kg beans, 30kg rice, and 70kg maize
• Package for C2 contains: 25kg beans and 45kg rice

Available stock:

• 850kg beans
• 810kg rice
• 980kg maize

Cost per package:

• C1 package costs 2,100 Tsh
• C2 package costs 1,800 Tsh

(i) Formulate a linear programming problem

(ii) How many packages should be supplied by the retail shop to realize maximum sales?

(iii) How much stock remains after meeting the orders?

Problem 5

An animal meal is to be made from two different kinds of food:

• Food F1 contains: 3 units of nutrient N1, 3 units of N2, and 4 units of N3 (cost: 8,000 Tsh per bag)
• Food F2 contains: 1 unit of N1, 3 units of N2, and 4 units of N3 (cost: 6,000 Tsh per bag)

Nutritional requirements per meal:

• At least 21 units of N1
• At least 30 units of N2
• At least 60 units of N3

How many bags of each type of food should be ordered to satisfy the nutritional requirements at minimum cost?

Problem 6

A manufacturer has two godowns storing products:

• Godown G1: 80 units
• Godown G2: 70 units

Customer orders:

• Customer C1: 35 units
• Customer C2: 60 units

Transport costs per unit:

Godown	Customer C1	Customer C2
G1	80/=	120/=
G2	100/=	130/=

How many units should the manufacturer deliver to each customer from each godown to minimize total transport cost?

Linear Programming Solutions

Detailed step-by-step solutions with explanations for all six problems

Problem 1: Tree Planting Optimization

How many trees of each type should be planted to maximize profit given area and budget constraints?

Solution:

Step 1: Define Variables
Let:
x = number of Type A trees
y = number of Type B trees

Step 2: Formulate Constraints
1. Area constraint: 10x + 20y ≤ 1000
2. Budget constraint: 20x + 25y ≤ 1400
3. Non-negativity: x ≥ 0, y ≥ 0

Step 3: Formulate Objective Function
Profit from Type A: 20kg × 2Tsh/kg = 40Tsh per tree
Profit from Type B: 40kg × 1.5Tsh/kg = 60Tsh per tree
Maximize: Z = 40x + 60y

Step 4: Solve Graphically
Find intersection points of constraints:
1. Intersection of 10x + 20y = 1000 and 20x + 25y = 1400
Solution: x = 40, y = 30
2. Test all corner points: (0,0), (0,50), (70,0), (40,30)

Step 5: Evaluate Objective at Corner Points

Point (x,y)	Profit Z = 40x + 60y
(0,0)	0 Tsh
(0,50)	3,000 Tsh
(70,0)	2,800 Tsh
(40,30)	3,400 Tsh (maximum)

Final Answer:
Plant 40 Type A trees and 30 Type B trees
Maximum profit: 3,400 Tsh

Problem 2: Investment Portfolio Optimization

How should Kurwa allocate 20,000/= among three funds to maximize return with given constraints?

Solution:

Step 1: Define Variables
Let:
x = amount in F1 (low risk)
y = amount in F2 (medium risk)
z = amount in F3 (high risk)

Step 2: Formulate Constraints
1. Total investment: x + y + z = 20,000
2. High risk limit: z ≤ 3,000
3. Ratio constraint: x ≥ 2y
4. Non-negativity: x ≥ 0, y ≥ 0, z ≥ 0

Step 3: Formulate Objective Function
Total return: R = 0.02x + 0.04y + 0.05z
Maximize R

Step 4: Simplify Problem
Express in terms of two variables using x + y + z = 20,000 ⇒ z = 20,000 - x - y
Substitute into other constraints:
20,000 - x - y ≤ 3,000 ⇒ x + y ≥ 17,000
x ≥ 2y

Step 5: Find Corner Points
1. Intersection of x = 2y and x + y = 17,000
Solution: y = 5,666.67, x = 11,333.33, z = 3,000
2. When z = 3,000 and x = 2y, with x + y = 17,000

Step 6: Evaluate Objective
At (11,333.33, 5,666.67, 3,000):
R = 0.02(11,333.33) + 0.04(5,666.67) + 0.05(3,000) = 226.67 + 226.67 + 150 = 603.34 Tsh
(This is the maximum possible return under given constraints)

Final Answer:
Invest 11,333.33/= in F1, 5,666.67/= in F2, and 3,000/= in F3
Maximum return: 603.34 Tsh at year end

Problem 3: Ornament Production Optimization

How should the company produce ornaments A and B to maximize profit given material constraints?

Solution:

Step 1: Define Variables
Let:
x = units of Type A ornaments
y = units of Type B ornaments

Step 2: Formulate Constraints
1. Silver constraint: 4x + 8y ≤ 400
2. Gold constraint: 8x + 4y ≤ 640
3. Non-negativity: x ≥ 0, y ≥ 0

Step 3: Formulate Objective Function
Profit: Z = 1000x + 1600y
Maximize Z

Step 4: Solve Graphically
Find intersection points:
1. Intersection of 4x + 8y = 400 and 8x + 4y = 640
Solution: x = 80, y = 10
2. Corner points: (0,0), (0,50), (80,0), (80,10)

Step 5: Evaluate Objective at Corner Points

Point (x,y)	Profit Z = 1000x + 1600y
(0,0)	0 Tsh
(0,50)	80,000 Tsh
(80,0)	80,000 Tsh
(80,10)	96,000 Tsh (maximum)

Final Answer:
Produce 80 units of Type A and 10 units of Type B
Maximum profit: 96,000 Tsh

Problem 4: Food Package Optimization

How many packages of each type should be supplied to maximize sales given stock constraints?

Solution:

Step 1: Define Variables
Let:
x = number of C1 packages
y = number of C2 packages

Step 2: Formulate Constraints
1. Beans: 50x + 25y ≤ 850
2. Rice: 30x + 45y ≤ 810
3. Maize: 70x ≤ 980 (only C1 requires maize)
4. Non-negativity: x ≥ 0, y ≥ 0

Step 3: Formulate Objective Function
Sales revenue: Z = 2100x + 1800y
Maximize Z

Step 4: Solve Graphically
Find intersection points:
1. From maize constraint: x ≤ 14
2. Intersection of beans and rice constraints:
50x + 25y = 850 and 30x + 45y = 810
Solution: x = 12, y = 10
3. Corner points: (0,0), (0,18), (14,0), (12,10), (14,6)

Step 5: Evaluate Objective at Corner Points

Point (x,y)	Sales Z = 2100x + 1800y
(0,0)	0 Tsh
(0,18)	32,400 Tsh
(14,0)	29,400 Tsh
(12,10)	43,200 Tsh
(14,6)	42,000 Tsh

Step 6: Calculate Remaining Stock
For optimal solution (12,10):
Beans used: 50×12 + 25×10 = 850kg (none left)
Rice used: 30×12 + 45×10 = 810kg (none left)
Maize used: 70×12 = 840kg, Remaining: 980 - 840 = 140kg

Final Answer:
Supply 12 C1 packages and 10 C2 packages
Maximum sales: 43,200 Tsh
Remaining stock: 140kg maize

Problem 5: Animal Feed Optimization

How many bags of each food type should be ordered to meet nutritional requirements at minimum cost?

Solution:

Step 1: Define Variables
Let:
x = bags of Food F1
y = bags of Food F2

Step 2: Formulate Constraints
1. Nutrient N1: 3x + y ≥ 21
2. Nutrient N2: 3x + 3y ≥ 30
3. Nutrient N3: 4x + 4y ≥ 60
4. Non-negativity: x ≥ 0, y ≥ 0

Step 3: Formulate Objective Function
Total cost: C = 8000x + 6000y
Minimize C

Step 4: Simplify Constraints
1. N2 constraint: x + y ≥ 10
2. N3 constraint: x + y ≥ 15 (dominant over N2)
3. N1 constraint remains: 3x + y ≥ 21

Step 5: Find Corner Points
1. Intersection of x + y = 15 and 3x + y = 21
Solution: x = 3, y = 12
2. When y = 0: x = 15 (from N3)

Step 6: Evaluate Objective
At (3,12): C = 8000×3 + 6000×12 = 96,000 Tsh
At (15,0): C = 8000×15 = 120,000 Tsh
Other points give higher costs

Final Answer:
Order 3 bags of F1 and 12 bags of F2
Minimum cost: 96,000 Tsh

Problem 6: Transportation Cost Minimization

How should products be delivered from godowns to customers to minimize transport costs?

Solution:

Step 1: Define Variables
Let:
x = units from G1 to C1
y = units from G1 to C2
Then:
35 - x = units from G2 to C1
60 - y = units from G2 to C2

Step 2: Formulate Constraints
1. G1 capacity: x + y ≤ 80
2. G2 capacity: (35 - x) + (60 - y) ≤ 70 ⇒ x + y ≥ 25
3. C1 demand: x + (35 - x) = 35 (automatically satisfied)
4. C2 demand: y + (60 - y) = 60 (automatically satisfied)
5. Non-negativity: x ≥ 0, y ≥ 0, 35 - x ≥ 0, 60 - y ≥ 0

Step 3: Formulate Objective Function
Total transport cost:
C = 80x + 120y + 100(35 - x) + 130(60 - y)
Simplify: C = -20x - 10y + 11,300
Minimize C (equivalent to maximizing 20x + 10y)

Step 4: Find Corner Points
Feasible region between 25 ≤ x + y ≤ 80
Additional constraints: 0 ≤ x ≤ 35, 0 ≤ y ≤ 60
Corner points: (0,25), (0,60), (35,0), (20,0), (35,45)

Step 5: Evaluate Objective

Point (x,y)	Cost C = -20x - 10y + 11,300
(0,25)	-20(0) -10(25) + 11,300 = 11,050 Tsh
(0,60)	-20(0) -10(60) + 11,300 = 10,700 Tsh
(35,0)	-20(35) -10(0) + 11,300 = 10,600 Tsh
(20,0)	-20(20) -10(0) + 11,300 = 10,900 Tsh
(35,45)	-20(35) -10(45) + 11,300 = 9,800 Tsh (minimum)

Step 6: Verify Feasibility of Optimal Point
At (35,45):
From G1: 35 to C1, 45 to C2 (total 80 ≤ 80)
From G2: 0 to C1, 15 to C2 (total 15 ≤ 70)
All constraints satisfied

Final Answer:
Delivery plan:
- From G1: 35 units to C1, 45 units to C2
- From G2: 0 units to C1, 15 units to C2
Minimum transport cost: 9,800 Tsh