|
|||||
Operations
Research (MTH601)
85
Example
2
Ingredients
Mixing
Fauji
Foundation produces a cereal
SUNFLOWER, which they
advertise as meeting the
minimum daily
requirements
for vitamins A and D. The
mixing department of the
company uses three main
ingredients in making
the
cereal-wheat, oats, and
rice, all three of which
contain amounts of vitamin A
and D. Given that each box
of
cereal
must contain minimum amounts
of vitamin A and D, the
company has instructed the
mixing department
determine
how many ounces of each
ingredient should go into
each box of cereal in order
to minimize total cost.
This
problem differs from the
previous one in that its
objective is to minimize cost,
rather than Maximize
profit.
Each
ingredient has the following
vitamin contribution and requirement
per box.
VITAMIN
CONTRIBUTION
Vitami
Wheat
Oats
Rice
Milligrams
n
(mg./oz.)
(mg./oz)
(mg./oz.)
Required/Box
A
10
20
08
100
D
07
14
12
70
The
cost of one ounce of wheat
is Rs. 0.4, the cost of an
ounce of oats is Rs. 0.6,
and the cost of one
ounce
of
rice is Rs. 0.2.
Decision
Variables
This
problem contains three
decision variables for the
number of ounces of each
ingredient in a box of
cereal:
X1 =
ounces of wheat
X2 =
ounces of oats
X3 =
ounces of rice
The
Objective Function
The
objective of the mixing
department of the Fauji Foundation is to
minimize the cost of each
box of
cereal.
The total cost is the
sum of the individual costs
resulting from each
ingredient. Thus, the
objective function
that
is to minimize total cos, Z, is expressed
as
Minimize
Z
= Rs. 0.4X1 + 0.6X2
+
0.2X3
where
Z
= total cost per box
Rs.
0.4
X1 = cost of wheat per
box
85
Operations
Research (MTH601)
86
0.6
X2 =
cost of rice per
box
0.2
X3 =
cost of rice per
box
Model
Constraints
In
this problem the constraints
reflect the requirements for
vitamin consistency of the
cereal. Each
ingredient
contributes a number of milligrams of
the vitamin to the cereal.
The constraint for vitamin A
is
10
X1 +
20 X2 + 8 X3
> 100
milligrams
where
10 X1 =
vitamin A contribution (in mg.) for
wheat
20
X2 =
vitamin A contribution (in mg.) for
oats
8X3 =
vitamin A contribution (in mg.) for
rice
Notice
that rather than an ( < ) inequality,
as used in the previous
example, this constraint
requires a >
(greater
than or minimum requirement specifying
that at least 100 mg of
vitamin A must be in a box. If a
minimum
cost
solution results so that more
than 100 mg is in the cereal
mix, which is acceptable, however,
the amount cannot
be
less than 100 mg.
The
constraint for vitamin D is
constructed like the
constraint for vitamin
A.
7X1 + 14
X2 + 12X3
> 70
milligrams
As
in the previous problem
there are also nonnegative
constraints indicating that negative
amounts of each
ingredient
cannot be in the
cereal.
X1,
X2, X3
> 0
The
L.P. model for this problem
can be summarized as
Minimize
Z
= Rs. 0.4 X1 +
0.6 X2
+ 0.2
X3
Subject
to
10X1 + 20
X2 + 8X3
>
100
7
X1 +
14 X2 + 12 X3
> 70
X1,
X2, X3
> 0
Example
3
Investment
Planning
Mr.
Majid Khan has Rs.
70, 000 to investment in
several alternatives. The
alternative investments
are
national
certificates with an 8.5%
return, Defence Savings
Certificates with a 10%
return, NIT with a 6.5%
return,
and
khas deposit with a return
of 13%. Each alternative has
the same time until
maturity. In addition,
each
86
Operations
Research (MTH601)
87
investment
alternative has a different perceived
risk thus creating a desire
to diversify. Majid Khan
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;
1.
No
more than 20% of the total
investment should be in khas
deposit.
2.
The
amount invested in Defence
Savings Certificates should
not exceed the amount
invested in the other
three
alternatives.
3.
At
least 30% of the investment
should be in NIT and Defence
Savings Certificates.
4.
The
ration of the amount
invested in national certificates to
the amount invested in NIT
should not exceed
one
to three.
Decision
Variables
There
are four decision variables in this
model representing the
monetary amount invested in
each
investment
alternative.
X1 =
the amount (Rs. ) invested
in national certificates
X2 =
the amount (Rs. ) invested
in Defence Savings
Cert.
X3 =
the amount (Rs. ) invested
in NIT.
X4 =
the amount (Rs. ) invested
in khas deposit.
The
Objective Function
The
objective of the investor is to
maximize the return from
the investment in the four
alternatives. The
total
return is the sum of the
individual returns from each
separate alternative.
Thus,
the objective function is expressed
as
Maximize
Z
= Rs. .085 X1 +
.100 X2
+ .65
X3 + .130 X4
Where
Z
= the total return from all
investments
Rs.
.085 X1 =
the return from the
investment in nat.
Cer.
.100
X2 =
the return from the
investment in certificates of
deposit.
.065
X3 =
the return from the
investment in NIT.
.130
X4 =
the return from the
investment in khas
deposit.
Model
Constraints
87
Operations
Research (MTH601)
88
In
this problem the constraints
are the guidelines
established by the investor
for diversifying the
total
investment.
Each guideline will be
transformed into a mathematical
constraint separately.
Guideline
one states that no more
than 20% of the total
investment should be in khas
deposit. Since the
total
investment will be Rs. 70,
000 (i.e., the investor
desires to invest the entire
amount), then 20% of Rs.
70, 000 is
Rs.
14, 000. Thus, this
constraint is
X4 <
Rs. 14, 000
The
second guideline indicates
that the amount invested in
Defence Savings Cert. should
not exceed the
amount
invested in the other three
alternatives. Since the
investment in Defence Savings
Cert. is X2 and
the amount
invested
in the other alternatives is
X1 +
X3 + X4
the
constraint is
X2 <
X1 + X3
+ X4
However,
the solution technique for
linear programming problems
will require that
constraints be in a
standard
form so that all decision
variables are on the left
side of the inequality (i.e., < )
and all numerical values
are
on
the right side. Thus, by
subtracting, X1 +
X3 + X4
from
both sides of the sign, this
constraint in proper
from
becomes
X2 -
X1 - X3
- X4 <
0
Thus
third guideline specifies that at
least 30% of the investment
should be in NIT and Defence
Savings
Certificates.
Given that 30% of the Rs.
70, 000 total is Rs. 21,
000 and the amount
invested in Defence
Savings
Certificates
and NIT is represented by
X2 +
X3, the constraint is,
X2 +
X3 > Rs. 21,
000
The
fourth guideline states that
the ratio of the amount
invested in national certificates to
the amount
invested
in NIT should not exceed
one to three. This
constraint is expressed as
(X1) /
(X3 )< 1/3
This
constraint is not in standard
linear programming form
because of the fractional relationship of
the
decision
variables, X1/X3.
It is converted as follows;
X1 < 1
X3/3
3
X1 - X3
< 0
Finally,
Majid Khan wants to invest
all of the Rs. 70,
000 in the four alternatives.
Thus, the sum of all
the
investments
in the four alternatives must
equal Rs. 70,
000,
X1 +
X2 + X3
+ X4 =
Rs. 70, 000
88
Operations
Research (MTH601)
89
This
last constraint differs from
the < and > inequalities previously
developed, in that a specific
requirement
exists to invest an exact
amount. Thus, the
possibility of investing more
than Rs. 70, 000 or
less than
Rs.
70, 000 is not
considered.
This
problem contains all three
of the types of constraints
that are possible in a
linear programming
problem:
<, = and >. Further, note
that there is no restriction on a
model containing any mix of
these types of
constraints
as demonstrated in this problem.
The
complete LP model for this
problem can be summarized
as
Maximize
Z
= .085X1 +
.100X2
+
.065X3
+
.130X4
Subject
to
X4 <
14, 000
X2 -
X1 - X3
- X4 <
0
X2 +
X3 > 21, 000
3X1 -
X3 < 0
X1 +
X2 + X3
+ X4 =
70, 000
X1,
X2, X3, X4, >
0
Example
4
Chemical
Mixture
United
Chemical Company produces a chemical
mixture for a customer in 1,
000 - pound batches.
The
mixture
contains three ingredients -
zinc, mercury, and potassium.
The mixture must conform to
formula
specifications
(i.e., a recipe) supplied by
the customer. The company
wants to know the amount of
each ingredient
to
put in the mixture that
will meet all the
requirements of the mix and
minimize total cost.
The
formula for each batch of
the mixture consists of the
following specifications:
1.
The
mixture must contain at
least 200 lbs. of
mercury.
2.
The
mixture must contain at
least 300 lbs. of
zinc.
3.
The
mixture must contain at
least 100 lbs. of
potassium.
The
cost per pound for
mercury is Rs. 4; for zinc,
Rs. 8; and for potassium,
Rs. 9.
Decision
Variables
The
model for this problem
contains three decision
variables representing the
amount of each ingredient
in
the
mixture:
89
Operations
Research (MTH601)
90
X1 =
the number of lbs. of
mercury in a batch.
X2 =
the number of lbs. of zinc
in a batch.
X3 =
the number of lbs. of
potassium in a batch.
The
Objective Function
The
objective of the company is to
minimize the cost of
producing a batch of the
chemical mixture. The
total
cost is the sum of the
individual costs of each
ingredient:
Minimize
Z = Rs. 4X1 +
8 X2 + 9 X3
where
Z
= the total cost of all
ingredients
Rs.
4X1 =
the cost of mercury in each
batch
8X2 =
the cost of zinc in each
batch
9X3 =
the cost of potassium in
each batch.
Model
Constraints
In
this problem the constraints
are derived for the
chemical formula.
The
first specification indicates
that the mixture must
contain at least 200 lbs. of
mercury,
X1 >
200
The
second specification is that
the mixture must contain at
least 300 lbs. of
zinc,
X2 >
300
The
third specification is that the
mixture must contain at
least 100 lbs. of
potassium,
X3 >
100
Finally,
it must not be over looked
that the whole mixture
relates to a 1, 000-lb. batch. As
such, the sum of
all
ingredients must exactly equal 1,
000 lbs.,
X1 +
X2 + X3
= 1,
000
The
complete linear programming
model can be summarized
as
Minimize
Z
= 4X1 +
8 X2 + 9 X3
Subject
to
X1 >
200
90
Operations
Research (MTH601)
91
X2 >
300
X3 >
100
X1 +
X2 + X3
= 1,
000
X1,
X2, X3
> 0
Example
5
Marketing
The
Bata Shoe Company has
contracted with an advertising
firm to determine the types
and amount of
advertising
it should have for its
stores. The three types of
advertising available are
radio and television
commercials
and
newspaper ads. The retail
store desires to know the
number of each type of
advertisement it should purchase
in
order
to Maximize exposure. It is estimated
that each ad and commercial
will reach the following
potential audience
and
cost the following
amount.
Type
of Advertisement
Exposure
Cost
(people/ad
or commercial)
Television
commercial
20,
000
Rs.
15, 000
Radio
commercial
12,
000
8,
000
Newspaper
ad
9,
000
4,
000
The
following resource constraints
exist:
1.
There
is a budget limit of Rs.
100,000 available for
advertising.
2.
The
television station has enough
time available for four
commercials.
3.
The
radio station has enough
time available for ten
radio commercials.
4.
The
newspaper has enough space
available for seven
ads.
5.
The
advertising agency has time
and staff to produce at most a total of
fifteen commercials ads.
Decision
Variables
This
model consists of three
decision variables representing
the number of each type of
advertising
produced:
X1 =
the number of television
commercials
X2 =
the number of radio
commercials
X3 =
the number of newspaper
ads
91
Operations
Research (MTH601)
92
The
Objective Function
The
objective of this problem is different
from the objectives in the
previous examples in which
only profit
was
Maximized (or cost
minimized). In this problem profit is
not Maximized, but rather
the audience exposure
is
Maximized.
This
objective function demonstrates that
although a linear programming
model must either Maximize
or
Minimize
some objective, the
objective itself can be in
terms of any type of
activity or valuation.
For
this problem the objective
of audience exposure is determined by
summing the audience
exposure
gained
from each type of
advertising
Maximize
Z
= 20, 000 X1 +
12, 000 X2
+ 9, 000
X3
Where
Z
= the total number of audience
exposures
20,
000 X1 =
the estimated number of
exposures from television
commercials
12,
000 X2 =
the estimated number of
exposures from radio
commercials
9,
000 X3 = the estimated
number of exposures from
newspaper ads
Model
Constraints
The
first constraint in this model
reflects the limited budget
of Rs. 100, 000 allocated
for advertisement,
Rs.
15,
000 X1 +
6, 000 X2
+ 4, 000
X3 < 100, 000
where
Rs.
15, 000 X1 =
the amount spent for
television advertising
6,
000 X2 =
the amount spent for
radio advertising
4,
000 X3 =
the amount spent for
newspaper advertising
The
next three constraints represent
the fact that television and
radio commercials are
limited to four and
ten,
respectively, while newspaper
ads are limited to
seven.
X1 < 4
commercials
X2 < 10
commercials
X3 < 7
ads
92
Operations
Research (MTH601)
93
The
final constraint specifies
that the total number of
commercials and ads cannot
exceed fifteen due to
the
limitations of the advertising
firm:
X1 +
X2 + X3
< 15
commercials and ads
The
complete linear programming
model for this problem is
summarized as
Maximize
Z
= 20, 000 X1 +
12, 000 X2
+ 9, 000
X3
Subject
to
Rs.
15, 000 X1 +
6, 000 X2
+ 4, 000
X3 < Rs. 100,
000
X1 <
4
X2 <
10
X3 <
7
X1 +
X2 + X3
< 15
X1,
X2, X3
> 0
Example
6
Transportation
The
Philips Television Company
produces and ships
televisions from three
warehouses to three retail
stores
on
a monthly basis. Each
warehouse 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.
Karachi
300
2.
Lahore
100
3.
Islamabad
200
------
600
Each
retail store has the
following monthly demand for
television sets:
Store
Demand
(sets)
A.
Faisalabad
150
B.
Peshawar
250
C.
Hyderabad
200
-----
600
93
Operations
Research (MTH601)
94
The
costs for transporting television
sets from each warehouse to
each retail store are different as a
result
of
different modes of transportation and
distances. The shiping cost
per television set for each
route are,
From
To
store
Warehouse
A
B
C
1
Rs.
6
Rs.
8 Rs. 1
2
4
2
3
3
3
5
7
Decision
Variables
The
model for this problem
consists of nine decision
variables representing the
number of television sets
transported
from each of the three
warehouses to each of the
three stores,
Xij
= the No. of television sets
shipped from warehouse "i"
to store "j" where i = 1, 2, 3
and j = A, B, C.
Xij is
referred to as a double subscripted
variable. However, the
subscript, whether double or
single simply
gives
a "name" to the variable (i.e.,
distinguishes it from other
decision variables). As such,
the reader should
not
view
it as more complex than it actually is.
For example, the decision
variable X3A Islamabad to store A
in
Faisalabad.
The
Objective Function
The
objective function of the television
manufacturer is to minimize the total
transportation costs for
all
shipments.
Thus, the objective function is
the sum of the individual
shipping costs from each
warehouse to each
store.
Minimize
Z
= Rs. 6X1A + 8X1B
+ 1X1C +
4X2A + 2X2B
+ 3X2C +
3X3A + 5X3B
+ 7X3C
Model
Constraints
The
constraints in this model are
available television sets at each
warehouse and the number of
sets
demanded
at each store. As such, six
constraints exist -- one for
each warehouse's supply and
one for each
store's
demand.
For example, warehouse 1 retail
stores. Since the amount
shipped to the three stores
is the sum of X1A, X1B,
and
X1C the constraint for
warehouse 1 is
X1A +
X1B + X1C
=
300
This
constrain is an equality (=) for
two reasons. First, more
than 300 television sets
cannot be shipped,
because
that is cannot be shipped,
because all 300 are
needed at the three stores,
the three warehouses must
supply
all
that can be supplied. Thus,
since the total shipped from
warehouse 1 cannot exceed
300 or be less than 300
the
constraint
is equality. Similarly, the other
two supply constraints for
warehouse 2 and 3 are also
equalities.
X2A +
X2B +X2C
=
100
94
Operations
Research (MTH601)
95
X3A +
X3B + X3C
=
200
The
three demand constraints are
developed in the same way
except that television sets
can be supplied
from
any of the three warehouses.
Thus, the amount shipped to
one store is the sum of
the shipments from the
three
warehouses:
X1A +
X2A + X3A
=
150
X1B +
X2B + X3B
=
250
X1C +
X2C + X3C
=
200
The
complete linear programming
model for this problem is
summarized as:
Minimize
Z
= Rs. 6X1A+8X1B+1X1C +
4X2A + 2X2B
+ 3X2C +
3X3A + 5X3B
+ 7X3C
subject
to
X1A +
X1B + X1C
=
300
X2A +
X2B + X2C
=
100
X3A +
X3B + X3C
=
200
X1A +
X2A + X3A
=
150
X1B +
X2B + X3B
=
250
X1C +
X2C + X3C
=
200
Xij >
0
95
Table of Contents:
|
|||||