xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-FM3817

时间：2021-04-21

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.

学霸联盟

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.

学霸联盟