Problem 1 - Consider the following all-integer linear program:
Max 1x1 + 1x2
s.t.
4x1 + 6x2 ≤ 22
1x1 + 5x2 ≤ 15
2x1 + 1x2 ≤ 9
x1, x2 ≥ 0 and integer
a. Graph the constraints for this problem. Use dots to indicate all feasible integer solutions.
b. Solve the LP Relaxation of this problem.
c. Find the optimal integer solution.
Problem 2 - Consider the following all-integer linear program:
Max 10x1 + 3x2
s. t.
6x1 + 7x2 ≤ 40
3x1 + 1x2 ≤ 11
x1, x2 ≥ 0 and integer
a. Formulate and solve the LP Relaxation of the problem. Solve it graphically, and round down to find a feasible solution. Specify an upper bound on the value of the optimal solution.
b. Solve the integer linear program graphically. Compare the value of this solution with the solution obtained in part (a).
c. Suppose the objective function changes to Max 3x1 1 6x2. Repeat parts (a) and (b).
Problem 3 - 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.
Only two of projects 1, 3, 5, and 6 must be undertaken. If a project is undertaken it has a value of 1, otherwise 0. Therefore, the sum of these variables must equal 2.
x1 + x3 + x5 + x6 = 2
b. Write a constraint modeling a situation in which, if projects 3 and 5 must be under- taken, they must be undertaken simultaneously.
x3 - x5 = 0 or x5 - x3 = 0
c. Write a constraint modeling a situation in which project 1 or 4 must be undertaken, but not both.
x1 + x4 = 1
d. Write constraints modeling a situation where project 4 cannot be undertaken unless projects 1 and 3 also are undertaken.
x4 ≤ x1 or x4 ≤ x3
-x1 + x4 ≤ 0 -x3 + x4 ≤ 0
e. Revise the requirement in part (d) to accommodate the case in which, when projects 1 and 3 are undertaken, project 4 also must be undertaken.
x4 ≥ x1 + x3 - 1
-x1 - x3 + x4 ≥ -1
Problem 4 - 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 three years are summarized as follows:
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 test marketing of the new product is carried out, the advertising campaign also must be conducted. Modify your formulation of part (b) to reflect this new situation.
Problem 5 - Hart Manufacturing makes three products. Each product requires manufacturing operations in three departments: A, B, and C. The labor-hour requirements, by department, are as follows:
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 total 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?
Problem 6 - 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 customer service during each hour of operation is summarized in the following table.
Each full-time employee starts on the hour and works a 4-hour shift, followed by 1 hour for lunch and then a 3-hour shift. Part-time employees work one 4-hour shift beginning on the hour. Considering salary and fringe benefits, full-time employees cost the bank $15 per hour ($105 a 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 for the optimal schedule of tellers. Comment on the solution.
d. After reviewing the solution to part (c), the bank manager 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.