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$$.

• $$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$$;