The University of Sydney
School of Mathematics and Statistics
Assignment
MATH2070/2970: Optimisation and Financial Mathematics Semester 2, 2022
Lecturers: Jie Yen Fan
Due on Friday 9th September at 11:59pm via Canvas
MATH2070: Do all questions except Question 5.
MATH2970: Do all questions except Question 4.
Please show your working. In particular,
– if you introduce new variables, define them clearly;
– at each iteration of simplex algorithm, indicate which variables enter and leave the
basis.
Please submit a single pdf file.
Please make sure your submission is clear and legible.
In the case of late submission, for each day late (up to a maximum of 10 days), you will
be deducted 5% of the maximum marks. Make sure you submit in time; a submission
on Saturday the 10th at 12:00am will incur an automatic deduction of 5%. It is your
responsibility to check that your submission was successful.
? Academic dishonesty is taken very seriously. You may discuss the questions with your
peers, however, you should write your solutions in your own words. Do not copy from each
other.
Copyright? 2022 The University of Sydney 1
1. Consider the following linear programming problem:
Maximise Z = 4x1 ? 4x2
subject to ? 2x1 + 2x2 ≤ 4
2x1 ? 2x2 ≤ 6
? x1 + 4x2 ≥ ?2
x1 ≥ 0, x2 ≥ 0.
Solve the problem using simplex method (algebraically). If there are more than one optimal
solution, give a complete characterisation to the solutions.
2. Consider the following linear programming problem:
Maximise Z = 3x1 + x2
subject to x1 ? x2 ≤ ?1
? x1 ? x2 ≤ ?3
2x1 + x2 ≤ 4
x1 ≥ 0, x2 ≥ 0.
(a) Solve the problem using two-phase simplex method.
(b) Solve the problem graphically.
3. Linear programming was already used in the oil industry in the 1950’s to work out the best
operating plan. Real-life problems that oil industry tries to solve are complex and interwoven.
Here we consider a simple problem.
Suppose there are two oil fields, A and B. Oil field A produces crude oil at the cost of $80 per
barrel and oil field B produces crude oil at $90 per barrel. A refinery then process the crude
oil to produce diesel, gasoline and jet fuel. Each barrel of the crude from A can be refined to
produce 20 gallons of diesel, 15 gallons of gasoline, and 12 gallons of jet fuel. Each barrel of
the crude from B can produce 15 gallons of each diesel, gasoline, and jet fuel. The refinery has
to produce 160 gallons of diesel, 100 gallons of gasoline, and 180 gallons of jet fuel to meet the
demand.
(a) Formulate an LP problem to determine how many barrels of crude from each oil field
should the oil refinery use to minimize the cost while meeting the demand.
(b) Obtain the dual to the problem in (a).
(c) Give solution to the oil refinery’s question by solving the dual problem.
4. (MATH2070 only.) Consider the following optimization problem
Minimise Z = ?2x1 + x2
subject to x1 + x2 ≤ 6
|x1 ? x2| ≤ 2
x1 ≥ 0, x2 ≥ 0.
(a) Is the problem an LP problem in its current form? Explain your answer.
(b) Sketch the feasible region.
(c) Convert the optimization problem into a standard LP problem. Then, solve the problem
using simplex method (algebraically).
[Hint: |x| ≤ b is equivalent to ?b ≤ x ≤ b.]
2
5. (MATH2970 only.)
(a) Consider the following optimization problem:
Minimise
n∑
i=1
|xi ? ci|
subject to Ax = b
x ≥ 0,
where ci’s are given values.
Convert this problem into an equivalent LP problem.
(b) Consider a set of n lines in R2, given by aix1 + bix2 + ci = 0, i = 1, . . . , n. Formulate an
LP problem to find a point x ∈ R2 that minimizes the sum of the distances between x
and each line.
(c) Consider the following three lines in R2:
4x1 + 3x2 ? 12 = 0,
3x1 ? 4x2 + 6 = 0,
4x1 ? 3x2 + 24 = 0.
What is the point x ≥ 0 in R2 that minimizes the sum of the distances between x and
each line? Formulate an LP problem to answer this question, and write it in standard
form.
Note: you are not required to solve the LP that you formulated.