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.
Mine Cost ($) Capacity Ash Content Sulfur Content
(tons) (per ton) (per ton)
1 50 1200 .08 .05
2 55 1000 .06 .04
3 62 1400 .04 .03
Table 1: Mine data
1
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.
customer 1 customer 2 customer 3 customer 4
800 + X 600 500 400 + Y
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.
customer 1 customer 2 customer 3 customer 4
Mine 1 4 6 8 12
Mine 2 9 6 7 11
Mine 3 8 12 3 5
Table 3: Transportation costs ($ per ton)
Your Task
1. Formulate a linear program that minimizes the cost of meeting customer demands. (10%)
2. 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. (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 resolving the LP. (10%)
2
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.
customer 1 customer 2 customer 3 customer 4
Processing Unit 3 5 7 11
Table 4: Transportation costs ($ per ton)
Your Task
1. Formulate a linear program that minimizes the cost of meeting customer 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
2× tons of
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
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.
customer 1 customer 2 customer 3 customer 4
Processing Unit A 3 5 7 11
Processing Unit B 2 4 5 9
Processing Unit C 4 6 9 12
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%)