Linear Programming:LIMITATIONS OF LINEAR PROGRAMMING

<< Linear Programming:LINEAR PROGRAMMING PROBLEM

Linear Programming:SOLUTION TO LINEAR PROGRAMMING PROBLEMS >>

VirtualUniversity of Pakistan

OperationsResearch (MTH601)

101

Commodity

Amount

Volume/ton

Profit/ton

(tons)

(cubicmeter)

(Rs.)

6000

600

4000

800

2000

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.

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 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

Table of Contents: