\Opgave 2

Primal problem

   max 8 x1 + 14 x2 + 11 x3 + 4 x4 + 12 x5 + 7 x6 + 4 x7 + 13 x8 + 9 x9

   s.t 1 x1 +  1 x2 +  1 x3                                             <= 480
                              1 x4 +  1 x5 + 1 x6                       <= 400
                                                    1 x7 +  1 x8 + 1 x9 <= 230
               1 x2                +  1 x5               +  1 x8        <= 420
                       1 x3                + 1 x6                + 1 x9 <= 250

The dual problem

  min 480 y1 + 400 y2 + 230 y3 + 420 y4 + 250 y5

  s.t     y1                                     >=  8
          y1                       + y4          >= 14
          y1                                + y5 >= 11
                   y2                            >=  4
                   y2              + y4          >= 12
                   y2                       + y5 >=  7
                            y3                   >=  4
                            y3     + y4          >= 13
                            y3              + y5 >=  9

The complementary slackness says that either a constraint is tight
or the corresponding dual variable is 0. Using this to the dual solution
with the proposed solution (x1 = 440, x3 = 40, x5 = 400, x8 = 20, x9 = 210)
we know that constraint 1, 3, 5, 8 and 9 must be tight. Thus

          y1                                      =  8
          y1                                + y5  = 11
                   y2              + y4           = 12
                            y3     + y4           = 13
                            y3              + y5  =  9

This problem has 5 variables and 5 equations thus it is easily solved.
We find 

         y1 = 8
         y5 = 3
         y3 = 6
         y4 = 7
         y2 = 5

Notice now that 

  a) the solution x is feasible
  b) the dual solution y is feasible
  c) x and y satisfy complementary slackness

which proves optimality