McGill University

Department of

Mathematics and Statistics

Courtney Paquette

MATH 417/517 – Linear Optimzation

Homework Set No. 2

Due Date: Friday, September 30 by 11:59 pm (local Montreal)

Submission Method: CrowdMark, submit each problem separately

3.1 (LP standard form) Bring the linear program

max x1 + 2x2 + 3x3 s.t. x1 + x3 0

x1 − x3 0

x1 + x2 = 1

x1, x2 0

to standard form

min cT x s.t. Ax = b, x ≥ 0

with A ∈ Rm×n, b ∈ Rm and c ∈ Rn and write down A, b, c and n, m ∈ N explicitly. (3 P.)

3.2 (LP modelling) A hauling company has trucks (of the same size) a the locations A and B, namely 18 at location A and 12 at location B. These are to be sent to the terminals R,S and T where there are 11, 10 and 9 trucks needed, respectively. The distances (in km) from the locations to the terminals are given in the following table:

Terminal R Terminal S Terminal T

Location A 9

Location B 7 8 10

The trucks are to be routed such that the kilometers driven are minimal and such that the needs at every terminal are met.

a) Formulate this problem as a linear program.

b) Use linear algebra to reduce it to a two-dimensional problem in order to solve it graphically.

(3+8 P.)

3.3 (The full rank assumption on A) Let P = P(A, b) be a nonempty polyhedron

in standard form with

A



− aT1 −

..

− aTm −



Rm×n

such that rank A = k < m and ai1, . . . , aikare linearly independent. Show that for (the polyhedron in standard form)

Q :=

we have Q = P

(4 P.)

x ∈ Rn

aTijx = bij(j = 1, . . . , k), x ≥ 0

3.4 (Finitely many basic feasible points) Let b ∈ Rm, A ∈ Rm×n with rank A = m and let P = P(A, b) be the polyhedron in standard form defined by (A, b). Show that P has at most finitely many basic feasible points.

(4 P.)

4.1 For v ∈ Rncompute inf  vT x | x ≥ 0 . (2 P.)

4.2 (Dual of the dual is the primal problem) For (A, b, c) Rm×n × Rm × Rn consider the primal linear program

min cT x s.t. Ax = b, x ≥ 0 (P)

and its dual

max bTy s.t. ATy ≤ c. (D)

Show that the dual of the dual program is (equivalent to) the primal. (4 P.)

4.3 Consider the primal linear program (P) and its dual (D) and show: a) If (P) is unbounded then (D) is infeasible.

b) If (D) is unbounded then (P) is infeasible.

Afterwards fill in the table below.

Use the symbol ’X’ if the case for the tuple (inf(P),sup(D)) can occur, and ’×’ if this case cannot occur. Verify the positive case by an example, and cite a result from the lecture that explains the negative case.

(2+9 P.)

*4.4 (Equivalence of Farkas Lemma and strong duality) Show that the Farkas Lemma (Proposition 2.4.5) follows from the strong duality theorem (Theorem 2.5.6).

(4 P.)

CoursePear™提供各类学术服务，Essay代写Assignment代写Exam / Quiz助攻Dissertation / Thesis代写Problem Set代做等。