week 9

\(\def\Real{\mathbb{R}}
\def\Comp{\mathbb{C}}
\def\Rat{\mathbb{Q}}
\def\Field{\mathbb{F}}
\def\Fun{\mathbf{Fun}}
\def\e{\mathbf{e}}
\def\f{\mathbf{f}}
\def\bv{\mathbf{v}}
\)

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
    \[
    A=\left(
    \begin{array}{ccc}
    3&2&1\\1&2&3\\
    \end{array}
    \right).
    \]
    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
    \[
    A=\left(
    \begin{array}{ccc}
    1&0&0\\0&0&1\\
    \end{array}
    \right):
    \]
    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
    \[
    \begin{array}{rll}
    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
    \end{array}
    \]
    as a function of \(a,b\).

    Answer:

    • \(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