QUANT 162: Intermediate Operations Research

Problem Set: Advanced Linear Programming

Instructions:
Formulate each problem as a Linear Programming model. Show complete model including definition
of variables, objective function, and constraints.

Problem Set:

1. Automobile traffic from three highways, H1, H2, and H3, must stop and wait for a green light before
exiting to a toll road. The tolls are $3, $4, and $5 for cars exiting from H1, H2, and H3, respectively.
The flow rates from H1, H2, and H3 are 500, 600, and 400 cars per hour. The traffic light cycle may
not exceed 2.2 minutes, and the green light on any highway must be at least 25 seconds. The yellow
light is on for 10 seconds. The tollgate can handle a maximum of 510 cars per hour. Assuming that no
cars move on yellow, determine the optimal green time interval for the three highways that will
maximize tollgate revenue per traffic cycle. Formulate an LP model.

2. A small engineering consulting firm is establishing its plan for the next year. The director and the
three partners are to meet to decide which projects to pursue.

Preliminary research has been done on eight projects. The expected profit for each project is given in
the following table together with the number of person-days of background preparation each will
require and the computer processing unit (CPU) time (in hours) each will use.

Project Profit Person-Days CPU

1 2.1 550 200
2 0.5 400 150
3 3.0 300 400
4 2.0 350 450
5 1.0 450 300
6 1.5 500 150
7 0.6 350 200
8 1.8 200 600

Excluding downtime, it is estimated that 1000 CPU hours will be available through the year. Presently
there are 10 engineers (including the director and the partners); each works 240 days per year. At
most three engineers could be let go, and management does not want to hire any new engineers for
next year, due to market uncertainties. A minimum of 3 projects need to be selected, so each partner
will be in charge of at least one project for the year. The director has four favorite projects (3,4,5,8)
and the company needs to select at least one of these.

The firm wishes to formulate an optimization model to determine which projects to undertake for the
year.

3. E.J. Korvair Department Store has $1,000 in available cash. At the beginning of each of the next six
months, E.J. will receive revenues and pay bills as shown in the table below. It is clear that E.J. will
have a short-term cash flow problem until the store receives revenues from the Christmas shopping
season. To solve this problem, E.J. must borrow money.

At the beginning of July, E.J. may take out a six-month loan. Any money borrowed for a six-month
period must be paid back at the end of December along with 9% interest (early payback does not
reduce the interest cost of the loan). E.J. may also meet cash needs through month-to-month
borrowing. Any money borrowed for a one-month period incurs an interest cost of 4% per month.
Use linear programming to determine how E.J. can minimize the cost of paying bills on time.

Month Revenues ($) Bills ($)

 July 1,000 5,000
August 2,000 5,000
September 2,000 6,000
October 4,000 2,000
November 7,000 2,000
December 9,000 1,000

4. A nationalized company can either manufacture capital goods or consumer goods. The company’s
production is being planned over a three-period horizon. At the beginning of period 1, the company
has 100 units of capital goods and 50 units of consumer goods in stock. Each unit of capital good can
be used to produce either 3 new units of capital goods at the expense of 3 units of consumer goods to
be provided from stock or 10 units of consumer goods, over an uninterrupted two-period interval, at
the end of which the unit of capital goods again becomes available for use. Once capital goods are
produced they can be used for production in subsequent periods. If necessary, capital goods can also
be left idle. The company will sell everything in its stock at the beginning of period 4 and close down.
The company can also sell either capital or consumer goods in any period according to the following
price schedule:

  $ / unit
Period Capital Good Consumer Good
1 $ 4.00 $ 0.10
2 $ 6.00 $ 0.15
3 $ 8.00 $ 0.15
4 $ 3.00 $ 0.10

Formulate as an LP model.

5. A company is in the process of divesting their properties at the end of 4 years. The company can
produce two kinds of products, namely product A and product B. Currently, the company has 75 units
of product A and 50 units of product B. Products A and B has a special relation such that product A
can be used to produce both products A and B. Specifically, each unit of product A can be used to
produce 3 units of product A (at the expense/consumption of 2 units of product B). On the other
hand, each unit of product A can also be used to produce 8 units of product B. When you use a unit
of product A, it will have to be used continuously for 2 years, after which it (the unit of product A) will
be available again for production. Instead of using the products for further production, you can sell
the products to the market. The table below gives you a summary of the price at which you can sell
product A and B.

Year Product A Price Product B Price

1 P10.00 P3.00
2 P12.00 P4.00
3 P15.00 P4.00
4 P10.00 P5.00

Formulate a linear programming problem that maximize the amount of money the company will get
after selling everything they have at the end of year 4 (assume you sell the two products at the end of
each year).

6. A machine shop has one drill press and five milling machines, which are to be used to produce an
assembly consisting of two parts, 1 and 2. The productivity of each machine for the two parts is given
below:
Production Time in minutes per piece
Part Drill Mill
1 3 20
 2 5 15
It is desired to maintain a balanced loading on all machines such that no machine runs more than 30
minutes per day longer than any other machine (assume that the milling load is split evenly among all
five milling machines).

Formulate a linear program to divide the work time of each machine to obtain the maximum number
of completed assemblies assuming an 8-hour working day.

7. You have been put in charge of the Dawson Creek oil refinery. The refinery produces gas and heating
oil from crude oil. Gas sells for $11 per barrel and must have an average grade level of at least 9.
Heating oil sells for $6 a barrel and must have an average grade level of at least 7. At most, 2000
barrels of gas and 600 barrels of heating oil can be sold.

Incoming crude can be processed by one of three methods. The per barrel yield and per barrel cost of
each processing method are shown in the table below:
Grade
Method 6 8 10 Cost ($ per barrel)
1 .2 .2 .6 3.40
2 .3 .4 .3 3.00
3 .4 .4 .2 2.60
For example, if we refine one barrel of incoming crude by method 1, it costs us $3.40 and yields .2
barrels of grade 6, .2 barrels of grade 8 and .6 barrels of grade 10. These costs include the costs of
buying the crude oil.

Before being processed into gas and heating oil, grades 6 and 8 may be sent through the catalytic
cracker to improve their quality. For $1 per barrel, one barrel of grade 6 can be “cracked” into a
barrel of grade 8. For $1.50 per barrel, a barrel of grade 8 can be cracked into a barrel of grade 10.
Determine how to maximize the refinery’s profit.

8. Sailco Corporation must decide how many sailboats should be produced during each of the next 4
quarters. Demand is as follows: 1st quarter: 40 sailboats, 2nd quarter: 60 sailboats, 3rd quarter: 75
sailboats, 4th quarter: 25 sailboats. At the beginning of the first quarter, Sailco has an inventory of 10
sailboats. At the beginning of each quarter, Sailco must decide how many sailboats should be
produced during the current quarter. During each quarter, Sailco can produce up to 40 sailboats at a
cost of $400 per sailboat. By having employees work overtime during a quarter, Sailco can produce
additional sailboats at a cost of $450 per sailboat for a maximum of 10 sailboats per quarter in
overtime. At the end of each quarter (after demand has been satisfied), a holding cost of $20 per
sailboat is incurred.
Assuming that demand could be back-logged at a cost of $30 / sailboat / month and that sailboats can
be held in inventory for a maximum of 2 quarter (after production), formulate an LP model that will
minimize Sailco’s costs.

9. The following figure shows the ceiling locations of five (5) sensors in a new factory relative to a
coordinate system (in meters) with origin at the lower left. A control box must be located anywhere
on the ceiling (20 meters x 40 meters) with cables running rectilinearly to each sensor. The designers
want to place the control box to minimize the cable required. Furthermore, the length of cable used
by the farthest (in terms of rectilinear distance) sensor from the control box must be at most 30
meters. Formulate a linear program that models the problem.
10. CSI Corporation produces cabinets. Each week, it requires 90,000 cu ft of processed lumber. The
company may obtain lumber in two ways. First, it may purchase lumber from an outside supplier and
then dry it in the supplier’s kiln. Second, it may chop down logs on its own land, cut them into lumber
at its sawmill, and finally dry the lumber in its own kiln. Brady can purchase grade 1 or grade 2
lumbers. Grade 1 lumber costs $3 per cu ft and when dried yields 0.7 cu ft of useful lumber. Grade 2
lumber costs $7 per cu ft and when dried yields 0.9 cu ft of useful lumber.

It costs the company $3 to chop down a log. After being cut and dried, a log yields 0.8 cu ft of lumber.
CSI Corporation incurs $4 per cu ft of lumber dried. It costs $2.50 per cu ft of logs sent through the
sawmill. Each week the sawmill can process up to 35,000 cu ft of lumber. Each week, up to 40,000 cu
ft of grade 1 lumber and up to 60,000 cu ft of grade 2 lumber can be purchased. Each week, 40 hours
of time are available for drying lumber. The time it takes to dry 1 cu ft of grade 1 lumber, grade 2
lumber, or logs is as follows: grade 1 – 2 seconds; grade 2 – 0.8 second; logs – 1.3 seconds.

Formulate an LP to help CSI Corporation minimize the weekly cost of meeting the demand for
processed lumber.

11. In an episode in the TV series: Numb3rs, Don Eppes (who works with the Federal Bureau of
Investigation or FBI) works with Charlie Eppes (a math genius) on an arson case (Arson is a criminal
offense where the criminal intentionally burns a property usually for insurance claims). Charlie claims
that a fire can have a unique “fingerprint” that can identify what type of arsonist an arson case has.
Using Charlie’s theory of “fingerprinting” fires, he has come up with 9 characteristics of every fire
(fuel, burn rate, scorch marks, smoke patterns, flame temperature, igniter, point of origin, intent and
results) rated with a number between 1 and 100.

In order to properly “fingerprint” a fire to an arsonist, Charlie is trying to come up with a linear
equation (as a function of the ratings of the 9 fire characteristics) that will give a fingerprint rating to
each fire case. The linear system is seen below:

0 ≤∝1 ≤1 , ∑ ∝i =1
F ( x 1 , x 2 , … , x 9 ) =∝1 x 1+∝2 x 2 +…+∝9 x 9 where
{ i
0≤ x i ≤ 100
Given a table (below) of 10 past fire cases (with their respective ratings for each of the 9
characteristics) with known arsonists (with a specific arsonist rating), develop a linear program to help
Charlie determine F(x1, x2, … , xn) given the 10 known arson cases and their known criminal.

Characteristic Case 1 Case 2 Case 3 Case 4 Case 5 Case 6 Case 7 Case 8 Case 9 Case 10
Fuel 57 12 98 54 74 15 62 35 39 40
Burn Rate 78 45 87 45 78 65 48 47 56 97
Scorch Marks 12 54 84 68 15 57 57 98 32 52
 Smoke 54 78 34 65 45 78 37 16 34 78
Patterns
Flame Temp 41 45 47 35 98 72 65 45 75 78
Igniter 67 87 12 47 87 11 15 66 55 21
Pt. of Origin 15 65 87 23 56 26 45 24 54 78
Intent 10 12 23 23 25 56 87 45 49 78
Results 75 89 98 12 48 78 56 26 35 48
Arsonist 1 1 5 3 4 5 3 5 2 2
Number

Arsonist Number Fingerprint rating

1 78
2 84
3 81
4 68
5 75

12. Mr. Smith is an avid gardener, and each spring he must plan what to plant in his vegetable garden. He
grows tomatoes (3 types), eggplants, zucchini and green peppers. He would like his garden to provide
a rich harvest of these vegetables so that he has fresh vegetables throughout the late summer and
fall, as well as frozen vegetables for the winter.

He has constructed the table below to help decide what to plant.

Weeks until first Yield per week / Length of Harvest

ft2/plant Hours / week
harvest plant (pds) (wks)
Beef Steak
9 0.1 10 2 10
Tomato
Better Boy
8 0.1 9 2 8
Tomato
Rutgers Tomato 7 0.15 6 1.5 10
Eggplant 8 0.05 8 1 8
Zucchini 10 0.05 6 3 10
Green Pepper 3 0.05 8 1 10

For each vegetable, he needs to decide the number of plants to grow. Each plant will occupy a certain
amount of area in the garden, as noted in the second column. His garden is 2000 square feet in total.

Also, each plant requires a certain amount of labor each week (third column), to weed, fertilize, water
and harvest. For instance, each Beefsteak tomato plant requires 0.1 hour per week. This labor
requirement starts when it is planted, and won’t end until the end of the harvest, 20 weeks later (i.e.,
the labor requirements continue even after the plant stops yielding produce.). Mr. Smith hires a
neighborhood girl at $8 per hour to do this work for him. However, he expects that the neighborhood
girl has only 25 hours to work each week, as she is also attending summer school.

Mr. Smith plants the entire garden on June 1. The fourth column indicates how many weeks until he
gets the first fresh vegetables from each plant type. Once the plant is yielding vegetables, he
estimates that he can harvest a fixed number of pounds per week, as given in the fifth column. This
harvest will go for a number of weeks, as noted in the sixth column. For instance, a Rutgers plant
produces 1.5 pounds of tomatoes each week for a ten-week period, namely from week 7 through to
week 16.

The growing season is from week 7 to week 20. During the growing season Mr. Smith will consume
10 pounds of fresh tomatoes each week. He insists on eating those that he grows.

In addition to eating his tomatoes, each week Mr. Smith has the option to freeze fresh tomatoes for
use in the winter. By week 20, he needs to have 250 pounds of frozen tomatoes. The tomatoes that
he freezes must come from his garden; he will not buy tomatoes for this use. Any leftover tomatoes
can be sold at the market at the market price. He expects that the market price will be $4 per pound
 for week 7, and then will drop in price by $.20 per pound every week thereafter. Thus, he expects in
week 20 the price per pound will be $1.40.

Mr. Smith uses the other vegetables to make vegetable soup that he stores for consumption in the
winter. His recipe calls for 1 pound of zucchini and 2 pounds of green peppers for every pound of
eggplant; this recipe will make 4 pounds of soup. To make the soup, all of the vegetables must be
fresh; that is, the vegetables were picked in the same week that the soup is made. By the end of the
season, he needs to have 200 pounds of soup prepared for the winter. Any leftover vegetables can be
used to make more soup to be sold at the market. Mr. Smith expects that he will be able to sell up to
2000 pounds of soup for $5 per pound. Excess eggplants, or zucchini or green peppers cannot be sold
and are put into the compost pile.

Formulate the problem as a linear programming model.

13. Greydog Bus Company operates buses between Boston and Washington DC. A bus trip between
these two cities takes 6 hours. Federal law requires that a driver rest for four or more hours between
trips. A driver’s workday consists of two trips: one from Boston to Washington and one from
Washington to Boston (or vice-versa). The table below gives the departure times for the buses.
Greydog’s goal is to minimize the total downtime for all drivers. How should Greydog assign crews to
trips? Develop a linear programming model. Note: It is permissible for a driver’s “day” to overlap
midnight. For example, a Washington-based driver can be assigned to the Washington-Boston 3 pm
trip and the Boston Washington 6 am trip. (25 pts)

Trip Departure Time Trip Departure Time

Boston 1 6:00 am Washington 1 5:30 am
Boston 2 7:30 am Washington 2 9:00 am
Boston 3 11:30 am Washington 3 3:00 pm
Boston 4 7:00 pm Washington 4 6:30 pm
Boston 5 12:30 am Washington 5 12:00 am