Optimization Theory (DS2) HW#4
Simplex in the Morning, Simplex in the Evening!

Abstract

Last homework on the simplex algorithm. This homework counts for two homework sets!

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

1. I am in Williamson, West Virginia, for an extended stay, and you are coming from Japan to visit me. “Rice! I need rice!” I tell you. I offer to pay you $3 above cost for each kilogram of Thai rice, $2/kg above cost for Chiba-ken mochigome, and $1/kg for plain old Nagano-ken koshihikari. You visit the grocery store, where they have 15kg of Thaimai on the shelf, 5kg of mochigome, and 12kg of koshihikari. You can buy any combination, including fractional kilograms. However, the weight of your suitcase cannot exceed 22kg.

   1. Write this as a linear program (inequalities okay).

   2. Solve this in R.

2. Take our favorite LP:

   $$maxz(\overrightarrow{x})=(2,3,0,0,0){(x_1,x_2,x_3,x_4,x_5)}^{⊺}$$

   (1)

   subject to

   		$=\left(\begin{array}{c}\hfill 6\hfill \\ \hfill 10\hfill \\ \hfill 4\hfill \end{array}\right)$		(2)
   	$x_1,x_2,x_3,x_4,x_5$	$\ge 0.$		(3)

   and show that you can solve it in R using the simplex() function.

3. Let’s finish off the problem by hand (last time you’ll have to do such grungy stuff by hand for the simplex algorithm, I promise). You will need to refer to both the lecture notes and the pseudocode for the simplex algorithm.

   The problem has already been carried through the first full iteration for you, and through the process of creating the next canonical form, in detail, ending in Eqs. 26-29. So here we will pick up the work at line 2 of the pseudocode, finding a basic solution.

   1. Find a new basic solution, $\overrightarrow{x_a^{\prime }}$. (This involves picking an element $x_i$ to optimize for, using our temporary variable $t$, and applying the ratio test to maximize $t$ and therefore $x_i$.) Report both $\overrightarrow{x_a^{\prime }}$ and the corresponding objective function value, $z_a^{\prime }=z(\overrightarrow{x_a^{\prime }})$.

   2. Check to see if $\overrightarrow{x_a^{\prime }}$ is optimal. (If so, you are done!)

   3. Pick a new element $k$ to add to the basis.

   4. Test $A_k$ for unboundedness.

   5. Conduct a new ratio test to pick the element you are going to remove from the basis. (Careful with the indices $r$ and $\iota$ here, it’s a little bit tricky.)

   6. Write down the new basis $B$.

      At this point, you have completed the loop, up through step 9 in the lecture notes or the end of the pseudocode.

   7. The next step (back at the top of the pseudocode) is to create a new version of the problem in canonical form for the new basis we just picked.

   At this point, you’ve been all the way around once. I suppose that’s far enough… otsukaresama deshita on the simplex algorithm! (And let’s all be grateful for computers that do the work for us!)