The University of Western Ontario
FM3817 - Optimization
Midterm Exam A
February 26, 2021
9:30am-10:30am
Print Your Name
Student No.
SIGNATURE
INSTRUCTOR: Dr. Hristo S. Sendov
INSTRUCTIONS:
(1) Write your name and id number in the space provided above.
(2) Write your name at the top of each page.
(3) Sign your exam.
(4) There are 8 pages including this cover page. Make sure that you have a complete copy.
(5) Answer each of the seven problems
(6) If you already have the solutions to questions 1 & 2 you do not have to re-write them. Just scan
your solutions.
(7) No calculators are allowed!
Problem Value Mark Awarded
1 10
2 10
3 12
4 10
5 10
6 8
7 10
Total 70
AM3817 NAME: 2
1. [10pts] Suppose the feasible region of an LP problem is bounded. Show that one of the extreme points
of the feasible region is an optimal solution. (Suppose for simplicity that the LP problem is in standard
equality form.)
Solution: The feasible region has finitely many extreme points say e1, e2, . . . , ek. Let e
∗ be the extreme
point with the largest objective value z(e∗) = cT e∗ = max{cT e1, cT e2, . . . , cT ek}. Let x ∈ FR. By the
Caratheodory Theorem, x =
∑n+1
j=1 αijeij , where αij ∈ [0, 1],
∑n+1
j=1 αij = 1. and ei1 , . . . , ein+1 are some
n+ 1 of all k extreme points. Then
z(x) = cTx =
n+1∑
j=1
αijc
T eij ≤
n+1∑
j=1
αijc
T e∗ = cT e∗
n+1∑
j=1
αij = c
T e∗ = z(e∗).
Hence, e∗ is an optimal solution.
AM3817 NAME: 3
2. [10pts] Find the points on the curve x41 + 3x1x2 + x
4
2 = 2 that are farthest from the origin.
Solution: We need to find the maximizer of x21 + x
2
2 subject to x
4
1 + 3x1x2 + x
4
2 = 2. The Lagrangian
is
L(x1, x2, λ) = x
2
1 + x
2
2 − λ(x41 + 3x1x2 + x42 − 2).
Then we have
∇L(x1, x2, λ) =
 2x1 − λ(4x31 + 3x2)2x2 − λ(4x32 + 3x1)
−(x41 + 3x1x2 + x42 − 2)
 .
Need to solve the system of equation ∇L(x1, x2, λ) = 0.
Using the constraint, one may verify that 4x31 + 3x2 6= 0 and 4x32 + 3x1 6= 0. Then by the first two
equations, we have
λ =
2x1
4x31 + 3x2
=
2x2
4x32 + 3x1
,
which can be simplified to
(x21 − x22)(4x1x2 − 3) = 0.
By the constraint, we must have 4x1x2 − 3 6= 0. So, either x1 = x2 or x1 = −x2. If x1 = x2, the third
equation becomes 2x42 + 3x
2
2 − 2 = 0. Hence, x∗2 = ±
√
2/2 with corresponding solutions
(x∗1, x
∗
2, λ
∗) =
(
±
√
2
2
,±
√
2
2
,
2
5
)
.
If x1 = −x2, the third equation becomes 2x42 − 3x22 − 2 = 0. Hence, x∗2 = ±
√
2 with corresponding
solutions
(x∗1, x
∗
2, λ
∗) =
(√
2,−
√
2,
2
5
)
and (x∗1, x
∗
2, λ
∗) =
(
−
√
2,
√
2,
2
5
)
.
Evaluate the objective function at these points:
f
(
±
√
2
2
,±
√
2
2
)
= 1, f(−
√
2,
√
2) = f(
√
2,−
√
2) = 4.
Since the feasible region is a closed and bounded curve, (−√2,√2) and (√2,−√2) are the points on
the curve that are farthest from the origin.
Asides: It is clear that the feasible region is a close set. However it is not so obvious that it is bounded.
By the condition, we have
2 = x41 + 3x1x2 + x
4
2 ≥ 2(x1x2)2 + 3x1x2.
Then we must have −12 ≤ x1x2 ≤ 2. Therefore
‖x‖4 = (x21 + x22)2 = x41 + x42 + 2x21x22 = 2(x1x2)2 − 3x1x2 + 2 ≤
1
2
+
3
2
+ 2 = 4.
Hence, the feasible region is bounded.
AM3817 NAME: 4
3. [12pts] Consider the following LP problem in standard equality form:
max z = cTx
s.t. Ax = b
x ≥ 0.
where A is an m× n matrix, x, c ∈ Rn and b ∈ Rm.
(1) What are the four important characteristics of the standard equality form?
1) It is a maximization problem
2) the objective function has no constant term
3) all functional constraints are all equalities
4) all decision variables are required to be non-negative
(2) State the definition of a basis;
A basis of the system of m equations Ax = b with n unknowns is an m-element subset B of
{1, ..., n} such that the set of column vectors {Aj | j ∈ B} is linearly independent
(3) State the definition of a basic solution;
A basic solution of a system of linear equations Ax = b is the unique solution of the system[
Ax = b
xj = 0 for all j 6∈ B (1)
for some basis B
(4) State the definition of a convex set;
A set C ⊂ Rn is convex if for any points x, y ∈ C we have (1− λ)x+ λy ∈ C for all λ ∈ [0, 1].
(5) State the definition of an extreme point of a convex set;
A point e ∈ C is called an extreme point of C if it cannot be represented as e = (1− λ)x+ λy for
some distinct x, y ∈ C and λ ∈ (0, 1)
(6) Use the fact that the feasible region is a convex set to show that the set of all optimal solutions
is a convex set;
Proof: If the LPP has no optimal solutions then the set of optimal solutions is empty and thus
convex
So suppose now that the LPP has at least one optimal solution, and let z∗ be the optimal value
The set of optimal solutions is then
S := {x ∈ Rn |x is feasible and cTx = z∗}
This is the intersection of the FR with the hyperplane {x ∈ Rn | cTx = z∗}, both convex sets
AM3817 NAME: 5
4. [10pts] Show that the following LP problem is unbounded and exhibit a sequence of feasible points
whose objective value goes to infinity.
max 4x3 − x4 + x5
s.t. x1 − x3 + 9x4 + x5 = 4
x2 − x3 + 3x4 − x5 = 3
x1 , x2 , x3 , x4 , x5 ≥ 0.
Solution. Notice that B = {1, 2} is a feasible basis with corresponding tableau:
max z − 4x3 + x4 − x5 = 0
s.t. x1 − x3 + 9x4 + x5 = 4
x2 − x3 + 3x4 − x5 = 3.
Since c¯3 = 4 > 0. Choose x3 as the entering variable. Then a¯13 = a¯23 = −1 < 0 implies that the LP
problem is unbounded. Let x3(t) = t, x1(t) = 4 + t, x2(t) = 3 + t and x4(t) = x5(t) = 0. As t→ +∞,
we get a sequence of feasible points whose objective value goes to infinity.
AM3817 NAME: 6
5. [8pts] Convert the following optimization problem into an equivalent LP problem in standard equality
form. {
min z = max{|x1 − x2 + 3x3|, | − x1 + 3x2 − x3|}
s.t. x1, x2, x3 ≥ 0.
Solution. Let t be a new variable, such that t ≥ max{|x1 − x2 + 3x3|, | − x1 + 3x2 − x3|}. Then the
problem is equivalent to
min t
s.t. t ≥ max{|x1 − x2 + 3x3|, | − x1 + 3x2 − x3|}
x1, x2, x3, t ≥ 0.
The constraint t ≥ max{|x1 − x2 + 3x3|, | − x1 + 3x2 − x3|} is equivalent to t ≥ |x1 − x2 + 3x3| and
t ≥ | − x1 + 3x2 − x3|. Hence, the problem is equivalent to
min t
s.t. x1 − x2 + 3x3 ≤ t
x1 − x2 + 3x3 ≥ −t
−x1 + 3x2 − x3 ≤ t
−x1 + 3x2 − x3 ≥ −t
x1, x2, x3, t ≥ 0.
Converting the minimization problem into maximization problem and adding slack variables, we have

max −t
s.t. −t + x1 − x2 + 3x3 + s1 = 0
−t − x1 + x2 − 3x3 + s2 = 0
−t − x1 + 3x2 − x3 + s3 = 0
−t + x1 − 3x2 + x3 + s4 = 0
t , x1 , x2 , x3 , s1 , s2 , s3 , s4 ≥ 0.
AM3817 NAME: 7
6. [10pts] On the tableau below, indicate the current basis and basic solution and objective value. It is
the basis feasible? Indicate the leaving and the entering variables. Perform one pivot. What is the
new tableau, basis, basic solution, and objective value?
max z − 5x2 − 2x5 = −8
s.t. + 3x2 + x3 + 2x5 = 18
+ 2x2 + x4 + x5 = 10
x1 − x2 − x5 = −4
Solution. The current basis is B = (3, 4, 1); the basic solution is x∗ = (−4, 0, 18, 10, 0); the objective
value is z∗ = −8. The basis is not feasible since in the x1-row, b¯1 = −4 < 0.
Since c¯2 = 5 > 0, choose x2 as the entering variable. Since t := min{18/3, 10/2} = 5, the leaving
variable is x4. Pivot on position (4, 2). The new tableau is
max z 52x4 +
1
2x5 = 17
s.t. x3 − 32x4 + 12x5 = 3
x2 +
1
2x4 +
1
2x5 = 5
x1 +
1
2x4 − 12x5 = 1.
The new basis is BNew = (3, 2, 1), corresponding to basic solution x∗ = (1, 5, 3, 0, 0) and objective value
is z∗ = 17.
Alternatively, you can choose x5 as the entering variable since c¯5 = 2 > 0. Since t := min{18/2, 10/1} =
9, the leaving variable is x3. Pivot on position (3, 5). The new tableau is
max z − 2x2 + x3 = 10
s.t. 32x2 +
1
2x3 + x5 = 9
1
2x2 − 12x3 + x4 = 1
x1 +
1
2x2 +
1
2x3 = 5.
The new basis is BNew = (5, 4, 1), corresponding to basic solution x∗ = (5, 0, 0, 1, 9) and objective value
is z∗ = 10.
AM3817 NAME: 8
7. [10pts] A regional power system has generating capacity in districts A, B, and C; and has contractual
obligations to supply power to districts X, Y , and Z, as indicated in the following tables.
District Generating capacity (MW) Cost ($/MW)
A 100 500
B 75 700
C 200 400
District Power to supply
X 55
Y 50
Z 90
Transmission lines exist between districts as indicated below. When a transmission line exists be-
tween two points, power can be transmitted between them at no cost, but there is power loss during
transmission, data on which is given below.
District Lines connect to Transmission loss % on line
A B,C 5%
A X,Z 10%
B C,A 5%
B Z,Y 10%
C A,B 5%
C Y,X 10%
Generated power cannot be stored. Formulate, but do not solve, the problem of finding an optimum
generation, distribution plan to meet the contractual obligations at X, Y , Z, at minimum cost, as an
LP.
AM3817 NAME: 9
Solution:
Figure 1: Transmission lines between districts.
Let Xi ≥ 0, i = A,B,C be the power generated at i. Let Xij ≥ 0, i = A,B,C and j = A,B,C,X, Y, Z
be the power transmitted from i to j. The objective is to minimize the cost: 500XA+700XB +400XC .
Due to generating capacity, we have XA ≤ 100, XB ≤ 75, XC ≤ 200.
To meet the supplying obligation, taking into account the power loss during transmission, we have
0.9(XAX +XCX) = 55
0.9(XBY +XCY ) = 50
0.9(XAZ +XBZ) = 90.
Since generated power cannot be stored, for all i = A,B,C, the power transmitted from i has to be
the same as the sum of the power generated in i and the power transmitted to i. Hence, we need
XA + 0.95(XBA +XCA) = XAX +XAZ +XAB +XAC
XB + 0.95(XAB +XCB) = XBY +XBZ +XBA +XBC
XC + 0.95(XAC +XBC) = XCX +XCY +XCA +XCB.










































































































































































































































































































































学霸联盟