Linear Programming Model and it’s Applications
> Contents of the Article:
- What is Linear Programming ?.
- Applications of Linear Programming.
- An Example.
- Geometric Representation.
- Refrences.
What is Linear Programming (LP) ? it is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.
where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients and A is a (known) matrix of coefficients. The expression to be maximized or minimized is called the objective function (cTx in this case).
Applications of Linear Programming arose as a mathematical model developed during World War II to plan expenditures and returns in order to reduce costs to the army and increase losses to the enemy. It was kept secret until 1947. Postwar, many industries found its use in their daily planning.
The founders of the subject are Leonid Kantorovich, a Russian mathematician who developed linear programming problems in 1939, George B. Dantzig, who published the simplex method in 1947, and John von Neumann, who developed the theory of the duality in the same year.
Application in AI programming and in particular in Planning like LPSAT wich is used in Resource Planing. It is essentially a propositional conjunctive normal form(CNF) that includes linear (in)equalities as propositions. When SAT solver returns the propositions that are satisfiable the linear programming solver is used to get the value of the arithmetic (in)equalities.
An Example taken from Introduction to Algorithms named “A political problem”.
Problem: you are a politician trying to win the election. You have three districts Urban, Sub-Urban, Rureal. Each contains 100, 200, 50, registered vote. To win the elections your primary issues in your program are “build-roads”, “gun-control”, “farm-subsidies” and “gasoline-tax”.
Your researchers gave you a table for the effects of paying 1$ on each issue, how many votes you will win and how many will you lose for each urban.
| Policy | urban | suburban | rural |
| build-roads | -2 | 5 | 3 |
| gun-control | 8 | 2 | -5 |
| farm-subsidies | 0 | 0 | 10 |
| gasoline-tax | 10 | 0 | -2 |
So inorder to win the election you decided that you need at least 50 votes, 100 votes, 25 votes respectively.
Solution Approach: let’s model each inequality
x1: amounts of dollars spent on “build-roads”
x2: amounts of dollars spent on “gun-control”
x3: amounts of dollars spent on “farm-subsidies”
x4: amounts of dollars spent on “gasoline-tax”
minimize x1 + x2 + x3 + x4
subject to
-2 * x1 + 8 * x2 + 0 * x3 + 10 * x4 >= 50 ( 1 )
5 * x1 + 2 * x2 + 0 * x3 + 0 * x4 >= 100 ( 2 )
3 * x1 + -5 * x2 +10 * x3 + -2 * x4 >= 25 ( 3 )
x1, x2, x3, x4 >= 0 ( 4 )
Geometric Representation is very important to understand linear programming more in depth, but inorder to be easy on geometric representation we will define another example with only two variables.
maximize x1 + x2
subject to
5 * x1 – 2 * x2 >= -2 ( 1 )
2 * x1 + x2 <= 10 ( 2 )
4 * x1 – x2 <= 8 ( 3 )
x1, x2 >= 0 ( 4 )
The Feasible area of solution is defined as the set of points that solve the 5 equations defined(shaded region).
References
Introduction to Algorithms(CLRS), 2nd edition (Chapter 29).
Wikipedia.
