# MAST20018辅导、辅导Python/C++程序

- 首页 >> Web 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.

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.