MATH 417/517 - Linear Optimzation Homework Set No. 2

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 e Rm ×n , b e Rm and c e Rn and write down A, b, c and n, m e 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:

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

\-   a1(T)     -)

(-   am(T)     -)

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

Q := {x e Rn  ' ai}(T)x = bi}   (j = 1, . . . , k),    x > 0 }

we have Q = P .

(4 P.)

3.4  (Finitely many basic feasible points) Let b e Rm , A e 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 e Rn  compute inf {vT x | x > 0 } .                                                          (2 P.)

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

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

and its dual

max bT y   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 ’文’ 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.)