MAST20018 – Introduction to Discrete Mathematics and Operations Research
Assignment 3
1. A company produces two kinds of products (A and B) in a single machine. The machine
operates for 20h every day. The production of each item A consumes 3h of the machine time
while the production of each item B consumes 5h of the machine time. You want to plan
the operations for the next 3 days. The demand of each product i = {A,B} for each day
t = {1, 2, 3} is given by dit. You currently have 1 unit of product A in inventory and 2 units
of product B in inventory. The production cost of each product varies according to the day
due to changes in electricity price. The cost to produce item i = {A,B} on day t = {1, 2, 3} is
given by cit. You can assume that a product left unfinished on a day can be completed on the
following day.
a) Formulate a linear programming problem that minimises production cost while meeting the
demand. Clearly define the variables you use and briefly explain the meaning of each constraint.
b) What would change in your model if there is a storage cost of hit for each product of type
i = {A,B} in inventory at the end of day t = {1, 2, 3}?
c) What would change in your model if the products can not be left unfinished on any given
day?
2. The shaded area in the figure below depicts the feasible region of a linear programming model
with 2 variables. Note that the feasible region is unbounded.
a) Write the constraints of the problem.
b) Consider the objective function f(x) = max ax1 + bx2. For which values of a and b will the
problem have two extreme points as optimal solutions?
1
MAST20018 – Introduction to Discrete Mathematics and Operations Research
3. When plotting data from a repeated experiment in order to test the validity of a supposed linear
relationship between two variables x1 and x2, the data points are usually not located exactly
on a straight line. There are several ways to find the best fitting line through the plotted
points. One of these is the method of least absolute deviation regression. In least absolute
deviation regression it is assumed that the exact underlying relationship is a straight line, say
x2 = αx1 + β. Let
{[
a1 b1
]
, . . . ,
[
an bn
]}
be the data set. For each i = 1, . . . , n, the
absolute error, ri, is defined by ri = ai? biα? β. The problem is to determine values of α and
β such that the sum of the absolute errors,
∑n
i=1 |ri|, is as small as possible.
a) Formulate the method of least absolute deviation regression as an optimisation model. In
this answer, you can use the function abs(x) which computes the absolute value of a variable
x ∈ R.
b) Using the function abs(x) makes your model in a) non-linear. Linearise your model such
that your optimisation problem is now a linear programming model.
Hint: The absolute value of a variable x ∈ R can be computed with two non-negative variables
x+ ≥ 0, x? ≥ 0 as follows:
abs(x) = x+ ? x?
as long as you know that at least one of the variables is set at zero and x+ + x? = x.