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

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 \}\).

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.

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\);
What does it mean exactly by “Describe A(K)”? How would I describe the set?
It is a convex cone on the plane. Any such cone is either all of the plane, or a ray, or the wedge between two rays. Describe which of those alternatives happens, and give the directions of the rays, if necessary.
Hi Professor, what do we need to describe for Q1 and Q2? Could you give an example?
See comment above.
I am having trouble solving Question 1, I can see that it is mapping R3+ to R2, but I am not sure about how exactly A(K) is mapped to in R2+. I see that two vectors are linearly independent in R3, but I do not see the relationship it has on the space it mapped to in R2. Can I have some hint on this one?
Cone K is a convex hull of three rays (which?). Hence A(K) will be the convex hull of the images of these three rays. Find these images, and you’ll be done.
Thanks for the hint! Just to confirm if I have your hint correctly. R3+ is the convex hull of x,y,z axes, and the projection of those three rays to R2 through A(K) would be a convex hull (cone) of a ray passing through (3,1) from origin and (1,3) from origin in the positive quadrant. So for transformation of convex hull we can just transform the boundaries (vertices) and the take the convex hull of those?
More or less correct.
Hi Professor, from my intuition, the answer to the 1st question is the positive subset of R2. Is it correct? If so, can you give a proof for it?
What is a “positive subset of R2”?