Linear programming

Linear Programming

What is a linear programming?

Linear programming is the process of taking various linear inequalities relating to some situation, and finding the "best" value obtainable under those conditions. A typical example would be taking the limitations of materials and labor, and then determining the "best" production levels for maximal profits under those conditions.

 • Optimization problem consisting in

 • maximizing (or minimizing) a linear objective function 

 • of n decision variables • subject to a set of constraints expressed by linear equations or inequalities.  • Originally, military context: "programme"="resource planning". Now "programme"="problem" 

Examples:

The three inequalities in the curly braces are the constraints. The area of the plane that they mark off will be the feasibility region. The formula "z = 3x + 4y" is the optimization equation. I need to find the(x, y) corner points of the feasibility region that return the largest and smallest values of z.
My first step is to solve each inequality for the more-easily graphed equivalent forms:

                    click this

It's easy to graph the system: 

So the corner points are (2, 6), (6, 4), and (–1, –3).
Somebody really smart proved that, for linear systems like this, the maximum and minimum values of the optimization equation will always be on the corners of the feasibility region. So, to find the solution to this exercise, I only need to plug these three points into "z = 3x + 4y".

(2, 6):      z = 3(2)   + 4(6)   =   6 + 24 =   30 
(6, 4):      z = 3(6)   + 4(4)   = 18 + 16 =   34 
(–1, –3):  z = 3(–1) + 4(–3) = –3 – 12 = –15


Then the maximum of z = 34 occurs at (6, 4),
and the minimum of z = –15 occurs at (–1, –3).

https://www.youtube.com/watch?v=-32jcGMpD2Q

References:

http://www-sop.inria.fr/members/Frederic.Giroire/teaching/ubinet/pdfs/slides-linear-programming-introduction.pdf

http://www.purplemath.com/modules/linprog.htm