EME 501: Introduction to Optimization &

Linear Programming
 Outline
• What is optimization?
• Example formulations
• Solution – the basics
• Types of constrained optimization problems
• Linear Programming
– Formulation
– Simplex
– Interior Point Methods
– Duality
• Preview: other optimization types and solution
methods
 Elements of Optimization
• Whenever you see or are setting up an optimization
problem, always ask yourself these questions:
• Who is the decision-maker?
• What is their objective? (Or do they have multiple
objectives?)
• What are their decision variables (the things within
the control of the decision-maker)
• What constraints does the decision-maker face?
Elements not within control of the decision maker are the parameters
 Constrained Optimization

Mathematical Formulation:
x can be a scalar or a vector Equality
Objective
Constraints
Function min f ( x) s.t.
x

Decision g ( x) = 0 Inequality
Variables h( x ) ≤ 0 Constraints
Objective functions are either minimizing functions or maximizing functions
Decision variables sometimes might not appear in the objective function
Constraints are rules and limits
 Example: Filing Cabinets
You need to buy some filing cabinets. You know that Cabinet X
costs $10 per unit, requires six square feet of floor space, and holds
eight cubic feet of files. Cabinet Y costs $20 per unit, requires eight
square feet of floor space, and holds twelve cubic feet of files. You
have been given $140 for this purchase, though you don't have to
spend that much. The office has room for no more than 72 square
feet of cabinets. How many of which model should you buy, in order
to maximize storage volume?
max 8X + 12 Y
Objective here would be to maximize storage
X, Y
Decision maker can control X and Y
constraints (space) 6X + 8Y <=72
This problem is an example of (budget) 10X + 20Y < 140
linear programming Non negativity
constraints X >= 0
Y >= 0
 Example: Filing Cabinets
You need to buy some filing cabinets. You know that Cabinet X
costs $10 per unit, requires six square feet of floor space, and holds
eight cubic feet of files. Cabinet Y costs $20 per unit, requires eight
square feet of floor space, and holds twelve cubic feet of files. You
have been given $140 for this purchase, though you don't have to
spend that much. The office has room for no more than 72 square
feet of cabinets. How many of which model should you buy, in order
to maximize storage volume?
max 8𝑥𝑥 + 12𝑦𝑦
𝑥𝑥,𝑦𝑦
Subject to:
10𝑥𝑥 + 20𝑦𝑦 ≤ 140
6𝑥𝑥 + 8𝑦𝑦 ≤ 72
𝑥𝑥, 𝑦𝑦 ≥ 0
 Example: Filing Cabinets
Max Z = 8x + 12y
subject to:
10x + 20y <= 140
7

6x + 8y <= 72
6

5
Budget Constraint:
x,y >=0 4
10x + 20y <= 140
3

2
y

-1

-2

-3
0 2 4 6 8 10 12 14 16 18 20

x
 Example: Filing Cabinets
Max Z = 8x + 12y
subject to: 10

10x + 20y <= 140 9

6x + 8y <= 72 8 Floor Space Constraint:

x,y >=0 7
6x + 8y <= 72
6

5
y

Budget Constraint:
3

2
10x + 20y <= 140
1

0
0 5 10 15 20 25

x
 Example: Filing Cabinets
Max Z = 8x + 12y
subject to: 10

10x + 20y <= 140 9

6x + 8y <= 72 8 Floor Space Constraint:

x,y >=0 7
6x + 8y <= 72
6

5
y

Budget Constraint:
3

Feasible Region 2
10x + 20y <= 140
1
All points in the grey region
are feasible, but we don't know 0
0 5 10 15 20 25

which one maximizes Z yet x

 Example: Filing Cabinets
Max Z = 8x + 12y
subject to: 10

10x + 20y <= 140 9

6x + 8y <= 72 8 Floor Space Constraint:

x,y >=0 7 6x + 8y <= 72
6

Z=72
y

Z=48 3

Budget Constraint:
10x + 20y <= 140
2

Z=24 1

0
0 5 10 15 20 25

x
 Example: Filing Cabinets
Max Z = 8x + 12y
subject to: 10

10x + 20y <= 140 9

6x + 8y <= 72 8 Floor Space Constraint:

x,y >=0 7 6x + 8y <= 72
6

5
Solution to be in a vertex
y

4 of a feasible region is very normal

solution in linear programming.
Budget Constraint:
3

10x + 20y <= 140

2

Solution: (8,3) 1

Value of Z (objective function) 0

0 5 10 15 20 25
At the optimal solution is 100 x
 Exercise: Toy Store
A store sells two types of toys, A and B. The store owner pays $8
and $14 for each one unit of toy A and B respectively. One unit of
toys A yields a profit of $2 while a unit of toys B yields a profit of
$3. The store owner estimates that no more than 2000 toys will be
sold every month and he does not plan to invest more than $20,000
in inventory of these toys. How many units of each type of toys
should be stocked in order to maximize his monthly total profit?
• Formulate the problem max A,B 2A + 3B
st
• Draw the problem graphically 8A + 14B <=20,000
A + B <= 2000
• What is the solution? A.B >=0

• Solve using MATLAB

• If you could increase budget to $20001 or inventory size to 2001,
which would be better for increasing profit?
 Example: Transportation Problem

i plants; j markets
Decision variables: x(i,j)
min 2.5𝑥𝑥 1,1 + 1.7𝑥𝑥 1,2 + 1.8𝑥𝑥 1,3 + 2.5𝑥𝑥 2,1 + 1.8𝑥𝑥 2,2 + 1.4𝑥𝑥(2,3)
 Example: Transportation Problem

Let xi,j be amount shipped from plant i to market j

min z = ∑ xi , j ci , j Objective Function
xi , j
i, j

Subject to: ∑x i, j ≥ Dj ∑x
i
i, j ≤ Si xi , j ≥ 0
j
Demand Supply Non-negativity
Constraint Constraint Constraint
 Example: Economic Dispatch

• You have generators i = 1,…,N

• Let xi be the amount of generation in MW from
generator i
• ci is the variable cost of generator i in $/MWh
• 𝑥𝑥̅𝑖𝑖 is the capacity (maximum output) of gen i
• Demand for one hour is D (in MW)
• What is the least cost dispatch?
min z = ∑ xi ci s.t. ∑ xi ≥ D 𝑥𝑥𝑖𝑖 ≤ 𝑥𝑥̅𝑖𝑖
xi
i i
xi ≥ 0
 Unconstrained Optimization

• Recall basic calculus

• First-order conditions
– First derivative = 0
• Second-order conditions
– 2nd derivative > 0 => Minimum
– 2nd derivative < 0 => Maximum
 Constrained Optimization: Example

• Wood and Wollenberg (1996) p. 58:

Minimize: f ( x1 , x2 ) = 0.25 x12 + x22
subject to: 5 − x1 − x2 = 0
 Solution of Example I

• Set up the Lagrangian:

ℒ = Objective function + λ * (constraint)

(add a penalty cost for violating constraint)

ℒ(x1,x2,λ) = 0.25 x12 + x22 + λ (5 − x1 − x2 )

 Solution of Example II

ℒ(x1,x2,λ) = 0.25 x12 + x22 + λ (5 − x1 − x2 )

• Derivative w.r.t. each variable, set to 0
∂L
= 0.5 x1 − λ = 0
∂x1
∂L
= 2 x2 − λ = 0
∂x2
∂L
= 5 − x1 − x2 = 0
∂λ
 Solution of Example II

ℒ(x1,x2,λ) = 0.25 x12 + x22 + λ (5 − x1 − x2 )

• Derivative w.r.t. each variable, set to 0
∂L
= 0.5 x1 − λ = 0 𝜆𝜆 = 0.5𝑥𝑥1
∂x1
∂L
= 2 x2 − λ = 0 𝜆𝜆 = 2𝑥𝑥2
∂x2
∂L
= 5 − x1 − x2 = 0 𝑥𝑥1 + 𝑥𝑥2 = 5
∂λ
 Solution of Example II

ℒ(x1,x2,λ) = 0.25 x12 + x22 + λ (5 − x1 − x2 )

• Derivative w.r.t. each variable, set to 0
∂L
= 0.5 x1 − λ = 0 𝜆𝜆 = 0.5𝑥𝑥1
∂x1
0.5𝑥𝑥1 = 2𝑥𝑥2
∂L 𝑥𝑥1 = 4𝑥𝑥2
= 2 x2 − λ = 0 𝜆𝜆 = 2𝑥𝑥2
∂x2
∂L
= 5 − x1 − x2 = 0 𝑥𝑥1 + 𝑥𝑥2 = 5
∂λ 4𝑥𝑥2 + 𝑥𝑥2 = 5
5𝑥𝑥2 = 5
 Solution of Example II

ℒ(x1,x2,λ) = 0.25 x12 + x22 + λ (5 − x1 − x2 )

• Derivative w.r.t. each variable, set to 0
𝜆𝜆 = 0.5𝑥𝑥1 0.5𝑥𝑥1 = 2𝑥𝑥2 𝑥𝑥1 = 4𝑥𝑥2
𝜆𝜆 = 2𝑥𝑥2

𝑥𝑥1 + 𝑥𝑥2 = 5 4𝑥𝑥2 + 𝑥𝑥2 = 5 5𝑥𝑥2 = 5

Solution:
𝑥𝑥2 = 1 𝑥𝑥1 = 4 𝜆𝜆 = 2
 Meaning of Lagrange Multipliers

ℒ(x1,x2,λ) = 0.25 x12 + x22 + λ (5 − x1 − x2 )

Solution: 𝑥𝑥2 = 1 𝑥𝑥1 = 4 𝜆𝜆 = 2
• What does “𝜆𝜆” mean?
• Also called: If λ = 0 →
Constraint is not binding
– Shadow Price
– Marginal Cost If λ ≠ 0 →
Constraint is binding
– Dual Variable
 λ tells you how much you could improve the
objective function if you could relax the constraint
by one unit
 LP in MATLAB
• Use function “linprog()” in Optimization Toolbox
• Put problem in matrix notation: linprog automatically assumes not
𝑇𝑇
min 𝑧𝑧 = 𝑐𝑐 𝑥𝑥 negativity
Subject to: 𝐴𝐴𝑥𝑥 ≥ 𝑏𝑏 By default MATLAB only does minimizing
If we can to maximize we just multiply the
𝑥𝑥 ≥ 0 function with negative one
• EXCEPT: Matlab’s linprog() assumes
min 𝑐𝑐 𝑇𝑇 𝑥𝑥
It also assumes that all the constraints are
Subject to: 𝐴𝐴𝐴𝐴 ≤ 𝑏𝑏 less than or equals to
𝑥𝑥 ≥ 0 To flip the inequality sign you can also
multiply the inequality with negative one on
• Just fill in vectors c and b and matrix Aboth sides
• Linprog() returns optimal x and minimized value z
• If maximizing, multiple values in c by -1
• If constraint is ≥, multiply that row of A and b by -1
 Example: Filing Cabinet
Matlab Code:
c = [8 12]'; Max Z = 8x + 12y
b = [140 72]'; subject to:
A = [ 10 20; 10x + 20y <= 140
6 8];
6x + 8y <= 72
[x,fval,exitflag,output,lambda] = linprog(-c,A,b)
x,y >=0
 Example: Filing Cabinet
Matlab Code:
c = [8 12]'; Max Z = 8x + 12y
b = [140 72]'; subject to:
A = [ 10 20; 10x + 20y <= 140
6 8];
6x + 8y <= 72
[x,fval,exitflag,output,lambda] = linprog(-c,A,b)
[Link] x,y >=0
>> filingcabinet2
Optimal solution found.
x =
8.0000 Shadow price: improvement in the objective
3.0000 function that you get by relaxing a constraint by
fval = one unit. It is denoted by the greek letter lambda
-100.0000
ans = If 140 -> 141: Max storage = 100.2
0.2000
1.0000
If 72 -> 73: Max storage = 101
 Example: Filing Cabinet II
Matlab Code:
c = [8 12]';
b = [140 73]';
A = [ 10 20;
6 8];
[x,fval,exitflag,output,lambda] = linprog(-c,A,b)
[Link] New Solution:
Old Solution:
>> filingcabinet2 >> filingcabinet2
Optimal solution found. Optimal solution found.
x = x2 =
8.0000 8.5000
3.0000 2.7500
fval = fval2 =
-100.0000 -101.0000
ans = Maximum Storage
0.2000 Volume increased
1.0000 By 101-100 = 1
 Types of Optimization
• Linear Programming (LP)
– Objective function, constraints are linear
• Nonlinear Programming (NLP)
– Objective function, constraints are nonlinear
– Special case: quadratic programming (QP)
• Integer Programming
– When decision variables must be integers
– Mixed integer linear programming (MILP)
• Stochastic Programming
– Objective function, constraints are uncertain
• Dynamic Programming (DP)
– Uncertain and decisions can be revised
 Idea of Linear Programming (LP)

100

90

80 90-100
80-90
70
70-80
60 60-70
50-60
50
40-50
40 30-40

30 20-30
12 10-20
20 10 0-10
8
10
6
0
0 4
1 2 3 4 5 6
2 Optimum
7 8 9 10 0
11 12 13
Optimum is always in a corner or an edge
 Linear Programming Solution Methods

• Simplex Algorithm
– Linear algebra-based method
– Search along edges (constraints) until solution cannot
be improved
• Interior Point Methods
– Approaches optimum from interior point
– Typically uses Newton-Rhapson (i.e., gradient
approach)
• Tradeoffs
– Simplex: each calculation is easy, could take many
– IPMs: each calculation expensive, converges faster
Idea of Nonlinear Programming (NLP)

450

400

350
400-450
350-400
300
300-350
250 250-300
200-250
200
150-200

150 100-150
50-100
7
100 0-50
5
50 3
1
0
-1
-5 -4 -3 -2 -1 0 -3
1 2 3 4 5 6 -5
7 8
 Linear Programming Standard Form

Original Problem:
Minimize: 2 x1 + 4 x2
Subject to: x1 + x2 ≥ 3
3 x1 + 2 x2 = 14
x1 ≥ 0
Becomes Elimination of free variables
+ −
Minimize: 2 x1 + 4 x2 − 4 x2 Slack variable
+ −
Subject to: x1 + x2 − x2 − x3 = 3
+ −
3 x1 + 2 x2 − 2 x2 = 14
+ −
x1 , x2 , x2 , x3 ≥ 0
 Linear Programming

𝑓𝑓 𝑥𝑥 and 𝑔𝑔 𝑥𝑥 are linear functions of 𝑥𝑥

𝑋𝑋 𝑖𝑖𝑖𝑖 convex

min 𝑓𝑓 𝑥𝑥
𝑥𝑥
𝑠𝑠𝑠𝑠. 𝑔𝑔 𝑥𝑥 ≥ 0
𝑥𝑥 ∈ 𝑋𝑋
 Linear Programming Framework
Standard Form for n variables and m constraints

min 𝑐𝑐 𝑇𝑇 𝑥𝑥
𝑥𝑥
𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏
𝑥𝑥 ≥ 𝟎𝟎
 Linear Programming Framework
Standard Form for n variables and m constraints

min 𝑐𝑐 𝑇𝑇 𝑥𝑥
𝑥𝑥
𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏
𝑥𝑥 ≥ 𝟎𝟎

(n x 1)
 Linear Programming Framework
Standard Form for n variables and m constraints

(n x 1)

min 𝑐𝑐 𝑇𝑇 𝑥𝑥
𝑥𝑥
𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏
𝑥𝑥 ≥ 𝟎𝟎

(n x 1)
 Linear Programming Framework
Standard Form for n variables and m constraints

(n x 1)

min 𝑐𝑐 𝑇𝑇 𝑥𝑥 (m x n)
𝑥𝑥
𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏 (m x 1)
𝑥𝑥 ≥ 𝟎𝟎

(n x 1)
 Example
min 𝑐𝑐 𝑇𝑇 𝑥𝑥 max 8𝑥𝑥 + 12𝑦𝑦
𝑥𝑥,𝑦𝑦
𝑥𝑥 Subject to:
𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏 10𝑥𝑥 + 20𝑦𝑦 ≤ 140
𝑥𝑥 ≥ 𝟎𝟎 6𝑥𝑥 + 8𝑦𝑦 ≤ 72
𝑥𝑥, 𝑦𝑦 ≥ 0
 Example
min 𝑐𝑐 𝑇𝑇 𝑥𝑥 max 8𝑥𝑥1 + 12𝑥𝑥2
𝑥𝑥,𝑦𝑦
𝑥𝑥 Subject to:
𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏 10𝑥𝑥1 + 20𝑥𝑥2 ≤ 140
𝑥𝑥 ≥ 𝟎𝟎 6𝑥𝑥1 + 8𝑥𝑥2 ≤ 72
𝑥𝑥1 , 𝑥𝑥2 ≥ 0

𝑥𝑥1
𝑥𝑥 = 𝑥𝑥
2

8
𝑐𝑐 =
12
 Example
min 𝑐𝑐 𝑇𝑇 𝑥𝑥 max 8𝑥𝑥1 + 12𝑥𝑥2
𝑥𝑥,𝑦𝑦
𝑥𝑥 Subject to:
𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏 10𝑥𝑥1 + 20𝑥𝑥2 ≤ 140
𝑥𝑥 ≥ 𝟎𝟎 6𝑥𝑥1 + 8𝑥𝑥2 ≤ 72
𝑥𝑥1 , 𝑥𝑥2 ≥ 0

𝑥𝑥1 10 20 𝑥𝑥1 140

𝑥𝑥 = 𝑥𝑥 ≤
2 6 8 𝑥𝑥2 72
8 A x b
𝑐𝑐 =
12
 Linear Programming
min 𝑐𝑐 𝑇𝑇 𝑥𝑥
𝑥𝑥 What if I want to maximize?
𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏
𝑥𝑥 ≥ 𝟎𝟎
m𝑖𝑖𝑖𝑖 −𝑐𝑐 𝑇𝑇 𝑥𝑥
𝑥𝑥
𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏
𝑥𝑥 ≥ 𝟎𝟎

8 𝑇𝑇 𝑥𝑥1 −8 𝑇𝑇 𝑥𝑥1
max 𝑥𝑥2 = min 𝑥𝑥2
12 −12
Linear Programming in MATLAB
In General: In MATLAB only:

min 𝑐𝑐 𝑇𝑇 𝑥𝑥 min 𝑐𝑐 𝑇𝑇 𝑥𝑥
𝑥𝑥 𝑥𝑥
𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏 𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≤ 𝑏𝑏
𝑥𝑥 ≥ 𝟎𝟎 𝑥𝑥 ≥ 𝟎𝟎

x = linprog(f,A,b)

solves min f'*x such that A*x ≤ b

Are these constraints binding?
Meaning that the solution makes sure that:
7x* + 2x* = 28
2x* + 12x* = 24
We checked using matlab:
A(1,:) *x and it gave 24, and A(2,:)*x and MATLAB gave 28 respectively
LP Example: Advertising Problem
• A company has started an advertising campaign and has to decide
how many ads to purchase on Broadcast TV shows and how
many from Streaming Services

• Each Broadcast Episode is watched by 7M Over-50 and 2M

Under-50.
• Each Streaming Episode is watched by 2M Over-50 and 12M
Under-50.

• Ads on Broadcast TV cost $50,000

• Ads on Streaming cost $100,000

• Ads need to be seen by at least 28M Over-50 and 24M Under-50.

• [NOTE: WE WILL ALLOW FRACTIONS FOR THIS

EXAMPLE!]
 Advertising Problem LP

𝑥𝑥1 : # spots purchased during Broadcast TV

𝑥𝑥2 : # spots purchased during Streaming TV

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
If I don't put in a negative sign in A and b in MATLAB, the constraints would be:
7x1 + 2x2 <= 28
2x1 + 12 x2 <=24 and the solution would be x1 = x2 = 0
 Advertising Problem LP

𝑇𝑇
min 𝑧𝑧 = 𝑐𝑐 𝑥𝑥
𝑥𝑥

𝐴𝐴 𝑥𝑥 ≥ 𝑏𝑏

𝑥𝑥 ≥ 𝟎𝟎
At the optimal solution, if the constraint is non-binding, the shadow price will be 0 because there
is no cost to relaxing the constraint. The solution is already beating the constraint
Advertising Problem LP

𝑥𝑥1
min 𝑧𝑧 = 𝑐𝑐 𝑇𝑇 𝑥𝑥2
𝑥𝑥
𝑥𝑥1
𝐴𝐴 𝑥𝑥2 ≥ 𝑏𝑏
𝑥𝑥1
𝑥𝑥2 ≥ 𝟎𝟎
 Advertising Problem LP

𝑥𝑥1
min 𝑧𝑧 = 𝑐𝑐 𝑇𝑇 𝑥𝑥2
𝑥𝑥

7 2 𝑥𝑥1 28
𝑥𝑥2 ≥
2 12 24
𝑥𝑥1
𝑥𝑥2 ≥ 𝟎𝟎
 Advertising Problem LP

𝑥𝑥1
min 𝑧𝑧 = 50 100 𝑥𝑥2
𝑥𝑥1,𝑥𝑥2

7 2 𝑥𝑥1 28
𝑥𝑥2 ≥
2 12 24
𝑥𝑥1 0
𝑥𝑥2 ≥
0
 Advertising Problem Solution
∗
∗ 𝑥𝑥1 3.6
• 𝑥𝑥 = ∗ = The asterick denotes the optimal solution
𝑥𝑥2 1.4

• 𝑧𝑧 ∗ = 𝑐𝑐 𝑇𝑇 𝑥𝑥 ∗
𝑥𝑥1∗
= 50 100 ∗
𝑥𝑥2
= 320

= 320,000
Q: When will an LP have a solution?

Q: Why can we solve LPs so quickly

Computers can solve LP's very quickly
 Advertising Problem LP

𝑥𝑥1 : # spots purchased during Broadcast TV

𝑥𝑥2 : # spots purchased during Streaming TV

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0 50
100
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Geometry of Advertising Problem

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0

This method of solving linear programs

is known as the interior point method, This and
3.6
the simplex method are two of the ways of solving 𝑥𝑥 ∗ =
linear programs on a computer 1.4
 LP Geometry 101

LP Standard Form

𝑇𝑇
min 𝑐𝑐 𝑥𝑥
𝑥𝑥
𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏
𝑥𝑥 ≥ 𝟎𝟎
- Each constraint in 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏 marks a half-space
- All constraints result in a polyhedron P = 𝑥𝑥 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏 , 𝑥𝑥 ≥ 𝟎𝟎}
- Every point within P is feasible
- 𝑥𝑥 ∗ is at one of the vertices of P
 LP Geometry 101
Exhaustive Search LP Solver

The interior point method

just looks at these vertexes, it
starts on the boundaries
whereas the interior point
method
does this search throughout the
feasible region until it finds the
solution. So this is why the
simplex is kind of better
 Will an LP always have a Solution?

• LP will always have a solution if P closed and

nonempty

• LP will be infeasible if P is empty

• LP will be unbounded if P is not closed

feasible: find a solution that satisfies the constraints
boundedness: solution is not going to shoot off to infinity
 Infeasibility
When ∄ 𝑥𝑥 𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏, 𝑥𝑥 ≥ 0

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Infeasibility
When ∄ 𝑥𝑥 𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏, 𝑥𝑥 ≥ 0

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1 + 𝑥𝑥2 ≤ 2
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Infeasibility
When ∄ 𝑥𝑥 𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏, 𝑥𝑥 ≥ 0

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1 + 𝑥𝑥2 ≤ 2
𝑥𝑥1, 𝑥𝑥2 ≥ 0

Cannot be simultaneoously in the

yellow AND red region, and hence this
is infeasible
 Infeasibility
When ∄ 𝑥𝑥 𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏, 𝑥𝑥 ≥ 0

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1 + 𝑥𝑥2 ≤ 2
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Unboundedness
When ∃𝑥𝑥 𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏, 𝑥𝑥 ≥ 0 and 𝑐𝑐 𝑇𝑇 𝑥𝑥 = −∞

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0
 Unboundedness
When ∃ 𝑥𝑥 ≥ 0 𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏 and 𝑐𝑐 𝑇𝑇 𝑥𝑥 = −∞

min 𝑧𝑧 = 50𝑥𝑥1 + 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0 50
100
 Unboundedness
When ∃ 𝑥𝑥 ≥ 0 𝑠𝑠𝑠𝑠. 𝐴𝐴𝐴𝐴 ≥ 𝑏𝑏 and 𝑐𝑐 𝑇𝑇 𝑥𝑥 = −∞

min 𝑧𝑧 = −50𝑥𝑥1 − 100𝑥𝑥2

𝑥𝑥1 ,𝑥𝑥2
𝑠𝑠𝑠𝑠. 7𝑥𝑥1 + 2𝑥𝑥2 ≥ 28
2𝑥𝑥1 + 12𝑥𝑥2 ≥ 24
𝑥𝑥1, 𝑥𝑥2 ≥ 0 −50
−100

it basically means we are trying

to maximize the function, and that
would really lead to a solution of
positive infinity