15.053 Lecture Notes - Lecture 9: Weak Duality
Document Summary
Duality: motivated by obtaining upper bounds for maximization problems. 11x + 20x + 27x minimize constraint 1: 3x + 5x + 7x 100 constraint 2: x + x + x 19 x , x , x 0 subject to. We nd that the optimal solution is 397. 5. Compare the objective function to 4 times constraint 2 and use the non-negativity constraint z = 11x + 20x + 27x 12x + 20x + 28x 400. Without solving the linear program, nd upper bounds on the optimum objective value by adding constraints subject to. Dual problem: obtaining the best (lowest) upper bound z = 60y + 170y + 8y subject to. Constraint 1: 5y + 10y + y 4. Constraint 3: 8y + 10y 6 y , y , y 0. Whenever we form a dual, the original problem is called the primal problem.
