2-504-09 Lecture Notes - Lecture 3: Prentice Hall, General Algebraic Modeling System, Cplex
2-604-15A Lecture notes
1
2. Introduction to linear programming
This chapter provides an introduction to linear programming. Specifically, a first
linear model for decision support is built in Section 2.1. Section 2.2 presents the
general shape of a mathematical programming problem. Section 2.3 proposes
some modelling tips, and finally Section 2.4 presents different methods to solve
linear problems.
2.1 The Sichuan Mining case
Sichuan Mining owns two mines in Panzhihua, an area particularly rich in
minerals located in the south of the Sichuan Province (China). Each mine
produces three different grades of coal (according to the carbon content): high
(anthracite coal), medium (bituminous coal), and low (lignite coal). Note that
each mine operates at most 16 hours a day.
During each hour of operations, mine 1 produces 6 tons of high-grade coal, 2
tons of medium-grade coal, and 4 tons of low-grade coal. Mine 2 produces 2
tons of high-grade coal, 2 tons of medium-grade coal, and 8 tons of low-grade
coal per hour of operations. It costs 1,400 Yuan per hour to operate mine 1 and
1,120 Yuan per hour to operate mine 2.
To fulfill its contractual obligations to an industrial customer located in
Chengdu, the capital of the Sichuan Province, Sichuan Mining has to supply at
least 50 tons of high-grade coal, 25 tons of medium-grade coal, and 70 tons of
low-grade coal per day.
How many hours per day should each mine be operated in order for Sichuan
Mining to supply its customer in the least costly way? Propose a mathematical
model to guide Sichuan Mining in its decision making.
Step 1: Analysis
In order to build a mathematical model, it is first necessary to carefully analyze
the problem that Sichuan Mining is facing.
Which data should be considered?
• The number of hours per day during which each mine can operate;
• the hourly output for each category of coal in each mine;
• the hourly operation cost for each mine;
• the quantity of coal to supply.
find more resources at oneclass.com
find more resources at oneclass.com
2-604-15A Lecture notes
2
Which decisions should be taken?
As explained previously, we need to determine the number of hours per day
during which both mines (mine 1 and mine 2) need to be operated.
For example, each mine could be operated during its maximal daily capacity,
that is 16 hours a day. Is that a good decision?
How can we evaluate the quality of the decisions?
As stated previously, we wish to find the decisions that yield the lowest possible
costs. Thus, the total production costs evaluate the quality of the decisions.
By considering all of the above (number of daily hours during which each mine
is operated to minimize total production cost), the obvious solution is not to
operate mines (fix the number of hours of operation at zero). Indeed, the total
production cost is also zero! In this case, because we are not producing any coal,
Sichuan Mining cannot meet its contractual commitments. Thus, it is necessary
to consider the entire context in which the decisions must be taken.
In which context are the decisions taken?
Sichuan Mining has two types of constraints. First, each mine can be operated a
maximum of 16 hours a day. Second, the coal demand must be satisfied; that is,
during one day of operation, both mines must produce a sufficient quantity of
high-grade coal (at least 50 tons), of medium-grade coal (at least 25 tons), and of
low-grade coal (at least 70 tons).
Step 2: Build a verbal model
To summarize our analysis, we can state the following problem:
1. determine the number of hours per day to operate mines 1 and 2;
2. in order to minimize total production cost;
3. while respecting: i) the minimal demands for each category of coal and ii)
the maximal number of hours per day during which each mine can operate.
Step 3: Build a mathematical model
The third and final step to build our mathematical model is to ‘translate’ our
verbal model (in English) into a mathematical model.
As with any translation, we need a ‘dictionary’ which will give us a list of
symbols to move from one model to another. We will match these symbols to
our decisions:
find more resources at oneclass.com
find more resources at oneclass.com
2-604-15A Lecture notes
3
• let x1 represent the number of hours per day during which mine 1 is
operated;
• and let x2 represent the number of hours per day during which mine 2 is
operated.
These symbols, representing the decisions, correspond to the (decision)
variables of the model. The latter will be written with these symbols.
The decisions must be taken in order to minimize total production cost. The
latter is computed by multiplying the number of hours during which each mine is
operated with its hourly cost. Mine 1 costs 1,400 Yuan per hour to operate, thus
a total of 1,400 × x1 Yuan per day (denoted by 1400 x1). Similarly, mine 2 costs
1,120 Yuan per hour to operate, for a total of 1120 x2 Yuan per day. The total
production cost for both mines (in Yuan per day) that we wish to minimize is
therefore computed as 1400 x1 + 1120 x2. This can be written with a
mathematical formulation as follows:
Min 1400 x1 + 1120 x2.
This function corresponds to the criterion used to assess the quality of the
decisions. We call this criterion the objective function of the model.
We then have to take into account the context in which decisions must be taken.
First, we must produce enough coal for each category. This can be expressed as
follows:
Daily production for a given quality ≥ demand for this quality.
The daily production is the sum of the output of the two mines. For each mine,
the latter amount is calculated by multiplying the hourly production (in tons per
hour) by the number of hours in operation. Thus, in one day, mine 1 produces
6 × x1 tons of high-grade coal. Similarly, mine 2 produces 2 × x2 tons of high-
quality coal. Because the daily demand for high-grade coal is at least 50 tons, the
equation describing the high-grade coal production constraint can be written as:
6 x1 + 2 x2 ≥ 50.
Similarly, we must ensure that the daily output of medium-grade coal is at least
25 tons. By following a similar approach, the constraint for the demand for
medium-grade coal can be written as follows:
2 x1 + 2 x2 ≥ 25,
where both mines produce 2 (tons per hour) of medium-grade coal and the
minimal daily demand for medium-grade coal is 25 (tons).
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
This chapter provides an introduction to linear programming. Specifically, a first linear model for decision support is built in section 2. 1. Section 2. 2 presents the general shape of a mathematical programming problem. Section 2. 3 proposes some modelling tips, and finally section 2. 4 presents different methods to solve linear problems. Sichuan mining owns two mines in panzhihua, an area particularly rich in minerals located in the south of the sichuan province (china). Each mine produces three different grades of coal (according to the carbon content): high (anthracite coal), medium (bituminous coal), and low (lignite coal). Note that each mine operates at most 16 hours a day. During each hour of operations, mine 1 produces 6 tons of high-grade coal, 2 tons of medium-grade coal, and 4 tons of low-grade coal. Mine 2 produces 2 tons of high-grade coal, 2 tons of medium-grade coal, and 8 tons of low-grade coal per hour of operations.
