

VirtualUniversity
of Pakistan
OperationsResearch
(MTH601)
101
Commodity
Amount
Volume/ton
Profit/ton
(tons)
(cubicmeter)
(Rs.)
A
6000
60
600
B
4000
50
800
C
2000
25
500
In
order to preserve the trim
of the ship, the weight in
each hold must be
proportional to the capacity in
tons. How
shouldcargo
be distributed so as to maximizeprofit?
(only formulation of the
problem needed).
LIMITATIONS
OF LINEAR PROGRAMMING
We
shall see the
underlyingassumptions of linear
programmingthat limit
itsapplication.
Proportionality
A
prerequisite in formulating the objective
function and the constraints in a
linear programming model
is
thelinearity.
This means thatthe
measure of effectivenessand
the usage of
resourcesavailable must be
proportional
to
the level of each
activitydecided individually.
But in real life situations
thereare many problems,
whichare non
linear,
and the solution to
suchproblems is obtainable
forsome special cases
only.Sometimes it is possible
to
convertthe
nonlinear programmingproblem
into the linearprogramming
model so thatthe simplex
methodcan
very
well be employed; but this
is not always possible.
In
certain linear
programmingproblems, it may appear
thatthe problem is completely
linearbut sometimes
deceiving.
It is not always problem is completely
linear but
sometimesdeceiving. It is not always
truethat both
the
marginal
measure of effectiveness
andthe marginal usage of
eachresource will be
constantsover the complete
or
entirerange
of levels of eachactivity.
For example if theproduction
level changes in an industry, the profit
or the
manhoursrequired
per unit of the level of
the activity may change. In
other words the coefficients in
theobjective
function
and the coefficients of
theconstraints may suffer a
change.
Anothertype
of nonlinear entering is what we call
the fixed chargeproblem.
This happens
wheneverthere
is
a 'set up' cost
associatedwith an activity. If x be
the level of the activity
and Δ
be
if
x
=
0
⎫
⎧0
Δ=⎨
⎬
⎩
Ax
+
B
if
x
≥
0⎭
whereA is
the fixed charge
coupledwith any positive level of
theactivity. Since Δ
is
not a linear function of x
over
its
entire range because of
sudden increase at x
=
0. Hence this poses
theobjection to include in
thelinear
programmingmodel.
Additivity
Let
the measure of
effectivenessand each
resource usage be directly
proportional to the level of
each
activityselected
individually. This doesnot
ensure linearity. A case of
nonlinearity may arise if there
arejoint
101
VirtualUniversity
of Pakistan
OperationsResearch
(MTH601)
102
interactionsbetween
some of the activities regarding
the total measure of
effectiveness or the total usage of
some
resource.Hence
it is required thatthe
additives be additive withrespect to
the measure of effectiveness
andeach
resourceusage.
This implies that the total
measure of effectiveness
andeach total resource
usagerequired for
the
jointperformance
of the activities must be equal to
the respective sums of
these quantities
resultingfrom each
activitybeing
consideredindividually.
This
idea can be illustrated with an
example. Let a company
manufacturetwo items.
Suppose thatthe
profit
would
be c1x1 if
the first item is produced
at a level of x1, and the
seconditem is not produced
at all(i.e.) x2 = 0 and
thatc2x2 would be the profit by
producing the second
itemonly at a level of x2 and the
firstitem is not produced
at
all(i.e.)
x1 = 0. These two
productsare additive with
respect to profits, only if the total
profitwould be c1x1 + c2x2
whenboth
x1 = 0 and x2 = 0. This would not be true
if prices are lowered in
order to sell both x1 and x2 instead of just
one
or the other.
Two
activities not additive with respect to
resource usage would
be,when a byproduct is
producedwith
thescrap
material from the primary item. This
material would stillhave to
be purchased if onlyone of
the twoitems
wereproduced.
If both the itemsare
produced, the total requirement is
less than thesum of
the requirements, if
each
wereproduced
individually.
Divisibility
Manytimes
we come across caseswhere
the optimal solution leads to a
noninteger value of the
decision
variables.But
if the decisionvariables
represent thenumber of items
produced, it would have
physicalsignificance
only
if they turn out to be
integer values. We
cannotproduce nonintegral
values.The solution
procedureneed
decisionvariable
must be permissible in order to
get an optimalsolution. This is what is
referred to as an 'integer
programmingproblem'.
Anyhow solution procedure is still
employed when an integer solution is
required.Suppose
we
use the simplex method to
obtain the solution to an
integerprogramming problem. If
theprocedure yields an
optimal
solution with integer
valuefor the decision
variables,then this will be
thedesired solution to
theproblem
referred.
If we do not get an
integersolution to the
problem, oneoption is to
round it off to the nearest
integervalue.
This
may lead to some
difficulties.First the
integer roundedoff to the
nearest integerneed not be
feasible.Second,
even
if it is feasible, this solution may not
be too near
optimality.Considerable progress
hasbeen made recently
in
developingthe
solution to integer programmingproblem
leading to optimuminteger
solution.
Deterministic
In
formulating the linear
programmingmodel for a
problem, the coefficients of profit or
cost,constraints
andresource
availability or usageare
assumed to be constantsknown. In
real life, theymay
not be known
completely
and they may be liable
forchanges from time to
time.Sometimes it is difficult to
predictthe precise
value
of these coefficients. Linear
programmingmodels are
developed to predict the
future solution in which
these
coefficients
must be known exactly to
getthe solution. These
coefficients may sometimes be
randomvariables
following
a certain probability distribution.
A
number of approaches is
sometimesused when some of
thecoefficients are not
known.Sometimes we
go
in for sensitivity analysis, an
extension of sensitivity analysis known
as parametric programming
andalso chance
constrainedlinear
programmingmodel.
102
Table of Contents:

