Fundamentals of Optimization MATH11111
Fundamentals of Optimization
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Fundamentals of Optimization
MATH11111
1300-1500 † *
† All students: you have an additional 1 hour to assemble and submit your PDF.
Final submission deadline: 16:00.
* Students with a Schedule of Adjustment: You are entitled to a further fixed
additional 1 hour for this remote examination.
Final submission deadline: 17:00
Attempt all questions
Important instructions
1. Start each question on a new sheet of paper.
2. Number your sheets of paper to help you scan them in order.
3. Only write on one side of each piece of paper.
4. If you have rough work to do, simply include it within your overall answer – put
brackets at the start and end of it if you want to highlight that it is rough work.
MATH11111 Fundamentals of Optimization 1
(1) Puzzle (8 marks)
Consider the following linear programming problem in standard form:
min 2x1 − 3x2 − 3x3 + c4 x4
s.t. 2x1 + x2 + 2x3 + 4x4 = b1
2x1 + 3x2 + 6x3 + 8x4 = b2
x1 , x2 , x3 , x4 ≥ 0
Below is the final dictionary with the optimal solution:
z = 4 + 3x3 + 5x4
x1 = G + d13 x3 − x4
x2 = 2 + d23 x3 − 2x4
Determine the unknown values for c4, b1, b2, G, d13, and d23. Justify your solution.
Recall that, for an invertible matrix M ∈ R2×2 given by
M =
[
a b
c d
]
,
its inverse is
M−1 =
1
det(M)
[
d −b
−c a
]
.
[Please turn over]
MATH11111 Fundamentals of Optimization 2
(2) Duality & Sensitivity Analysis (12 marks & 40 marks)
(a) Determine an optimal solution x∗ ∈ R4 and the optimal value z∗ ∈ R for the
following linear programming problem using the graphical method:
(P ) min 4x1 + 11x2 + 5x3 + 4x4
s.t. −x1 + x2 + x3 + x4 = −3
x1 + 2x2 − 2x4 = 9
x1 , x2 , x3 , x4 ≥ 0
Justify your solution. [12 marks]
(b) Consider the following linear programming problem:
min − 2x1 + 3x2 − 3x3 + 2x4 − 4x5
s.t. 2x1 + x2 + 3x3 + x4 + 2x5 = 10
3x1 + 2x2 + x3 + 2x5 = 18
x1 , x2 , x3 , x4 , x5 ≥ 0
The optimal dictionary is given below:
z = 14 + 28x3 + 15x4 + 6x5
x1 = 2 − 5x3 − 2x4 − 2x5
x2 = 6 + 7x3 + 3x4 + 2x5
[Please turn over]
MATH11111 Fundamentals of Optimization 3
Instructions:
• For the primal simplex, if there is more than one nonbasic variable with a
negative reduced cost, choose the one with the most negative reduced cost
as the entering variable. In the minimum ratio test, if there is a tie between
two or more rows, choose the row whose basic variable has the smallest
index to determine the leaving variable.
• For the dual simplex, if there is more than one negative basic variable,
choose the one with the most negative value as the leaving variable and
break ties in favour of the basic variable with the smallest index. In the
minimum ratio test, if there is a tie between two or more nonbasic variables,
then break the tie in favour of the nonbasic variable with the smallest index.
Questions:
(i) By how much can we decrease the value of b1 = 10 such that current
dictionary remains optimal? Justify your solution. [6 marks]
(ii) If we increase the value of b1 = 10 by δ = 4, does the current dictionary
remain optimal? Justify your solution.
If not, then perform one iteration of the appropriate simplex method
and derive a new dictionary with its corresponding solution. For the new
dictionary, write down the index sets B and N , values of all variables,
reduced costs of all variables, and the current objective function value.
State whether the corresponding solution is optimal or not. State whether
it is primal feasible or dual feasible or both. Justify your solution.
[14 marks]
(iii) By how much can you decrease the value of c4 = 2 such that the current
dictionary remains optimal? Justify your solution. [3 marks]
(iv) If we increase the value of c4 = 2 by δ = 4, does the current dictionary
remain optimal? Justify your solution.
If not, then perform one iteration of the appropriate simplex method
and derive a new dictionary with its corresponding solution. For the new
dictionary, write down the index sets B and N , values of all variables,
reduced costs of all variables, and the current objective function value.
State whether the corresponding solution is optimal or not. State whether
it is primal feasible or dual feasible or both. Justify your solution.
[2 marks]
(v) If we decrease the value of c2 = 3 by δ = 3, does the current dictionary
remain optimal? Justify your solution.
If not, then perform one iteration of the appropriate simplex method
and derive a new dictionary with its corresponding solution. For the new
dictionary, write down the index sets B and N , values of all variables,
reduced costs of all variables, and the current objective function value.
State whether the corresponding solution is optimal or not. State whether
it is primal feasible or dual feasible or both. Justify your solution.
[9 marks]
(vi) Consider the variable x5. If we change A
5 from [2, 2]T to [2, 2]T + δ[1, 2]T ,
where δ ∈ R, find the range of δ for which the current dictionary remains
optimal. Justify your solution. [6 marks]
[Please turn over]
MATH11111 Fundamentals of Optimization 4
(3) Duality (14 marks)
Consider the following linear programming problem in standard form:
(P) min{cTx : Ax = b, x ≥ 0},
where A ∈ Rm×n, b ∈ Rm, and c ∈ Rn are the parameters, x ∈ Rn is the vector of
decision variables, and 0 ∈ Rn denotes the vector of all zeroes.
Assume that (P) has a finite optimal value. Suppose that the right-hand side vector
b ∈ Rm is replaced by b′ ∈ Rm, where b′ 6= b, i.e., the new linear programming
problem is given by
(P′) min{cTx : Ax = b′, x ≥ 0}.
Prove the following statement:
The linear programming problem (P′) is either infeasible or has a finite optimal
value.
[Please turn over]
MATH11111 Fundamentals of Optimization 5
(4) Duality & Convexity (26 marks)
Consider the following polyhedron:
P = {x ∈ Rn : Ax = b, x ≥ 0},
where A ∈ Rm×n, b ∈ Rm, and c ∈ Rn, and 0 ∈ Rn denotes the vector of all zeroes.
Assume that P 6= ∅.
Consider the following linear programming problem parametrized by the cost vector
c ∈ Rn:
(P(c)) min{cTx : x ∈ P},
i.e., for each vector c ∈ Rn, the corresponding linear programming problem is denoted
by (P(c)).
Let f : Rn → R ∪ {−∞} be a function defined as follows. For each c ∈ Rn,
f(c) denotes the optimal value of the linear programming problem (P(c)). For a
given vector c ∈ Rn, note that we define f(c) = −∞ if the corresponding linear
programming problem (P(c)) is unbounded.
(a) Show that there exists a vector cˆ ∈ Rn such that f(cˆ) is finite (i.e., the
corresponding linear programming problem (P(cˆ)) has a finite optimal value).
[6 marks]
(b) Prove that f is a concave function. (Hint: Consider how the dual problem
changes as a function of c and think of using appropriate duality relations.)