理论计算机科学（PPT专题讲稿）Topics in Theoretical Computer Science（Linear Programming）

CMSC5706 Topics in Theoretical Computer Science Week 2: Linear Programming Instructor: Shengyu Zhang 1

Instructor: Shengyu Zhang 1

LP Motivating examples a Introduction to algorithms Simplex algorithm o On a particular example a General algorithm Duality An application to game theory

LP ◼ Motivating examples ◼ Introduction to algorithms ◼ Simplex algorithm ❑ On a particular example ❑ General algorithm ◼ Duality ◼ An application to game theory 2

Example 1: profit maximization A company has two types of products: P, Q Profit: P---$1 each; Q---S6 each Constraints a Daily productivity(including both P and Q)is 400 a daily demand for P is 200 a daily demand for Q is 300 Question How many P and o should we produce to maximize the profit? o x, units of P. x, units of q

Example 1: profit maximization ◼ A company has two types of products: P, Q. ◼ Profit: P --- $1 each; Q --- $6 each. ◼ Constraints: ❑ Daily productivity (including both P and Q) is 400 ❑ Daily demand for P is 200 ❑ Daily demand for Q is 300 ◼ Question: How many P and Q should we produce to maximize the profit? ❑ 𝑥1 units of P, 𝑥2 units of Q 3

How to solve? x, units of p Variables x, units of Q o x and x Constraints Constraints a daily productivity(including a X1 +x2 $400 both p and Q )is 400 口x1≤200 Daily demand for p is 200 口x,≤300 a daily demand for Q is 300 1x2≥0 Question how much P Objective and Q to produce to maxxi+ 6x2 maximize the profit?

How to solve? ◼ 𝑥1 units of P 𝑥2 units of Q ◼ Constraints: ❑ Daily productivity (including both P and Q) is 400 ❑ Daily demand for P is 200 ❑ Daily demand for Q is 300 ◼ Question: how much P and Q to produce to maximize the profit? ◼ Variables: ❑ 𝑥1 and 𝑥2. ◼ Constraints: ❑ 𝑥1 + 𝑥2 ≤ 400 ❑ 𝑥1 ≤ 200 ❑ 𝑥2 ≤ 300 ❑ 𝑥1, 𝑥2 ≥ 0 ◼ Objective: max 𝑥1 + 6𝑥2 4

Illustrative figures Optimum point c=1500 .C=600

Illustrative figures 5

Example 2 a We are managing a network with bandwidth as shown by numbers on eages a Bandwidth: max units of flows 3 connections: AB BC. CA a We get $3, $2, $4 for providing them respectively o two routes for each connection short and long Question: How to route the connections to maximize our revenue?

Example 2 ◼ We are managing a network with bandwidth as shown by numbers on edges. ❑ Bandwidth: max units of flows ◼ 3 connections: AB, BC, CA ❑ We get $3, $2, $4 for providing them respectively. ❑ Two routes for each connection: short and long. ◼ Question: How to route the connections to maximize our revenue? 6

Example 2 xar: amount of flow of the short route xAp: amount of flow of the long route ariables 0 AB, XAB XBC, xBC, XAC, xAC Constraints 口xAB+xAB+xAC+xAC≤12(edge(A,a) 口xAB+xAB+xBC+xBC≤10(edge(B,b) 口xBC+xBC+xAC+xAC≤8(edge(C,c) 口xAB+xBC+xAc≤6 (edge(a, b)) axAc+xAB+xBC≤13 (edge(b, c)) 口xAB+xBC+xAC≤11 (edge(a, c)) 口xAB,xAB,xBC,xBC,xAC,xAC≥0 Objective: max 3 (AB+XAB)+ 2(xBC +xBC)+4(xAC Xac)

Example 2 ◼ Variables: ❑ 𝑥𝐴𝐵, 𝑥𝐴𝐵 ′ ,𝑥𝐵𝐶,𝑥𝐵𝐶 ′ ,𝑥𝐴𝐶,𝑥𝐴𝐶 ′ . ◼ Constraints: ❑ 𝑥𝐴𝐵 + 𝑥𝐴𝐵 ′ + 𝑥𝐴𝐶 + 𝑥𝐴𝐶 ′ ≤ 12 (edge (𝐴, 𝑎)) ❑ 𝑥𝐴𝐵 + 𝑥𝐴𝐵 ′ + 𝑥𝐵𝐶 + 𝑥𝐵𝐶 ′ ≤ 10 (edge (𝐵, 𝑏)) ❑ 𝑥𝐵𝐶 + 𝑥𝐵𝐶 ′ + 𝑥𝐴𝐶 + 𝑥𝐴𝐶 ′ ≤ 8 (edge (𝐶, 𝑐)) ❑ 𝑥𝐴𝐵 + 𝑥𝐵𝐶 ′ + 𝑥𝐴𝐶 ′ ≤ 6 (edge (𝑎, 𝑏)) ❑ 𝑥𝐴𝐶 ′ + 𝑥𝐴𝐵 ′ + 𝑥𝐵𝐶 ≤ 13 (edge (𝑏, 𝑐)) ❑ 𝑥𝐴𝐵 + 𝑥𝐵𝐶 ′ + 𝑥𝐴𝐶 ′ ≤ 11 (edge (𝑎, 𝑐)) ❑ 𝑥𝐴𝐵, 𝑥𝐴𝐵 ′ ,𝑥𝐵𝐶,𝑥𝐵𝐶 ′ ,𝑥𝐴𝐶,𝑥𝐴𝐶 ′ ≥ 0 ◼ Objective: max 3(𝑥𝐴𝐵 + 𝑥𝐴𝐵 ′ ) + 2(𝑥𝐵𝐶 + 𝑥𝐵𝐶 ′ ) + 4(𝑥𝐴𝐶 + 𝑥𝐴𝐶 ′ ) 𝑥𝐴𝐵: amount of flow of the short route 𝑥𝐴𝐵 ′ : amount of flow of the long route 7

LP in general Max/min a linear function of variables a Called the objective function All constraints are linear(in)equalities Equational form Superscript transpose of vectors max cr maXC1x1+…+Cnxn s t. Ax= b st.a1x1+…+amxn=b ≥0,Vi=1,… a x: variables Inequality: entry-wise a(A, b): coefficients in constraints

LP in general ◼ Max/min a linear function of variables ❑ Called the objective function ◼ All constraints are linear (in)equalities ◼ Equational form: max 𝒄 𝑇𝒙 max 𝑐1𝑥1 + ⋯ + 𝑐𝑛𝑥𝑛 s.t. 𝐴𝒙 = 𝒃 s.t. 𝑎𝑖1𝑥1 + ⋯ + 𝑎𝑖𝑛𝑥𝑛 = 𝑏𝑖 , ∀𝑖 = 1, … , 𝑚 𝒙 ≥ 𝟎 𝑥𝑖 ≥ 0, ∀𝑖 = 1, … ,𝑛 ❑ 𝒙: variables. ❑ (𝐴, 𝒃): coefficients in constraints Superscript T: transpose of vectors. Inequality: entry-wise 8

Transformations between forms Min vs, max o mince台max-Cx Inequality directions 口ax≥be-axs-b Equalities to inequalities: (ai: row i in matrix A) o ax=b eax> b. and ax s b

Transformations between forms ◼ Min vs. max: ❑ min 𝒄 𝑇𝒙 ⇔ max−𝒄 𝑇𝒙 ◼ Inequality directions: ❑ 𝒂𝒊 𝑇𝒙 ≥ 𝑏𝑖 ⇔ −𝒂𝒊 𝑇𝒙 ≤ −𝑏𝑖 ◼ Equalities to inequalities: (𝒂𝒊 : row 𝑖 in matrix 𝐴) ❑ 𝒂𝒊 𝑇𝒙 = 𝑏𝑖 ⇔ 𝒂𝒊 𝑇𝒙 ≥ 𝑏𝑖 , and 𝒂𝒊 𝑇𝒙 ≤ 𝑏𝑖 . 9

Transformations between forms a Inequalities to equalities aax≥b台ax=b2+S,S1≥0 The newly introduced variable Si is called slack variable “ Unrestricted”to“ nonnegative constraint” 口x; unrestricted兮x;=S-tS≥0,t≥0

Transformations between forms ◼ Inequalities to equalities: ❑ 𝒂𝒊 𝑇𝒙 ≥ 𝑏𝑖 ⇔ 𝒂𝒊 𝑇𝒙 = 𝑏𝑖 + 𝑠𝑖 , 𝑠𝑖 ≥ 0 ◼ The newly introduced variable 𝑠𝑖 is called slack variable ◼ “Unrestricted” to “nonnegative constraint”: ❑ 𝑥𝑖 unrestricted ⇔ 𝑥𝑖 = 𝑠– 𝑡, 𝑠 ≥ 0,𝑡 ≥ 0 10