INTEGER PROGRAMMING – PROB # 1
(Integer Programming – Formulation)
Northeastern Airlines is considering the purchase of new long-,
medium-, and short-range jet passenger airplanes. The purchase price
would be $67 million for each long-range plane, $50 million for each
medium-range plane, and $35 million for each short-range plane. The
board of directors has authorized a maximum commitment of $1500
million for these purchases. Regardless of which airplanes are
purchased, air travel of all distances is expected to be sufficiently
large that these planes would be utilised at essentially maximum
capacity. It is estimated that the net annual profit (after capital
recovery costs are subtracted) would be $4.2 million per long-range
plane, $3 million per medium-range plane, and $2.3 million per short-
range plane.
It is predicted that enough trained pilots will be available to the
company to crew 30 new airplanes. If only short-range planes were
purchased, the maintenance facilities would be able to handle 40 new
1
planes. However, each medium-range plane is equivalent to 1 short-
3
2
range planes, and each long-range plane is equivalent to 1 short-
3
range planes in terms of their use of the maintenance facilities.
The information given here was obtained by a preliminary analysis of
the problem. A more detailed analysis will be conducted subsequently.
However, using the preceding data as a first approximation,
management wishes to know how many planes of each type should be
purchased to maximise profit.
Reference: Hillier, F.S., G.J. Liberman, B. Nag, and P. Basu,
Introduction to Operations Research, 9th edition, Tata McGraw-Hill.
Page 1 of 3
INTEGER PROGRAMMING – PROB # 2
(Integer Programming – Formulation)
An automobile company is considering manufacturing three types of
cars (compact, midsize, and large) and two types of minivans (midsize
and large). The resources required and the profit contributions yielded
by each type of vehicle are shown in Exhibit 1. At present, 6500 tons
of steel and 65,000 hours of labor are available. If any vehicles of a
given type are produced, production of that type of vehicle is
economically feasible only if at least a minimal number of that type
are produced. These minimal numbers are also listed in Exhibit 1.
Develop an Integer Programming model to obtain an optimal
production schedule. What will be the optimal solution if the steel
availability changes to 6000 tons?
Exhibit 1
Compact Mid-Size Mid-Size Large
Vehicle Type Large Car
Car Car Minivan Minivan
Steel (tons)/unit 1.5 3 5 6 8
Labour (hours)/unit 30 25 40 45 55
Minimum Production
1000 1000 1000 200 200
(if any)
Profit Contribution
100000 125000 150000 275000 350000
per unit (`)
Reference: Albright, S.C., and W.L. Winston, Management Science
Modeling, 4th edition, Cengage Learning.
Page 2 of 3
INTEGER PROGRAMMING – PROB # 3
A company manufactures three different products: A, B, and C. The
per-unit profit margins for the three products are $6, $10, and $5. The
products could be manufactured using one of two processes. The per-
unit production requirements for each product for each process is
given in the table below:
Per-unit production requirements
Product A Product B Product C Hours available
Process
(hours) (hours) (hours) (per week)
1 4 6 3 2000
2 5 7 4 2400
The demand for product A is predicted to be between 50 and 100 units
per week, demand for product B is predicted to be between 150 and
200 units per week, and demand for product C is predicted to be
between 100 and 150 units per week.
If the company decides to use process 1, it will incur a setup cost of
$100 and the setup will take 24 hours. If the company decides to use
process 2, it will incur a setup cost of $80 and the setup will take 18
hours. If the company wants to use only one of the two processes,
develop an integer programming model to determine the production
schedule that will maximise the profits for the company.
Page 3 of 3