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