Solve each problem by hand using dynamic programming. To get you started on this topic, each problem will tell you

The stages

The states within each stage

For each stage$-$state combination, the decisions you are choosing between

A specific interpretation of the value function for the problem

In future homework assignments and exams, I will ask you determine and state these choices yourself.

Solve each problem by hand using dynamic programming, showing your work. State the optimal solution and its value.

Q$1$: Food Truck Tactics

Joe$$s Grease truck is allowed to operate in three locations $($which we will just call $1,2,$ and $3).$ Joe parks the truck and sells food in a single location for a day and then has the option to move to another location overnight. His moving costs between locations are

Location

$1$

$2$

$3$

$1$

$ $-$

$ $50$

$ $100$

$2$

$ $50$

$ $-$

$ $75$

$3$

$ $100$

$ $75$

$ $-$

Joe estimates his profit from selling food in each location on each day as follows:

Day

Location

$1$

$2$

$3$

$4$

$1$

$ $180$

$ $210$

$ $200$

$ $250$

$2$

$ $170$

$ $205$

$ $230$

$ $240$

$3$

$ $260$

$ $220$

$ $190$

$ $255$

For example, if operates in location $2$ on day $3,$ he expects to make a $$230$ profit selling food.

Joe has already committed to spend day $1$ in location $3,$ and he must be back at location $1$ after day $4($either by already being there on day $4,$ or moving there overnight after day $4).$ Within these constraints, how can Joe maximize his overall profits $($total profit from selling food, minus total moving costs$)$ for days $1$ through $4?$

When solving this problem,

The stages are the four days

At each stage, the state is where the food truck is located that day

In each stage$-$state combination, the decision is where to go next at the end of the day $($or stay in the same place$)$

ft$($i$)$ is the best profit attainable in days t through $4$ if Joe spends day t in location i$.$