42111: Static and Dynamic Optimzation Introduction

(1)

42111: Static and Dynamic Optimzation Introduction

Richard M. Lusby

DTU Management Engineering

(2)

People & Places

Primary Contacts

•Static: Associate Professor Richard Lusby

•rmlu@dtu.dk, office: 424/208

•Static: Assistant Professor Evelien van der Hurk

•evdh@dtu.dk, office: 424/226

•Dynamic: Associate Professor Niels Kjølstad Poulsen

•nkpo@dtu.dk, office: 303b/016

Location

All lectures and exercises will take place in B421-A73

(3)

Course Objectives

Main Objective

To give a well-founded knowledge, both theoretical and practical, of static and dynamic optimization models for data-based decision making. You will be able to formulate and solve operations research and technical-economic models, and to appreciate the interplay between optimization models and the real-life problems described by these.

My part of the course

•Static Optimization

•Non-Linear Programs

•Theoretical properties, Formulations, Solution Methods

(4)

Course Objectives

Main Objective

To give a well-founded knowledge, both theoretical and practical, of static and dynamic optimization models for data-based decision making. You will be able to formulate and solve operations research and technical-economic models, and to appreciate the interplay between optimization models and the real-life problems described by these.

My part of the course

•Static Optimization

•Non-Linear Programs

•Theoretical properties, Formulations, Solution Methods

(5)

Learning Objectives (1)

•Analyzea given problem in order toformulatean optimization model

•Formulateandanalyzemodels as these are met in static and dynamic optimization.

•Describeandexplain the assumptions underlying models and computations

•Analyzean optimization problem in order to identify an appropriate solution method

•Understandand - using software -solvesystems of equations for given optimization problems

•Interpretthe solutions from a given optimization model

(6)

Learning Objectives (2)

•Describeandexplain the mathematical background for the applied solution methods.

•Performsensitivity analysis as part of the evaluating of what-if scenarios in decision making.

•Make useof the possibilities for sensitivity analysis in standard optimization software.

(7)

Course Evaluation

•Twowritten projects (one for static, one for dynamic)

•To be completed individually

•If you collaborate with another student, this must be documented

•Your final mark will be based on the evaluation of the two projects

•Reportsmustbe submitted electronically via CampusNet

•Static report due: Friday,October 13^th

•Dynamic report due: Friday,December 22^nd

•Project one will be distributednextweek

(8)

Calendar - Lecture Plan

Date Topic

04 September Introduction

11 September Linear programming and duality 18 September Convexity and optimality

25 September Optimization with (in)equality constraints 02 October More on Lagrange

09 October (Approximate) Solution Algorithms for Non-linear problems

Mathematical Programming

•Components:

•Decision variables

•Objective function

•Constraints

•Model types:

•Linear Programming

•Integer Programming

•Non-linear Programming

•Today’s Agenda:

•Linear programming review

•Non-linear programming intro

•Chapter 12 Hillier & Liberman 9^th Edition

(10)

Linear Programming (1)

Example

The WYNDOR GLASS CO. produces high quality glass products, including windows and glass doors. It has 3 plants. Aluminium frames and hardware are made in Plant 1, wood frames are made in Plant 2, and Plant 3 produces the glass and assembles the products. Management is introducing the following two

products (in batches of 20):

•Product 1: An 8-foot glass door with an aluminum frame (ppb = $3,000)

•Product 2: A 4×6foot double hung wood-framed window (ppb = $5,000)

Data

Production Time Required (hrs)

Plant Product 1 Product 2 Hours avail.

1 1 0 4

2 0 2 12

3 3 2 18

(11)

Linear Programming (2)







maximize Z = 3x

₁

+ 5x

₂

subject to: x

₁

≤ 4

2x

2

≤ 12 3x

₁

+ 2x

₂

≤ 18

x

1

≥ 0

x

2

≥ 0







(12)

Linear Programming (2)







maximize Z = 3x

₁

+ 5x

₂

subject to: x

₁

≤ 4

2x

2

≤ 12 3x

₁

+ 2x

₂

≤ 18

x

1

≥ 0

x

2

≥ 0







(13)

Linear Programming (2)







maximize Z = 3x

₁

+ 5x

₂

subject to: x

₁

≤ 4

2x

2

≤ 12 3x

₁

+ 2x

₂

≤ 18

x

1

≥ 0

x

2

≥ 0







(14)

Linear Programming (2)







maximize Z = 3x

₁

+ 5x

₂

subject to: x

₁

≤ 4

2x

2

≤ 12 3x

₁

+ 2x

₂

≤ 18

x

1

≥ 0

x

2

≥ 0







(15)

Linear Programming (2)







maximize Z = 3x

₁

+ 5x

₂

subject to: x

₁

≤ 4

2x

2

≤ 12 3x

₁

+ 2x

₂

≤ 18

x

1

≥ 0

x

2

≥ 0







(16)

Linear Programming (2)







maximize Z = 3x

₁

+ 5x

₂

subject to: x

₁

≤ 4

2x

2

≤ 12 3x

₁

+ 2x

₂

≤ 18

x

1

≥ 0

x

2

≥ 0







(17)

Linear Programming (2)







maximize Z = 3x

₁

+ 5x

₂

subject to: x

₁

≤ 4

2x

2

≤ 12 3x

₁

+ 2x

₂

≤ 18

x

1

≥ 0

x

2

≥ 0







(18)

Linear Programming

1 2 3 4 5 6 7

1 2 3 4 5 6 7 x

₂

x

1

Z = 25

(19)

Linear Programming

maximize c

^T

x

subject to: x ∈ X

(20)

Linear Programming

•Consider the polyhedronX =Ax≤b

•A solutionx⁰ isfeasibleifAx⁰≤b

•A solutionx^∗ isoptimalifAx^∗≤b,c^Tx^∗≥,c^Tx ∀x∈ X

•The set of feasible solutions to an LP is termed thefeasible region

•forms a (possibly unbounded)convexset.

•Anextreme point ofX cannot be written as a linear combination of other points inX

@λ∈(0,1) :x=λy+ (1−λ)z, x,y,z∈ X,x6=y,x6=z

•A solutionx⁰ is abasic feasible solutionif Ax⁰≤b,∃B:x⁰ =A⁻¹_B b

•or,x⁰ is a basic feasible solution if and only ifx⁰ is an extreme point

(21)

Linear Programming

•Every linear program can be one of : infeasible,unbounded, or have aunique optimal solution value

•Every linear program has an extreme point that is an optimal solution

•A solution approach need only consider extreme points

•A constraint of a linear program isbindingat a pointx⁰ if the inequality is met with equality atx⁰. It isnonbinding/slackotherwise.

•What is a dual variable?

•If I have an unbounded polyhedron is my formulation unbounded?

•Can an LP have multiple optimal solutions? What does this mean?

•How do we solve linear programs?

(22)

Linear Programming

•Every linear program can be one of : infeasible,unbounded, or have aunique optimal solution value

•Every linear program has an extreme point that is an optimal solution

•A solution approach need only consider extreme points

•A constraint of a linear program isbindingat a pointx⁰ if the inequality is met with equality atx⁰. It isnonbinding/slackotherwise.

•What is a dual variable?

•If I have an unbounded polyhedron is my formulation unbounded?

•Can an LP have multiple optimal solutions? What does this mean?

•How do we solve linear programs?

(23)

Solution Method

(24)

Linear Programming

maximize

#

≥

"

0 0

#

(25)

Non Linear Programming

maximize f (x)

subject to: g

_i

(x) ≤ b

_i

∀i

x ≥ 0

(26)

Product-mix problem

•Production: y

•Price required to selly units: p(y)

•Total cost of producingyunits: c(y)

•Profit:

π(y) =yp(y)−c(y)

•Cost of shipping one extra unit: stair-case constant

•Cost of shippingy units: c(y), piecewise linear

•x_ij: The volume shipped from sourceito destinationj

•Share price of stockj: pj

•Return on one share of stockj is a random variable with meanµj and variance σjj

•Covariance between stock returns of two stocksiandj: σ_ij

•Portfolio is to consist ofx_j shares of stockj ∀j

•Mean of portfolio return:

X

j

µ_jx_j

•Variance of portfolio return:

X

i

X

j

σijxixj

(41)

Portfolio Selection

X

j

µ_jx_j

X

i

X

j

σijxixj

(42)

Portfolio Selection

X

j

µ_jx_j

X

i

X

j

σijxixj

(43)

Portfolio Selection

X

j

µ_jx_j

X

i

X

j

σijxixj

(44)

Portfolio Selection

X

j

µ_jx_j

X

i

X

j

σijxixj

(45)

Portfolio Selection

X

j

µ_jx_j

X

i

X

j

σijxixj

(46)

Portfolio Selection

•We usually want a high return with a low risk

•Minimum acceptable expected return: r

•Maximum budget available: b

Formulation

minimize P

i

P

jσijxixj

subject to: P

jµ_jx_j ≥r

P

jpjxj ≤b

•Non-negativity constraints?

•Parametric programming onr yields the efficient frontier

(47)

Portfolio Selection

Formulation

minimize P

i

P

jσijxixj

subject to: P

jµ_jx_j ≥r

P

jpjxj ≤b

(48)

Portfolio Selection

Formulation

minimize P

i

P

jσijxixj

subject to: P

jµ_jx_j ≥r

P

jpjxj ≤b

(49)

Portfolio Selection

Formulation

minimize P

i

P

jσijxixj

subject to: P

jµ_jx_j ≥r

P

jpjxj ≤b

(50)

Portfolio Selection

Formulation

minimize P

i

P

jσijxixj

subject to: P

jµ_jx_j ≥r

P

jpjxj ≤b

(51)

Portfolio Selection

Formulation

minimize P

i

P

jσijxixj

subject to: P

jµ_jx_j ≥r

P

jpjxj ≤b

(52)

Portfolio Selection

Formulation

minimize P

i

P

jσijxixj

subject to: P

jµ_jx_j ≥r

P

jpjxj ≤b

(53)

Non-Linear Programming Example 1







maximize Z = 3x

₁

+5x

₂

subject to: x

1

≤ 4

9x

²₁

+5x

²₂

≤ 216

x

₁

≥ 0

x

2

≥ 0







(54)

Graphical Illustration (1)

1 2 3 4 5 6 7

1 2 3 4 5 6 7 x

2

x

₁

Z = 36

(2,6)

(55)

Graphical Illustration (2)

•The optimal solution remains unchanged

•It isNOTa corner point of the feasible region

1

≤ 4

2x

₂

≤ 12

3x

1

+2x

2

≤ 18

x

1

≥ 0

x

₂

≥ 0







(61)

Graphical Illustration (1)

1 2 3 4 5 6 7

1 2 3 4 5 6 7 x

2

x

₁

Z = 857

(

⁸₃

,5)

(62)

Graphical Illustration (2)

•The optimal solution is also not a corner point

•The locus of points withZ= 857intersects the feasible region at this point only

•The locus of points withZ >857does not intersect the feasible region at all

₂

≥ 0







(67)

Graphical Illustration (1)

1 2 3 4 5 6 7

1 2 3 4 5 6 7 x

2

₁

(3,3)

Z=198 Z=189 Z=162 Z=117

(72)

Graphical Illustration (2)

•The optimal solution is aninteriorpoint of the feasible region

•Solution to the unconstrained global maximum

•A general solution approach needs to considerallpoints

(73)

Graphical Illustration (2)

(74)

Graphical Illustration (2)

(75)

Graphical Illustration (2)

(76)

Convexity

•Convex Function

•Concave Function







maximize Z = 3x

₁

+5x

₂

subject to: x

1

≤ 4

8x

1

− x

²₁

+14x

2

− x

²₂

≤ 49

x

₁

≥ 0

x

2

≥ 0







(85)

Graphical Illustration (1)

1 2 3 4 5 6 7

1 2 3 4 5 6 7 x

2

x

₁

Z = 27 Z = 35

(4,3)

(0,7)

(86)

Problem Types

•Unconstrained Optimization

•No constraints

•Linearly Constrained Optimization

•linear constraints

•Quadratic Programming

•quadratic objective function, linear constraints

•Convex Programming

•minimize a convex function on a convex set

•Separable Programming

•objective function and constraints are separable i.e. sum of functions of individual decision variables

(87)

Class Exercises

Problem 1

minimize (x₁−255)² +10(x₁−220) +(x2−x1)² +10(x2−240)

+(x₃−x₂)² +10(x₃−200) +(255−x₃)² subject to: x1≥220 x2≥240 x3≥200

Problem 2

maximize 36x1+ 9x²₁−6x³₁+ 36x2−3x³₂ subject to: x1+x2≤3, x1≥0, x2≥0

(88)

Richard M. Lusby

DTU Management Engineering, Technical University of Denmark

Building 424, Room 208 rmlu@dtu.dk

2800 Kgs. Lyngby, Denmark phone +45 4525 3084 http://www.man.dtu.dk

42111: Static and Dynamic Optimzation Introduction