• What are thestagesin this problem?
• What defines thestateswithin each stage?
• For each stage-state combination, what are thedecisionsyou are choosing between?

solve the problem by hand using dynamic programming.State the optimal solution and its value.

Q

It is currently Sunday, and a sales representative who lives in Bloomington and must be in Indianapolis by Thursday.On each of Monday, Tuesday, and Wednesday, he can sell his wares in Indianapolis, Bloomington, or Chicago.From past experience, he believes that he can earn $12 from spending a day in Indianapolis, $16 from spending the day in Bloomington, and $17 from spending a day in Chicago.The costs for traveling between cities are shown in the table below.How should he plan his travels from now through Thursday, in order to maximize his profit?His profit is the total earnings compiled over the three days, minus the total travel costs incurred.

To

From Indianapolis Bloomington Chicago

Indianapolis $0 $5 $2

Bloomington $5 $0 $7

Chicago $2 $7 $0

For consistency, please use the following numbering scheme for the days:

Day 1Sunday, when the sales rep cannot work and has to be in Bloomington

Day 2Monday

Day 3Tuesday

Day 4Wednesday

Day 5Thursday, when the sales representative must be in Indianapolis.

Assume travel occurs in the evening (after working in the case of days 2 through 4).If the sales representative does not spend Wednesday (day 4) in Indianapolis, he will travel to Indianapolis that evening.In this problem, the objective value is total sales income minus total travel expenses.