Case 1

Gas tank capacity: 15 Gallons

Initially no gas in the tank

	ci: Gas price per gallon at station Si	gi: Number of gallons needed to go from Si to Si+1
1	$3	1
2	$1	5
3	$6	2
4	$2	13
Destination

In this case, the optimal refueling policy is <Y1=1, Y2=15, Y3=0, Y4=5>. In other words, refill the vehicle with 1, 15, and 5 gallons in stations S1, S2, and S4 respectively, ending in a total fuel cost of $3*1 + $1*15 + $6*0 + $2*5=$28.

Station Si	Number of gallons when arriving at Si	Yi: gallon purchased at station Si	Number of gallons when leaving Si
1	0	1	1
2	0	15	15
3	10	0	10
4	8	5	13
Destination	0

Case 2

Gas tank capacity: 15 Gallons

Initially no gas in the tank

Station Si	ci: Gas price per gallon at station Si	gi: Number of gallons needed to go from Si to Si+1
1	$4	7
2	$5	5
3	$3	9
4	$6	13
5	$2	12
6	$1	3
Destination

In this case, what is the optimal refueling policy (i.e. how much should we refill the vehicle in each of the statins to minimize the refueling cost)? What is the minimal refueling cost?

Station Si	Number of gallons when arriving at Si	Yi: gallon purchased at station Si	Number of gallons when leaving Si
1
2
3
4
5
6
Destination