Question? Leave a message!




LP duality: economic interpretation

LP duality: economic interpretation
Dr.TomHunt Profile Pic
Dr.TomHunt,United States,Teacher
Published Date:23-07-2017
Website URL
Comment
LINEAR PROGRAMMING II LP duality ‣ strong duality theorem ‣ bonus proof of LP duality ‣ applications ‣ Lecture slides by Kevin Wayne Last updated on 5/15/17 10:34 AMLINEAR PROGRAMMING II LP duality ‣ Strong duality theorem ‣ Bonus proof of LP duality ‣ Applications ‣LP duality Primal problem. (P) max 13A + 23B s. t. 5A + 15B ≤ 480 4A + 4B ≤ 160 35A + 20B ≤ 1190 A , B ≥ 0 € Goal. Find a lower bound on optimal value. Easy. Any feasible solution provides one. Ex 1. (A, B) = (34, 0) ⇒ z ≥ 442 Ex 2. (A, B) = (0, 32) ⇒ z ≥ 736 Ex 3. (A, B) = (7.5, 29.5) ⇒ z ≥ 776 Ex 4. (A, B) = (12, 28) ⇒ z ≥ 800 3LP duality Primal problem. (P) max 13A + 23B s. t. 5A + 15B ≤ 480 4A + 4B ≤ 160 35A + 20B ≤ 1190 A , B ≥ 0 € Goal. Find an upper bound on optimal value. nd Ex 1. Multiply 2 inequality by 6: 24 A + 24 B ≤ 960. 
 ⇒ z = 13 A + 23 B ≤ 24 A + 24 B ≤ 960. objective function 4LP duality Primal problem. (P) max 13A + 23B s. t. 5A + 15B ≤ 480 4A + 4B ≤ 160 35A + 20B ≤ 1190 A , B ≥ 0 € Goal. Find an upper bound on optimal value. st nd Ex 2. Add 2 times 1 inequality to 2 inequality: ≤ ⇒ z = 13 A + 23 B ≤ 14 A + 34 B ≤ 1120. 5LP duality Primal problem. (P) max 13A + 23B s. t. 5A + 15B ≤ 480 4A + 4B ≤ 160 35A + 20B ≤ 1190 A , B ≥ 0 € Goal. Find an upper bound on optimal value. st nd Ex 2. Add 1 times 1 inequality to 2 times 2 inequality: ≤ ⇒ z = 13 A + 23 B ≤ 13 A + 23 B ≤ 800. 
 Recall lower bound. (A, B) = (34, 0) ⇒ z ≥ 442
 Combine upper and lower bounds: z = 800. 6LP duality Primal problem. (P) max 13A + 23B s. t. 5A + 15B ≤ 480 4A + 4B ≤ 160 35A + 20B ≤ 1190 A , B ≥ 0 Idea. Add nonnegative combination (C, H, M) of the constraints s.t.
 € 13A + 23B ≤ (5C + 4H + 35M ) A + (15C + 4H + 20M ) B ≤ 480C +160H +1190M Dual problem. Find best such upper bound. € (D) min 480C + 160H + 1190M s. t. 5C + 4H + 35M ≥ 13 15C + 4H + 20M ≥ 23 C , H , M ≥ 0 7 € LP duality: economic interpretation Brewer: find optimal mix of beer and ale to maximize profits. (P) max 13A + 23B s. t. 5A + 15B ≤ 480 4A + 4B ≤ 160 35A + 20B ≤ 1190 A , B ≥ 0 € Entrepreneur: buy individual resources from brewer at min cost. C, H, M = unit price for corn, hops, malt. ・ Brewer won't agree to sell resources if 5C + 4H + 35M 13. ・ (D) min 480C + 160H + 1190M s. t. 5C + 4H + 35M ≥ 13 15C + 4H + 20M ≥ 23 C , H , M ≥ 0 8 € LP duals Canonical form. T T (P) maxc x (D) miny b T s. t. Ax ≤ b s. t. A y ≥ c x ≥ 0 y ≥ 0 € € 9Double dual Canonical form. T T (P) maxc x (D) miny b T s. t. Ax ≤ b s. t. A y ≥ c x ≥ 0 y ≥ 0 € € Property. The dual of the dual is the primal. Pf. Rewrite (D) as a maximization problem in canonical form; take dual. T T (DD) min −c z (D') max −y b T T T s. t. −(A ) z ≥ −b s. t. −A y ≤ −c z ≥ 0 y ≥ 0 10 € € Taking duals LP dual recipe. Primal (P) maximize minimize Dual (D) y unrestricted 
 a x = b i i 
 a x≤ b
 y ≥ 0
 constraints variables i a x≥ b y ≤ 0 i i T a y ≥ c j x ≥ 0
 j T a y ≤ c j 
 x ≤ 0
 variables constraints j T a y = c j unrestricted Pf. Rewrite LP in standard form and take dual. 11LINEAR PROGRAMMING II LP duality ‣ strong duality theorem ‣ bonus proof of LP duality ‣ applications ‣LP strong duality Theorem. Gale–Kuhn–Tucker 1951, Dantzig–von Neumann 1947
 m×n m n For A ∈ ℜ , b ∈ ℜ , c ∈ ℜ , if (P) and (D) are nonempty, then max = min. T T (P) maxc x (D) miny b T s. t. Ax ≤ b s. t. A y ≥ c x ≥ 0 y ≥ 0 € € Generalizes: Dilworth's theorem. ・ König–Egervary theorem. ・ Max-flow min-cut theorem. ・ von Neumann's minimax theorem. ・ … ・ Pf. ahead 13LP weak duality m×n m n Theorem. For A ∈ ℜ , b ∈ ℜ , c ∈ ℜ , if (P) and (D) are nonempty,
 then max ≤ min. T T (P) maxc x (D) miny b T s. t. Ax ≤ b s. t. A y ≥ c x ≥ 0 y ≥ 0 € € m n Pf. Suppose x ∈ ℜ is feasible for (P) and y ∈ ℜ is feasible for (D). T T y ≥ 0, A x ≤ b ⇒ y A x ≤ y b ・ T T T x ≥ 0, A y ≥ c ⇒ y A x ≥ c x ・ T T T Combine: c x ≤ y A x ≤ y b. • ・ 14Projection lemma Weierstrass' theorem. Let X be a compact set, and let f(x) be a continuous function on X. Then min f(x) : x ∈ X exists. 
 m Projection lemma. Let X ⊂ ℜ be a nonempty closed convex set, and let y ∉ X. Then there exists x ∈ X with minimum distance from y.
 T Moreover, for all x ∈ X we have (y – x) (x – x) ≤ 0. obtuse angle y – x 2 x y x X 15Projection lemma Weierstrass' theorem. Let X be a compact set, and let f(x) be a continuous function on X. Then min f(x) : x ∈ X exists. 
 m Projection lemma. Let X ⊂ ℜ be a nonempty closed convex set, and
 let y ∉ X. Then there exists x ∈ X with minimum distance from y.
 T Moreover, for all x ∈ X we have (y – x) (x – x) ≤ 0. Pf. Define f(x) = y – x . ・ x Want to apply Weierstrass, but X not
 ・ y necessarily bounded. x X ≠ φ ⇒ there exists x' ∈ X. ・ x' Define X' = x ∈ X : y – x ≤ y – x' 
 ・ so that X' is closed, bounded, and
 X' min f(x) : x ∈ X = min f(x) : x ∈ X' . By Weierstrass, min exists. ・ X 16Projection lemma Weierstrass' theorem. Let X be a compact set, and let f(x) be a continuous function on X. Then min f(x) : x ∈ X exists. 
 m Projection lemma. Let X ⊂ ℜ be a nonempty closed convex set, and
 let y ∉ X. Then there exists x ∈ X with minimum distance from y.
 T Moreover, for all x ∈ X we have (y – x) (x – x) ≤ 0. Pf. 2 2 x min distance ⇒ y – x ≤ y – x for all x ∈ X. ・ By convexity: if x ∈ X, then x + ε (x – x) ∈ X for all 0 ε 1. ・ 2 2 
 y – x ≤ y – x – ε(x – x) ・ 2 2 2 T = y – x + ε (x – x) – 2 ε (y – x) (x - x) T 2 Thus, (y – x) (x - x) ≤ ½ ε (x – x) . ・ + Letting ε → 0 , we obtain the desired result. • ・ 17Separating hyperplane theorem m Theorem. Let X ⊂ ℜ be a nonempty closed convex set, and let y ∉ X.
 m T m Then there exists a hyperplane H = x ∈ ℜ : a x = α where a ∈ ℜ ,
 α ∈ ℜ that separates y from X. T a x ≥ α for all x ∈ X
 T a y α Pf. Let x be closest point in X to y. ・ By projection lemma,
 ・ y T (y – x) (x – x) ≤ 0 for all x ∈ X T Choose a = x – y ≠ 0 and α = a x. x ・ T If x ∈ X, then a (x – x) ≥ 0;
 ・ T T thus ⇒ a x ≥ a x = α. x T T 2 Also, a y = a (x – a) = α – a α • ・ X m T H = x ∈ ℜ : a x = α 18Farkas' lemma m×n m Theorem. For A ∈ ℜ , b ∈ ℜ exactly one of the following
 two systems holds: n m (I) ∃x∈ℜ (II) ∃y∈ℜ T s. t. Ax = b s. t. A y ≥ 0 T x ≥ 0 y b 0 Pf. not both Suppose x satisfies (I) and y satisfies (II).
 € € T T Then 0 y b = y Ax ≥ 0, a contradiction. Pf. at least one Suppose (I) infeasible. We will show (II) feasible. Consider S = A x : x ≥ 0 so that S closed, convex, b ∉ S. ・ m Let y ∈ ℜ , α∈ ℜ be a hyperplane that separates b from S:
 ・ T T y b α, y s ≥ α for all s ∈ S. T 0 ∈ S ⇒ α ≤ 0 ⇒ y b 0 ・ T T y Ax ≥ α for all x ≥ 0 ⇒ y A ≥ 0 since x can be arbitrarily large. • ・ 19Another theorem of the alternative m×n m Corollary. For A ∈ ℜ , b ∈ ℜ exactly one of the following two systems holds: m (II) ∃y∈ℜ n (I) ∃x∈ℜ T s. t. A y ≥ 0 s. t. Ax ≤ b T y b 0 x ≥ 0 y ≥ 0 € € Pf. Apply Farkas' lemma to: m n m (II' ) ∃y∈ℜ (I' ) ∃x∈ℜ ,s∈ℜ T s. t. A y ≥ 0 s. t. Ax + Is = b Iy ≥ 0 x, s ≥ 0 T y b 0 € € 20