## Description

## Problem 1 – The Spice Must Flow

House Atreides mines spice at a set of locations M𝑀 on Arrakis and ships it to a set of Houses H𝐻. The cost per ton of producing spice at mine m∈M𝑚∈𝑀 is pm𝑝𝑚. The sand content (in percent) of the spice at mine m∈M𝑚∈𝑀 is am𝑎𝑚, the sulfur content of the spice at mine m∈M𝑚∈𝑀 is sm𝑠𝑚, and the total tons of spice available at mine m∈M𝑚∈𝑀 is um𝑢𝑚. Each House h∈Hℎ∈𝐻 requires dh𝑑ℎ tons of spice. The cost (in Solari) of shipping a ton of spice from mine m∈M𝑚∈𝑀 to House h∈Hℎ∈𝐻 is cmh𝑐𝑚ℎ. It is required that the spice shipped to each House contain at most α𝛼% sand and at most γ𝛾% sulfur in total.

Formulate a linear programming model that minimizes the cost of meeting demands of the Houses. Be sure to clearly define the decision variables. (*Hint*: you will need variables representing the amount of spice shipped from each mine to each house.) Implement this general model in Julia and use it to solve the instance with data that is given along with this homework assignment in the file “spice-data.ipnyb.”

## Problem 2 – Spice Refineries

In the distant future, spice is one of the most valuable commodities that exists. However, it must be properly refined by House Atreides before leaving Arrakis to be sold across the galaxy. In order to refine the spice, House Atreides must operate its many refineries, which require water. In order to increase the output of spice at a refinery, there is a “cost” of 120 gallons of water per ton to operate the refinery at the higher output level. If instead the refinery decreases production level of spice by 1 ton/day, the cost per ton is only 50 gallons of water. (E.g., if current production level is 10 tons and the refinery wants to increase output to 12 tons, the cost is 2 tons * 120 gallons/ton = 240 gallons.)

Demand for spice in the next week is given in the following table:

Day (t𝑡) | Demand (tons) |
---|---|

1 | 40 |

2 | 80 |

3 | 200 |

4 | 250 |

5 | 120 |

6 | 60 |

7 | 30 |

The refinery is currently operating at an output level of 40 tons of spice per day. There are 10 tons of refined spice in inventory right now (day “0”). It costs 20 gallons of water per ton of spice to store up to 80 tons of spice in inventory. To operate a larger storage unit, additional tons (above 80) can be stored at a cost of 50 gallons of water per ton of spice. (Inventory is checked at the end of each day.) If the refinery is unable to meet demand for a given day, House Atreides will be penalized by the Empire and must pay 100 gallons of water per ton of spice short.

Formulate and solve a linear program to determine the optimal production schedule to help House Atreides minimize the amount of water needed to operate the refineries. Give a mathematical formulation of the model as well as your Julia code and solution values.

## Problem 3 – Dice Delivery

You recently discovered you can make some extra money by leasing polyhedral dice to a group of friends playing Dungeons and Dragons. You recently lent 85 dice to 10 different people. Unforuntately, you made some mistakes and gave some people the wrong number of dice. The players have agreed to help with redistributing the dice, as long as they don’t have to drive very far. Suppose that the time to drive between each pair of people is 1.5 times the Euclidean distance to travel between each location given in the table below. The cost of gas is $0.40 per minute of driving. Although it is a bad strategy, also assume that the cost of traveling is per die (so transporting 2 dice a given distance costs 2××1.5××0.4××distance).

Player | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|

X coord | 20 | 18 | 0 | 35 | 2 | 11 | 33 | 2 | 4 | 12 |

Y coord | 8 | 13 | 5 | 7 | 11 | 15 | 22 | 7 | 10 | 0 |

Dice requested | 5 | 7 | 16 | 4 | 7 | 15 | 8 | 10 | 1 | 12 |

Current dice | 15 | 6 | 10 | 1 | 17 | 9 | 9 | 3 | 10 | 5 |

How should the dice be redistributed to minimize total travel cost?

## Problem 4 – Shortest path modeling

A company sells six types of boxes, ranging in volume from 17 to 35 cubic feet. The demand and size (volume) of each box are given in the table below.

Box | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|

Size | 35 | 29 | 28 | 25 | 19 | 17 |

Demand | 40 | 35 | 55 | 70 | 15 | 40 |

The variable cost per unit of producing each box is equal to its size divided by 10. In addition, if any positive number of a particular box is produced, a fixed cost of $10 is incurred. For example, the variable cost to produce one type 1 box is \$35 / 10 = 3.5, and so the total cost to produce 40 type 1 boxes would be $10 for the fixed cost, and 40*3.5=140 for variable costs, for a total cost of \$150. If the company desires, demand for a box may be satisfied by a box of larger size.

Formulate the problem of finding the amount of each box to produce in order to minimize the total cost to meet the customer demands as a shortest path problem. Solve the problem in Julia and report your solution.