INEN 622: Group Quiz 2

 

Each question is worth 10pt.  The quiz is closed book and notes. 

 

1.       (10 pts) Perform one iteration of the Dual Simplex Method on the following LP:

 

Min    6x1 + 8x2

s.t.     x1 + 2x2 ³ 2

          2x1 + x2 ³ 6

          x1, x2 ³ 0

 

2.     (10 pts) Perform one iteration of the Dual Simplex Method on the following LP:

 

Min    60x1 + 10x2 + 20x3

s.t.     3x1 + x2 + x3 ³ 5

          x1 - x2 + x3 ³ -1

          x1 + 2x2 - x3 ³ 1

          x1, x2, x3 ³ 0

 

3.  Find the optimal values and optimal primal and dual solution to the LP by the graphical method and complementary slackness:

 

Min      4x1 + 6x2 + 7x3

s.t.       2x1 + 3x2 + 4x3 ³ 3

x1 + 2x2 + 2x3 ³ 1

x1³ 0, x2 £ 0

 

 

    4.  Knowing that the optimal basic variables of the following LP are x1, x2, x3, find the allowable ranges for c1, c2, c4, c5, c6, b1, b3:

 

Max   2x1+ x2 + x3

s.t.     x1 + x3  £ 1

          x2 + x3  £ 2

x1 + x2  £ 3

          x1, x2, x3 ³ 0

 

 

 

5.     Use complementary slackness to prove or disprove that x1*= 3, x2*= -1, x3*= 0, x4*= 2 is an optimal solution to the following LP:

 

 

Max     6x1 + x2 - x3 - x4

s.t.       x1 + 2x2 + x3 + x4 £ 5

3x1 + x2 - x3 ³ 8

     x2 + x3 + x4 = 1

x3, x4 ³ 0

 

 

6.      Generate a Chvátal-Gomory cut for basic variable row x4 of the following dictionary and perform one iteration of the dual simplex method with the new slack variable:

 

x2  =    4  -       4x7  +   5/2x6   -     3x5

                   x3  =  15  -    1/2x7  -  3/2x6   -      4x5

                   x1  =  16  -    3/2x7  -  9/2x6   +   5/2x5

                   x4  =    1/2  +  14x7  -  3/2x6   +  21/2x5

                   z  =        10   -  2x7  -       x6    -          x5