MATH3202/7232 Operations Research & Mathematical Planning 2021
Practical 9 – Further DP Examples
These are various DP examples, several of which come from the Winston textbook.
Democracy
A State consists of three cities with populations 1.2 million people, 1.4 million people and 400,000 people. The House of Representatives consists of three representatives. Given proportional representation, City 1 should have d1 = 3(1.2/3) = 1.2 representatives; City 2 should have d2 = 1.4 representatives; and City 3 should have d3 = 0.4 representatives. Since each city must receive an integral number of representatives, this is impossible.
The State has therefore decided to allocate 𝑥! representatives to city 𝑖, where the allocation should minimize the maximum discrepancy between the desired and actual number of representatives received by a city. How many representatives should each city receive?
Altitude Sickness
Joe Cougar needs to drive from A to J. Due to a medical condition he wants to avoid high altitude. The following figure gives the maximum altitude of roads between intermediate cities on the way to J.
What route minimizes the maximum altitude of Joe’s journey?
Advertising
A firm is planning its advertising strategy for a period of four weeks. In each week the sales level will be either High or Low and the firm will receive profits on sales of $800 or $600, respectively.
If the sales were High in the previous week then there is a 60% chance that sales will be High again in the current week if they do not advertise in the current week or 80% if they do advertise. If the sales were Low in the previous week then there is a 20% chance that sales will be High in the current week if they do not advertise in the current week or 60% if they do advertise.
The cost of advertising in one week is $70. An extra cost of $80 is incurred if the level of sales (and thus production) is changed from one week to the next.
What advertising strategy should the firm pursue?