Problem 1
The following table specifies the weights and values per unit of five different products held in storage. The quantity of each product is unlimited.
|
Product ( i ) Weight per unit ( w i ) Value per unit ( v i ) |
||
|
1 |
7 |
9 |
|
2 |
5 |
4 |
|
3 |
4 |
3 |
|
4 |
3 |
2 |
|
5 |
1 |
0.5 |
A plane with a weight capacity of 13 is to be used, for one trip only, to transport the products. We would like to know how many units of each product should be loaded onto the plane to maximize the value of goods shipped.
Use dynamic programming to find the optimal solution. Please provide the following details (a) describe clearly the stages, (b) states, (c) allowable decisions at each state in each stage, etc. Finally, please state what the optimal quantity of each product to be loaded to the plane is.
Problem 2
Suppose (by some miracle) that you have access to a particular company’s stock prices over the next 10 days, and they are as follows:
|
Day Price |
|
|
1 |
7 |
|
2 |
3 |
|
3 |
2 |
|
4 |
8 |
|
5 |
11 |
|
6 |
9 |
|
7 |
5 |
|
8 |
10 |
|
9 |
6 |
|
10 |
4 |
It is the start of Day 1, and you do not own any shares. At the start of each day, you can either purchase one share or sell any shares that you have on hand (as many as you like, but not more than you own), or do nothing. Suppose that shares are worthless after Day 10 (the company goes bankrupt on Day 11). Your goal is to maximize profit over the 10-day period.
Please solve the above problem by formulating a dynamic program following the steps below
a) What are the states and stages associated with this problem?
b) What is the set of feasible actions associated with stage n and state s ? How much is gained/lost by taking each action?
(Hint: It may be easier to let your action be the number of shares you have at the end of day n , rather than the number of shares you buy or sell on that day)
c) How can the optimization function be interpreted here? That is, given a stage n and a state s , what is fn* (s)?
d) Formulate the above problem as a dynamic program and solve it using GAMS/Python. Write the optimal sequence of actions below, and the profit that these yields