` Blending Problem

` Product Mix Problem

` Transportation Problem
` Data Envelopment Analysis
` Portfolio Planning Problem
Ferdinand Feed Company receives four raw
grains from which it blends its dry pet
food. The pet food advertises that each 8-
ounce packet meets the minimum daily
requirements for vitamin C, protein and
iron. The cost of each raw grain as well as
the vitamin C, protein, and iron units per
pound of each grain are summarized on
the next slide.
 Vitamin C Protein Iron
Grain Units/lb Units/lb Units/lb Cost/lb
1 9 12 0 .75
2 16 10 14 .90
3 8 10 15 .80
4 10 8 7 .70

Ferdinand is interested in producing the 8-ounce

mixture at minimum cost while meeting the minimum
daily requirements of 6 units of vitamin C, 5 units of
protein, and 5 units of iron.
` See Blending Model.xlsx
` Define the decision variables
xj = the pounds of grain j (j = 1,2,3,4)
used in the 8-ounce mixture
` Define the objective function
Minimize the total cost for an 8-ounce
mixture:
MIN .75x1 + .90x2 + .80x3 + .70x4
` Define the constraints
Total weight of the mix is 8-ounces (.5 pounds):
(1) x1 + x2 + x3 + x4 = .5
Total amount of Vitamin C in the mix is at least 6
units:
(2) 9x1 + 16x2 + 8x3 + 10x4 ≥ 6
Total amount of protein in the mix is at least 5
units:
(3) 12x1 + 10x2 + 10x3 + 8x4 ≥ 5
Total amount of iron in the mix is at least 5
units:
(4) 14x2 + 15x3 + 7x4 ≥ 5
Nonnegativity of variables: xj > 0 for all j
` See Blending Model.txt
Floataway Tours has $420,000 that can be used
to purchase new rental boats for hire during
the summer. The boats can be purchased from
two different manufacturers. Floataway Tours
would like to purchase at least 50 boats and
would like to purchase the same number from
Sleekboat as from Racer to maintain goodwill.
At the same time, Floataway Tours wishes to
have a total seating capacity of at least 200.
Formulate this problem as a linear program.

Maximum Expected
Boat Builder Cost Seating Daily Profit
Speedhawk Sleekboat $6000 3 $ 70
Silverbird Sleekboat $7000 5 $ 80
Catman Racer $5000 2 $ 50
Classy Racer $9000 6 $110
` Define the decision variables
x1 = number of Speedhawks ordered
x2 = number of Silverbirds ordered
x3 = number of Catmans ordered
x4 = number of Classys ordered
` Define the objective function
Maximize total expected daily profit:
Max: (Expected daily profit per unit)
x (Number of units)
Max: 70x1 + 80x2 + 50x3 + 110x4
` Define the constraints
(1) Spend no more than $420,000:
6000x1 + 7000x2 + 5000x3 + 9000x4 < 420,000
(2) Purchase at least 50 boats:
x1 + x2 + x3 + x4 > 50
(3) Number of boats from Sleekboat equals
number of boats from Racer:
x1 + x2 = x3 + x4 or x1 + x2 - x3 - x4 = 0
` Define the constraints (continued)
(4) Capacity at least 200:
3x1 + 5x2 + 2x3 + 6x4 > 200
Nonnegativity of variables:
xj > 0, for j = 1,2,3,4
` Complete Formulation

Max 70x1 + 80x2 + 50x3 + 110x4

s.t.
6000x1 + 7000x2 + 5000x3 + 9000x4 < 420,000
x1 + x2 + x3 + x4 > 50
x1 + x2 - x3 - x4 = 0
3x1 + 5x2 + 2x3 + 6x4 > 200
x1, x2, x3, x4 > 0
` Solution Summary
ƒ Purchase 28 Speedhawks from Sleekboat.
ƒ Purchase 28 Classy’s from Racer.
ƒ Total expected daily profit is $5,040.00.
ƒ The minimum number of boats was exceeded by 6
(surplus for constraint #2).
ƒ The minimum seating capacity was exceeded by
52 (surplus for constraint #4).
The Navy has 9,000 pounds of material in Albany,
Georgia that it wishes to ship to three installations:
San Diego, Norfolk, and Pensacola. They require
4,000, 2,500, and 2,500 pounds, respectively.
Government regulations require equal distribution
of shipping among the three carriers.
Transportation Problem

The shipping costs per pound for truck, railroad,

and airplane transit are shown on the next slide.
Formulate and solve a linear program to determine
the shipping arrangements (mode, destination, and
quantity) that will minimize the total shipping cost.
Transportation Problem

Destination
Mode San Diego Norfolk Pensacola
Truck $12 $6 $5
Railroad 20 11 9
Airplane 30 26 28
Transportation Problem

` Define the Decision Variables

We want to determine the pounds of
material, xij , to be shipped by mode i to
destination j. The following table
summarizes the decision variables:
San Diego Norfolk Pensacola
Truck x11 x12 x13
Railroad x21 x22 x23
Airplane x31 x32 x33
Transportation Problem
` Define the Objective Function
Minimize the total shipping cost.
Min: (shipping cost per pound for each
mode per destination pairing) x (number
of pounds shipped by mode per
destination pairing).
Min: 12x11 + 6x12 + 5x13
+ 20x21 + 11x22 + 9x23
+ 30x31 + 26x32 + 28x33
Transportation Problem
` Define the Constraints
Equal use of transportation modes:
(1) x11 + x12 + x13 = 3000
(2) x21 + x22 + x23 = 3000
(3) x31 + x32 + x33 = 3000
Destination material requirements:
(4) x11 + x21 + x31 = 4000
(5) x12 + x22 + x32 = 2500
(6) x13 + x23 + x33 = 2500
Nonnegativity of variables:
xij > 0, i = 1,2,3 and j = 1,2,3
 Transportation Problem

` Solution Summary
ƒ San Diego will receive 1000 lbs. by truck
ƒ and 3000 lbs. by airplane.
ƒ Norfolk will receive 2000 lbs. by truck
ƒ and 500 lbs. by railroad.
ƒ Pensacola will receive 2500 lbs. by railroad.
ƒ The total shipping cost will be $142,000.
` Data envelopment analysis (DEA) is an LP application
used to determine the relative operating efficiency of
units with the same goals and objectives.
` DEA creates a fictitious composite unit made up of an
optimal weighted average (W1, W2,…) of existing units.
` An individual unit, k, can be compared by determining E,
the fraction of unit k’s input resources required by the
optimal composite unit.
` If E < 1, unit k is less efficient than the composite unit
and be deemed relatively inefficient.
` If E = 1, there is no evidence that unit k is inefficient,
but one cannot conclude that k is absolutely efficient.22
` The DEA Model

MIN E
s.t. Weighted outputs > Unit k’s output
(for each measured output)
Weighted inputs < E [Unit k’s input]
(for each measured input)
Sum of weights = 1
E, weights > 0
The Langley County School District is trying to
determine the relative efficiency of its three high
schools. In particular, it wants to evaluate
Roosevelt High. The district is evaluating
performances on SAT scores, the number of
seniors finishing high school, and the number
of students who enter college as a function of
the number of teachers teaching senior classes,
the prorated budget for senior instruction, and
the number of students in the senior class.
` Input

Roosevelt Lincoln Washington

Senior Faculty 37 25 23
Budget ($100,000's) 6.4 5.0 4.7
Senior Enrollments 850 700 600
` Output

Roosevelt Lincoln Washington

Average SAT Score 800 830 900
High School Graduates 450 500 400
College Admissions 140 250 370
` Decision Variables

E = Fraction of Roosevelt's input resources

required by the composite high school
w1 = Weight applied to Roosevelt's input/output
resources by the composite high school
w2 = Weight applied to Lincoln’s input/output
resources by the composite high school
w3 = Weight applied to Washington's input/output
resources by the composite high school
` Objective Function
Minimize the fraction of Roosevelt High
School's input resources required by the
composite high school:
MIN E
` Constraints
Sum of the Weights is 1:
(1) w1 + w2 + w3 = 1
Output Constraints:
Since w1 = 1 is possible, each output of the
composite school must be at least as great as that
of Roosevelt:
(2) 800w1 + 830w2 + 900w3 > 800 (SAT Scores)
(3) 450w1 + 500w2 + 400w3 > 450 (Graduates)
(4) 140w1 + 250w2 + 370w3 > 140 (College
Admissions)
` Constraints
Input Constraints:
The input resources available to the composite school is a
fractional multiple, E, of the resources available to Roosevelt.
Since the composite high school cannot use more input than
that available to it, the input constraints are:
(5) 37w1 + 25w2 + 23w3 < 37E (Faculty)
(6) 6.4w1 + 5.0w2 + 4.7w3 < 6.4E (Budget)
(7) 850w1 + 700w2 + 600w3 < 850E (Seniors)
Nonnegativity of variables:
E, w1, w2, w3 > 0
` Conclusion
Objective function (E) is 0.765 = 76.5%, W1 = 0,
W2 = W3 = 0.5. Therefore, Roosevelt is 76.5%
efficient and also the output shows that the
composite school is made up of equal weights of
Lincoln and Washington.
` See Example 4.1 Postal employ
scheduling.xlsx
` See Example 4.4 Blending.xlsx