University:
The University Of Western Ontario
Course:
MATH 3020A | Introduction to Abstract Algebra
Academic year:

2024
Views:

488

Pages:

3
Author:

Kyuwon J.

CO250 test prep Advanced Questions and Solutions Question 1: Linear Programming with Degeneracy Solve the following LP problem: Maximize: z = 4x1 + 3x2   x1 + x2 ≤ 6, Subject to: 3x1 + 2x2 ≤ 12,   x1 , x2 ≥ 0. Solution Step 1: Convert to standard form. x1 + x2 + s1 = 6, 3x1 + 2x2 + s2 = 12, s1 , s2 ≥ 0. Step 2: Initial Tableau. Basic Variable x1 x2 s1 RHS s1 1 1 1 6 3 2 0 12 s2 z −4 −3 0 0 Step 3: Solve iteratively. After pivoting, the final tableau is: Basic Variable x1 x2 s1 RHS x1 1 0 0.5 4 x2 0 1 0.5 2 z 0 0 2.5 20 Solution: x1 = 4, x2 = 2, z = 20. — Question 2: Integer Programming with Branch-and-Bound Solve the following Integer Programming problem: Maximize: z = 5x1 + 4x2   x1 + 2x2 ≤ 10, Subject to: 3x1 + x2 ≤ 12,   x1 , x2 ≥ 0, x1 , x2 ∈ Z. 1 Solution Step 1: Relax to LP. Relaxing the integer constraint, the optimal solution to the LP is: x1 = 3.2, x2 = 2.4, z = 26.4. Step 2: Branch at x1 = 3 and x1 = 4. Solving the branches: - For x1 = 3, x2 = 2, z = 23. - For x1 = 4, x2 = 1, z = 24. Solution: x1 = 4, x2 = 1, z = 24. — Question 3: Duality Analysis Given the primal: Maximize: z = 3x1 + 4x2   x1 + 2x2 ≤ 8, Subject to: 3x1 + x2 ≤ 6,   x1 , x2 ≥ 0. Write the dual problem and solve it. Solution Dual Problem: Minimize: w = 8y1 + 6y2   y1 + 3y2 ≥ 3, Subject to: 2y1 + y2 ≥ 4,   y1 , y2 ≥ 0. Solution to Dual: Using Simplex: y1 = 1.6, y2 = 0.4, w = 12. Dual Solution: w = 12. — Question 4: Sensitivity Analysis For the LP: Maximize: z = 6x1 + 3x2   2x1 + x2 ≤ 10, Subject to: x1 + 3x2 ≤ 15,   x1 , x2 ≥ 0. Analyze how the optimal solution changes if the RHS of the second constraint increases from 15 to 20. 2 Solution Step 1: Original Solution. Original optimal solution is: x1 = 5, x2 = 0, z = 30. Step 2: New Constraint. When RHS = 20, shadow price analysis shows: zincreasesby5 × shadow price. New Solution: x1 = 6, x2 = 0, z = 36. — 3