Bowie State University Integer Linear Programming Worksheet

Problem 1

Botswana Electronics Company (BEC), is contemplating a research and development program encompassing eight major projects. The company is constrained from embarking on all of the projects by the number of available scientists (40) and the budget available for the projects ($300,000). In the following are the resource requirements and the estimated profit for each project..

a) Using binary variables write down an algebraic formulation of an integer (linear) programming formulation for this problem. Document your algebraic model so that it is clear what the variables, constraints, and objective function mean b) Implement your model in Solver. Document your model appropriately so it is possible to identify the decision variables, objective function, and constraints without going into Solver. Paste a screenshot of the model here. Use “FORMULATEXT” in your model to show calculations.

c) Based on the solution to your model, what is the maximum profit? Which projects should be selected to achieve this profit?

d) Suppose projects 3 and 7 are mutually exclusive. That is, BEC should not undertake both. Write down a linear constraint that implements this condition.

e) Add the constraint from part d into your model and reoptimize your model. Do this in a separate worksheet. (You can right click the name of the original sheet of your model and select move or copy. Then make a copy of your original sheet, rename it and then make changes to the solver model therein).

f) What is the revised project portfolio and the revised maximum profit?

Problem 2

Reservation Scheduling: Roth Auto Rentals, a car rental company specializing in SUVs, is making up a schedule for the next weekend’s demands. The peak demand period occurs on the weekend, when Roth may not have enough SUVs to meat demand. The customer demands that have been logged in are listed below.

The rental cost depends on which days the contract covers, as shown in the next table.

Roth Auto Rentals carries only one type of vehicle and expects to have 10 SUVs available for rent over the weekend.

• a)Provide the complete integer linear programing formulation. Clearly specify decision variables, objective function and constraints.
• b)Build a model in Excel and paste a screenshot here. Use “FORMULATEXT” in your model to show calculations.
• c)What is the maximum revenue that can be generated from the list of orders?
• d)In the optimal solution of (a), what percentage of customer demand is satisfied?
• e)In the optimal solution of (a), what percentage of dollar demand is satisfied?
• f)Answer the set of three questions above for fleet sizes of 11-16. You might want to adjust your model so you can use SolverTable and create a table to report your answers concisely.