Problem 1: Waste Management
City 1 produces 500 tons of waste per day, and city 2 produces 400 tons of waste per day. Waste must be incinerated at incinerator 1 or 2, and each incinerator can process up to 500 tons of waste per day. The cost to incinerate waste is $40/ton at incinerator 1 and $30/ton at incinerator 2. After incineration, the waste should be sent to a disposal landfill. The landfill will receive the 900 tons of incinerated waste per day (i.e., the waste produced will go through an incinerator then go to the landfill). It costs $3 per mile to transport a ton of material. Distances (in miles) between locations are shown in the table below.
As the waste disposal planner, you want to minimize the total cost of shipping the waste produced in cities to disposal landfill after incineration. In this problem, you are asked to formulate the above waste disposal planning problem as a minimum cost flow problem.
a) Express the above problem on a network by drawing nodes, arcs, determining node values, arc costs, arc capacities if any, such that no node has a capacity restriction associated with it and no node has a cost for using the node. (Hint: How would you modify your network so that you do not have capacity constraints on your nodes and costs on your nodes?). Then, mathematically formulate the above problem as a minimum cost flow problem using the network representation that you have.
b) Formulate the problem you had in part a in Excel and solve it using excel solver.
Problem 2: Production planning
Suppose that you are the production manager of a manufacturing company that produces hiking-boots. For the next year, the demand for the hiking-boots pairs in months 1, 2, and 3 are 3000, 2000, and 5000, respectively. Each hiking-boots pair costs $30 to manufacture. At the beginning of month 1, there are 1,500 hiking-boots pairs available. As the production manager, you want to determine how many hiking-boots pairs to produce within each month so that the available inventory at the beginning of a month plus the number of hiking-boots pairs produced within the same month is at least sufficient to satisfy the demand. However, the production facility has manufacturing capacity such that it cannot produce more than 3,500 hiking-boots pairs in any of the months. Also, the ending inventory in months 1 and 2, i.e., the number of hiking-boot pairs remaining unsold at the end of month 1 and month 2, can be sold in the following months (i.e., in month 2 and month 3); but, there is a $8 unit cost of inventory for each pair remaining at the end of a month. There will be no remaining pairs at the end of month 3. As the production manager, you want to find the cost minimizing production plan for the hiking-boots pairs, where the total cost is equal to the production plus inventory costs. That is, you want to determine how many hiking-boots pairs to produce within each month so that you satisfy the demand in each month and minimize the total cost (assume that you can produce fractional number of hiking-boots pairs).
a) Represent the above problem as a network optimization problem. Particularly, you will need to formulate a minimum cost flow problem. Draw the network by defining the nodes, node values, and what they represent; and, the arcs, arc costs, arc capacities (if any), and what they represent. Then, state the problem as a minimum cost flow problem and give the mathematical formulation for this network optimization problem. (Hint: you will have 4 nodes, 1 node is the production facility, which will be the supply node, the other three nodes are the months, which will be demand nodes. Total supply will be equal to the total demand minus the available inventory at the beginning, and the demand at the node for month 1 will be month 1's demand minus the available inventory at the beginning. You will also have 5 arcs in total.)
b) Formulate the problem you had in part a in Excel and solve it using excel solver.
Problem 3: Missouri S&T Evacuation Plan (from Midterm 1 of Spring 2014)
Recently, there was a gas line break in the Missouri S&T campus. Dr. Konur got very scared of the alerts while he was working in his office a lot for his students in the EMGT 365 class. Thus, he decided to come up with an evacuation plan in a case of an emergency. He first downloaded the campus map using the following link: https://www.mst.edu/map/ (Campus Map PDF or Campus Map JPG).
If an emergency happens in the campus, Dr. Konur will immediately leave his office in the Engineering-Management-Building (facility # 5) and he thinks he will be safe if he either reaches to Allgood-Bailey-Stadium (facility # 34) or Rock-Mechanics-and-Explosive-Research-Center (facility # 14). He wants to go to one of these facilities from his office as fast as he can in case of an emergency. However, since in case of an emergency there will be a chaos, he cannot directly go to Allgood-Bailey-Stadium (facility # 34) or Rock-Mechanics-and-Explosive-Research-Center (facility # 14). He has the following possible walks between the facilities:
- From Engineering-Management-Building (facility # 5), he can go to either Chancellor's-Residence (facility # 40) or Kummer-Student-Design-Center (facility # 47).
- From Chancellor's-Residence (facility # 40), he can go to Kummer-Student-Design-Center (facility # 47) or Allgood-Bailey-Stadium (facility # 34) or Miner-Dome-Indoor-Practice-Facility (facility # 48).
- From Kummer-Student-Design-Center (facility # 47), he can go to Allgood-Bailey-Stadium (facility # 34).
- From Miner-Dome-Indoor-Practice-Facility (facility # 48), he can go to Allgood-Bailey-Stadium (facility # 34) or Rock-Mechanics-and-Explosive-Research-Center (facility # 14).
In one of his off-days, Dr. Konur calculated how fast he can go between these facilities. The table below shows the time to reach from a facility to another in seconds.
Dr. Konur wants to find the path with the shortest time to one of the safe facilities, i.e., either Allgood-Bailey-Stadium (facility # 34) or Rock-Mechanics-and-Explosive-Research-Center (facility # 14).
a) Represent Dr. Konur's shortest time path problem on a network by drawing the nodes and explain what they represent, drawing the arcs, and what they represent, arc costs if any, arc capacities if any, node values if any. State the shortest path problem on the network you have created similar to "Find the shortest path from node A to node B on the network".
(Hint: you will need to define a dummy destination node and connect your original destinations to your dummy destination so that you have a single destination). Mathematically formulate the shortest path problem you have defined as a minimum cost flow problem.
After solving his shortest path problem, Dr. Konur realizes that he was being selfish, he was not thinking about the people in the Engineering-Management-Building (facility # 5). Therefore, he decided to find the maximum number of people he can evacuate from Engineering-Management-Building (facility # 5) to the safe facilities. However, there is a limit on the number of people who can simultaneously be evacuated on each possible link defined above. The table below shows the maximum number of people that can reach from a facility to another.
b) Mathematically formulate a maximum-flow problem that will determine the maximum number of people that can travel to the safe facilities, i.e., Allgood-Bailey-Stadium (facility # 34) and Rock-Mechanics-and-Explosive-Research-Center (facility # 14), from Engineering-Management-Building (facility # 5).
Problem 4: Baklava Shipment (from Midterm 1 of Fall 2012)
Dr. Konur plans to start a new business on marketing Baklavas in Rolla, MO. His father has a bakery/pastry store in Istanbul, Turkey and Dr. Konur wants to ship as much baklava as possible from Istanbul to Rolla. However, upon investigation of custom rules, he finds out that international food shipment to U.S. has the following restrictions:
- Any food shipment should arrive in New York City customs
- You cannot ship more than 120,000 baklavas through New York City
- Any food shipment originated from Istanbul should go to Paris or London before entering New York City
- If a shipment stops at Paris, it can be sent to London before being shipped to New York City; however, you cannot ship from London to Paris
Additional to these restrictions, the company that Dr. Konur wants to use for his shipments has the following limitations for baklava shipments:
Dr. Konur knows that the maximum amount of baklavas he can send from New York City to Rolla, using the network between New York City and Rolla, is 150,000. Now he wants to find the maximum amount of baklavas that he can ship from Istanbul to Rolla given the above custom restrictions and the shipping company limitations.
Please answer the following questions based on the problem statement given above.
a) Represent Dr. Konur's problem on a network by defining the nodes, node values (if any), arcs, arc costs (if any), arc capacities (if any) and state it as a maximum-flow problem and mathematically formulate Dr. Konur's maximum-flow problem as a linear model (Hint: You will need to define a dummy node to take care of the limit that can be sent through New York customs).
b) Model the above problem using spreadsheet, i.e., on Excel and find the optimum solution using Excel solver.
About sub-paths of a shortest path
Suppose that you have a network with nodes A, B, C... Z. Furthermore, suppose that you know the shortest path from node A to node Z, denoted as A→Z. You know that this shortest path, i.e., the pat A→Z passes through node K. That is, A→Z=A→K→Z. Will the sub-path A→K be a shortest path from node A to node K? Yes or No? Explain why?