CSC 445/545: Fall 2014, Assignment #2
Due: Friday Oct. 3, beginning of class

Reminder: Our first test is in class on Fri. Oct. 10.

  1. Given the following dictionary: 

    X5 = 12.00+  2.00 X1 +  3.00 X2 +  1.00 X3 -  4.00 X4
X6 =  8.00+  1.00 X1 -  8.00 X2 +  4.00 X3 -  4.00 X4
X7 =  6.00+  2.00 X1 -  6.00 X2 +  2.00 X3 -  3.00 X4
--------------------------------------------------------
z  = 17.00- 10.00 X1 +  6.00 X2 +  2.00 X3 + 10.00 X4
    Which variables enter and exit if
    (a) [3] the largest coefficient rule is applied with smallest subscript used to break ties with regards to the variable which exits?
    (b) [3] the smallest subscript rule is applied to choose both the entering and leaving variables?
    (c) [4] a solution is reached using a minimum number of pivots?
    Justify your answers.
  2. Consider this optimization problem:
    Maximize 1.00 X1 - 1.00 X2 + 2.00 X3 
    subject to
 1.00 X1 -  4.00 X2 -  2.00 X3  <= -4
 1.00 X1 +  1.00 X2 +  1.00 X3  <= 10
-1.00 X1 +  2.00 X2 -  1.00 X3  <= -8
-1.00 X1 -  2.00 X2 +  4.00 X3  <= -2
X1, X2, X3 >= 0

    (a) [5] Set up the initial phase 1 dictionary and show the dictionary resulting from the first pivot.

    (b) [5] The final dictionary is this one: 

    X1 =  7.38-  0.04 X4 -  0.46 X5 +  0.32 X6 +  0.18 X7 
X2 =  1.41+  0.14 X4 -  0.14 X5 -  0.08 X6 +  0.08 X7 
X8 =  1.11+  0.20 X4 +  0.30 X5 +  0.38 X6 +  0.12 X7 
X3 =  2.32+  0.11 X4 -  0.11 X5 +  0.14 X6 -  0.14 X7 
-----------------------------------------------
z  = -1.11-  0.20 X4 -  0.30 X5 -  0.38 X6 -  0.12 X7
    what does this tell you about the original problem?
  3. Consider this initial dictionary for a problem S in standard form: 
    X5 =  6-  1 X1 +  1 X2 +  0 X3 +  0 X4 
X6 =  6-  1 X1 +  1 X2 -  1 X3 +  1 X4 
X7 =  2+  1 X1 -  1 X2 -  1 X3 +  1 X4 
X8 = -4+  0 X1 +  0 X2 +  1 X3 -  1 X4 
X9 =  4+  1 X1 -  1 X2 +  1 X3 -  1 X4 
-----------------------------------------------
z  =  0-  1 X1 +  1 X2 -  1 X3 +  1 X4 

    The initial Phase 1 dictionary looks like this:
Phase 1: Before pivoting to make feasible.
X5 =  6-  1 X1 +  1 X2 +  0 X3 +  0 X4 +  1 X0
X6 =  6-  1 X1 +  1 X2 -  1 X3 +  1 X4 +  1 X0
X7 =  2+  1 X1 -  1 X2 -  1 X3 +  1 X4 +  1 X0
X8 = -4+  0 X1 +  0 X2 +  1 X3 -  1 X4 +  1 X0
X9 =  4+  1 X1 -  1 X2 +  1 X3 -  1 X4 +  1 X0
-----------------------------------------------
z  =  0+  0 X1 +  0 X2 +  0 X3 +  0 X4 -  1 X0
    This standard form problem S was created from another problem P that was not in standard form because:
    (a) [6] Use these clues and the two dictionaries to deduce the original optimization problem P.
    (b) [4] What is the equivalent standard form problem S?
    (c) [2] For the first pivot applied to the initial Phase 1 dictionary, which variable enters and which one leaves?
    (d) [2] At the end of Phase 1, X0 was still in the basis: 
     
X5 =  4.00+  0.00 X2 +  0.00 X4 +  0.75 X6 -  0.25 X7 +  0.50 X8 
X1 =  2.00+  1.00 X2 +  0.00 X4 -  0.50 X6 +  0.50 X7 +  0.00 X8 
X3 =  4.00+  0.00 X2 +  1.00 X4 -  0.25 X6 -  0.25 X7 +  0.50 X8 
X0=   0.00+  0.00 X2 +  0.00 X4 +  0.25 X6 +  0.25 X7 +  0.50 X8 
X9 = 10.00+  0.00 X2 +  0.00 X4 -  0.50 X6 +  0.50 X7 +  1.00 X8 
-----------------------------------------------
z  = -0.00+  0.00 X2 +  0.00 X4 -  0.25 X6 -  0.25 X7 -  0.50 X8
    Which variable should enter and which one should leave before starting phase 2?
    (e) [3] The final dictionary for the problem is this one: 
    X5 =  4.00+  0.00 X2 +  0.00 X4 -  1.00 X7 -  1.00 X8 
X1 =  2.00+  1.00 X2 +  0.00 X4 +  1.00 X7 +  1.00 X8 
X3 =  4.00+  0.00 X2 +  1.00 X4 +  0.00 X7 +  1.00 X8 
X6 = -0.00+  0.00 X2 +  0.00 X4 -  1.00 X7 -  2.00 X8 
X9 = 10.00+  0.00 X2 +  0.00 X4 +  1.00 X7 +  2.00 X8 
-----------------------------------------------
z  = -6.00+  0.00 X2 +  0.00 X4 -  1.00 X7 -  2.00 X8
    What are the values for xi for i from 1 to 9, and for z that correspond to this dictionary?
    (f) [3] What does this tell you about the values for x1 and x2 and for z for the original problem P?
    (g) [5] Draw a picture that shows each of the constraints from the original problem P and shade in the feasible region.
    (h) [5] For each corner of the feasible region, indicate the values for x1, x2 and z. Hint: the corner that minimizes z should correspond to the solution that arose from solving the standard form optimization problem S.
  4. Consider this linear programming problem: Maximize x1 + x2 + 5 x 3
    subject to
    x1 + 2 x2 <= 2
    -x1 - 2 x2 <= -2
    x1 + x2 + x 3 <= 5
    x1, x2, x 3 >= 0

    (a) [5] Set up the initial dictionary for the phase 1 problem then take the first pivot to make the current solution feasible.
    (b) [2] Show the dictionary that results after one more pivot that has x1 entering and x4 leaving.
    (c) [5] Note that X0 is still in the basis after the pivot from (b) yet the solution is optimal. Do what is needed to prepare the dictionary to start phase 2, explaining what you are doing and why.
    (d) [3] Finish solving the problem either by hand or using your program and explaining what you are doing.

  5. (a) [6] State the dual problem for the problem stated in the previous question.
    (b) [3] Reformulate the dual problem so it is in our standard form.
    (c) [3] I solved the standard form dual problem using my program and the final dictionary was: 
    Y4 =  2.0+  0.0 Y1 +  0.5 Y5 +  0.5 Y6 
Y2 =  2.0+  1.0 Y1 -  0.5 Y5 +  0.5 Y6 
Y3 =  5.0+  0.0 Y1 +  0.0 Y5 +  1.0 Y6 
-----------------------------------------------
z  =-21.0+  0.0 Y1 -  1.0 Y5 -  4.0 Y6 

The optimal solution: -21
Y1=0, Y2=2, Y3=5, Y4=2, Y5=0, Y6=0
    How can you determine what the primal solution should be from the information in this final dual dictionary? That is, explain how to compute x1, x2, and x3 and z for the primal from this last dual dictionary. Hint: you can use this to double check your work from the previous question.
    (d) [3] Explain how you can determine the values of y1, y2, y3 and z from the dual problem given the final dictionary you obtained in the previous question for the primal problem.
  6. Consider this problem: 
    Maximize   2 X1  - 1 X2
subject to
           2 X1  - 2 X2  <=  2
          -3 X1  + 3 X2  <= -6
X >= 0
    (a) [3] Find the solution to the primal problem either by hand or by using your computer program.
    (b) [2] What is the dual problem?
    (c) [2] Convert the dual problem to standard form.
    (d) [3] Find the solution to the dual problem either by hand or by using your computer program.

  7. Tom is running a tutoring business. He has 3 types of classes: Middle School, High School, and Adult. He has a classroom available at no charge for 10 hours per week.

    For the middle school classes, he has 4 students per class and each one pays a fee of $15 per hour. These classes require 2 tutors. He pays his tutors the minimum wage- $8 per hour. For the high school classes, Tom has 4 students per class each paying $10 per hour, but only one tutor is required for these. For the adult classes he offers one on one tutoring (one adult and one tutor) and the fee per student is $30 because of this individual attention. He has 14 tutor hours available per week.

    In one hour of each of the middle school and high school classes, Tom uses 8 pages of worksheets per student for each of the 4 students so a total of 32 worksheet pages per hour for each of these classes. The adults are expected to get their course resources off the web and print them themselves. But he must photocopy the worksheets for the other students and he has a photocopying quota of 256 pages per week.

    (a) [2] State the problem of maximizing Tom's profit per week as a linear programming problem.

    (b) [4] Tom's optimal solution involves classes for all three groups of students. Find the inverse of the basis matrix for this situation. Show your work.

    (c) [4] Use your result from (b) to determine the final dictionary for the Simplex method (including the z row).