Linear Programming Tutorial Week 7

Problem 1 Problem Statement: A small factory produces two types of products: A and B. The production of each product requires two resources: labor hours and raw materials. Each unit of product A requires 2 labor hours and 3 units of raw materials, while each unit of product B requires 4 labor hours and 2 units of raw materials. The factory has a total of 120 labor hours and 100 units of raw materials available per week. The profit per unit is $30 for product A and $50 for product B. Formulate and solve a linear programming problem to maximize the factory’s weekly profit. Step 1: Define the Decision Variables Let: x = Number of units of product A to produce per week. y = Number of units of product B to produce per week. Step 2: Formulate the Objective Function The objective is to maximize the total profit: Maximize Z = 30x + 50y Step 3: Formulate the Constraints 1. Labor hours constraint: 2x + 4y ≤ 120 2. Raw materials constraint: 3x + 2y ≤ 100 3. Non-negativity constraints: x ≥ 0, y ≥ 0 Step 4: Solve the Problem To solve, graph the constraints and find the feasible region. Identify the vertices of the feasible region and evaluate the objective function at each vertex. Solution: The vertices of the feasible region are: • (0, 30): Z = 0(30) + 50(30) = 1500 • (20, 20): Z = 30(20) + 50(20) = 1600 • (33.33, 0): Z = 30(33.33) + 50(0) = 1000 Conclusion: The maximum profit is achieved at (20, 20), with a maximum profit of: Z = 1600 — Problem 2 Problem Statement: A transportation company needs to decide how to allocate its fleet of trucks to deliver three types of goods: G1 , G2 , and G3 , to maximize revenue. Each type of good requires different loading and transport times per truck and generates different revenues. The company has the following constraints: 1 - A maximum of 150 loading hours is available. - A maximum of 120 transport hours is available. - At most 40 trucks can be allocated. The table below summarizes the requirements and revenue for each type of good: Good G1 G2 G3 Loading Time (hours/truck) 3 4 5 Transport Time (hours/truck) 2 3 4 Revenue ($/truck) 400 500 600 Determine the optimal number of trucks to allocate to each type of good to maximize revenue. Additionally, solve the dual problem to interpret the shadow prices of the constraints. Step 1: Define the Decision Variables Let: x1 = Number of trucks allocated to G1 x2 = Number of trucks allocated to G2 x3 = Number of trucks allocated to G3 Step 2: Formulate the Objective Function The objective is to maximize revenue: Maximize Z = 400x1 + 500x2 + 600x3 Step 3: Formulate the Constraints 1. Loading hours constraint: 3x1 + 4x2 + 5x3 ≤ 150 2. Transport hours constraint: 2x1 + 3x2 + 4x3 ≤ 120 3. Truck availability constraint: x1 + x2 + x3 ≤ 40 4. Non-negativity constraints: x1 , x2 , x3 ≥ 0 Step 4: Solve the Primal Problem Using the simplex method or computational tools, solve the system. Solution: The optimal solution is: x1 = 10, x2 = 20, x3 = 10 The maximum revenue is: Z = 400(10) + 500(20) + 600(10) = 20000 2 Step 5: Solve the Dual Problem Define y1 , y2 , y3 as the shadow prices for the loading hours, transport hours, and truck availability constraints, respectively. The dual problem is: Minimize W = 150y1 + 120y2 + 40y3 Subject to: 1. 3y1 + 2y2 + y3 ≥ 400 2. 4y1 + 3y2 + y3 ≥ 500 3. 5y1 + 4y2 + y3 ≥ 600 4. y1 , y2 , y3 ≥ 0 Solution: The optimal shadow prices are: y1 = 100, y2 = 0, y3 = 200 Interpretation: • Shadow price of loading hours: $100 • Shadow price of transport hours: $0 • Shadow price of truck availability: $200 Step 6: Conclusion The company should allocate 10 trucks to G1 , 20 trucks to G2 , and 10 trucks to G3 to achieve a maximum revenue of $20000. 3