Question? Leave a message!




LP duality: economic interpretation

LP duality: economic interpretation
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. ・ Maxflow mincut 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 € € 20LP strong duality m×n m n Theorem. strong duality 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 Pf. max ≤ min Weak LP duality. € € Pf. min ≤ max Suppose max α. We show min α. m n (II) ∃y∈ℜ , z∈ℜ (I) ∃x∈ℜ T s. t. A y− c z ≥ 0 s. t. Ax ≤ b T T y b−α z 0 −c x ≤ −α y, z ≥ 0 x ≥ 0 By definition of α, (I) infeasible ⇒ (II) feasible by Farkas' Corollary. ・ € € 21LP strong duality m (II) ∃y∈ℜ , z∈ℜ T s. t. A y−cz ≥ 0 T y b−α z 0 y,z ≥ 0 Let y, z be a solution to (II). € Case 1. z = 0 m T T Then, y ∈ ℜ : A y ≥ 0, y b 0, y ≥ 0 is feasible. ・ n Farkas Corollary ⇒ x ∈ ℜ : Ax ≤ b, x ≥ 0 is infeasible. ・ Contradiction since by assumption (P) is nonempty. ・ Case 2. z 0 Scale y, z so that y satisfies (II) and z = 1. ・ T Resulting y feasible to (D) and y b α. • ・ 22LINEAR PROGRAMMING II LP duality ‣ strong duality theorem ‣ bonus proof of LP duality ‣ applications ‣Strong duality theorem m×n m n Theorem. For A ∈ ℜ , b ∈ ℜ , c ∈ ℜ , if (P) and (D) are nonempty,
 then max = min. T (P) maxc x T (D) miny b s. t. Ax = b T s. t. A y ≥ c x ≥ 0 € € 24Review: simplex tableaux T 1 subtract c A times constraints B B T T −1 T −1 T T (c − c A A )x = Z − c A b c x + c x = Z N B B N N B B B B N N −1 −1 Ix + A A x = A b A x + A x = b B B N N B B B N N x , x ≥ 0 x , x ≥ 0 B N B N initial tableaux tableaux corresponding to basis B 1 multiply by A B € € 1 Primal solution. x = A b ≥ 0, x = 0 B B N T T 1 Optimal basis. c – c A A ≤ 0 N B B N 25Simplex tableaux: dual solution T 1 subtract c A times constraints B B T T −1 T −1 T T (c − c A A )x = Z − c A b c x + c x = Z N B B N N B B B B N N −1 −1 Ix + A A x = A b A x + A x = b B B N N B B B N N x , x ≥ 0 x , x ≥ 0 B N B N initial tableaux tableaux corresponding to basis B 1 multiply by A B € € 1 Primal solution. x = A b ≥ 0, x = 0 B B N T T 1 Optimal basis. c – c A A ≤ 0 N B B N T T 1 Dual solution. y = c A B B T T T y A = y A y A B N −1 T T y b = c A b 1 1 T T B B = c A A c A A B B B B B N T T = c x + c x B B B B 1 T T = c c A A T B B B N = c x T T ≥ c c B N min ≤ max T dual feasible = c 26 € € Simplex algorithm: LP duality T 1 subtract c A times constraints B B T T −1 T −1 T T (c − c A A )x = Z − c A b c x + c x = Z N B B N N B B B B N N −1 −1 Ix + A A x = A b A x + A x = b B B N N B B B N N x , x ≥ 0 x , x ≥ 0 B N B N initial tableaux tableaux corresponding to basis B 1 multiply by A B € € 1 Primal solution. x = A b ≥ 0, x = 0 B B N T T 1 Optimal basis. c – c A A ≤ 0 N B B N T T 1 Dual solution. y = c A B B Simplex algorithm yields constructive proof of LP duality. 27LINEAR PROGRAMMING II LP duality ‣ strong duality theorem ‣ alternate proof of LP duality ‣ applications ‣LP duality: economic interpretation Brewer: find optimal mix of beer and ale to maximize profits. (P) max 13A + 23B A = 12
 s. t. 5A + 15B ≤ 480 B = 28 
 4A + 4B ≤ 160 OPT = 800 35A + 20B ≤ 1190 A , B ≥ 0 € Entrepreneur: buy individual resources from brewer at min cost. (D) min 480C + 160H + 1190M C = 1
 H = 2 
 s. t. 5C + 4H + 35M ≥ 13 M = 0
 15C + 4H + 20M ≥ 23 OPT = 800 C , H , M ≥ 0 € LP duality. Market clears. 29LP duality: sensitivity analysis Q. How much should brewer be willing to pay (marginal price) for additional supplies of scarce resources A. corn 1, hops 2, malt 0. Q. Suppose a new product "light beer" is proposed. It requires 2 corn, 5 hops, 24 malt. How much profit must be obtained from light beer to justify diverting resources from production of beer and ale A. At least 2 (1) + 5 (2) + 24 (0) = 12 / barrel. 30LP is in NP ∩ coNP m×n m n n 
 LP. For A ∈ ℜ , b ∈ ℜ , c ∈ ℜ , α ∈ ℜ, does there exist x ∈ ℜ T such that: Ax = b, x ≥ 0, c x ≥ α Theorem. LP is in NP ∩ coNP. Pf. Already showed LP is in NP. ・ If LP is infeasible, then apply Farkas' Lemma to get certificate of ・ infeasibility: m (II) ∃y∈ℜ , z∈ℜ T s. t. A y ≥ 0 T y b − αz 0 or equivalently,
 z ≥ 0 T y b – α z = –1 € 31
Website URL
Comment