Prev Next Top Quiz0713

Math 407 Summer 06 Quiz 07-13

Problem A
Suppose that we are given the following tableau
    x1    x2    x3    x4    x5    x6    z    b
     1     1     1     0     1     0    0    2
     1     2     3     0     0     1    0    4
     1     3    -1     1     0     0    0    6
     0     1     2     0     0     0   -1    0
  1. What is the current basis function  
         D : \{ 1, 2, 3 \} \rightarrow \{ 1, 2, 3, 4, 5, 6 \}
     (mapping the row index to the corresponding basic variable index) ?
  2. What is the current basis set
         B \subset \{ 1, 2, 3, 4, 5, 6 \}
     (the set of basic variable indices) ?
  3. Using Bland's smallest-subscript rule, what variable would enter the basis ? What variable would leave the basis ?
  4. If we choose the variable with largest coefficient in the objective  z to enter the basis, what variable would enter the basis ? What are the possible choices for the variable that leaves the basis ?


Solution
  1. The current basis function is defined by  \[
    \begin{array}{ccccc}
    D(1) = 5 & , & D(2) = 6 & , & D(3) = 4
    \end{array}
    \]      .
  2. The current basis set is  \[
         B = \{ 5 , 6 , 4 \}
    \] 
  3. Using Bland's smallest-subscript rule, the variable that would enter the basis is  x2 and the leaving variable would be  x4.
  4. Using the largest coefficient rule, the variable would enter the basis is  x3 and  x6 is the only choice for the leaving variable.


Problem B
A dictionary is called feasible if its corresponding basic solution is feasible. Problem 3.10 of the text contains the hypothesis: A feasible dictionary whose representation for the objective is  \[
     z = v + c_1 * x_1 + c_2 * x_2 + ... + c_n * x_n
\]  corresponds to an optimal basic solution if and only if  c_j \leq 0 for all  j . Show that this hypothesis is false. (Hint, I used the problem of maximizing  x_1 subject to  x_1 \geq 0 and  x_1 \leq 0 .)

Solution
The optimal solution for the problem
     maximize   x1
     subject to x1 <= 0
                x1 >= 0
is  x1 = 0. This problem has the following representation
     maximize   x1
     subject to x1 + s1 = 0
                x1 >= 0, s1 >= 0
One feasible dictionary for this problem is
     s1 = - x1
     ---------
     z  =   x1
and the corresponding basic solution is  x1 = 0,  s1 = 0. This is the optimal solution, but not all the objective coefficients are less than or equal zero (in this representation).

Problem C
Suppose that feasible dictionary whose representation for the objective is  \[
     z = v + c_1 * x_1 + c_2 * x_2 + \cdots + c_n * x_n
\]  where  c_j \leq 0 for all  j . Show that the corresponding basic solution is optimal.

Solution
The text discusses this situation for a special case in the text surrounding equation (2.11). For this problem, we consider the general case.

The objective function value corresponding to the basic solution is  v . Suppose that we have any feasible point  x \in \R^n . It follows that  x_j \geq 0 for  j = 1 , \ldots , n . By assumption  c_j \leq 0 for all  j hence  \[
\begin{array}{rcll}
0 & \geq & c_j x_j & \hspace{1cm} (j = 1 , \cdots , n )  \\
0 & \geq & c_1 x_1 + \cdots + c_n x_n                    \\
v & \geq & v + c_1 x_1 + \cdots + c_n x_n                \\
v & \geq & z 
\end{array}
\]  This the value of the objective at  x is less than or equal the value at the basic solution mentioned above.

Problem D
Use the simplex method to solve the auxillary problem (as constructed on page 40 of the text) and thereby find a feasible dictionary for the problem
     maximize    z  =      x1
     subject to  s1 = -1 - x1 + x2 
                 s2 =  2 - x1 - x2 
     s1 >= 0, s2 >= 0, x1 >= 0, x2 >=0

Solution
The initial auxillary problem, before the first pivot, is represented by the following infeasible dictionary:
     maximize    w  = - x0
     subject to  s1 = -1 + x0 - x1 + x2
                 s2 =  2 + x0 - x1 - x2
     s1>=0, s2>=0, x0>=0, x1>=0, x2>=0
The first pivot of the auxillary problem yields the following feasible dictionary:
     maximize    w  = - (1 + s1 + x1 - x2)
     subject to  x0 =  1 + s1 + x1 - x2
                 s2 =  2 + (1 + s1 + x1 - x2) - x1 - x2
     s1>=0, s2>=0, x0>=0, x1>=0, x2>=0
which simplifies to
     maximize    w  = -1 - s1 - x1 +     x2
     subject to  x0 =  1 + s1 + x1 -     x2
                 s2 =  3 + s1      - 2 * x2
     s1>=0, s2>=0, x0>=0, x1>=0, x2>=0
Applying the simplex method, the only choice for the entering variable is  x2. The corresponding ratios are  1 and  3 / 2. Thus the only choice for the leaving variable is  x0. The resulting dictionary is
     maximize    w  = -1 - s1 - x1 + (1 + s1 + x1 - x0)
     subject to  x2 =  1 + s1 + x1 -     x0
                 s2 =  3 + s1 - 2 * (1 + s1 + x1 - x0)
     s1>=0, s2>=0, x0>=0, x1>=0, x2>=0
which simplifies to
     maximize    w  =  0      -     x0
     subject to  x2 =  1 + s1 -     x0 +     x1
                 s2 =  1 - s1 + 2 * x0 - 2 * x1
     s1>=0, s2>=0, x0>=0, x1>=0, x2>=0
Since  x0 is a non-basic variable in this representation, we can drop it and obtain the following feasible dictionary for the original problem:
     maximize    z  =               x1
     subject to  x2 =  1 + s1 +     x1
                 s2 =  1 - s1 - 2 * x1
     s1>=0, s2>=0, x1>=0, x2>=0
Input File: Quiz0713.omh