Read Chapter 9 Sections 1,2, (you may skip piecewise linear functions), and Sections 3,4,9.

Submit the following two problems:

(1).  A company produces 3 types of computers using raw material and labor.  If any of type i computer is produced, there is a set-up cost, given in the table below.  In such a case, at least 10 units of that computer type must be produced (in other words, the number of each type of computer produced is either zero or ≥ 10). A total of 130 units of raw material and 40 hours of labor are available each week.

Formulate an integer program to maximize the weekly proit.  Let x1, x2, x3 be the number of computers of type 1,2,3 produced. Make sure to clearly deine any additional variables you are using in the formulation.

(2).  (a) An Integer Programming problem in which x1  and x3 must be integer is being solved using the branch and bound method. The optimal solution to subproblem 1 (the LP relaxation) is z = 13.6, x1  = 2.9, x2  = 3.3, x3 = 4.7. The branches to be added in order to get subproblems 2 and 3 are:

(i) x1 ≤ 2 and x3 ≤ 4.

(v) other (none of the above).

(b). An Integer Programming problem in which all variables must be integer is being solved using the cutting plane method. The optimal tableau for the LP relaxation is given below. What is a cut to be added next is:

Additional practice problems - do not turn these in:

Problem 1 Section 9-2 (page 502).

Problem 12 Section 9-2 (page 503).

Problem 6 Section 9-3 (page 522).

Consider problem 2 of Section 9-8 (page 549). Find a cutting plane based on the given table, using the second constraint (the last row of the table). No need to solve the new LP.

For each of the following state whether TRUE or FALSE.

(a). When using the branch and bound approach to solve an integer programming problem, the LP relaxation has x1  = 2.9, and all other variables are integer. The branches added to the sub problems are x1  ≤ 2 and x1 ≥ 2.