Linear Programming (LP) - Linear Optimization

LP - Example Problems

• Toy Problem

  given:

  • a toy company make 2 toys: x₁ and x₂
  • these toys are made of 2 materials: A and B
  • to make toy x₁, it needs 5 units of A and 2 units of B
  • to make toy x₂, it needs 3 units of A and 3 units of B
  • there is a maximum of 30 units of A
  • there is a maximum of 20 units of B
  • each toy x₁ can be sold for $10
  • each toy x₂ can be sold for $7

  what is the optimum product mix that maximizes the profit?

• Network Flow Problems

LP - Ways to Structure an LP Problem

refer to: Ways Structuring Problem

LP - Ways to Solve an LP Problem

refer to: Algorithms Solving Problem

LP - Theorems

Theorem #1

If an LP has an optimal solution, then the optimal solution would be at the corner point of the feasible region

Theorem #2

every LP either:

• has a unique optimal solution
• has multiple/infinite optimal solutions
• infeasible - no feasible solution
• unbounded - no feasible solution that is maximal

LP - Subpages

• LP - Algorithms Solving Problem
• LP - Duality
• LP - Network Flow Problems
• LP - Ways Structuring Problem