Instructions: Attached are some sample exam questions so you can see the type of questions I ask. The final exam will have three or four questions. You are responsible only for what I covered in class. The exam is designed to be done in 90 minutes, though we will start at 8AM on December 10 to give you a few extra minutes. The exam will end at 9:55 sharp. Note that these are sample problems from previous years that might have had a slightly different emphasis.
Problem 1. [25] A customer has a portfolio of investments and wishes to determine if she has the optimal portfolio over all possible investments. Each investment has three properties:
The customer has $1,000 to invest, and wishes to maximize the average percentage return (with uninvested money assumed to have zero return) subject to the average quality being at most 6 and the fraction of money spent in ``socially good'' investments being at least 40%. Currently she is investing in three investments as follows:
She has formulated and solved a linear program for her problem, and has the following results:
MAX 1.12 A + 1.07 B + 1.09 C
SUBJECT TO
2) A + B + C <= 1000
3) A - 4 B - C <= 0
4) - 0.4 A + 0.6 B + 0.6 C >= 0
END
OBJECTIVE FUNCTION VALUE
1) 1106.6666
VARIABLE VALUE REDUCED COST
A 600.000000 0.000000
B 66.666672 0.000000
C 333.333313 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 1.107
3) 0.000000 0.007
4) 0.000000 -0.017
(a) For each of the following investments, determine whether the investment can possibly improve her current portfolio:
(b) What would be the maximum quality rating permited for a ``good'' investment with return 1.10 in order to be considered for improvement of the current (A,B,C) portfolio?
Problem 2. [25] Everything-Jelly creates specialty packages of mixed jellybeans. Each package contains exactly 100 jellybeans, which differ only in color. The possible colors are Red, Blue, Green, and Purple. Currently, Everything-Jelly has 1 million of each color jellybean. The goal is to maximize the revenue that results from the sale of the produced packages. Any mixture of 100 jellybeans is possible, with the following restrictions:
(a) Formulate this problem in a manner suitable for solution by variable generation (hint: you should have a variable for each feasible package contents).
(b) Take the following feasible packages, and show the above formulation restricted to these packages:
A) 10 Red, 10 Blue, 10 Green, 70 Purple
B) 10 Red, 10 Blue, 70 Green, 10 Purple
C) 10 Red, 70 Blue, 10 Green, 10 Purple
D) 70 Red, 10 Blue, 10 Green, 10 Purple
(c) Given dual values for each constraint in your formulation (call
then 
, formulate the subproblem to be solved to
determine if there is a pattern that can improve on the current mix of
patterns.
(d) How will you know when the current mix of patterns is optimal?
Problem 4. [25] The concentrator
location problem is as follows: There are n locations embedded
in the Euclidean plane (so the distance between 
and
is 
). The problem is to
label some of these as concentrators and to assign each location
to be served by some concentrator. A concentrator services
itself and a number of other locations. For our purposes, we will
assume that a concentrator services exactly 5 locations (including
itself). The cost associated with a set of concentrators is the total
distance from each location to the concetrator serving it. The
following diagram shows a feasible solution for a particular instance.
(a) Assume the set of concentrators is known. Give a greedy algorithm for assigning the service for the other locations. Completely describe the steps of this heuristic and state why the heuristic is a greedy heuristic.
(b) Now assume that the concentrators are not known, so the goal is to both choose the concentrators and to assign service. Give a break-combine heuristic for this problem. Completely describe the steps of this heuristic and state why the heuristic is a break-combine heuristic.
Problem 1. [25]
A glass cutting concern takes long rods of glass and cuts them into smaller pieces. On a particular day, there are a large number of rods of length 100. The cost of a cutting pattern is taken to be $100, unless the number of pieces is more than 3, in which case the cost is $110 to account for the more complicated setup. The objective is to meet the following orders at minimum cost:
(a) Formulate the problem of minimizing the number of rods
used by creating a variable for each feasible cutting pattern. For
each feasible cutting pattern i, let 
be the number of
20 length rods, 
be the number of 30 length rods, and so
on. Let 
be the cost of pattern i. You should have one
constraint for the demand for 20 lengths, one for 30 lengths, and so
on.
(b) Consider the following cutting patterns:
A: 5x20
B: 3x30
C: 2x40
D: 2x50
Give the formulation in (a) restricted to these cutting patterns.
(c) Suppose the dual variables corresponding to the constraints are as follows:
Formulate a subproblem or subproblems to determine if there exists a pattern to add to improve the current solution. Give an example of a improving pattern and of a pattern whose addition will not improve the current solution.
Problem 2. [25]
Consider the following manufacturing system: a set of jobs must be
assigned to a number of machines. Each job must be assigned to
exactly one machine. If job j is assigned to machine i, a cost of
is incurred. Job j takes 
units of time on machine
i. Each machine has only k time units available. If a job is
not assigned to any machine, a cost of 100 is charged.
For instance, for four jobs and three machines, the data might be:
Cost:
Time:
with 7 time units available on each machine. The objective is to minimize the cost subject to assigning each job to a machine.
(a) Give a greedy heuristic for this problem. Illustrate your heuristic using the above data.
(b) Give an exchange heuristic for this problem. Illustrate your heuristic with the above data. You may use either your heuristic solution in part (a) as a starting heuristic or any other starting point that illustrates a successful exchange.
Problem 4. [25] [MSTC Note: most of these are from readings different than yours]. Consider the following statements about the readings. For each statement, note if it is true or false. If the statement is false, briefly explain why the statement is false.
(a) In ``Optimizing Flight Crew Schedules'' by Ira Gershkoff, the method presented determines the optimal crew schedules.
(b) In ``Natural Resource Land Management ...'' by Kent et al. the system designed has been implemented at some national forests.
(c) In ``The Solution of Large 0-1 Integer Programming Problems encountered in Automated Cartography'' the cost of a label assignment equals the euclidean distance from the label to the point being labeled.
(d) In ``A minimal technology routing system for Meals on Wheels'', it is necessary to start from the beginning when a new customer is added.
(e) In ``Devising a cost effective schedule for a baseball league'', the schedule they create was not actually used by the league.
Problem 3. [25] Consider the statistics of the following baseball players (don't worry, you need know nothing about baseball):
To analyze this using DEA, we can treat ``At Bats'' as the input (an ``At Bat'' is an opportunity to get a hit). THere are two types of outputs: ``Home Runs'' and ``Hits''. The efficiency of a player is his ability to turn ``At Bats'' into ``Hits'' and ``Home Runs''.
The following is a linear program from a DEA calculation. For which player is this linear program designed? Is that player efficient? If not, what combination of players prove that he is not efficient and what is his efficiency rating?
MIN TH
SUBJECT TO
2) - 226 TH + 272 L1 + 226 L2 + 205 L3 + 236 L4 <= 0
3) 19 L1 + 11 L2 + 3 L3 + 8 L4 >= 11
4) 76 L1 + 62 L2 + 64 L3 + 64 L4 >= 62
END
: go
LP OPTIMUM FOUND AT STEP 0
OBJECTIVE FUNCTION VALUE
1) 0.94499481
VARIABLE VALUE REDUCED COST
TH 0.944995 0.000000
L1 0.524292 0.000000
L2 0.000000 0.055005
L3 0.346154 0.000000
L4 0.000000 0.096234