What is Linear Programming?

 Linear Programming is the field of optimization that

concerns the
 (1) maximization or minimization of a linear function
 (2) subject to constraints that are also linear
Example: The Diet Problem
 Due to a limited budget you would like to find the
most economical mix of food items subject to
providing sufficient daily nutrition.
 The available food items are peanut butter, bananas,
and chocolate.
Food Items and Nutritional Values
Food item Fat (g/serving) Carbohydrate Protein
(g/serving) (g/serving)

Peanut butter 130 51.6 64.7

Banana 1 51 2

Chocolate 12 22 2
Diet Problem: Cost of Food Items
Food Item $/serving

Peanut Butter .20

Banana .10

Chocolate .15
Nutritional Requirements
 Suppose it is decided by a dietician that you need at
least 35 grams of fat, at least 130 grams of
carbohydrate, and at least 76 grams of protein daily.
 What is the least cost combination of the food items so
that the nutritional requirements are satisfied?
 This problem can be formulated as a linear program.
Problem structure
 The problem has the following structure
 (1) there is an objective i.e. minimize cost of food items
used
 (2) there are constraints i.e. food items must satisfy
nutritional requirements
 Both of these constructs can be modelled
mathematically through linear expressions in which
case the problem is a linear program.
Problem Structure

Minimize cost of food items used

Subject to food items must provide enough fat
food items must provide enough carbohydrates
food items must provide enough protein
 Decision Variables
Before the mathematical expressions can be created
decision variables must be defined.

The decision variables for the diet problem represent

the amount of each food item to be determined and
are defined as

xpb = servings of peanut butter

xb = servings of bananas
xc = servings of chocolate
Objective of the Diet Problem
The cost of a combination of the three food items
is given by
.20xpb + .10xb + .15xc

which is a linear expression since the variables are

raised to the first power. This cost function is the
objective function.

Then, the objective of the diet problem is to minimize

this linear cost (objective function).
Constraints of the Diet Problem
The first constraint ensures that there is enough fat
from the food items
130xpb + 1xb + 12xc ≥ 35
The second constraint ensures that there is enough
carbohydrates
51.6xpb + 51xb + 22xc ≥ 130

The third constraint ensures that there is enough

protein
64.7xpb + 2xb + 2xc ≥ 76
All constraints are linear expressions.
Non-negativity constraints
One last set of (linear) constraints involves imposing
non-negativity constraints on the decision variables
to ensure that the amounts determined make sense.

xpb , xb , xc ≥ 0
Diet Problem Linear Program
Putting together all of the parts the linear program
can now be written as follows:

minimize .20xpb + .10xb + .15xc

subject to 130xpb + 1xb + 12xc ≥ 35
51.6xpb + 51xb + 22xc ≥ 130
64.7xpb + 2xb + 2xc ≥ 76
xpb , xb , xc ≥ 0
General Diet Problem
 The diet problem can be generalized to consider n
food items with m nutritional requirements

xi = amount of food item i

ci = cost of one serving of food item i
aij = amount of nutrient i in one
serving
of food item j
bj = amount of nutrient j required
General Diet Problem
minimize c1 x1 + c2 x2 + + cn xn
subject to a11 x1 + a12 x2 + + a1n xn  b1
a21 x1 + a22 x2 + + a2 n xn  b2

am1 x1 + am 2 x2 + + amn xn  bm
x1 , x2 , , xn  0
Embedded Assumptions
 Proportionality
 Divisibility
 Additivity
 Certainty
Proportionality
 Proportionality means that the contribution towards
the objective function and constraints of decisions are
directly proportional to its values e.g. there are no
economies of scale such as quantity based discounts.

 For example, in the diet problem every unit (serving)

of peanut butter xpb will contribute .20 towards the
overall cost and 130 grams of fat towards the fat
nutrient requirement.
Divisibility
 Divisibility means that the decision variables can take
on any real number.
 For example, the amount of peanut butter in the diet
problem can be less than one serving like 35% of a
serving, i.e. xpb = .35, or more than one serving.
Additivity
 Additivity means that the contribution of a decision
variable towards the objective or constraints does not
depend on other decision variables.
 In other words, the total contribution is the sum of
individual contributions of each decision variable.
 For example, the contribution of every serving of
peanut butter in the diet problem towards the overall
fat requirement of 35 grams is 130 grams independent
of the amount of servings of the other food items.
Certainty
 Certainty means that the data used as coefficients for a
linear programming model such as the objective
coefficients c and constraint coefficients A and b are
known with certainty.
Steps for Linear Programming
Model Formulation
 (1) Identify decision variables
 (2) Form objective function
 (3) Form constraints
 (4) Ensure all mathematical expressions are linear
 (5) Ensure all embedded assumptions are met
Financial Optimization: Bond
Portfolio Construction
 Suppose that a bank has the following liability
schedule
Year 1 Year 2 Year 3

$12,000 $18,000 $20,000

 i.e. the bank needs to pay $12,000 at the end of the

first year, $18,000 at the end of the second year, and
$20,000 at the end of the third year.
Bond Portfolio Construction
 Bonds are securities that are sold by agencies such as
corporations or governments that entitle the buyer to
periodic interest (coupon) payments and the payment
of the principle (face value) at some time in the future
(maturity).
 The bank wishes to use three bonds to form a portfolio
(a collection of bonds) today to hold until all bonds
have matured and that will generate the required cash
to meet the liabilities.
Bond Portfolio Optimization
Bond 1 2 3
Price 102 99 98
Coupon 5 3.5 3.5
Maturity year 1 2 3

All bonds have face value of a $100 and the coupons are annual
(with one coupon per year).

For example, one unit of Bond 2 costs $99 now and the holder will
receive $3.5 after 1 year and then $3.5 plus the face value of $100 at
the end of the second year which is the maturity of Bond 2.
Decision Variables
Let the xi = amount of bond i purchased.

 x1 
Then, x =  x2  is the bond portfolio.
 
 x3 
Bond Portfolio Optimization
 (1) The objective is to minimize the cost of a
portfolio

 (2) Each constraint should ensure that that cash

flow generated by the bonds for a given time
period is sufficient to match the liability for
that period.
Bond Portfolio Linear Program
minimize 102 x1 + 99 x2 + 98 x3
subject to 105 x1 + 3.5 x2 + 3.5 x3  12000
103.5 x2 + 3.5 x3  18000
103.5 x3  20000
x1 , x2 , x3  0
General Linear Programs
 The diet problem, production planning, and bond
portfolio problems had constraints that were uniform
in orientation e.g. The diet problem had all greater
than or equal to constraints.
 Furthermore, the three examples also required all of
the decision variables to be non-negative.
 In general, a linear program can be specified in many
different ways the only major requirements being that
the objective function and constraints have to be
linear.
General Linear Programs
minimize or maximize cT x
subject to aiT x  bi i  L
aiT x  bi i  G
aiT x = bi i  E
xj  0 j  NN
xj  0 j  NP
Example
maximize 5 x1 + x2 − 3 x3
subject to x1 + x2  6
x2 + x3  7
x1 − x3 = 2
x1  0
x2  0
x3 unrestricted
Application: Portfolio Optimization
 Consider an investment in n stocks where each stock i
has a random rate of return ri with an expected return
of ui. Moreover, the covariance between the returns of
stock i and stock j is  ij .
 Let xi = the proportion of wealth invested in stock i, a
portfolio is the represented by the vector
x = (x1, x2, …, xn)T.
 Markowitz (1952) construct a Mean-Variance
Optimization (MVO) as follows:
Application: Portfolio Optimization
   xx
n n
minimize i =1 j =1 ij i j

subject to  u x = R
n
i =1 i i

 x =1
n
i =1 i

xi  0, i = 1, ,n
 The objective is to minimize the risk of portfolio subject to
meeting an expected goal R and ensuring the budget is
exhausted.
 However the model is non-linear because of quadratic term
in objective function and there are n(n-1)/2 covariance
terms to estimate.
Application: Portfolio Optimization
 Konno and Yamazaki (1991) use the absolute deviation
of the portfolio return instead of standard deviation,
and construct Mean-Absolute Deviation (MAD) model.
1 T
 i =1 ( ri − ui ) xi   ( rit − ui ) xi
n n
minimize E =
T t =1 i =1

n
subject to ux =R
i =1 i i


n
i =1 i
x =1
xi  0, i = 1, ,n

 where rit = the realized return for asset i at sub-period t.

 Set  i =1 ( it i ) i t t  i =1 ( rit − ui ) xi = st − yt , st  0, yt  0 , for all t
n n
r − u x = s + y ,
= 1, …, T. The MAD becomes following LP:
Application: Portfolio Optimization
 (s + y )
T
minimize t =1 t t

subject to  ( r − u ) x
n
i =1 it i i = st − yt , t = 1, ,T

 ux =R
n
i =1 i i

 x =1
n
i =1 i

xi  0, i = 1, ,n
st  0, yt  0, t = 1, ,T
Solving LP by MATLAB
 The function linprog in MATLAB can be used to solve
the following standard LP:
minimize f T x
subject to Ax  b inequality constraint
Aeqx = beq equality constraint
lb  x  ub lower and upper bound

 The optimal solution and objective value are obtained

by the following statement:
[x, fval] = linprog(f, A, b, Aeq, beq, lb, ub)
Example 1 f =  −3, −5, −3 ' ;
minimize − 3 x1 − 5 x2 − 3 x3 1, −1,1 15 
subject to x1 − x2 + x3  15 A=  ; b =   ;
 2,3, 6  30 
2 x1 + 3 x2 + 6 x3  30 Matlab Aeq = [2,1, 0]; beq = 30 ;
2 x1 + x2 = 30 code
lb =  0, 0, 0 ' ; ub = 15,10,5 ' ;
0  x1  15
[x, fval ] =
0  x2  10
linprog(f , A, b, Aeq, beq, lb, ub);
0  x3  5

x=
15.0000
0.0000
0.0000
fval =
- 45.0000
Example 2
f =  −3, −5, −3 ' ;
minimize − 3 x1 − 5 x2 − 3 x3 1, −1,1 15 
A=  ; b = 30  ;
subject to x1 − x2 + x3  15 Matlab  2,3, 6   
2 x1 + 3 x2 + 6 x3  30 code Aeq =   ; beq =   ;
0  x1 lb =  0, 0, 0 ' ;
0  x2
[x, fval ] =
0  x3
linprog(f , A, b, Aeq, beq, lb);

x=
0.0000
10.0000
0.0000
fval =
- 50.0000