Sets 𝑁 of cities
Data 𝑑! target number of representatives
𝑅 total number of representatives
Stage Which city we are up to.
State Remaining number of representatives.
𝑎” action at stage t is the number of representatives assigned to city t.
𝑉 (𝑠 ) smallest maximum discrepancy when assigning 𝑠 representatives to cities {𝑡, 𝑡 + 1, … , |𝑁|} “””
We want to know 𝑉 (𝑅) $
𝑉(𝑠 )= min max{𝑎𝑏𝑠(𝑎 −𝑑 ),𝑉 (𝑠 −𝑎 )} ” ” %&’!&(! ” ” “)$ ” ”
𝑉|+|9𝑠|+|: = 𝑎𝑏𝑠(𝑎|+| − 𝑠|+|)
Sets 𝑁 of cities
𝐴𝑟𝑐𝑠 where arc 𝑎 is (𝑓𝑟𝑜𝑚’ , 𝑡𝑜’ )
Data h𝑖𝑔h’ highest altitude on arc 𝑎
Stage Which city we are at
State Don’t need state (can leave out one of stage or state)
𝑎” action at stage t is the arc to take
𝑉 () The minimum of the maximum altitude along all the paths from city t to the destination city ”
We want to know 𝑉 () ,
𝑉( )= min
! ‘∈,./( | 0.12″3!
𝑉( )=0 4
max(h𝑖𝑔h,𝑉 ( )) ‘ “1”
Sets Data
Stage State
𝑎”
𝑉 (𝑠 ) “”
𝑇 set of weeks
𝑃𝑟𝑜𝑓𝑖𝑡5 = $800, 𝑃𝑟𝑜𝑓𝑖𝑡6 = $600, 𝐶𝑜𝑠𝑡𝐴𝑑 = −$70, 𝐶𝑜𝑠𝑡𝑆𝑤𝑖𝑡𝑐h = −$80 𝑃 = 0.6, 𝑃 = 0.8, 𝑃 = 0.2, 𝑃 = 0.6
𝑉| 8 | ) $ ( . ) = 0 𝑉 (𝐻)
”
= maxR
𝑉 (𝐿) ”
= maxR
𝐶𝑜𝑠𝑡𝐴𝑑 + 𝑃
($800 + 𝑉 “)$
(𝐻)) + (1 − 𝑃
)($600 + 𝐶𝑜𝑠𝑡𝑆𝑤𝑖𝑡𝑐h + 𝑉
(𝐿)) (𝐿))
𝑎𝑑𝑣𝑒𝑟𝑡𝑖𝑠𝑒 𝑑𝑜𝑛9𝑡 𝑎𝑑𝑣𝑒𝑟𝑡𝑖𝑠𝑒
𝑎𝑑𝑣𝑒𝑟𝑡𝑖𝑠𝑒 𝑑𝑜𝑛9𝑡 𝑎𝑑𝑣𝑒𝑟𝑡𝑖𝑠𝑒
55+ 557
65+ 657
which week we are at
level of sales in the previous week (H or L) advertise (Y or N)
Maximum expected profit from week t onwards
𝑃 55+
($800 + 𝑉 (𝐻)) + (1 − 𝑃 “)$ 55+
557
557
)($600 + 𝐶𝑜𝑠𝑡𝑆𝑤𝑖𝑡𝑐h + 𝑉 “)$
“)$ (𝐿))
𝐶𝑜𝑠𝑡𝐴𝑑 + 𝑃 ($800 + 𝐶𝑜𝑠𝑡𝑆𝑤𝑖𝑡𝑐h + 𝑉 657 “)$
(𝐻)) + (1 − 𝑃 )($600 + 𝑉 657 “)$
𝑃 ($800 + 𝐶𝑜𝑠𝑡𝑆𝑤𝑖𝑡𝑐h + 𝑉 (𝐻)) + (1 − 𝑃 )($600 + 𝑉 (𝐿)) 65+ “)$ 65+ “)$