BUS 203 Quantitative Applications

Solutions to Assignment 8

Problem 7-2
Problem 7-3 thru 6
Problem 7-12

7-2.

a) x1=3.5; x2=4.5; OV= 12.5
b) There are 29 of them. Blue dots in the green area.
c) There are two optimal solutions x1=0; x2=6 and x1=2; x2=5, both have OV=12
d) We get x1=3; x2=4; OV=11. clearly not optimal.

7-3.
For a Min problem the LP relaxation would provide a Lower Bound . Since the LP relaxation is obtained by ignoring some constraints(integrality) the solution value would be better (lower) than if we had enforced those constraints.

7-4.
For a Min problem a feasible solution (obtained by rounding the LP solution or any other means) gives an Upper Bound . Since we are not interested in any solution whose value exceeds the value of this known solution.

7-5.
For a Max problem the LP provides an Upper Bound .

7-6.
For a Max problem rounding (to get a feasible solution would give a Lower Bound .
[go to top]

7-12.
Let Aj, Bj and Cj the shipments from warehouse A, B and C to customer j and YA, YB, and YC zero/one switch variables denoting whether warehouse A, B, and C will be used.

  MIN 15A1 + 32A2 + 21A3 + 9B1 + 7B2 + 6B3 + 11C1 + 18C2
    + 5C3 + 500YA + 750YB + 600YC
  SUBJECT TO
            A1 + B1 + C1 >= 200
            A2 + B2 + C2 >= 150
            A3 + B3 + C3 >= 175
            A1 + A2 + A3 - 525 YA <= 0
            B1 + B2 + B3 - 525 YB <= 0
            C1 + C2 + C3 - 525 YC <= 0
            YA + YB + YC >=   2
            Aj, Bj, Cj>=0, YA, YB, YC =0,1

Excel solution
[go to top]