$$ HW$03$

$($lecture $6)($problem $10\mathrm{.}6-5,{10}^{th}$ and ${11}^{th}$ edition$)$ The Makonsel Company

$($a$)$ Please draw the picture.

$($b$)$ Please write down its linear programming model.

$($lecture $6,7)($problem $10\mathrm{.}3-6,{10}^{th}$ and ${11}^{th}$ edition$)$ One of Speedy Airlines' flights.

$($a$)($lecture note $7-4)$ Please use myopic policy to find out the path and its corresponding time.

$($b$)$ Please write down its linear programming model.

$($c$)$ Please use the brute force method to find out the distances of all possible routes by summing the numbers for each route. In this case, there are $7$ possibilities and you need to evaluate each of them.

$($d$)$ Please use the dynamic programming algorithm in Lecture $7\mathrm{.}1$ to solve the problem by hand.

$($lecture $7)$ For the Knapsack Problem

$($a$)$ What are the items we choose and its total value if we use the greedy policy of "the most valuable"?

$($b$)$ Please compare the value in $($a$)$ with the optimal value.

$($c$)$ Please use the recursive computation to compute the value of $F(4,3).$

$($d$)$ Please use the recursive computation to compute the value of $F(4,5).$