Quant440

Welcome to Quantitative Business Analysis WIKI - 440 CBU


Linear Programing


is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming mathematical optimization. More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

Sample


Suppose that a farmer has a piece of farm land, say L km2, to be planted with either wheat or barley or some combination of the two. The farmer has a limited amount of fertilizer, F kilograms, and insecticide, P kilograms. Every square kilometer of wheat requires F1 kilograms of fertilizer, and P1 kilograms of insecticide, while every square kilometer of barley requires F2 kilograms of fertilizer, and P2 kilograms of insecticide. Let S1 be the selling price of wheat per square kilometer, and S2 be the selling price of barley. If we denote the area of land planted with wheat and barley by x1 and x2 respectively, then profit can be maximized by choosing optimal values for x1 and x2. This problem can be expressed with the following linear programming problem in the standard form:
Maximize:
S_1cdot x_1+S_2cdot x_2
S_1cdot x_1+S_2cdot x_2

(maximize the revenue—revenue is the "objective function")
Subject to:
x_1 + x_2leq L
x_1 + x_2leq L

(limit on total area)

F_1cdot x_1+F_2cdot x_2leq F
F_1cdot x_1+F_2cdot x_2leq F

(limit on fertilizer)

P_1cdot x_1 + P_2cdot x_2leq P
P_1cdot x_1 + P_2cdot x_2leq P

(limit on insecticide)

x_1geq 0, x_2geq 0
x_1geq 0, x_2geq 0

(cannot plant a negative area).
Which in matrix form becomes:
maximize
begin{bmatrix} S_1 & S_2 end{bmatrix} begin{bmatrix} x_1  x_2 end{bmatrix}
begin{bmatrix} S_1 & S_2 end{bmatrix} begin{bmatrix} x_1 x_2 end{bmatrix}
subject to
begin{bmatrix} 1 & 1  F_1 & F_2  P_1 & P_2 end{bmatrix} begin{bmatrix} x_1  x_2 end{bmatrix} le begin{bmatrix} L  F  P end{bmatrix}, , begin{bmatrix} x_1  x_2 end{bmatrix} ge begin{bmatrix} 0  0 end{bmatrix}.
begin{bmatrix} 1 & 1 F_1 & F_2 P_1 & P_2 end{bmatrix} begin{bmatrix} x_1 x_2 end{bmatrix} le begin{bmatrix} L F P end{bmatrix}, , begin{bmatrix} x_1 x_2 end{bmatrix} ge begin{bmatrix} 0 0 end{bmatrix}.


Source: Wikipedia