# 辅导MATH2070、C++,java语言编程辅导

- 首页 >> Algorithm 算法 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.

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.