\Opgave 16

Adding slack variables we get

  z = 7 x1 +   x2  
      4 x1 +   x2 + x3           = 28
        x1 + 4 x2      + x4      = 27
        x1 -   x2           + x5 =  1

Running the simplex algorithm one ends up with the equations

            4   1      1
     x1 = 5 - - - x3 - - x5
            5   5      5

            4   1      4
     x2 = 4 - - - x3 - - x5
            5   5      5

     x4 =   2 +   x3 - 3 x5
                        
Deriving a gomory cut from the first fractional inequality

          1      1        4
     x1 + - x3 + - x5 = 5 - 
          5      5        5

we get the cut

      1      1       4
      - x3 + - x5 >= -
      5      5       5

substituting the original variables 

      x3 = 28 - 4 x1 - x2
      x5 = 1  -   x1 + x2

we get the valid inequality

      x1 <= 5

The original problem has LP-solution (5.8, 4.8)
so the cut separates the present LP-solution. The
objective value is 4.54.

Adding the inequality to the problem, CPLEX finds
the solution (5, 5.5) which has objective value 4.05.

The integer-optimal solution is (5,5) with objective
value 4.