Optimization Theory (DS2) HW#3
Polytopes, Bases, and Canonical Form (Almost to the Full Simplex Algorithm!)

Problems and page numbers from the paperback edition of A Gentle Introduction to Optimization, by B. Guenin et al.

1. Consider the polytope:

   1. If we have a two-variable (two-dimensional) problem with $k$ constraints, what is the maximum number of vertices and edges of our polygon? (Easy.)

   2. If we have a three-variable (three-dimensional) problem with $k$ constraints, what is the maximum number of faces, vertices and edges of our polyhedron? (Still pretty easy, please do this yourself, not google it.)

   3. If we have an $n$-variable ($n$-dimensional) problem with $k$ constraints, what is the maximum number of vertices and edges of our polytope? (Yes, this requires you to think in more than three dimensions a bit. See if you can figure this out, rather than just googling the answer. If you must google up the answer – or, better yet, go to the library and look in an actual book – be sure to cite where you got it.)

2. Canonical form: In Secs. 3.1 and 3.2 of the lecture notes for Lecture #4, we had the R and Octave code for changing the constraint matrix on our problem. Your goal here is to produce the equivalent code (in R, Octave, Mathematica, or some other language I can read) to complete this transformation of our problem.

   This should be done just for the same problem in Eqs. 2-4 of the lecture notes, showing me that you know how to get Eqs. 11-13. Just solving this single problem ad hoc using the interpreter is fine, you don’t need to write fully general functions here.

   Please show me that your code works! Capturing a screen shot is a reasonable thing to do, or copy-paste into a document (submit PDF, not Word) or even copy-paste directly into SFS will probably be adequate for this problem (but not for most of the others in this homework set).

   1. We already did the constraint matrix, but not the constraint values vector $\overrightarrow{b}$. Calculate the new $\overrightarrow{b^{\prime }}$, following Eq. 28.

   2. Calculate the new objective function $max\{\overrightarrow{z^{\prime }}\}$ following Eq. 21, using Eqs. 24-27 from the lecture notes.

   3. Now write out the new, complete LP, including the objective function, constraint equations, and non-negativity constraints. (You’ll need math markup for this, so no pure text – i.e., you can’t submit this one directly in SFS.)

3. (Problem 2 in Sec. 2.4 of the textbook.)
   The following LP is in SEF:

   		$max\{(1,-2,0,1,3)\overrightarrow{x}\}$		(1)
   	subject to
   				(2)
   		$\overrightarrow{x}\ge \overrightarrow{0}$		(3)

   Find an equivalent LP in canonical form for:

   1. the basis {1, 4}.

   2. the basis {3, 5}.

   In each case, state whether the basis (i.e., the corresponding basic solution) is feasible.