# Operations Research

<<< Previous Linear Programming:LIMITATIONS OF LINEAR PROGRAMMING Next >>>

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 non-linear 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
man-hoursrequired 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.
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 non-linearity 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 by-product 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 non-integer 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 non-integral 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 integer-programming 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