9/2/2021

IE 411:
Operations Research II

Dr. Ammar Y. Alqahtani

Assistant Professor of Industrial Engineering
College of Engineering
King Abdulaziz University

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 1

Alqahtani

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 2

Alqahtani

1
 9/2/2021

EXAMPLE 1 Distributing Medical Teams to Countries

The WORLD HEALTH COUNCIL is devoted to improving health care in the
underdeveloped countries of the world. It now has five medical teams available to
allocate among three such countries to improve their medical care, health
education, and training programs. Therefore, the council needs to determine how
many teams (if any) to allocate to each of these countries to maximize the total
effectiveness of the five teams. The teams must be kept intact, so the number
allocated to each country must be an integer.
The measure of performance being used is additional person-years of life. (For a
particular country, this measure equals the increased life expectancy in years
times the country’s population). Which allocation maximizes the measure of
performance?

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 3

Alqahtani

Standard Mathematical Programming

Formulation

3
Maximize  p (x )
n 1
n n

subject to
3

x
n 1
n  5,

and
xn are nonnegativ e integers, n  1, 2, 3

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 4

Alqahtani

2
 9/2/2021

DP Formulation of Example 1

• Stage n: country, n = 1, 2, 3
• Decision variable xn: number of medical teams allocated to the nth
country
• State sn: number of medical teams still available for allocation to
remaining countries (n, …, 3)
• State transformation:

where s1 = 5.

• Recursive Relationship:

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 5

Alqahtani

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 6

Alqahtani

3
 9/2/2021

DP Solution Procedure

n=3
S3 f3*(S3) X3*

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 7

Alqahtani

DP Solution Procedure

n=2

X2 𝒇𝟐 𝒔𝟐 , 𝒙𝟐 = 𝒑𝟐 𝒙𝟐 + 𝒇𝟐 ∗ 𝒔𝟐 − 𝒙𝟐
S2 f2*(S2) X2*
0 1 2 3 4 5

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 8

Alqahtani

4
 9/2/2021

DP Solution Procedure

n=1

X1 𝒇𝟏 𝒔𝟏 , 𝒙𝟏 = 𝒑𝟏 𝒙𝟏 + 𝒇𝟏 ∗ 𝒔𝟏 − 𝒙𝟏
S1 f1*(S1) X1*
0 1 2 3 4 5

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 9

Alqahtani

DP Solution Procedure

Optimal solution:
s1*= 1,
s2 = s1 – x1* = 5 – 1 = 4 => x2* = 3
s3 = s2 – x2* = 4 – 3 = 1 => x3* = 1

x1

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 10

Alqahtani

5
 9/2/2021

EXAMPLE 2 Distributing Scientists to Research Teams

• A government space project is conducting research on a certain engineering
problem that must be solved before people can fly safely to Mars. Three
research teams are currently trying three different approaches for solving this
problem. The estimate has been made that, under present circumstances, the
probability that the respective teams – call them 1,2, and 3 – will not succeed is
0.40, 0.60, and 0.80, respectively. Thus, the current probability that all three
teams will fail is (0.40)(0.60)(0.80) = 0.192. Because the objective is to minimize
the probability of failure, two more top scientists have been assigned to the
project.
The table below gives the estimated probability that the respective teams
will fail when 0,1,or 2 additional scientists are added to that team. Only integer
numbers of scientists are considered because each new scientist will need to
devote full attention to one team. The problem is to determine how to allocate
the two additional scientists to minimize the probability that all three teams will
fail.

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 11

Alqahtani

Standard Mathematical Programming Formulation

, i = 1, 2, 3.

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 12

Alqahtani

6
 9/2/2021

DP Formulation of Example 2

• Stage n: team n = 1, 2, 3
• Decision variable xn: number of additional scientists allocated to team n
• State sn: number of scientists still available for allocation to remaining teams
(n, …, 3)
• State transformation:

• Recursive Relationship:

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 13

Alqahtani

DP Solution Procedure

n=3

S3 f3*(S3) X3*

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 14

Alqahtani

7
 9/2/2021

DP Solution Procedure

n=2

X2 𝒇𝟐 𝒔𝟐 , 𝒙𝟐 = 𝒑𝟐 𝒙𝟐 + 𝒇𝟐 ∗ 𝒔𝟐 − 𝒙𝟐
f2*(S2) X2*
S2 0 1 2

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 15

Alqahtani

DP Solution Procedure

n=1

X1 𝒇𝟏 𝒔𝟏 , 𝒙𝟏 = 𝒑𝟏 𝒙𝟏 + 𝒇𝟏 ∗ 𝒔𝟏 − 𝒙𝟏
S1 f1*(S1) X1*
0 1 2

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 16

Alqahtani

8
 9/2/2021

DP Solution Procedure

Optimal solution:
x1*= 1,
s2 = s1 – x1* = 2 – 1 = 1 => x2* = 0
s3 = s2 – x2* = 1 – 0 = 1 => x3* = 1

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 17

Alqahtani

EXAMPLE 3 Wyndor Glass Company Problem

Maximize Z = 3x1 + 5x2
subject to
x1 ≤4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
and
x1, x2 ≥ 0

We need some notation for the parameters:

Maximize Z = c1x1 + c2x2

subject to
a11x1+ a12x2 ≤ 4
a21x1+ a22x2 ≤ 12
a31x1+ a32x2 ≤ 18
and
x1, x2 ≥ 0

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 18

Alqahtani

9
 9/2/2021

DP Formulation of Example 3
• Stage n: activity n = 1, 2
• Decision variable xn: activity level
• State vector sn: amount of resources still available for allocation to
remaining activities sn = (R1, R2, R3) with s1 = (4,12,18)
• State transformation:
stage n stage n+1
xn
sn=(R1,R2,R3) sn+1=(R1- α1nxn, R2- α2nxn, R3- α3nxn)

max[c n x n  fn 1 (s n 1 )]
*
• Recursive Relationship: fn*(R1, R2, R3): =
xn

Curse of Dimensionality: the number of calculations required “blows up” with the
number of state variables.
Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 19
Alqahtani

DP Solution Procedure

x1*=2 =>
R1 = 4 – 2 = 2, R2 = 12, R3 = 18 – 3(2) = 12
R 12 R 12 
x 2  min  2  , 3    6
*

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 2 2 2 2 20

Alqahtani

10
 9/2/2021

A Nonlinear Optimization Problem Solved by

Dynamic Programming
Consider the nonlinear problem:
Maximize z  2 x1  x12  x2
Subject to x1  x 2  3
x1 , x 2  0

DP Formulation by Dynamic Programming :

Stages : Activities n = 1,2
Dec.Var. : Activity levels xn, n = 1,2
State : Amount available for allocation, sn, n = 1,2; s1 = 3
State transformation : xn
sn sn-xn
Stage n Stage n+1

Recursive relationship : f n ( s n , xn )  g n ( xn )  f n1 ( s n  xn ) ; f 3 ()  0

where g1 ( x1 )  2 x1  x1 and g 2 ( x 2 )  x 2
2

f n ( sn )  max f n ( sn , xn ), 0  xn  sn

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 21

Alqahtani

DP Solution:

Stage n = 2
f 2 (s 2 , x 2 )  g 2 ( x 2 )  x 2  f 2 (s 2 )  max x 2   s 2 ; x 2  s 2


0  x2  s2

Stage n = 1
f1 (s1 , x1 )  g1 ( x1 )  f 2 (s1  x1 )  2x1  x12  f2 (3  x1 )


f1 (3)  max 2 x1  x12  3  x1  
 max x1  x12  3 
0 x1 3 0 x1 3

f1 (3, x1 )
 1  2 x1  0  x1  1
x1 2
 f1 (3, x1 )
2
yields a maximum (since  2  0 )
x12
 
 x1  1 
2 x2  2
5 with z  f1 (3)  3 1
4

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 22

Alqahtani

11
 9/2/2021

Knapsack Problem
Suppose that a 20-Kg knapsack is to be filled with three types of items. The
weight and benefit of an item depends on type, as shown in the table below.
In order to maximize total benefit, how should the knapsack be filled if at
least one item from each type should be included. Formulate and solve by
Dynamic Programming.
Type (n) Weight (wn) Benefit (cn)
1 4 10
2 3 7
3 5 12
Integer Programming Formulation of the Knapsack Problem.

Max 10x1 + 7x2 + 12x3

s.t. 4x1 + 3x2 + 5x3 ≤ 20
xj ≥ 1 and integer, n = 1, 2, 3
Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 23
Alqahtani

DP Formulation of the Knapsack Problem

• Stage n: type of item, n = 1, 2, 3

• Decision variable xn: number of items of type n placed in the knapsack
• State sn: Knapsack capacity left for remaining types, n, …, 3
• State transformation:
stage n stage n+1
xn
sn sn+1=sn- wnxn

• Recursive Relationship:
fn(sn,xn) = c n x n + fn+1*(sn+1)

fn*(sn): = max fn (s n , x n )
xn

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 24

Alqahtani

12
 9/2/2021

DP Solution Procedure

n=3

S3 f3*(S3) X3*

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 25

Alqahtani

DP Solution Procedure

n=2
X2 𝒇𝟐 𝒔𝟐 , 𝒙𝟐 = 𝒑𝟐 𝒙𝟐 + 𝒇𝟐 ∗ 𝒔𝟐 − 𝒙𝟐
f2*(S2) X2*
S2 1 2 3

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 26

Alqahtani

13
 9/2/2021

DP Solution Procedure

n=1

X1 𝒇𝟏 𝒔𝟏 , 𝒙𝟏 = 𝒑𝟏 𝒙𝟏 + 𝒇𝟏 ∗ 𝒔𝟏 − 𝒙𝟏
S1 f1*(S1) X1*
1 2 3

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 27

Alqahtani

Capacity Expansion

A state expects the following annual growth in electricity demand during the next ten
years.

Year (n) 1 2 3 4 5 6 7 8 9 10
Growth in MWs (dn) 2 3 1 5 2 3 5 3 2 1

To meet the demand, capacity must be constructed. The cost of capacity as a function
of size is shown in the table below.

Size in MWs (xn) 1 2 3 4 5

Cost in $ millions, cn(xn) 20 38 55 70 80

The discount rate for time value of money calculations is i = .10.

Find the optimum capacity expansion plan to minimize the present worth of capital
expenditures.

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 28

Alqahtani

14
 9/2/2021

DP Formulation of the Capacity Expansion Problem

• Stage n: year n = 1, 2, …,10

• Decision variable: xn: capacity built in year n, xn = 0, 1, …, 5
• State sn: free (available above demand) capacity to meet demand
growth in remaining years n, n+1, …, 10
• State transformation:
stage n+1
stage n xn
sn sn+1=sn+ xn-dn

• Recursive Relationship:

fn(sn,xn) = c n ( x n ) + [fn+1*(sn+1)]/(1+i)

fn*(sn): = min fn (s n , x n )
xn 0,1,...,5

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 29

Alqahtani

Machine Replacement

Plan the replacement policy for a machine which must perform some function for the
next 10 years. The machine is currently 3 years old. To purchase a new machine
requires an investment of $40K. A machine can be used for at most five years. The
operating cost and trade-in value depend on the age of machine as in the table below:

Age (k) 1 2 3 4 5
Operating Cost, in $1000s, op(k) 13[1] 14 16 19 22
Trade-in Value, in $1000s, tr(k) 30[2] 25 20 18 16
The salvage value at the end of the ten years period is the same as the trade-in value.
The discount rate for time value of money calculations is i=.10. Find the machine
replacement policy that minimizes the present value of investment plus operating
cost less trade-in and salvage values.
Hint: The stage is the current year and the state is the age of the machine. The
decision variable xn takes the value 1 if machine is replaced at the beginning of year
n and 0 if it is not.
[1] Operating cost during the first year of operation
[2] Trade-in value after exactly one year of operation (age = 1).

Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 30

Alqahtani

15
 9/2/2021

DP Formulation of the Machine Replacement

Problem
• Stage n: year n = 1, 2, …,10
1, if machine is replaced in year n 
xn   
• Decision variable: 0, otherwise 
• State sn: age of machine at the beginning of year n
• State transformation: stage n+1
stage n sn+1= sn+ 1
xn 0
sn
• Recursive Relationship: 1
sn+1= 1
 f n 1 * (s n  1)
op (s n  1) 
 1.1
, if x n  0
fn(sn,xn)  
13  40  t (s )  f n 1 * (1) , if x  1 fn*(sn) = xmin fn (s n , x n )


r n
1.1
n n  0 ,1

fn(sn, xn) : minimum present value of the total cost for the remaining years n, n+1, …,
10, given that at the beginning of year n the existing machine is sn years old and the
replacement decision is xn
op(s10  1)  t r (s10  1) / 1.1, for x10  0
f10(s10, x10) 
13  40  t r (s10 )  t r (1) / 1.1, for x10  1
Dynamic Programming©Dr. Ammar Y. Introduction to Operations Research 9th Edition 31
Alqahtani

16