Linear Programming

Intro

This topic is more practical and less theoretical in nature. We will follow of the tone of this topic and approach it in a way that is geared toward problem solving instead of rigorous theory building. We won't dive too deep into the underlying algorithm (aka simplex). It does some matrix magic revisit after math401.

Note: While a polynomial algorithm for LP does exist, simplex is still faster in practice (with worse case being exponential).

Linear Programming (LP) is a method to solve the problem of maximizing or minimizing a linear objective function subject to some linear (inequality) constraints. Naturally, it heavily utilizes linear algebra such as matrices and vectors.

Application

LP is widely used in business ,economics, and engineering to solve optimization problems. Lagrange multipliers do not scale very well. LP models are also very popular in the industry such as food (nutrition), transportation, energy, telecommunications, and manufacturing (Amazon warehouse supply).

Example

Maximize Chocolate Profit

Reference

• 6.046 Lecture 15 Notes

• UBC ECON594 Ch10 Linear Programming

• Lagrange Multiplier vs Simplex