Prev Next Top Quiz0622

Math 407 Summer 06 Quiz 06-22

Name: ___________________________

Problem A
Problem number 1.2 of the text book is
     minimize     - 8*x1 + 9*x2 +  2*x3 - 6*x4 - 5*x5
     subject to     6*x1 + 6*x2 - 10*x3 + 2*x4 - 8*x5 >= 3
                      x1 ,   x2 ,    x3 ,   x4 ,   x5 >= 0
Write down a standard form representation of this problem:

Solution
The general standard form is equation (1.7). For this problem, we get
     maximize     + 8*x1 - 9*x2 -  2*x3 + 6*x4 + 5*x5
     subject to   - 6*x1 - 6*x2 + 10*x3 - 2*x4 + 8*x5 <= 3
                      x1 ,   x2 ,    x3 ,   x4 ,   x5 >= 0
One could also answer this question by defining the terms in equation (1.7); i.e.
     n   = 5, 
     m   = 1,
     c1  = 8,   c2 = -9,  c3 = -2,  c4 = 6,   c5 = 5
     a11 = -6, a12 = -6, a13 = 10, a14 = -2, a15 = 8

Problem B
We define problems (B.1), (B.2) and (B.3) by
     maximize      x1 +   x2 - x3
     subject to  2*x1 +   x2       <= 1        (B.1)
                   x1 ,   x2 , x3  >= 0

     maximize      x1 +   x2 - x3
     subject to  2*x1 -   x2       <= 1        (B.2)
                   x1 ,   x2 , x3  >= 0

     maximize      x1 +   x2 - x3
     subject to  - x1 - 2*x2       <= 1        (B.3)
                   x1 ,   x2 , x3  >= 0

Which of the problems above are infeasible, which are unbounded, and which have an optimal solution (Hint, look at problem 1.4 in the text.) ?

Solution
In problem (B.1),  x1 <= .5 and  x2 <= 1. It follows that (B.1) is not unbounded. In addition,  x1 = 0,  x2 = 0 is a feasible solution. Thus (B.1) has an optimal solution .

If  x1 = 0,  x3 = 0, and  x2 >= 1 in problem (B.2), the objective is equal  x2 and the constraint is satisfied. Thus (B.2) is unbounded.

If  x1 = 0,  x3 = 0, and  x2 >= .5 in problem (B.3), the objective is equal  x2 and the constraint is satisfied. Thus (B.3) is unbounded.

Problem C
The following is dictionary representation of equation (2.1)
     maximize     z =      5*x1 + 4*x2 + 3*x3
     subject to  s1 = 5  - 2*x1 - 3*x2 -   x3
                 s2 = 11 - 4*x1 -   x2 - 2*x3
                 s3 = 8  - 3*x1 - 4*x2 - 2*x3
                  s1, s2, s3, x1, x2, x3 >= 0
The basic feasible solution corresponding to this dictionary is
     s1 = 5, s2 = 11, s3 = 8, x1 = 0, x2 = 0, x3 = 0
Keeping  x1 and  x2 equal to zero, and using the equations above for the values of  s1,  s2 and  s3, there is a maximum value of  x3 that corresponds to a feasible solution. What is the corresponding feasible solution and value for  z ?

Solution
     x1 = 0
     x2 = 0
     x3 = 4
     s1 = 5  -   x3 = 1
     s2 = 11 - 2*x3 = 3
     s3 = 8  - 2*x3 = 0  
      z =      3*x3 = 12

Problem D
We are given the following dictionary representation of a problem
     maximize     z =      4*x1 + 4*x2
     subject to  s1 = 6  - 2*x1 - 4*x2 
                 s2 = 20 - 4*x1 -   x2
                 s1, s2, x1, x2  >= 0
The first constraint equation above can be written as
                 x1 = 3 - 2*x2 - .5*s1
Replace the equation for  s1 above by this equation, and then use this equation to replace  x1 in the equations for  z and  s2 above. What is the resulting dictionary representation of the problem above ?

Solution
     maximize     z =      4*(3 - 2*x2 - .5*s1) + 4*x2
     subject to  x1 = 3 - 2*x2 - .5*s1
                 s2 = 20 - 4*(3 - 2*x2 - .5*s1) -   x2
                 s1, s2, x1, x2  >= 0

     maximize     z = 12  - 4*x2 -  2*s1 
     subject to  x1 = 3   - 2*x2 - .5*s1
                 s2 = 8   + 7*x2 +  2*s1
Input File: Quiz0622.omh