Linear Programming
- The main idea of LP is to optimize some linear function subject to a list of linear constrains
- Optimize = minimize OR maximize
- This is applicable only for linear functions
Guidelines for Model Formulation
- Understand the problem
- Describe the objective
- Describe each constraint
- Define the decision variables
- Write the objective in terms of the decision variables
- Write the constraints in terms of the decision variables
Carpenter Problem
- Tables take 10 units of lumber, 5 hours of labour, make $180
- Bookcases take 20 units of lumber, 4 hours of labour, make $200
- Available Resource:
- 200 units of lumber
- 80 hours of labour
Formulating the Linear Function and Inequalities
- Goal: Make as much money as possible → Optimize:
- Constraints (Inequalities) denoting that Tables → and Bookcase → :
- Labour hours:
- Lumber units:
- Non-negative:
- Graphing:
- By graphing the inequalities, we will have the Feasible Region, in which the possible solutions are located
- To find the optimum solution, we have to find the spot where we are using ALL of the wood and ALL of the labour and that will give us the most amount of money
- Extreme values occur at vertices of a convex, bounded, feasible region
Simplex Method
- It is an iterative method used to find the optimum solution by creating a matrix using the equations and finding the pivot columns. Watch this video for details.
- Asymptotic Analysis:
- Worst case
- In practice, the average case is polynomial such that is integer
Politics Problem
- How to campaign to win an election?
- Estimate votes obtained per dollar spent adverting is support of a particular issue:
Policy (Issue) | Urban | Suburban | Rural | Variable |
Build roads | -2 | 5 | 3 | x1 |
Gun controls | 8 | 2 | -5 | x2 |
Farm subsidies | 0 | 0 | 10 | x3 |
Gasoline tax | 10 | 0 | 2 | x4 |
- Want majority in each demographic by spending the minimum amount of money:
Demog. | Urban | Suburban | Rural |
Population | 100,000 | 200,000 | 50,000 |
Majority | 50,000 | 100,000 | 25,000 |
Algebraic Setup
Let denote $ spent per issue. Minimize subject to these constraints:
Such that
- For integers the problem would be NP-Complete which is more complicated
- Number of variables
- Number of constraints
- Simplex algorithm solves any Linear Problem in of time
- It is easy to use and very efficient in practice
