REGIONAL ECONOMICS MID-TERM EXAM

Linear Programming Part 1

J. M. Pogodzinski

Agenda

• Mathematical Programming Problems • Economic Theory and Mathematical Programming Problems • Linear Programming Problems

• The Objective Function • The Inequality Constraints • The Non-Negativity Constraints (which are inequality constraints) • Equality Constraints? • The Feasible Set

• Does a Solution Exist to a Linear Programming Problem? (the existence question) • Applications (Uses) of Linear Programming • Solving Linear Programming Problems • Theorems About Linear Programming

Mathematical Programming Problems

• A Mathematical Programming Problem consists of: • An objective function • Constraints defined somehow – equations, inequalities,…

• Little can be said about such a general problem – we need to make assumptions about the objective function and/or about the constraints before we can say anything about the existence of solutions, algorithms for finding solutions (if they exist), properties of solutions

About Objective Functions

• Very common to assume there is only one objective function • Objective functions are either maximized or minimized – the generic term is

optimized. The specific problem determines whether maximization or minimization is appropriate. There are deeper connections between maximization and minimization. Maximization problems can be restated as minimization problems. More importantly, specific maximization problems are associated with specific minimization problems through duality.

• It is possible to consider multi-objective mathematical programming problems (there is a legitimate topic called multi-objective linear programming)

• What do you get out of multi-objective linear programming (if there is a solution)?

• The Pareto Frontier • We will not consider multi-objective linear programming because it is

computationally difficult

About Objective Functions

• Example (from microeconomics): Consumers maximize utility subject to a budget constraint

• 𝑚𝑎𝑥𝑥,𝑦 𝑈 𝑥,𝑦 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑝𝑥𝑥 + 𝑝𝑦𝑦 = 𝑀 (and 𝑥 ≥ 0 and y ≥ 0) • We assume that 𝑈 𝑥,𝑦 is a quasi-concave continuous function

(Note: famous paper “Quasi-Concave Programming” by Kenneth J. Arrow and Alain C. Enthoven, Econometrica, Vol. 29, No. 4 (Oct., 1961), pp. 779-800)

• A function 𝑈 𝑥,𝑦 is quasi-concave if its upper level sets are convex sets

Constraints

• Most common to define constraints by one or more equations or inequalities

• Note on finite constraint sets – existence of optimum • For example, in the consumer choice problem mentioned in the

previous slide, an equation called the budget equation defined the constraint set - 𝑝𝑥𝑥 + 𝑝𝑦𝑦 = 𝑀 (and 𝑥 ≥ 0 and y ≥ 0)

• We might also have defined the constraint set with several inequalities: 𝑝𝑥𝑥 + 𝑝𝑦𝑦 ≤ 𝑀 and 𝑥 ≥ 0 and y ≥ 0

• We can write the equation 𝑝𝑥𝑥 + 𝑝𝑦𝑦 = 𝑀 as two inequalities: 𝑝𝑥𝑥 + 𝑝𝑦𝑦 ≤ 𝑀 and 𝑝𝑥𝑥 + 𝑝𝑦𝑦 ≥ 𝑀

The Consumer Choice Problem

𝑚𝑎𝑥𝑥,𝑦 𝑈 𝑥,𝑦 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑝𝑥𝑥 + 𝑝𝑦𝑦 = 𝑀 (and 𝑥 ≥ 0 and y ≥ 0)

Draw the constraint set (the feasible set) Draw some upper level sets of the objective function

Are these sets convex sets?

Convex Sets – Yes or No?

• Examples

Linear Programming Problems

• An LP Problem has: • A linear objective function • Linear inequality constraints • Non-negativity constraints

LP Problem – General Form

• Decision variables: 𝑥𝑗 (𝑗 = 1,…,𝑛) • (Linear) Objective function: Π = 𝑐1𝑥1 + 𝑐2𝑥2 + ⋯+ 𝑐𝑛𝑥𝑛 • (Linear) Inequality constraints:

𝑎11𝑥1 + ⋯+ 𝑎1𝑛𝑥𝑛 ≤ 𝑏1 𝑎21𝑥1 + ⋯+ 𝑎2𝑛𝑥𝑛 ≤ 𝑏2

𝑎𝑚1𝑥1 + ⋯+ 𝑎𝑚𝑛𝑥𝑛 ≤ 𝑏𝑚 • Non-negativity constraints: 𝑥1 ≥ 0, 𝑥2 ≥ 0,…, 𝑥𝑛 ≥ 0

Write this in matrix notation

Write this in matrix notation

x – variables a, b, c – parameters (constants)

Write this in matrix notation

LP Problem – An Example

• A Production Problem • 𝑥𝑗 amount of good j to be produced (j=1,…,n) • 𝑎𝑖𝑗 amount of resource i required to produce one unit of good j* • 𝑏𝑖 amount of resource i available • 𝑐𝑗 profit per unit of good j

*CONVENTION: (i,j) = (row, column)

Graph it! Solve it!

Write in matrix notation!

Products Variables socks x1 shirts x2

Resources Parameters Looms b1 10

Sewing Machines b2 15 Labor b3 12

Coefficient Matrix 1 1 3 1 2 1

Product net revenue Pi-1 Pi-2 Pi-3 socks c1 1 2 1 shirts c2 1 1 2

Linear Programming Part 2

J. M. Pogodzinski

Agenda

• Some LP Theorems • Excel skills: sumproduct, matrix multiplication, matrix inversion • Using Excel to Solve LP Problems (demo) • Binding and non-binding constraints • The Dual LP Problem • The Dual Solution Variables • The Value of the Program • The Duality Theorem • Interpretation of the Dual Solution Variables

Some Linear Programming Theorems

• If a Linear Programming (LP) Problem has a solution, the solution occurs at a vertex of the feasible set.

• If the feasible set is bounded, there are a finite number of vertices. • This means there is an “obvious” algorithm for solving an LP Problem

with a bounded feasible set: compute the value of the objective function at every vertex of the feasible set – the largest value is the maximum; the smallest value is the minimum.

• Not every LP Problem that has a solution has a bounded feasible set

Excel Skills (demos and downloadable file)

• Dot product • Transpose Matrix • Inverse Matrix • Solve an LP Problem

The Dual LP Problem

• For every LP Problem, there is a related LP Problem called the “dual” of the first problem

• The first problem is called the Primal LP Problem, the related problem is called the Dual LP Problem

• The dual of the Dual LP Problem is the Primal LP Problem

Going from the Primal LP Problem to the Dual LP Problem The Primal LP Problem

𝑎11𝑄1 + ⋯+ 𝑎1𝑛𝑄𝑛 ≤ 𝐶1 .

.

. 𝑎𝑚1𝑄1 + ⋯+ 𝑎𝑚𝑛𝑄𝑛 ≤ 𝐶𝑚

𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 Π = 𝑃1𝑄1 + ⋯+ 𝑃𝑛𝑄𝑛

𝑄1 ≥ 0,𝑄2 ≥ 0,…,𝑄𝑛 ≥ 0

Baumol’s “mad gremlin”

The Dual LP Problem 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 Α = 𝐶1𝑉1 + ⋯+ 𝐶𝑚𝑉𝑚

𝑎11𝑉1 + ⋯+ 𝑎𝑚1𝑉𝑚 ≥ 𝑃1

𝑉1 ≥ 0,𝑉2 ≥ 0,…,𝑉𝑚 ≥ 0

𝑎1𝑛𝑉1 + ⋯+ 𝑎𝑚𝑛𝑉𝑚 ≥ 𝑃𝑛

.

.

.

𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 Π = 𝑃1𝑄1 + ⋯+ 𝑃𝑛𝑄𝑛

𝑎11𝑄1 + ⋯+ 𝑎1𝑛𝑄𝑛 ≤ 𝐶1 . . .

𝑎𝑚1𝑄1 + ⋯+ 𝑎𝑚𝑛𝑄𝑛 ≤ 𝐶𝑚

𝑄1 ≥ 0,𝑄2 ≥ 0,…, 𝑄𝑛 ≥ 0

𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 Α = 𝐶1𝑉1 + ⋯+ 𝐶𝑚𝑉𝑚

𝑎11𝑉1 + ⋯+ 𝑎𝑚1𝑉𝑚 ≥ 𝑃1 . . .

𝑎1𝑛𝑉1 + ⋯+ 𝑎𝑚𝑛𝑉𝑚 ≤ 𝑃𝑛

𝑉1 ≥ 0, 𝑉2 ≥ 0, …,𝑉𝑚 ≥ 0

Primal and Dual: Head-to-Head

𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 Π = 𝑃1𝑄1 + ⋯+ 𝑃𝑛𝑄𝑛

𝑎11𝑄1 + ⋯+ 𝑎1𝑛𝑄𝑛 ≤ 𝐶1 . . .

𝑎𝑚1𝑄1 + ⋯+ 𝑎𝑚𝑛𝑄𝑛 ≤ 𝐶𝑚

𝑄1 ≥ 0,𝑄2 ≥ 0,…, 𝑄𝑛 ≥ 0

𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 Α = 𝐶1𝑉1 + ⋯+ 𝐶𝑚𝑉𝑚

𝑎11𝑉1 + ⋯+ 𝑎𝑚1𝑉𝑚 ≥ 𝑃1 . . .

𝑎1𝑛𝑉1 + ⋯+ 𝑎𝑚𝑛𝑉𝑚 ≥ 𝑃𝑛

𝑉1 ≥ 0, 𝑉2 ≥ 0, …,𝑉𝑚 ≥ 0

Objective Function P – parameters

Q – choice variables n

Objective Function C – parameters

V – choice variables m

Transposed Coefficient Matrices

Primal (mxn) Dual (nxm)

Constraints: m inequalities in n unknowns Constraints: n inequalities in m unknowns

Analysis of Primal and Dual LP

Problems

Primal LP Problem

Dual LP Problem

Duality Theorem

• Definition: the value of the program for an LP Problem is the value of the objective function at the optimal solution.

• THEOREM: If the Primal LP Problem has a solution, then the Dual LP Problem has a solution, and Value of the Primal Program equals the Value of the Dual Program.

• Note: the values of the programs are equal, not the solutions of the programs

Demo: The Dual LP Problem

• Formulation of the Dual LP Problem in Excel (demo) • Solution of the Dual LP Problem using Excel (demo)

Interpreting the Dual Solution Values

Linear Programming Part 3

J. M. Pogodzinski

Agenda

• Applications of LP • The Diet Problem • Transportation Problems

The Diet Problem

• How to feed an army in the most economical way while meeting nutritional requirements (also, according to Hadley, feeding livestock, provisioning submarine or spacecraft)

• Dietician must select amounts of n foods (F1, F2, …, Fn) that provide certain amounts of m nutrients (N1, N2, …, Nm)

• Each person must consume (G1, G2, …, Gm) of the corresponding nutrient • aij denotes the amount of the i-th nutrient contained in one unit of the j-th

food, i.e., aij is the amount of Ni contained in one unit of Fj • The choice variable is the amounts of foods to be eaten (e1, e2,…,en) • The prices of each food are (p1, p2, …,pn)

Coefficient Matrix for the Diet Problem

F1 F2 . . . Fn N1 a11 a12 a1n N2 a21 a22 a2n . . .

Nm am1 am2 amn

In-Class Activity

• Assume • (G1, G2, …, Gm) • (e1, e2,…,en) • (p1, p2, …,pn) are column vectors, i.e., G is mx1, and e and p are nx1

• Using matrix notation, write down the LP Problem • Using matrix notation, write down the Dual LP Problem

Diet Problem – In-Class Example

Transportation Problem

• Let a commodity be produced at each of m plants (P1,P2,…,Pm) [m origins] • The commodity is needed in each of n markets (M1,M2,…,Mn) [n

destinations] • Denote by Ci the capacity of the i-th plant [availability at origins] • Denote by dj the demand in the j-th market [needs at destinations] • Denote by cij the cost of shipping one unit of the commodity from plant i

to market j • Determine a shipping schedule xij (the amount to be shipped from plant i

to market j) • Assume σ𝑖=1

𝑚 𝐶𝑖 = σ𝑗=1 𝑛 𝑑𝑗 [What does this mean?]

Inequality and Non-Negativity Constraints of the Transportation Problem The Objective Function of the Transportation Problem • σ𝑗=1

𝑛 𝑥𝑖𝑗 = 𝐶𝑖 𝑖 = 1,…,𝑚

• σ𝑖=1 𝑚 𝑥𝑖𝑗 = 𝑑𝑗 𝑗 = 1,…,𝑛

• 𝑥𝑖𝑗 ≥ 0

• 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑧 = σ𝑖,𝑗 𝑐𝑖𝑗𝑥𝑖𝑗

The Transportation Problem in Matrix Notation

• 𝒙 = (𝑥11,…,𝑥1𝑛,𝑥21,…,𝑥2𝑛,…,𝑥𝑚𝑛) • 𝒃 = (𝐶1,…,𝐶𝑚,𝑑1,…,𝑑𝑛)

• 𝑨 is an 𝑚 + 𝑛 x 𝑚𝑛 matrix

• Transportation Problem • 𝑨𝒙 = 𝒃,𝒙 ≥ 0max𝑜𝑟 min𝑧 = 𝒄𝒙

Linear Programming Part 4

J. M. Pogodzinski

Agenda

• Dual of the Diet Problem • More about the Transportation Problem • Variants of the Transportation Problem • Dual of the Transportation Problem

Recall: The Diet Problem

• How to feed an army in the most economical way while meeting nutritional requirements (also, according to Hadley, feeding livestock, provisioning submarine or spacecraft)

• Dietician must select amounts of n foods (F1, F2, …, Fn) that provide certain amounts of m nutrients (N1, N2, …, Nm)

• Each person must consume (G1, G2, …, Gm) of the corresponding nutrient • aij denotes the amount of the i-th nutrient contained in one unit of the j-th

food, i.e., aij is the amount of Ni contained in one unit of Fj • The choice variable is the amounts of foods to be eaten (e1, e2,…,en) • The prices of each food are (p1, p2, …,pn)

The Diet Problem in Matrix Notation (Example)

F1 F2 F3 F4 F5 N1 1 0 1 1 2 N2 0 1 0 1 1

G1 700 G2 400

e1 e2 e3 e4 e5

≥ 0 ≥ 0 ≥ 0 ≥ 0 ≥ 0

p1 2 p2 20 p3 3 p4 11 p5 12

What is the objective function and do you maximize it or minimize it?

Explain the logic of the Diet Problem

The Dual to the Diet Problem (Example)

G1 700 G2 400

p1 2 p2 20 p3 3 p4 11 p5 12

What is the objective function and do you maximize it or minimize it?

Explain the logic of the Dual to the Diet Problem

N1 N2 F1 1 0 F2 0 1 F3 1 0 F4 1 1 F5 2 1

v1 v2

≥ 0 ≥ 0

Recall: The Transportation Problem

• Let a commodity be produced at each of m plants (P1,P2,…,Pm) [m origins] • The commodity is needed in each of n markets (M1,M2,…,Mn) [n

destinations] • Denote by Ci the capacity of the i-th plant [availability at origins] • Denote by dj the demand in the j-th market [needs at destinations] • Denote by cij the cost of shipping one unit of the commodity from plant i

to market j • Determine a shipping schedule xij (the amount to be shipped from plant i

to market j) • Assume σ𝑖=1

𝑚 𝐶𝑖 = σ𝑗=1 𝑛 𝑑𝑗 [What does this mean?]

Transportation Problem (Example) m 2 origins

n 4 destinations Ax = b Matrix A (m+n)x(mn) rows 6

columns 8

1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1

Vector b a1 origin 10 a2 origin 15 b1 destination 2 b2 destination 6 b3 destination 8 b4 destination 9

Vector c c11 3 c12 4 c13 2 c14 5 c21 3 c22 6 c23 7 c24 4

Vector x x11 x12 x13 x14 x21 x22 x23 x24

What is the objective function and do you maximize it or minimize it?

Explain the logic of the Transportation Problem