MSCI534 Coursework 2018-19: Deliver the Coal
General Information
For this exercise you can use any optimisation package you want, as long as it is capable of solving both LPs and MILPs, and providing sensitivity analysis for LPs. I recommend using LINDO, as it is free and easy to use.
Your report should take the form of a Word document (or PDF if you prefer). The main body of the report should be no longer than 10 pages in length. (If you wish, you can put detailed solver output in an appendix.) The report should be submitted online via MOODLE by 10am on Tuesday 12th March.
The exercise is to be done individually. Late work or evidence of collusion will be penalised in the manner specified in the department¡¯s teaching code of practice.
In the following problem you should replace X by the number between 0 and 99 formed by the 5th and 6th digit of your library card number, and Y by the number between 0 and 99 formed by the 7th and 8th digit of your library card number. For example, if your library card number is 09123456, then X = 34 and Y = 56.
Part I (worth 40%)
Coalco produces coal at three mines and ships it to four customers. The cost per ton of producing coal, and the production capacity (in tons) for each mine are given in Table 1. Coalco should satisfy the demands of the four customers.
Table 1: Mine data
1
Mine
Cost ($)
Capacity (tons)
Ash Content (per ton)
Sulfur Content (per ton)
1 2 3
50 55 62
1200
1000
1400
.08 .06 .04
.05 .04 .03
The cost per tone of producing the coal, the ash and sulfur content (per ton) of the coal, and the production capacity (in tons) for each mine are given in table 1. The demand of each customer is given in Table 2. It is required that the total amount of coal shipped to all four customers contains at most 5% ash and at most 4% sulfur. In other words, if Ci denotes the tons that are shipped to customer i, i = 1,…,4, then we require that C1 +C2 +C3 +C4 contains at most 5% ash and 4% sulfur.
Table 2: Customer demands in tons
The cost (in $) of shipping a ton of coal from a mine to each customer is given in Table 3.
Table 3: Transportation costs ($ per ton)
Your Task
1. Formulate a linear program that minimizes the cost of meeting cus- tomer demands. (10%)
2. Solve the linear program using computer software and specify an op- timal way to satisfy customer demands. Include a copy of the output from the software as part of your answer. (10%)
3. If the transportation cost between mine 1 and customer 3 drops from 8 to 5, will the optimal solution, optimal basis and optimal cost change? Carefully justify your answer based on the solver outputs. Note, that you should answer this question without resolving the LP. (10%)
4. Coalco can achieve a minor increase at the production capacity of its mines. However, this will come at a cost of $2 per ton while the maximum total increase that can be achieved is 22 tons. Should Coalco increase its production capacity? If yes, specify by how much and explain how to optimally distribute the additional capacity among the three mines. Note, that you should answer this question without re- solving the LP. (10%)
2
customer 1
customer 2
customer 3
customer 4
800 + X
600
500
400 + Y
customer 1
customer 2
customer 3
customer 4
Mine 1 Mine 2 Mine 3
4 9 8
6
6 12
8 7 3
12 11 5
Part II (worth 30%)
Consider Part I of the case study and assume that Coalco can also use a processing unit to reduce the ash and sulfur content of the coal extracted from mine 1. The transportation cost of shipping one ton of coal from mine 1 to the processing unit is $2 and the transportation cost of shipping one ton of coal from the processing unit to each of the four customers is given in table 4. The unit can process at most half of the coal extracted from mine 1, while the processing cost is $10 per ton. After processing, the coal will contain 50% less ash and sulfur.
Table 4: Transportation costs ($ per ton)
Your Task
1. Formulate a linear program that minimizes the cost of meeting cus- tomer demands. Solve the linear program using computer software and specify an optimal way to satisfy customer demands. Include a copy of the output from the software as part of your answer. (15%)
2. Based on the description of Part II, the processing unit can accept at
most half of the tons extracted from mine 1. Assume now that the
processing unit can accept further quantities but at a premium cost of
$1 per extra ton. More precisely, if at most half of the tons extracted
from mine 1 are sent to the processing unit there won¡¯t be any extra
charge. However, any extra ton of coal above the quota ( 1¡Á tons of 2
coal extracted from mine 1) that is forwarded to the processing unit is charged a premium of $1 per ton. What is the relationship between the total cost and the additional capacity of the processing unit? In other words, by how much will the total cost increase or decrease when additional capacity is being used? (15%)
Part III (worth 30%)
Consider Part I of the case study and assume that Coalco can use one of three different processing units which we call A, B and C. Each unit can process coal from one mine only. Moreover, the coal extracted from mine 1, 2 and 3 can be either forwarded directly to any customer or it can be sent to the processing unit A, B and C respectively, and from there to any customer. Note that A, B and C can process up to half the quantity of
3
customer 1
customer 2
customer 3
customer 4
Processing Unit
3
5
7
11
coal extracted from mine 1, 2 and 3 respectively. The transportation costs between mine 1 and unit A, mine 2 and unit B, mine 3 and unit C, is $2, $3 and $4 per ton respectively. The transportation costs between processing units and customers are given in table 5. After processing the coal at any of the three units the ash and sulfur content will be 50% lower. The processing cost is $10, $11 and $13 per ton for A, B and C respectively. Coalco can use at most one of A, B and C.
Table 5: Transportation costs ($ per ton)
Your Task
1. Formulate a mixed-integer linear program (MILP) that minimizes the cost of meeting customer demands. (20%)
2. Solve the MIP using computer software and specify an optimal way to satisfy customer demands. Include a copy of the output from the software as part of your answer, and comment on it. (10%)
customer 1
customer 2
customer 3
customer 4
Processing Unit A Processing Unit B Processing Unit C
3 2 4
5 4 6
7 5 9
11 9 12
4