Linear Programming

Linear programming Question 1: Linear Programming Problem Maximize: z = 5x1 + 4x2   3x1 + 2x2 ≤ 18, Subject to: 2x1 + x2 ≤ 10,   x1 , x2 ≥ 0. Solution Step 1: Convert constraints to equations by adding slack variables. 3x1 + 2x2 + s1 = 18, 2x1 + x2 + s2 = 10, s1 , s2 ≥ 0. Step 2: Set up the initial Simplex tableau. Basic Variable x1 x2 s1 s2 Right-hand side (RHS) s1 3 2 1 0 18 2 1 0 1 10 s2 z −5 −4 0 0 0 Step 3: Perform pivoting. The pivot column is x1 (most negative in z-row). The RHS pivot row is s2 (smallest positive ratio Pivot , i.e., 10/2 = 5). After performing Gaussian elimination and additional iterations, the final tableau is: Basic Variable x1 x2 s1 s2 RHS x1 1 0.5 0 0.5 5 x2 0 1 0.5 −0.5 5 z 0 0 2.5 2.5 45 Solution: x1 = 5, x2 = 5, z = 45. — Question 2: Duality in Linear Programming Problem Given the primal: Minimize: z = 2x1 + 3x2 1   x1 + 4x2 ≥ 8, Subject to: 2x1 + 3x2 ≥ 10,   x1 , x2 ≥ 0. Solution Step 1: Write the primal in standard form. The primal is already in standard form with inequalities ≥. Step 2: Define the dual problem. Dual: Maximize w = 8y1 + 10y2   y1 + 2y2 ≤ 2, Subject to: 4y1 + 3y2 ≤ 3,   y1 , y2 ≥ 0. Step 3: Solution to Dual. Using the Simplex Method, the optimal solution to the dual is: y1 = 1, y2 = 1, w = 18. — Question 3: Simplex Method Problem Maximize: z = 7x1 + 6x2   x1 + 2x2 ≤ 8, Subject to: 3x1 + 2x2 ≤ 12,   x1 , x2 ≥ 0. Solution Step 1: Convert to standard form. x1 + 2x2 + s1 = 8, 3x1 + 2x2 + s2 = 12, s1 , s2 ≥ 0. Step 2: Set up the initial tableau. Basic Variable x1 x2 s1 s2 RHS s1 1 2 1 0 8 s2 3 2 0 1 12 z −7 −6 0 0 0 Step 3: Perform iterations. After solving: x1 = 4, x2 = 2, z = 46. — 2 Question 4: Integer Programming Problem Maximize: z = 6x1 + 5x2   x1 + x2 ≤ 6, Subject to: 2x1 + 3x2 ≤ 12,   x1 , x2 ≥ 0, x1 , x2 ∈ Z. Solution Step 1: Solve as an LP relaxation. Relaxing the integer constraints: x1 = 2.4, x2 = 3.6, z = 34.8. Step 2: Use Branch-and-Bound. Branching at x2 = 3 and solving for integer constraints yields: x1 = 2, x2 = 3, z = 33. Solution: x1 = 2, x2 = 3, z = 33. — Question 5: Sensitivity Analysis Problem Maximize: z = 4x1 + 3x2   x1 + 2x2 ≤ 10, Subject to: 3x1 + x2 ≤ 15,   x1 , x2 ≥ 0. Solution Step 1: Solve initial LP. Optimal solution is: x1 = 3, x2 = 2, z = 18. Step 2: Analyze constraint changes. If the second constraint changes to 3x1 + x2 ≤ 20, shadow price analysis indicates z increases by 5. New Solution: z = 23. 3