Integer Programming Problems |

**Problem 1**

The following questions refer to a capital budgeting problem with six projects represented by 0 - 1 variables x1, x2, x3, x4, x5, and x6.

**a.** Write a constraint modeling a situation in which two
of the projects 1, 3, 5, and 6 must be undertaken.

**b.** Write a constraint modeling a situation in which
projects 3 and 5 must be undertaken simultaneously.

**c.** Write a constraint modeling a situation in which
projects 1 or 4 must be undertaken, but not both.

**d.** Write constraints modeling a situation where project
4 cannot be undertaken unless projects 1 and 3 also are
undertaken.

**e.** Revise the requirement in part (d) to accommodate
the case in which, when projects 1 and 3 are undertaken, project
4 must also be undertaken.

**Problem 2**

Spencer Enterprises is attempting to choose among a series of new investment alternatives. The potential investment alternatives, the net present value of the future stream of returns, the capital requirements, and the available capital funds over the next 3 years are summarized as follows:

Alternative | Net present Value ($) |
Capital | Requirements | ($) |

Year 1 | Year 2 | Year 3 | ||

Limited warehouse expansion | 4,000 | 3,000 | 1,000 | 4,000 |

Extensive warehouse expansion | 6,000 | 2,500 | 3,500 | 3,500 |

Test market new product | 10,500 | 6,000 | 4,000 | 5,000 |

Advertising campaign | 4,000 | 2,000 | 1,500 | 1,800 |

Basic research | 8,000 | 5,000 | 1,000 | 4,000 |

Purchase new equipment | 3,000 | 1,000 | 500 | 900 |

Capital funds
available |
10,500 | 7,000 | 8,750 |

**a.** Develop and solve an integer programming model for
maximizing the net present value.

**b.** Assume that only one of the warehouse expansion
projects can be implemented. Modify your model of part (a).

**c.** Suppose that, if the test marketing of the new
product is carried out, the advertising campaign must also be
conducted. Modify your formulation of part (b) to reflect this
new situation.

**Problem 3.**

Hart Manufacturing makes three products. Each product requires manufacturing operations in three departments: A, B, and C. The labor-hour requirements, by department, are

Department |
Product 1 |
Product 2 |
Product 3 |

A | 1.50 | 3.00 | 2.00 |

B | 2.00 | 1.00 | 2.50 |

C | 0.25 | 0.25 | 0.25 |

During the next production period, the labor-hours available are 450 in department A, 350 in department B, and 50 in department C. The profit contributions per unit are $25 for product 1, $28 for product 2, and $30 for product 3.

**a.** Formulate a linear programming model for maximizing
total profit contribution.

**b.** Solve the linear program formulated in part (a). How
much of each product should be produced and what is the projected
profit contribution?

**c.** After evaluating the solution obtained in part (b),
one of the production supervisors noted that production setup
costs had not been taken into account. She noted that setup costs
are $400 for product 1, $550 for product 2, and $600 for product
3. If the solution developed in part (b) is to be used, what is
the total profit contribution after taking into account the setup
costs?

**d.** Management realized that the optimal product mix,
taking setup costs into account, might be different from the one
recommended in part (b). Formulate a mixed-integer linear program
that takes setup costs into account.

**e.** Use a computer code to solve the mixed-integer
linear program formulated in part (d). How much of each product
should be produced and what is the projected total profit
contribution? Compare this profit contribution to that obtained
in part (c).

**Problem 4.**

The Northshore Bank is working to develop an efficient work schedule for full-time and part-time tellers. The schedule must provide for efficient operation of the bank including adequate customer service, employee breaks, and so on. On Fridays the bank is open from 9:00 a.m. to 7:00 p.m. The number of tellers necessary to provide adequate service during each hour of operation is summarized below.

Time | 9-10 | 10-11 | 11-12 | 12-1 | 1-2 | 2-3 | 3-4 | 4-5 | 5-6 | 6-7 |

Number of Tellers | 6 | 4 | 8 | 10 | 9 | 6 | 4 | 7 | 6 | 6 |

Each full-time employee starts on the hour and works a four-hour shift, followed by one hour for lunch and then a three-hour shift. Part-time employees work one four-hour shift beginning on the hour. Considering salary and fringe benefits, full-time employees cost the bank $15 per hour ($105 per day), and part-time employees cost the bank $8 per hour ($32 per day).

**a.** Formulate an integer programming model that can be
used to develop a schedule that will satisfy customer service
needs at a minimum employee cost. (Hint: Let xi = number of
full-time employees coming on duty at the beginning of hour i and
yi = number of part-time employees coming on duty at the
beginning of hour i.)

**b.** Solve the LP Relaxation of your model in part (a).

**c.** Solve the optimal schedule of tellers. Comment on
the solution.

**d.** After reviewing the solution to part (c), the bank
manager has realized that some additional requirements must be
specified. Specifically, she wants to ensure that one full-time
employee is on duty at all times and that there is a staff of at
least five full-time employees. Revise your model to incorporate
these additional requirements and solve for the optimal solution.