Prev Next Top Quiz0727

Math 407 Quiz 06-07-27

Name: ___________________________

Problem A
Solve the problem
     maximize     x1 + x2         w.r.t x in Z+^2
     subject to 2*x1 + x2   <= 5
                  x1 + 2*x2 <= 5
You must show your work for this problem; i.e., prove that your solution is optimal.

Hint
If  y in  R+^2 solves the problem above, then  y1 is not an integer. Furthermore, you should only have to branch once to the following two cases;  x1 <= [y1] and  x1 >= [y1]+1.

Solution

Original Problem
We consider the relaxed problem where  x is a positive real vector; i.e.,
     maximize     x1 + x2         w.r.t x in R+^2
     subject to 2*x1 + x2   <= 5
                  x1 + 2*x2 <= 5
Adding slack variables we obtain the following tableau representation:
      x1      x2      s1      s2       z       b
       2       1       1       0       0       5
       1       2       0       1       0       5
       1       1       0       0      -1       0
Note that the corresponding basis is  (s1, s2). Pivoting with  x1 to enter and  s1 to leave the basis we have
      x1      x2      s1      s2       z       b
       1     0.5     0.5       0       0     2.5
       0     1.5    -0.5       1       0     2.5
       0     0.5    -0.5       0      -1    -2.5
Note that the corresponding basis is  (x1, s2). Pivoting with  x2 to enter and  s2 to leave the basis we have
      x1      x2      s1      s2       z       b
       1       0     2/3    -1/3       0     5/3
       0       1    -1/3     2/3       0     5/3
       0       0    -1/3    -1/3      -1   -10/3
Note that the corresponding basis is  (x1, x2). It follows that the optimal solution is  x1 = 5/3,  x2 = 5/3 and the corresponding objective is  z = 10/3.

Branch Less Than or Equal
The first branch we consider is  x1 <= [5/3] = 1.
     maximize     x1 + x2         w.r.t x in R+^2
     subject to 2*x1 + x2   <= 5
                  x1 + 2*x2 <= 5
                  x1        <= 1
Adding slack variables we obtain the following tableau representation:
      x1      x2      s1      s2      s3       z       b
       2       1       1       0       0       0       5
       1       2       0       1       0       0       5
       1       0       0       0       1       0       1       
       1       1       0       0       0      -1       0
Note that the corresponding basis is  (s1, s2, s3). Pivoting with  x1 to enter and  s3 to leave the basis we have:
      x1      x2      s1      s2      s3       z       b
       0       1       1       0      -2       0       3
       0       2       0       1      -1       0       4
       1       0       0       0       1       0       1
       0       1       0       0      -1      -1      -1
Note that the corresponding basis is  (s1, s2, x1). Pivoting with  x2 to enter and  s2 to leave the basis we have:
      x1      x2      s1      s2      s3       z       b
       0       0       1    -0.5    -1.5       0       1
       0       1       0     0.5    -0.5       0       2
       1       0       0       0       1       0       1
       0       0       0    -0.5    -0.5      -1      -3
It follows that the optimal solution is  x1 = 1,  x2 = 2 and the corresponding objective is  z = 3.

Branch Greater Than or Equal
The second branch we consider is  x1 >= [5/3] + 1 = 2.
     maximize     x1 + x2         w.r.t x in R+^2
     subject to 2*x1 + x2   <=  5
                  x1 + 2*x2 <=  5
                - x1        <= -2
Not all of the right hand side coefficients are positive, so we need to first find a feasible basis for this problem. To this end, we use the TwoPhase method and first solve the auxiliary problem
     maximize   - x0                     w.r.t x in R+^3
     subject to - x0 + 2*x1 + x2   <=  5
                - x0 +   x1 + 2*x2 <=  5
                - x0 -   x1        <= -2
The initial dictionary for this problem is
     s1 =  5 + x0 - 2*x1 -   x2 
     s2 =  5 + x0 -   x1 - 2*x2 
     s3 = -2 + x0 +   x1
      y =    - x0
We can make this dictionary feasible by having  x0 enter the basis and  s3 leave:
     s1 =  5 + (2 + s3 - x1) - 2*x1 -   x2 
     s2 =  5 + (2 + s3 - x1) -   x1 - 2*x2 
     x0 =       2 + s3 - x1
      y =    - (2 + s3 - x1)
Grouping terms we have
     s1 =  7 + s3 - 3*x1 -   x2 
     s2 =  7 + s3 - 2*x1 - 2*x2 
     x0 =  2 + s3 -   x1
      y = -2 - s3 +   x1
Choosing  x1 to enter the basis and  x0 to leave, we obtain
     s1 =  7 + s3 - 3*(2 + s3 - x0) -   x2 
     s2 =  7 + s3 - 2*(2 + s3 - x0) - 2*x2 
     x1 =  2 + s3 - x0
      y = -2 - s3 +   (2 + s3 - x0)
Grouping terms we have
     s1 =  1 - 2*s3 + 3*x0 -   x2 
     s2 =  3 -   s3 + 2*x0 - 2*x2 
     x1 =  2 +   s3 -   x0
      y =  0        -   x0
We now have a feasible dictionary that does not contain the auxiliary variable  x0, so we can drop it and write our original problem as
     s1 =  1 - 2*s3 -   x2 
     s2 =  3 -   s3 - 2*x2 
     x1 =  2 +   s3 
      z =  2 +   s3 +   x2
(Note that we have replaced  x1 by  2 + s3 in the expression for the original objective  z.) Choosing  x2 to enter the basis and  s1 to leave, we obtain
     x2 =  1 - s1 - 2*s3 
     s2 =  3      -   s3 - 2*(1 - s1 - 2*s3) 
     x1 =  2      +   s3 
      z =  2      +   s3 +   (1 - s1 - 2*s3)
Grouping terms we have
     x2 =  1 -   s1 - 2*s3 
     s2 =  1 + 2*s1 + 3*s3 
     x1 =  2        +   s3
     z  =  3 -   s1 -   s3
It follows that the optimal solution is  x1 = 2,  x2 = 1 and the corresponding objective is  z = 3.

Summary
There are only two possible cases;  x1 <= 1 or  x1 >= 2. In the first case, the optimal solution is  x1 = 1,  x2 = 2 and the corresponding objective is  z = 3. In the second case, the optimal solution is  x1 = 2,  x2 = 1 and the corresponding objective is  z = 3. Thus both these solutions are optimal for the original problem.
Input File: Quiz0727.omh