Prev Next Top Quiz0629

Math 407 Summer 06 Quiz 06-29

Name: ___________________________

Problem A
The following tableau is a representation of Problem 2.1.a on page 26 of the text:
     x1   x2   x3   s1   s2   s3   z   b
      1    1    2    1    0    0   0   4
      2    0    3    0    1    0   0   5
      2    1    3    0    0    1   0   7
      3    2    4    0    0    0  -1   0
  1. What is the basic solution corresponding to this tableau representation; i.e., what is the corresponding values for  x1,  x2,  x3,  s1,  s2 and  s3 ? What is the objective function value  z corresponding to this basic solution ? Is this basic solution feasible and why ?
  2. What would the objective function value be after one pivot operation on the  x1 column ? What would it be for the  x2 and  x3 columns ?


Solution
  1. The basic solution is  
         x1 = 0, x2 = 0, x3 = 0, s1 = 4, s2 = 5, s3 = 7
    The corresponding objective function value is  z = 0. The basic solution is feasible because all the components of  x and  s are greater than or equal zero; i.e., they satisfy the constraints.
  2. Pivoting about the  x1 column would result in a value of  
         x1 = min( 4/1 , 5/2 , 7/2 ) = 2.5
    and  s2 = 0 (the rest of the variables would be that same as before). Thus the new objective value would be  
         z = 3 * 2.5 = 7.5
    Pivoting about the  x2 column would result in a value of
         x2 = min( 4/1 , --- , 7/1 ) = 4
    and  s1 = 0. Thus the new objective value would be
         z = 2 * 4 = 8
    Pivoting about the  x3 column would result in a value of
         x3 = min( 4/2 , 5/3 , 7/3 ) = 5/3
    and  s2 = 0. Thus the new objective value would be
         z = 4 * 5 / 3 = 20 / 3

Problem B
Write down the tableau that results from pivoting the tableau above about the second column and first row. Then write down the tableau that results from pivoting this new tableau about the first column and second row. (Hint, the resulting basic solution is optimal and corresponds to the solution for Problem 2.1.a on page 465 of the text.)

Solution
The tableau that results from pivoting the tableau in the problem statement about the second column and first row is
     x1     x2     x3     s1     s2     s3     z      b
      1      1      2      1      0      0     0      4
      2      0      3      0      1      0     0      5
      1      0      1     -1      0      1     0      3
      1      0      0     -2      0      0    -1     -8
The tableau that results from pivoting the tableau directly above about the first column and second row is
     x1     x2     x3     s1     s2     s3     z      b
      0      1    1/2      1   -1/2      0     0    3/2
      1      0    3/2      0    1/2      0     0    5/2
      0      0   -1/2     -1   -1/2      1     0    1/2
      0      0   -3/2     -2   -1/2      0    -1  -21/2

Problem C
The e-mail message body below will use the Neos interface to Clp to solve Problem 2.1.a in the text. Fill in the missing characters above the _ characters (where each _ corresponds to a missing character).
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
maximize    3*x1 + 2*x2 + 4*x3                   Problem 2.1.a
subject to    x1 +   x2 + 2*x3 <= 4              in Vasek Chvatal's
            2*x1        + 3*x3 <= 5              Linear Programming book
            2*x1 +   x2 + 3*x3 <= 7
              x1 ,   x2 ,   x3 >= 0
]]></comments>
<MPS><![CDATA[*
*Op Name0     Name1     Value1      
*23 56789012  56789012  567890123456
NAME          P 2.1.a
ROWS
 N  z
 L  r1
 L  r2
 L  r3
COLUMNS
    x1        z         __
    x1        r1        __
    x1        r2        __
    x1        r3        __
    x2        z         __
    x2        r1        __
    x2        r3        __
    x3        z         __
    x3        r1        __
    x3        r2        __
    x3        r3        __
RHS
    b         r1        __
    b         r2        __
    b         r3        __
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalSimplex
solution -
]]></param>
</document>
Solution
<document>
<category>lp</category>
<solver>Clp</solver>
<inputMethod>MPS</inputMethod>
<comments><![CDATA[
Problem 2.1.a in Vasek Chvatal's book: Linear Programming
maximize    3*x1 + 2*x2 + 4*x3
subject to    x1 +   x2 + 2*x3 <= 4
            2*x1        + 3*x3 <= 5
            2*x1 +   x2 + 3*x3 <= 7
              x1 ,   x2 ,   x3 >= 0
]]></comments>
<MPS><![CDATA[*
*Op Name0     Name1     Value1      
*23 56789012  56789012  567890123456
NAME          P 2.1.a
ROWS
 N  z
 L  r1
 L  r2
 L  r3
COLUMNS
    x1        z         3
    x1        r1        1
    x1        r2        2
    x1        r3        2
*
    x2        z         2
    x2        r1        1
    x2        r3        1
*
    x3        z         4
    x3        r1        2
    x3        r2        3
    x3        r3        3
*
RHS
    b         r1        4
    b         r2        5
    b         r3        7
ENDATA
*]]></MPS>
<param><![CDATA[
maximize
primalSimplex
solution -
]]></param>
</document>
Problem D
Suppose that we want to solve the problem
     minimize    3*x1 + 2*x2 + 4*x3
     subject to    x1 +   x2 + 2*x3 >= 4
                 2*x1        + 3*x3 >= 5
                 2*x1 +   x2 + 3*x3 >= 7
                   x1 ,   x2 ,   x3 >= 0
What would you change in the input for the previous problem, to solve this new problem ?

Solution
There are multiple ways to solve this problem. Here one that only requires changing four short lines in the input file: In the <param> record, change the word maximize to the word minimize. In the ROWS record, change L r1 to G r1, change L r2 to G r2, and change L r3 to G r3.
Input File: Quiz0629.omh