Marketing Applications

Applications of linear programming in marketing are

numerous. In this section we discuss applications in media
selection and marketing research.

Media Selection

Relax-and-Enjoy Lake Development Corporation is developing

a lakeside community at a privately owned lake. The primary
market for the lakeside lots and homes includes all middle- and
upper-income families within approximately 100 miles of the
development. Relax-and-Enjoy has employed the advertising
firm of Boone, Phillips and Jackson (BP&J) to design the
promotional campaign.

After considering possible advertising media and the

market to be covered, BP&J has recommended that the first
month's advertising be restricted to five media. At the end of the
month, BP&J will then reevaluate its strategy based on the
month's results. BP&J has collected data on the number of
potential customers reached, the cost per advertisement, the
maximum number of times each medium is available, and the
exposure quality rating for each of the five media. The quality
rating is measured in terms of an exposure quality unit, a
measure of the relative value of one advertisement in each of the
media. This measure, based on BP&J's experience in the
advertising business, takes into account factors such as audience
demographics (age, income, and education of the audience
reached), image presented, and quality of the advertisement. The
information collected is presented in Table 1.
ADVERTISING MEDIA ALTERNATIVES FOR THE RELAX-AND-ENJOY LAKE
DEVELOPMENT CORPORATION
Advertising Media Number of Cost ($) Per Maximum Exposure
Potential Advertisement Times Quality
Customers Available Per Units
Reached Month*

1. Daytime TV (1 min),
station WKLA 1000 1500 15 65

2. Evening TV (30 sec),

station WKLA 2000 3000 10 90

3. Daily newspaper (full

page), The Morning 1500 400 25 40
Journal

4. Sunday newspaper
magazine (1/2 page 2500 1000 4 60
color), The Sunday Press

5. Radio, 8:00 A.M. or 5:00

P.M. news (30 sec), station 300 100 30 20
KNOP

* The maximum number of times the medium is available is either the maximum number
of times the advertising medium occurs (e.g., four Sundays per month or the maximum
number of times BP&J recommends that the medium be used).
Relax-and-Enjoy provided BP&J with an advertising budget of
$30,000 for the first month's campaign. In addition, Relax-and-
Enjoy imposed the following restrictions on how BP&J may
allocate these funds: At least 10 television commercials must be
used, at least 50,000 potential customers must be reached, and
no more than $18,000 may be spent on television
advertisements. What advertising media selection plan should be
recommended?
Marketing Research

An organization conducts marketing research to learn about

consumer characteristics, attitudes, and preferences. Marketing
research firms that specialize in providing such information
often do the actual research for client organizations. Typical
services offered by a marketing research firm include designing
the study, conducting market surveys, analyzing the data
collected, and providing summary reports and recommendations
for the client. In the research design phase, targets or quotas may
be established for the number and types of respondents to be
surveyed. The marketing research firm's objective is to conduct
the survey so as to meet the client's needs at a minimum cost.

Market Survey, Inc. (MSI), specializes in evaluating

consumer reaction to new products, services, and advertising
campaigns. A client firm has requested MSI's assistance in
ascertaining consumer reaction to a recently marketed household
product. During meetings with the client, MSI agreed to conduct
door-to-door personal interviews to obtain responses from
households with children and households without children. In
addition, MSI agreed to conduct both day and evening
interviews. Specifically, the client's contract called for MSI to
conduct 1000 interviews under the following quota guidelines.

1. Interview at least 400 households with children.

2. Interview at least 400 households without children.
3. The total number of households interviewed during the
evening must be at least as great as the number of households
interviewed during the day.
4. At least 40% of the interviews for households with children
must be conducted during the evening.
5. At least 60% of the interviews for households without
children must be conducted during the evening.

Because the interviews for households with children take

additional interviewer time and because evening interviewers
are paid more than daytime interviewers, the cost varies with the
type of interview. Based on previous research studies, estimates
of the interview costs are as follows:

Interview Cost

Household Day Evening

Children $20 $25

No children $18 $20

What is the household, time-of-day interview plan that will

satisfy the contract requirements at a minimum total
interviewing cost?
Financial Applications

In finance, linear programming has been applied in

problem situations involving capital budgeting, make-or-buy
decisions, asset allocation, portfolio selection, financial
planning, and many more. In this section, we describe a
portfolio selection problem.

Portfolio Selection

Portfolio selection problems involve situations in which a

financial manager must select specific investmentsfor example,
stocks and bondsfrom a variety of investment alternatives.
Managers of mutual funds, credit unions, insurance companies,
and banks frequently encounter this type of problem. The
objective function for portfolio selection problems usually is
maximization of expected return or minimization of risk. The
constraints usually take the form of restrictions on the type of
permissible investments, state laws, company policy, maximum
permissible risk, and so on. Problems of this type have been
formulated and solved using a variety of mathematical
programming techniques. In this section we formulate and solve
a portfolio selection problem as a linear program.

Consider the case of Welte Mutual Funds, Inc., located in

New York City. Welte has just obtained $100,000 by converting
industrial bonds to cash and is now looking for other investment
opportunities for these funds. Based on Welte's current
investments, the firm's top financial analyst recommends that all
new investments be made in the oil industry, steel industry, or in
government bonds. Specifically, the analyst has identified five
investment opportunities and projected their annual rates of
return. The investments and rates of return are shown in Table.
Management of Welte has imposed the following investment
guidelines.
1. Neither industry (oil or steel) should receive more than
$50,000.
2. Government bonds should be at least 25% of the steel
industry investments.
3. The investment in Pacific Oil, the high-return but high-
risk investment, cannot be more than 60% of the total oil
industry investment.

What portfolio recommendations investments and amounts

should be made for the available $100,000? Given the objective
of maximizing projected return subject to the budgetary and
managerially imposed constraints, we can answer this question
by formulating and solving a linear programming model of the
problem. The solution will provide investment recommendations
for the management of Welte Mutual Funds.
Table INVESTMENT OPPORTUNITIES FOR WELTE MUTUAL FUNDS

Investment Projected Rate of Return (%)

Atlantic Oil 7.3
Pacific Oil 10.3
Midwest Steel 6.4
Huber Steel 7.5
Government bonds 4.5
Gravel Inc. manufactures two products used in the heavy
equipment industry. Both products require manufacturing
operations in two departments. The following are the
production time (in hours) and profit contribution figure for
the two products.
Labor-Hours
Produ Profit Per Dept. A Dept. B
ct Unit
1 Tk. 250 6 12
2 Tk. 200 8 10

For the coming production period, Gravel Inc. has

available a total of 1000 hours of labor that can be
allocated to either of the two departments.
Formulate an LP model that will maximize the total
contribution to profit.
Paint Fair Company advertises its weekly sales in newspapers,
television, and radio. Each taka spent in advertising in newspapers is
estimated to reach an exposure of 12 buying customers, each taka in
TV reaches an exposure of 15 buying customers, and each taka in
radio reaches an exposure of 10 buying customers, The company has
an agreement with all three media services according to which it will
spend not less than 20 percent of its total money actually expended in
each medium. Further, it is agreed that the combined newspaper and
television budget will not be larger than three times the radio budget.

The company has just decided to spend no more than Tk. 170,000 on
advertising. The problem is: how much should the company budget
for each medium if it is interested in reaching as many buying
customers as possible?
Formulate a linear programming model to solve the problem.

Candy Kane Cosmetics (CKC) produces Leslie Perfume, which

requires chemicals and labor. Two production processes are
available: Process 1 transforms 1 unit of labor and 2 units of
chemicals into 3 oz of perfume. Process 2 transforms 2 units
of labor and 3 units of chemicals into 5 oz of perfume. It
costs CKC $3 to purchase a unit of labor and $2 to purchase a
unit of chemicals. Each year, up to 20,000 units of labor and
35,000 units of chemicals can be purchased. In the absence
of advertising, CKC believes it can sell 1,000 oz of perfume.
To stimulate demand for Leslie, CKC can hire the lovely model
Jenny Nelson. Jenny is paid $100/hour. Each hour Jenny
works for the company is estimated to increase the demand
for Leslie Perfume by 200 oz. Each ounce of Leslie Perfume
sells for $5. Use linear programming to determine how CKC
can maximize profits.
Kathleen Allen, an individual investor, has $70,000 to divide among several
investments. The alternative investments are municipal bonds with an
8.5% annual return, certificates of deposit with a 5% return, treasury bills
with a 6.5% return, and a growth stock fund with a 13% annual return.
The investments are all evaluated after 1 year. However, each investment
alternative has a different perceived risk to the investor; thus, it is
advisable to diversify. Kathleen wants to know how much to invest in each
alternative in order to maximize the return.

The following guidelines have been established for diversifying the

investments and lessening the risk perceived by the investor:

1. No more than 20% of the total investment should be in municipal

bonds.
2. The amount invested in certificates of deposit should not exceed the
amount invested in the other three alternatives.
3. At least 30% of the investment should be in treasury bills and
certificates of deposit.
4. To be safe, more should be invested in CDs and treasury bills than in
municipal bonds and the growth stock fund, by a ratio of at least 1.2
to 1.

Kathleen wants to invest the entire $70,000.

National Bank is preparing to invest up to 5 million taka of its cash
reserves. The bank is considering the following alternatives:

Alternatives Expected rate of return Risk factor

(percent)
Treasury security 7.6 0
Corporate bond 8.9 1
Loans to corporations 10.3 2
Stocks 14.0 5

The bank’s investment policy requires that:

a) The amount loaned to corporations will not exceed the amount
invested in Treasury securities
b) The weighted risk factor will not exceed 1.90
c) For every taka invested in stocks, there will be at least 0.50 taka
invested in Treasury securities
d) The amount invested in stocks will not exceed 25 percent of the
total amount invested.
Formulate a linear programming model to solve the problem.
TIlfiftem Bank is in the process of devising a loan policy that
involves a maximum of $12 million.
The following table provides the pertinent data about available
types of loans.

Type of loan Interest rate Bad-debt ratio

Personal .140 .10
Car .130 .07
Home .120 .03
Farm .125 .05
Commercial .100 .02

Bad debts are unrecoverable and produce no interest revenue.

Competition with other financial institutions requires that the

bank allocate at least 40% of the funds to farm and commercial
loans. To assist the housing industry in the region, home loans
must equal at least 50% of the personal, car, and home loans.
The bank also has a stated policy of not allowing the overall ratio
of bad debts on all loans to exceed 4%.
A Diet Example

Breathtakers, a health and fitness center, operates a morning fitness

program for senior citizens. The program includes aerobic exercise,
either swimming or step exercise, followed by a healthy breakfast in the
dining room. Breathtakers' dietitian wants to develop a breakfast that
will be high in calories, calcium, protein, and fiber, which are especially
important to senior citizens, but low in fat and cholesterol. She also
wants to minimize cost. She has selected the following possible food
items, whose individual nutrient contributions and cost from which to
develop a standard breakfast menu are shown in the following table:

Breakfast Fat Cholesterol Iron Calcium Protein Fiber

Calories Cost
Food (g) (mg) (mg) (mg) (g) (g)

1. Bran cereal (cup) 90 0 0 6 20 3 5 $0.18

2. Dry cereal (cup) 110 2 0 4 48 4 2 0.22
3. Oatmeal (cup) 100 2 0 2 12 5 3 0.10
4. Oat bran (cup) 90 2 0 3 8 6 4 0.12
5. Egg 75 5 270 1 30 7 0 0.10
6. Bacon (slice) 35 3 8 0 0 2 0 0.09
7. Orange 65 0 0 1 52 1 1 0.40
8. Milk2% (cup) 100 4 12 0 250 9 0 0.16
9. Orange juice 120 0 0 0 3 1 0 0.50
(cup)
10. Wheat toast 65 1 0 1 26 3 3 0.07
(slice)

The dietitian wants the breakfast to include at least 420 calories, 5

milligrams of iron, 400 milligrams of calcium, 20 grams of protein, and
12 grams of fiber. Furthermore, she wants to limit fat to no more than 20
grams and cholesterol to 30 milligrams.
A hospital dietitian prepares breakfast menus every morning for the hospital patients. Part of the
dietitian's responsibility is to make sure that minimum daily requirements for vitamins A and B are met. At
the same time, the cost of the menus must be kept as low as possible. The main breakfast staples
providing vitamins A and B are eggs, bacon, and cereal. The vitamin requirements and vitamin
contributions for each staple follow:

Vitamin Contributions

Vitamin mg/Egg mg/Bacon Strip mg/Cereal Cup Minimum Daily Requirements

A 2 4 1 16
B 3 2 1 12

An egg costs $0.04, a bacon strip costs $0.03, and a cup of cereal costs $0.02. The dietitian wants to
know how much of each staple to serve per order to meet the minimum daily vitamin requirements while
minimizing total cost.

a. Formulate a linear programming model for this problem.

The Bluegrass Farms Problem:

Bluegrass Farms has been experimenting with a special diet for its
racehorses. The feed components available for the diet are a standard
horse feed product, a vitamin-enriched oat product and mineral feed
additive. The nutritional value in units per pound and the costs for the
three feed component are summarized below:

Feed component Standard Enriched Additive Daily Diet

Oat requirement
Ingredient A 0.8 0.2 0.0 1.8
Ingredient B 1.0 1.5 3.0 5.0
Ingredient C 0.1 0.6 2.0 4.8
Cost per pound $0.25 $0.50 $3.00

In addition, to control the weight of the horse, the total daily feed
for a horse should not exceed 6 pounds. Bluegrass Farms would
like to determine the minimum-cost mix that will satisfy the daily
diet requirements.
The United Charities annual fund-raising drive is scheduled to
take place next week. Donations are collected during the day and
night, by telephone, and through personal contact. The average
donation resulting from each type of contact is as follows:

Phone Personal
Day $2 $4
Night 3 7

The charity group has enough donated gasoline and cars to make
at most 300 personal contacts during one day and night
combined. The volunteer minutes required to conduct each type
of interview are as follows:

Phone (min.) Personal (min.)

Day 6 15
Night 5 12

The charity has 20 volunteer hours available each day and 40

volunteer hours available each night. The chairperson of the
fund-raising drive wants to know how many different types of
contacts to schedule in a 24-hour period (i.e., 1 day and 1 night)
to maximize total donations.

Formulate a linear programming model for this problem.

Precision Instrument Inc. has a contract to supply Electronic Calculator Company 600
microcircuits in July and 500 microcircuits in August. Precision makes and tests the microcircuits
on an assembly line, using people both a regular and second shift basis. In July, because of
other commitments, only 650 microcircuits can be produced during regular time and only 200
microcircuits during the second shift. On the other hand, only 450 microcircuits can be
produced during regular time in August and only 150 in the second shift. The problem is that
the production costs differ not only for each shift, but also for each of the two months.
Specifically, in the month of July the regular shift cost is Tk.250 per microcircuit, while the
second shift cost Tk.350 per microcircuit. The respective costs for August are Tk.300 and
Tk.375. Of course, Precision can make more than 600 microcircuits required by Electronic in
July, but in this case, Precision must store the difference over from July at a unit inventory cost
of Tk.25. Precision would like to determine the production schedule to minimize the total cost.
Formulate as a linear programming problem.
Jackson Hole Manufacturing is a small manufacturer of plastic products
used in the automotive and computer industries. One of its major
contracts is with a large computer company and involves the production
of plastic printer cases for the computer company's portable printers.
The printer cases are produced on two injection molding machines. The
M-100 machine has a production capacity of 25 printer cases per hour,
and the M-200 machine has a production capacity of 40 cases per hour.
Both machines use the same chemical material to produce the printer
cases; the M-100 uses 40 pounds of the raw material per hour and the
M-200 uses 50 pounds per hour. The computer company has asked
Jackson Hole to produce as many of the cases during the upcoming
week as possible and has said that it will pay $18 for each case Jackson
Hole can deliver. However, next week is a regularly scheduled vacation
period for most of Jackson Hole's production employees; during this
time, annual maintenance is performed for all equipment in the plant.
Because of the downtime for maintenance, the M-100 will be available
for no more than 15 hours, and the M-200 will be available for no more
than 10 hours. However, because of the high setup cost involved with
both machines, management has a requirement that, if production is
scheduled on either machine, the machine must be operated for at least 5
hours. The supplier of the chemical material used in the production
process has informed Jackson Hole that a maximum of 1000 pounds of
the chemical material will be available for next week's production; the
cost for this raw material is $6 per pound. In addition to the raw material
cost, Jackson Hole estimates that the hourly cost of operating the M-100
and the M-200 are $50 and $75, respectively.

a. Formulate a linear programming model that can be used to

maximize the contribution to profit.
The Kalo Fertilizer Company produces two brands of lawn fertilizer
Super Two and Green Grow at plants in Fresno, California, and
Dearborn, Michigan. The plant at Fresno has resources available to
produce 5,000 pounds of fertilizer daily; the plant at Dearborn has
enough resources to produce 6,000 pounds daily. The cost per pound
of producing each brand at each plant is as follows:

Plant
Product Fresno Dearborn
Super Two $2 $4
Green Grow 2 3

The company has a daily budget of $45,000 for both plants combined.
Based on past sales, the company knows the maximum demand
(converted to a daily basis) is 6,000 pounds for Super Two and 7,000
pounds for Green Grow. The selling price is $9 per pound for Super
Two and $7 per pound for Green Grow. The company wants to know
the number of pounds of each brand of fertilizer to produce at each
plant in order to maximize profit.

a. Formulate a linear programming model for this problem.

Brady 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 saw-mill, and finally dry
the lumber in its own kiln. Brady can purchase grade 1 or
grade 2 lumber. 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 cubic foot 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. Brady incurs costs of $4 per cu ft of lumber
dried. It costs $2.50 per cu ft of logs sent through the
saw-mill. Each week, the saw-mill 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; log—1.3
seconds. Formulate an LP to help Brady minimize the
weekly cost of meeting the demand for processed lumber.
A Make-or-Buy Decision
We illustrate the use of a linear programming model to determine
how much of each of several component parts a company should
manufacture and how much it should purchase from an outside supplier.
Such a decision is referred to as a make-or-buy decision.
The Janders Company markets various business and engineering
products. Currently, Janders is preparing to introduce two new
calculators: one for the business market called the Financial Manager
and one for the engineering market called the Technician. Each
calculator has three components: a base, an electronic cartridge, and a
face plate or top. The same base is used for both calculators, but the
cartridges and tops are different. All components can be manufactured
by the company or purchased from outside suppliers. The manufacturing
costs and purchase prices for the components and manufacturing times
(in minutes) for the components are summarized in Table 1.
Janders' forecasters indicate that 3000 Financial Manager
calculators and 2000-Technician calculators will be needed. However,
manufacturing capacity is limited. The company has 200 hours of
regular manufacturing time and 50 hours of overtime that can be
scheduled for the calculators. Overtime involves a premium at the
additional cost of $9 per hour.

Table 1 MANUFACTURING COSTS AND PURCHASE PRICES FOR JANDERS' CALCULATOR COMPONENTS
Cost Per Unit
Component Manufacture Purchase Manufacturing
(Regular Time) Time (minutes)
Base $0.50 $0.60 1.0
Financial 3.75 4.00 3.0
cartridge
Technician 3.30 3.90 2.5
cartridge
Financial top 0.60 0.65 1.0
Technician top 0.75 0.78 1.5
A Blend Example
A petroleum company produces three grades of motor oil super,
premium, and extra from three components. The company wants
to determine the optimal mix of the three components in each
grade of motor oil that will maximize profit. The maximum
quantities available of each component and their cost per barrel
are as follows:
Component Maximum Barrels Available/Day Cost/Barrel
1 4,500 $12
2 2,700 10
3 3,500 14

To ensure the appropriate blend, each grade has certain general

specifications. Each grade must have a minimum amount of
component 1 plus a combination of other components, as
follows:

Grade Component Specifications Selling Price/Barrel

Super At least 50% of 1 $23
Not more than 30% of 2
Premium At least 40% of 1 20
Not more than 25% of 3
Extra At least 60% of 1 18
At least 10% of 2

The company wants to produce at least 3,000 barrels of each

grade of motor oil.
Meghna Oil Company produces two grades of gasoline: regular and high octane.
Both gasolines are produced by blending two types of crude oil. Although both
types of crude oil contains the two important ingredients required to produce
both gasolines, the percentage of important ingredients in each types of crude oil
differs, as does the cost per gallon. The percentage of ingredients A and B in
each type of crude oil and the cost per gallon are shown:
Crude Oil Cost Ingredient A Ingredient B
1 Tk. 10 20% 60%
2 Tk. 15 50% 30%

Each gallon of regular gasoline must contain at least 40% of ingredient A,

whereas each gallon high octane can contain at most 50% of ingredient B. Daily
demand for regular and high-octane gasoline is 800,000 and 500,000 gallons,
respectively. How many gallons of each type of crude oil should be used in the
two gasolines to satisfy daily demand at a minimum cost? Formulate an LP
model.

The Mill Mountain Coffee Shop blends coffee on the premises for its customers.
It sells three basic blends in 1-pound bags, Special, Mountain Dark, and Mill
Regular. It uses four different types of coffee to produce the blends Brazilian,
mocha, Columbian, and mild. The shop has the following blend recipe
requirements:

Blend Mix Requirements Selling Price/Pound

Special At least 40% Columbian, at least 30% mocha $6.50
Dark At least 60% Brazilian, no more than 10% mild 5.25
Regular No more than 60% mild, at least 30% Brazilian 3.75

The cost of Brazilian coffee is $2.00 per pound, the cost of mocha is $2.75 per
pound, the cost of Columbian is $2.90 per pound, and the cost of mild is $1.70
per pound. The shop has 110 pounds of Brazilian coffee, 70 pounds of mocha,
80 pounds of Columbian, and 150 pounds of mild coffee available per week. The
shop wants to know the amount of each blend it should prepare each week to
maximize profit.

Formulate a linear programming model for this problem.

The Metalco Company desires to blend a new alloy of 40 percent tin, 35 percent zinc,
and 25 percent lead from several available alloys having the following properties:
1.

The objective is to determine the proportions of these alloys that should be

blended to produce the new alloy at a minimum cost.

Bark's Pet Food Company produces canned cat food called

Meow Chow and canned dog food called Bow Chow. The
company produces the pet food from horse meat, ground
fish, and a cereal additive. Each week the company has 600
pounds of horse meat, 800 pounds of ground fish, and 1,000
pounds of cereal additive available to produce both kinds of
pet food. Meow Chow must be at least half fish, and Bow
Chow must be at least half horse meat. The company has
2,250 16-ounce cans available each week. A can of Meow
Chow earns $0.80 in profit, and a can of Bow Chow earns
$0.96 in profit. The company wants to know how many cans
of Meow Chow and Bow Chow to produce each week in
order to maximize profit.
Formulate a linear programming model for this problem.
Lawns Unlimited is a lawn care and maintenance company. One
of its services is to seed new lawns as well as bare or damaged
areas in established lawns. The company uses three basic grass
seed mixes it calls Home 1, Home 2, and Commercial 3. It uses
three kinds of grass seed: tall fescue, mustang fescue, and
bluegrass. The requirements for each grass mix are as follows:

Mix Mix Requirements

Home 1 No more than 50% tall fescue

At least 20% mustang fescue

Home 2 At least 30% bluegrass

At least 30% mustang fescue

No more than 20% tall fescue

Commercial 3 At least 50% but no more than 70% tall fescue

At least 10% bluegrass

The company believes it needs to have at least 1,200 pounds of

Home 1 mix, 900 pounds of Home 2 mix, and 2,400 pounds of
Commercial 3 seed mix on hand. A pound of tall fescue costs
the company $1.70, a pound of mustang fescue costs $2.80,
and a pound of bluegrass costs $3.25. The company wants to
know how many pounds of each type of grass seed to purchase
to minimize cost.
Formulate a linear programming model for this problem.
ABC Co. produces two products with contribution to profit per unit of Tk. 10 and Tk.9
respectively. Total labor requirements per unit produced and total hours of labor available from
personnel to each of four departments are given below:

Dept. Pdt. 1 Pdt. 2 Total hours available

1 0.65 0.95 6500
2 0.45 0.85 6000
3 1.00 0.70 7000
4 0.15 0.30 1400
Suppose, the company has a cross training program that enables some employees to be
transferred between departments. By taking advantages of the cross training skills, a limited
number of employees and labor hours may be transferred from one department to another.
From Dept. Cross training transfers permitted to Maximum Hours Transferable
Dept.
1 2 3 4
1 -- Yes Yes -- 400
2 -- -- Yes Yes 800
3 -- -- -- Yes 100
4 Yes Yes -- -- 200

How to assign workforce to maximize profit?

Staffing problem
A Post Office requires different numbers of employees on different days of the week. Union rules state
each employee must work 5 consecutive days and then receive two days off. Find the minimum number
of employees needed.

The police department schedules RAB officers for 8-hour shifts. The beginning
times for the shifts are 8.00 A.M., noon, 4.00 P.M., 8.00 P.M., midnight and 4.00
A.M. An officer beginning a shift at one of these times work for the next 8 hours.
During normal weekend operations, the number of officers needed varies
depending on the time of the day. The department staffing guidelines require the
following minimum number of officers on duty:

Time of Day Minimum Officers on Duty

8.00 A.M. - noon 5
Noon – 4.00 P.M. 6
4.00 P.M. - 8.00 P.M. 10
8.00 P.M. - Midnight 7
Midnight - 4.00 A.M 4
4.00 A.M -8.00 A.M 6

Determine the number of RAB officers that should be scheduled to begin the 8-
hours shifts each of the 6 times to minimize the total number of officers
required.
Mazy's Department Store has decided to stay open on a 24-hour basis. The store manager has
divided the 24-hour day into six 4-hour periods and determined the following minimum
personnel requirements for each period:

Time Personnel Needed

Midnight-4:00 A.M. 90
4:00-8:00 A.M. 215
8:00-Noon 250
Noon-4:00 P.M. 65
4:00-8:00 P.M. 300
8:00-Midnight 125

Personnel must report for work at the beginning of one of these times and work 8 consecutive
hours. The store manager wants to know the minimum number of employees to assign for each
4-hour segment to minimize the total number of employees.

a. Formulate a linear programming model for this problem.

Larry Edison is the director of the Computer Center for Buckly College. He now needs to
schedule the staffing of the center. It is open from 8 A.M. until midnight. Larry has monitored
the usage of the center at various times of the day, and determined that the following numbers
of computer consultants are required:

Time of Day Minimum Number of Consultants

Required to Be on Duty
8 A.M.–noon 4
Noon–4 P.M. 8
4 P.M.–8 P.M. 10
8 P.M.–midnight 6
Two types of computer consultants can be hired: full-time and part-time. The full-time
consultants work for 8 consecutive hours in any of the following shifts: morning (8 A.M.–4
P.M.), afternoon (noon–8 P.M.), and evening (4 P.M.–midnight). Full-time consultants are paid
$14 per hour. Part-time consultants can be hired to work any of the four shifts listed in the
above table. Part-time consultants are paid $12 per hour.
An additional requirement is that during every time period, there must be at least 2 full-time
consultants on duty for every part-time consultant on duty. Larry would like to determine how
many full-time and how many part-time workers should work each shift to meet the above
requirements at the minimum possible cost.
Formulate a linear programming model for this problem.
A post office requires different numbers of full-time
employees on different days of the week. The number of
full-time employees required on each day is given in
following Table. Union rules state that each full-time
employee must work five consecutive days and then
receive two days off. For example, an employee who
works Monday to Friday must be off on Saturday and
Sunday. The post office wants to meet its daily
requirements using only fulltime employees. Formulate an
LP that the post office can use to minimize the number of
full-time employees who must be hired.
In the post office example, suppose that each full-time
employee works 8 hours per day. Thus, Monday’s
requirement of 17 workers may be viewed as a
requirement of 8(17) = 136 hours. The post office may
meet its daily labor requirements by using both full-time
and part-time employees. During each week, a full-time
employee works
8 hours a day for five consecutive days, and a part-time
employee works 4 hours a day for five consecutive days.
A full-time employee costs the post office $15 per hour,
whereas a part-time employee (with reduced fringe
benefits) costs the post office only $10 per hour. Union
requirements limit part-time labor to 25% of weekly labor
requirements.
Formulate an LP to minimize the post office’s weekly labor
costs.
Each day, workers at the Gotham City Police Department work two 6-hour shifts chosen from
12 A.M. to 6 A.M., 6 A.M. to 12 P.M., 12 P.M. to 6 P.M., and 6 P.M. to 12 A.M. The following
number of workers are needed during each shift: 12 A.M. to 6 A.M.—15 workers; 6 A.M. to 12
P.M.—5 workers; 12 P.M. to 6 P.M.—12 workers; 6 P.M. to 12 A.M.—6 workers. Workers whose
two shifts are consecutive are paid $12 per hour; workers whose shifts are not consecutive are
paid $18 per hour. Formulate an LP that can be used to minimize the cost of meeting the daily
workforce demands of the Gotham City Police Department.

Western Family Steakhouse offers a variety of low-cost meals and quick service. Other than
management, the steakhouse operates with two full-time employees who work 8 hours per day.
The rest of the employees are part-time employees who are scheduled for 4-hour shifts during
peak meal times. On Saturdays the steakhouse is open from 11:00 A.M. to 10:00 P.M.
Management wants to develop a schedule for part-time employees that will minimize labor
costs and still provide excellent customer service. The average wage rate for the part-time
employees is $4.60 per hour. The total number of full-time and part-time employees needed
varies with the time of day as shown.
Time Total Number of Employees Needed
11:00 A.M.-noon 9
Noon-1:00 P.M. 9
1:00 P.M.-2:00 P.M. 9
2:00 P.M.-3:00 P.M. 3
3:00 P.M.-4:00 P.M. 3
4:00 P.M.-5:00 P.M. 3
5:00 P.M.-6:00 P.M. 6
6:00 P.M.-7:00 P.M. 12
7:00 P.M.-8:00 P.M. 12
8:00 P.M.-9:00 P.M. 7
9:00 P.M.-10:00 P.M. 7

One full-time employee comes on duty at 11:00 A.M., works 4 hours, takes an hour off, and
returns for another 4 hours. The other full-time employee comes to work at 1:00 P.M. and
works the same 4-hours-on, 1-hour-off, 4-hours-on pattern.
a. Develop a minimum-cost schedule for part-time employees.
b. What is the total payroll for the part-time employees? How many part-time shifts are
needed? Use the surplus variables to comment on the desirability of scheduling at least some of
the part-time employees for 3-hour shifts.
A Transportation Example
Formulate a linear programming model for this problem. The fancy group owns
factories in four towns (W, X, Y and Z) which distribute to three Fancy retail dress
shops (in A, B and C). Factory availabilities, projected stores demands, and unit
shipping cost are summarized in the table that follows:

To A B C Factory
availability
From
W Tk. 8 12 Tk. 4 82
X 5 6 8 38
Y 7 9 21 46
Z 14 3 7 29
Store Demand 120 44 31

Formulate a linear programming model.

The Zephyr Television Company ships televisions from three

warehouses to three retail stores on a monthly basis. Each
warehouse has a fixed supply per month, and each store has a fixed
demand per month. The manufacturer wants to know the number of
television sets to ship from each warehouse to each store in order to
minimize the total cost of transportation.
Each warehouse has the following supply of televisions available for
shipment each month:

Warehouse Supply (sets)

1. Cincinnati 300
2. Atlanta 200
3. Pittsburgh 200
700
Each retail store has the following monthly demand for television
sets:

Store Demand (sets)

A. New York 150
B. Dallas 250
C. Detroit 200
600

Costs of transporting television sets from the warehouses to the

retail stores vary as a result of differences in modes of transportation
and distances. The shipping cost per television set for each route is
as follows:

To Store
From Warehouse A B C
1 $16 $18 $11
2 14 12 13
3 13 15 17
Joy company currently maintains plant in Gazipur, Mymensing and
Faridpur that supply major distribution centers in Dhaka, Rajshahi,
Comilla and Chittagong. Because of an expanding demand, Joy has
decided to open a forth plant and has narrowed the choice to one of
two areas – Feni or Savar. The pertinent production and distribution
costs, as well as the plant capacities and distribution demands, are
shown in the accompanying table:

Distribution Dhaka Rajshahi Comilla Chittagong Capacity Unit

Production
cost
Plant
Gazipur Tk. Tk. 55 Tk. Tk. 60 15000 Tk. 48
25 40
Mymensing 35 30 50 40 6000 50
Faridpur 36 45 26 66 14000 52
Feni (Proposed) 60 38 65 27 11000 53
Savar 35 30 41 50 11000 49
(Proposed)
Forecasted 10000 12000 15000 9000
Demand
Which of the new possible plant should be opened?
The Roadnet Transport Company has expanded its shipping capacity
by purchasing 90 trailer trucks from a bankrupt competitor. The
company subsequently located 30 of the purchased trucks at each of
its shipping warehouses in Charlotte, Memphis, and Louisville. The
company makes shipments from each of these warehouses to
terminals in St. Louis, Atlanta, and New York. Each truck is capable of
making one shipment per week. The terminal managers have each
indicated their capacity for extra shipments. The manager at St. Louis
can accommodate 40 additional trucks per week, the manager at
Atlanta can accommodate 60 additional trucks, and the manager at
New York can accommodate 50 additional trucks. The company
makes the following profit per truck-load shipment from each
warehouse to each terminal. The profits differ as a result of
differences in products shipped, shipping costs, and transport rates:

Terminal
Warehouse St. Louis Atlanta New York
Charlotte $1,800 $2,100 $1,600
Memphis 1,000 700 900
Louisville 1,400 800 2,200

The company wants to know how many trucks to assign to each route
(i.e., warehouse to terminal) to maximize profit.

Formulate a linear programming model for this problem.

Assignment Problem:

The manager of the Ewing and Barnes Department Store has four
employees available to assign to three departments in the store lamps,
sporting goods, and linens. The manager wants each of these departments
to have at least one employee, but not more than two. Therefore, two
departments will be assigned one employee, and one department will be
assigned two. Each employee has different areas of expertise, which are
reflected in the daily sales each employee is expected to generate in each
department, as follows:

Department Sales
Employee Lamps Sporting Goods Linens
1 $130 $150 $ 90
2 275 300 100
3 180 225 140
4 200 120 160

The manager wishes to know which employee(s) to assign to each

department in order to maximize expected sales.

Formulate a linear programming model for this problem.

In a job shop operation, three jobs may be performed on any of four
machines. The hours required for each job on each machine are presented
in the accompanying table. The plant supervisor would like to assign jobs
so that total time is minimized.

MACHINE
JOB M1 M2 M3 M4
J1 6 7 5 9
J2 8 5 6 7
J3 10 8 6 6

Formulate a linear programming model for this problem.

The Bunker Manufacturing firm has five employees and six machines
and wants to assign the employees to the machines to minimize cost.
A cost table showing the cost incurred by each employee on each
machine follows:

Machine
Employee A B C D E F
1 $12 $7 $20 $14 $8 $10
2 10 14 13 20 9 11
3 5 3 6 9 7 10
4 9 11 7 16 9 10
5 10 6 14 8 10 12

Because of union rules regarding departmental transfers, employee 3

cannot be assigned to machine E, and employee 4 cannot be assigned
to machine B. Solve this problem, indicate the optimal assignment,
and compute total minimum cost.
The Omega pharmaceutical firm has five salespersons, whom the
firm wants to assign to five sales regions. Given their various
previous contacts, the salespersons are able to cover the regions in
different amounts of time. The amount of time (days) required by
each salesperson to cover each city is shown in the following table:

Region (days)
Salesperson
A B C D E
1 17 10 15 16 20
2 12 9 16 9 14
3 11 16 14 15 12
4 14 10 10 18 17
5 13 12 9 15 11

Formulate this problem as a general linear programming model.