week 9


Linear Proramming

Barvinok, 4.

Convex closed cones, their polars.

General LP problems. Dual problems for general LP.

Polyhedral cones, strong duality.

Sample problems

  1. Let \(K=\Real_+^3\) be the cone of vectors with nonnegative coordinates. Consider a mapping \(A:\Real^3\to\Real^2\) given by the matrix
    Describe \(A(K)\)

    Answer: cone spanned by the rays \((3t,t),(t,3t),t\geq0\), or, equivalently, given by \(\{y\leq 3x, x\leq 3y \}\).

  2. Same question for \(K=\{xy\geq z^2, x\geq 0\}\), and \(A:\Real^3\to\Real^2\) given by
    describe \(A(K)\)

    Answer: the set \(\{x\gt 0\}\cup (0,0)\) in the \(\langle x,z\rangle\) plane.

  3. Find the optimum for the LP
    ax&+by&\to\min,\ \mathrm{subject\ to}\\
    -x&+y&\leq 1\\
    x&-y&\leq 1\\
    x&+y&\leq 3\\
    x&&\geq 0\\
    &y&\geq 0
    as a function of \(a,b\).


    • \(0\) for \(a,b\geq 0\);
    • \(a\) for \(a\leq 0 \leq a+b\);
    • \(b\) for \(b\leq 0\leq a+b\);
    • \(2a+b\) for \(a+|b|\leq 0\);
    • \(2b+a\) for \(|a|+b\leq 0\);

10 Responses to week 9