Linear Programming Theory #pdf

468 times

598 KB

**File Content -**

C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 1 of 18
CHAPTER 11: LINEAR PROGRAMMING
Question:
Explain LPP.
Answer:
Linear programming is a mathematical technique for determining the optimal
allocation of resources and achieving the specified objective when there are
alternative uses of the resources like money, manpower, materials,
machines and other facilities. The objective in resource allocation may be
either cost minimization or profit maximization.
Categories of the Linear Programming Problems (LPP):
i. General Linear Programming Problems.
ii. Transportation Problems.
iii. Assignment Problems.
(General Linear Programming problems are dealt with in this chapter and the
rest will be taken up in the following chapters.)
General Linear Programming: A linear programming problem consists of
an objective function (viz. Maximising or Minimising) with a set of variables
subject to certain constraints involving the usage of resources that can be
expressed as linear mathematical functions.
Question:
Explain the requirements of LP.
Answer:
In order to apply LP the following requirements are to be met:
a. Objective to be identifiable and measurable: There should be an
objective which should be in identifiable and measurable terms.
b. Activities to be identifiable and measurable: The activities to be
included should be distinctively identifiable and measurable in
quantitative terms.
c. Resources to be identifiable and measurable: The limited
resources of the system which are to be allocated for attainment of
goal should also be identifiable and measurable.
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 2 of 18
d. Divisibility: The resources required are directly proportional to
respective outputs.
e. Additivity: The relationships representing the objective function and
the resource constraints must be in linear nature in the form of
equations or inequalities respectively.
f. Finite Choices: There should be feasible alternative courses of action
available to the decision maker.
When the above conditions are satisfied in a given situation, the problem can
be expressed in algebraic form called LPP and then solved for optimal
solution.
Formulation of an LPP: The basic and first step for a solution to a LPP
begins with the formulation of the objective function with variables and
utilisation of the resources with respective constraints expressed in the form
of equations or inequations. This can be explained further by an example.
Consider a unit manufacturing 2 products A & B with unit profits of Rs. 3 &
Rs. 4 respectively. Further, the products are to be produced using 2
materials X & Y as per the following table:
Particulars Material X Material Y
Product A 2 Kgs. 4 Kgs.
Product B 3 Kgs 2 Kgs.
Maximum availability of materials 16 Kgs. 16 Kgs.
Presuming that there is no restriction on demand, and x1 & x2 are the
respective units of A & B produced, the above can be formulated as:
Maximise 3x1+4x2; Objective function
Subject to:
2x1 + 3x2 ≤ 16 Constraint for Material X
4x1 + 2x2 ≤ 16 Constraint for material Y
Non Negativity Constraint: Further, the units of A & B produced cannot be
negative. Hence the following non negativity constraints are also included.
x1 ≥ 0 & x2 ≥ O
Solution of an LPP: There are 3 methods of solving an LPP:
a. Graphical Method;
b. Trial and Error Method; and
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 3 of 18
c. Simplex Method.
Graphical Method: This method can be used to solve LPP only when there
are 2 variables. For higher variables, this method cannot be applied. The
following are the steps involved in solving LPP by graphical method:
a. Formulating the linear programming problem.
b. Plotting the capacity constraints on the graph paper.
c. Determining the region that satisfies the set of given inequalities.
d. Ensuring that the feasible region is bounded. If the region is not
bounded, it implies either there are additional hidden conditions or the
problem does not have solution.
e. Identifying feasible region and coordinates of corner points.
f. Constructing the matrix E of the extreme points, and the column
vector C of the objective function.
g. Testing the corner point which gives maximum profit. The optimum
solution to a LPP will lie only at one of the corner points only based on
EXTREME POINT THEOREM. Hence, other intermittent points need
not be checked.
h. Finding the matrix product E C. The objective function is optimised
relating to the same row elements of the extreme point matrix E.
i. If the slope of the objective function is same as that of one side of
feasible region, there are multiple solutions to the problem. However,
the optimized value of the objective function remains the same.
j. For decision – making purpose, sometimes, it is required to know
whether optimal point leaves some resources unutilized.
Consider:
Maximise 3x1+4x2; Objective function
Subject to:
2x1 + 3x2 ≤ 16 Constraint for Material X
4x1 + 2x2 ≤ 16 Constraint for material Y
X1, x2 ≥ 0
The graph will be:
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 4 of 18
The shaded region in the graph represents the feasible region. Hence the
solution will be at one of the corners of the feasible region multiplied with
column vector Viz.
0 0
0 5.33 X 3
2 4 4
4 0
Thus the values will be:
For (0, 0) it will be 0*3+0*4=0
For (0, 5.33) it will be 0*3+5.33*4=21.32
For (2, 4) it will be 2*3+4*4=22 and
For (4, 0) it will be 4*3+0*4=12
Of the above, since 22 is maximum, it is the result.
5.33
0
4
8
0
2x1+3x2=16
y = 0
4x1+2x2=16
-1
0
1
2
3
4
5
6
7
8
9
0123456789
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 5 of 18
Trial & Error Method: This is the algebraic approach of solving LPP. Under
this method, first the inequalities are to be converted into equalities. This
can be done by adding non negative slack variables in the equations. Slack
variables represent idle resources. In the objective function, the
contribution per unit of a slack variable is always taken as zero, since no
profit can be made on idle resources. Upon adding slack variables, the LPP
formulation illustrated above will be:
Maximise 3x1+4x2+0x3+0x4; Objective function
Subject to:
2x1 + 3x2 + x3 + 0x4 = 16 Constraint for Material X
4x1 + 2x2 + 0x3 + x4 = 16 Constraint for material Y A
x1 ≥ 0; x2 ≥ O; x3 ≥ 0; x4 ≥ 0.
Similarly in ≥ (greater than equal to) type inequalities, we subtract a
variable called surplus variable to convert into equality. Surplus variables
represent excess amount of resources utilised over and above the
available resources. In the objective function, the contribution per unit of
surplus variable is also taken as zero.
In the equations mentioned above, the number of variables are greater than
the number of equations. These types of equations give infinite solutions
yet it has finite vertices. The coordinates of the vertices can be determined
by applying Basis Theorem.
Basis Theorem: It states that for a system of m equations in n variables
(where n > m) has a solution in which at least (n-m) of the variables have
value of zero as a vertex. This solution is called a basic solution.
In our illustration, we are having 4 variables with 2 equations. Hence, as
per basis theorem, out of 4 variables, at least 2 variables should have zero
values. By permutation and combination method, assigning zeros to 2
variables at a time in the given set of 2 equations of the illustration, we get
below the 6 sets of simultaneous equations:
Set 1 When x1 & x2 are taken as zeros: 1x3+0x4=16
x3 = 16
0x3+1x4=16
x4 = 16
Set 2 When x1 & x3 are taken as zeros: 3x2=16
x2 = 16/3
2x2+x4=16
x4=16/3
Set 3 When x1 & x4 are taken as zeros: 3x2+x3=16
x3=-8
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 6 of 18
The equations are solved as simultaneous equations to get the values of
variables. Since set 3 & set 4 have negative values (which is against our
assumption of ≥ 0) they are ignored.
By substituting the values of x1 to x4 in the objective function:
Maximise 3x1+4x2+0x3+0x4, we get
For set 1 0
For set 2 64/3
For set 5 12
For set 6 22
Hence, solution for set 6 is optimal.
Limitations of Trial & Error Method: This method has serious limitations
as detailed below:
A. In case the constraints (m) and variables (n) are more, the solution
will be very tedious and time consuming.
B. The profits / losses of successive solutions keep fluctuating as seen
above.
C. Since some sets yield unfeasible solutions, there needs to be a method
for their early identification and elimination to save time.
Simplex Method: This is a mathematical algorithm for solving LPP and is
very widely used. In this case, subsequent iterations lead to successive
improvements in arriving at the objective of maximisation or minimisation.
This is highly efficient and versatile and also amenable for further
mathematical treatment and interesting interpretations can be made. The
simplex algorithm applies to both maximisation and minimisation problems.
The only difference in the algorithm involves the selection of the incoming
variable. In the maximisation problem the incoming variable is the one with
highest +ve value in net evaluation row (NER). (Conversely, it is the most –
ve variable that is selected as the incoming variable in a minimization
problem.) And if all elements in the NER are either negative (or +ve for
2x2=16 x2=8
Set 4 When x2 & x3 are taken as zeros: 2x1=16
x1=8
4x1+x4=16
x4=-16
Set 5 When x2 & x4 are taken as zeros: 2x1+x3=16
x3=8
4x1=16
x1=4
Set 6 When x3 & x4 are taken as zeros: 2x1+3x2=16 x1=2
4x1+2x2=16
x2=4
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 7 of 18
minimisation) or zero, it is the indication for the optimal solution.
Considering the initial example:
Maximise 3x1+4x2+0x3+0x4; Objective function
Subject to:
2x1 + 3x2 + x3 + 0x4 = 16 Constraint for Material X
4x1 + 2x2 + 0x3 + x4= 16 Constraint for material Y A
x1 ≥ 0; x2 ≥ O; x3 ≥ 0; x4 ≥ 0.
The initial Simplex table can be formed as below:
Coefft. Matrix Identity Matrix
Basic Variables Non Basic Variables
1 2 3 4
5
6
Fixed
Ratio
Program
(basic
variables)
Profit
/ unit Qty. 3 4 0 0 Replac
ement
Ratio
x1 x2 x3 x4
A
x3 0 16 2 3 1 0
16/3
2/3 x4 0 16 4 2 0 1 8 Key Rows
N E R 3 4 0 0
B
1/4 x2 4 16/3 2/3 1 1/3 0 8 Key
Elements
x4 0 16/3 8/3 0 -2/3 1 2
N E R 1/3 0 -4/3 0
C
x2 4 4 0 1 1/2 -1/4 Key
Columns
x1 3 2 1 0 -1/4 3/8
N E R 0 0 -5/4 -1/8
Simplex table is vertically divided into 6 columns (1,2,3,4,5&6) and
horizontally into 3 rows A, B & C.
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 8 of 18
Column 1 consists fixed ratio that is obtained by dividing the corresponding
key column element with key element.
Column 2 consists basic variables that are considered for the solution (Basic
variables are the variables that are listed under program column. Rest of
the variables are called non-basic variables.) In the initial solution, always,
artificial slack variables if any, and surplus and / or slack variables are
considered.
Column 3 consists corresponding coefficients of the basic variables in the
objective function.
Column 4 consists figures listed on the right hand side of the constraints.
Column 5 consists respective coefficients of the objective function.
Column 6 consists Replacement Ratio that is obtained by dividing the
quantities with respective elements in the key column.
Figures in rows A, B & C indicate successive iterations.
The steps involved in Simplex Method solution are:
a. Formulation of LPP by restating in mathematical form, i. e writing
the objective function and the constraints;
b. Developing equations from inequalities by adding or deducting slack
/ surplus / artificial slack variables;
c. Ensuring all variables are ≥ 0: All variables are to be ≥ 0. If there
is any unrestricted variable (discussed later), it should be converted.
d. RHS of the constraints to be +ve: It should be ensured that the
right hand side of the constraints is +ve. If not, it should be made
+ve by multiplying the entire equation with -1.
e. Developing the initial table including the NER;
f. Identifying the Key Column: Key column is the column with
highest +ve no. for maximisation problems and highest –ve no. for
minimisation problems from the values in NER;
g. Identifying the Key Row: Key row is the minimum of the figures
obtained by dividing the quantities with respective elements of pivot
column. The figures so obtained are called Replacement Ratios or
Minimum Ratios. In case if there happen to be any negative figures as
replacement ratios, such figures are to be ignored. However, zeros
are to be considered. Key Element (i.e. the intersection element of
Key column and Key Row);
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 9 of 18
h. Calculating the revised row: This is calculated by dividing all the
elements of key row with the Key Element.
i. Calculating the Fixed Ratio: This is arrived by dividing each
element of Key Column with Key Element;
j. Calculation of balance rows: This is done by subtracting the
existing row element from the product of the fixed ratio and the
corresponding key element in the key row;
k. Ascertaining the NER: This is done by deducting the sum of the
products of profit column figures with corresponding elements in each
column and deducting such sum from the corresponding coefficient of
the objective function;
l. Checking for optimality: i. e. to find whether all the values in the
NER are zero or are –ve for maximisation objective (zero or +ve for
minimisation objective.)
m. If this is not achieved then, steps (d) to (j) are to be repeated till
these criteria are satisfied.
The words Key and Pivot are used interchangeably with same meaning.
Note: We understand that the mathematical language and sense of the
points described above are confusing and could be difficult to understand as
well at one outgo. Readers are strongly advised to very carefully follow the
method of solving the LPP illustrations in the class room and to practice
them to understand and appreciate the beauty of this versatile mathematical
algorithm backed by strong logic.
Artificial Slack variables: consider the constraint function 3x+9y≥100. To
convert this into equal, we deduct from left hand side the Surplus Variable
(S1) thus making it 3x+9y-S1=100. Surplus variables represent excess
amount of resources utilised over and above the available resources.
In case we presume x & y to be zero, then the value of S1 turns to be –ve.
This will be against our basic assumption of all variables ≥ 0. To overcome
this contradiction, we introduce another variable called Artificial Slack
Variable A1. Artificial Variables represent imaginary brands. Whereas
slack variables and surplus variables have always zeros as cost coefficients,
Artificial slack variables always have infinitely large cost coefficients, usually
represented by M. Further, the sign of artificial slack variables in the
objective function depends on the type of objective function whether it is
maximising or minimising. In case of maximising problems, the sign of M
will be –ve and for minimising problems, the sign will be +ve. The signs for
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 10 of 18
artificial slack variables in objective function do not have any relationship
with the signs ≥ or ≤ in the constraint function. Further, in the initial
iteration, always artificial slack variables are considered in the program
column and once artificial variables are replaced with real variables, they will
never come into the iteration again due to the infinitely large cost
coefficients associated with them.
Equality sign in constraints: In case there exists ‘=’ (equal) sign in the
constraint, then only Artificial Slack Variable is added with M as coefficient in
the objective function. Sign of M in objective function depends on the type of
problem (i.e. maximisation (-ve) or minimisation (+ve)). Slack or surplus
variables are not used for this constraint. This is because under simplex
method, in the initial solution, only slack variables, surplus variables and
artificial slack variables are considered for iteration.
Question:
Define and explain unrestricted variable.
Answer:
Unrestricted variable: One of the primary conditions of an LPP is all
variables should be ≥ zero. There could be cases where a variable can take
any value viz. –ve, zero or +ve. This type of variable is called unrestricted
variable. In such cases, the unrestricted variable is to be shown as the
difference of 2 non –ve variables, thus meeting the requirement of LPP.
Example: consider the objective function having 3 variables x1,x2 ≥ 0 and
x3 is unrestricted. X3 is unrestricted implies it can be –ve, zero or +ve. In
these types of cases, x3 should be represented as x4-x5, where both x4, x5
≥ 0 and x3 should be replaced by x4-x5 in the objective function and all
constraints. After arriving at the solution, at the end, x4-x5 should be
substituted for x3.
Question:
Explain Multiple Optimal Solutions with graphical illustration:
Answer:
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 11 of 18
The solution to a LPP need not be unique. An LPP may have multiple optimal
solutions, and this will happen when:
1. One of the constraints line is parallel to objective function line on
graph (i.e. iso profit line, a line indicating same profit.),
2. the constraint line should form part of boundaries of feasible region of
the graph, and
3. the constraint should be a binding constraint (Binding constraint is a
constraint that is essential for the given problem. ie. It cannot be
redundant constraint.)
In the optimal simplex table, if the NER contains zero(s) under non basic
variable(s), then the solution is not unique and multiple solutions do exist.
Consider maximise 8x1+16x2
Subject to x1+x2 ≤ 200
X2 ≤ 125
3x1+6x2 ≤ 900 and
X1, x2 ≥ 0
The graph for the above will be as below:
125
200
0
125125
0
150
200
00
150
x1+x2=200
y = 125
3x1+6x2=900
0
50
100
150
200
250
050100150200250300350
Between these 2 points,soluitons will be
infinite
Linesparallel to object function line i. e. Iso
Profit Lines
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 12 of 18
It may be observed that the points (50, 125) and (100, 100) give same
results for the objective function. Further, infinite solutions will exit between
these two points.
Question:
Explain Infeasible Solution with graphical illustration.
Answer:
There will not be any solution to an LPP when the constraints are
inconsistent. In the graphic method we can find this when the feasible
region is empty and unbounded. i.e. there will not be any point on the graph
which meets all constraints.
When there exists an Artificial variable as basic variable with a +ve value in
quantity column of optimal simplex table, then there will be no feasible
solution.
Consider maximise 20x1+30x2
Subject to 2x1+x2 ≤ 40
4x1-x2 ≤ 20
X1 ≥ 30 and
X1, x2 ≥ 0
This can be graphically represented as:
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 13 of 18
Since there do not exist any points in the graph satisfying all the given
constraints, the solution is infeasible.
Question:
Explain Unbounded Problem with graphical illustration.
Answer:
For a maximisation LPP unboundedness occurs when there is no constraint in
the solution so that one or more variables can be increased infinitely without
violating any of the constraints. It could be possible to find several high
values to variables obeying the constraints.
If all replacement ratios are –ve or equal to ∞ in a simplex table, then the
algorithm terminates and it implies the solution is unbounded.
Consider maximise 10x1+20x2
Subject to 2x1+4x2 ≥ 16
x1+5x2 ≥ 15 and
x1, x2 ≥ 0
this can be graphically represented as:
0
40
-20
0
40
0
10
40
2x1+x2=40
4x1-x2=20
-30
-20
-10
0
10
20
30
40
50
05101520253035
x1=30Feasible Regionx1=30Feasible Region
2x1+4x2=16x1+5x2=15
-0.5
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
0246810121416
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 14 of 18
In this case there is no outer limit to the feasible region. Hence, the
solutions are infinite.
Infeasibility Vs. Unboundedness: Both infeasibility and unboundedness
are similar as both do not have any specific optimal solution. The striking
difference is in case of infeasibility there will not be even a single feasible
solution whereas in case unboundedness there will be infinite feasible
solutions.
Degeneracy: When one or more of the basic variables have zero in
quantity column, the simplex table and the solution are said to degenerate.
This happens when in the preceding table the replacement ratios of 2 or
more basic variables are same. Further, in case of degeneracy, the following
table will not reflect any improvement in the objective function, which is one
of the main features of simplex tables. In such a scenario, the table will not
comply with Basis Theorem. It is very important to note that degeneracy in
LPP could be temporary and could vanish in the final solution. Hence the
table should be solved till NER criteria are met.
In graphic method it can be identified when one of the constraint lines does
not pass through the optimum coordinates.
Question:
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 15 of 18
Write the characteristics of Dual in Linear Programming.
Answer:
1. Every LPP is called Primal and can be expressed as a dual and vice
versa.
2. The number of constraints in the primal model equals the number of
variables in the dual model and vice versa. Further, the coefficients of
the objective function in the primal become the right hand sides of the
constraints in the dual and the right hand sides of the primal become
the coefficients of the objective function in the dual. Vice versa also
holds good between dual and primal.
3. If the primal model is a maximisation problem then the dual will be a
minimisation problem and vice versa.
4. If the constraints in primal have ≤ sign, in the dual they have ≥ sign
and vice versa. Before writing dual it is necessary to express the
primal LPP in standard form. i.e. all the constraints for a maximisation
problem are to be put in the form of ≤ and for minimisation problem
all the constraints are to be put in the form of ≥. All variables for the
problem should be non –ve. i.e. ≥ zero.
A ≥ sign can be converted into ≤ by multiplying both sides with -1 and
vice versa.
Further, in case there is a constraint with equality sign it needs to
be split into ≤ and ≥ signs constraints and multiplying one of them
with -1 as per requirement depending on maximisation or
minimisation.
Example:
Consider 3x1+4x2=22.
This can be written as 3x1+4x2≤22 and 3x1+4x2≥22 and converting
one of them into ≤ or ≥ sign by multiplying with -1 on either sides of
the inequality depending on the requirement of maximisation or
minimisation.
5. The solution of the primal model will be same as the solution of the
dual model and vice versa.
6. The objective functions of the two optimal tables will have identical
final values.
7. Dual of the primals dual problem is the primal problem itself.
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 16 of 18
8. Feasible solutions to a primal and dual problem are both optimal if the
complementary slackness conditions hold, that is, (value of a primal
variable) x (value of the corresponding dual surplus variable) = 0 or
(value of a primal slack variable) x (value of the corresponding dual
variable) = 0. If this relationship does not hold, than either the primal
solution or the dual solution or both are not optimal.
9. If the primal problem has no optimal solution because of infeasibility,
then the dual problem will have no optimal solution because of
unboundedness and vice versa.
Special points on LPPs’:
1. The positive figures (for maximisation problems) in NER indicate the
unit opportunity cost being foregone by not including them
respectively in the program and vice versa for minimisation problems.
2. Surplus variable along with Artificial Slack variable are both used when
we come across ≥ sign in the constraints functions to make them
equal. Further artificial slack variable is used to comply with non
negative assumption.
3. Fractions in Simplex iterations are to be continued as they are for ease
in further workings instead of converting them into decimals.
Converting them into decimals will land the solver into confusion and
problems.
4. Inequalities in wrong direction: Whether to introduce slack or
surplus and artificial slack variable depends on the type of inequality
and has got nothing to do with whether the objective function is
maximisation or minimisation.
5. Sign of Artificial slack variable: Similarly, The sign for artificial
slack variables in objective function does not have any relationship
with the signs ≥ or ≤ in the constraint function. In maximisation
problems M has –ve sign and minimisation problems M has +ve sign.
Once an artificial slack variable exits from simplex iteration, again it
will never enter because of the prohibitively high value associated with
it.
6. In case 2 or more variables have same values in NER then, any one of
them can be chosen as incoming variable for iteration.
7. Lower or upper bounds can be specified in an LPP. For example, it can
be given that variable x1 ≥ 50. In such cases, another variable y1 is
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 17 of 18
assumed where y1 = x1 + 50 implies x1=y1–50 and substituting the
value of x1 with y1-50 at all places and continuing in the routine way.
8. In all simplex tables there is bound to be a unit matrix eventhough,
the columns may not be adjacent.
9. Simplex method, Dual method, Graphical method and Trial & error
methods provide different ways of solving the problems. In all cases
the result will be same and each has its ads and disads. Of all, the
simplex method is versatile.
Question:
Explain the areas where LP is used.
Answer:
LP can be comfortably used in:
a) Production, Planning and Product Mix Problems;
b) Blending Problems;
c) Diet Problems;
d) Trim-loss Problems;
e) Distribution Problems;
f) Advertising Mix;
g) Manufacturing Problems;
h) Assembling Problems;
i) Investment Problems;
j) Agricultural Applications;
k) Flights scheduling;
l) Production Balancing, Inventories, Work force,
m) Personnel Assignment Problems; etc.
Question:
State the limitations of LPP.
Answer:
The limitations of LPP are:
1. Primary requirement of LPP is that objective function and the
constraints are to be linear.
C A & C M A Coaching Centre, Nallakunta, Hyderabad. P V Ram, B. Sc., ACA, ACMA – 98481 85073
Score 60+ thro’ SYSTEMATIC & SMART Study Page 18 of 18
2. In LPP fractional values are permitted to the decision variables.
Practically this may not be always possible. In certain cases this can
be overcome by treating the fractional parts as Work in Process or
rounding off fractions.
3. In LPP, coefficients of the objective function and the constraint
equations are to be completely known and these should not change
during period of study.
4. LPP does not consider the effect of time and uncertainty.
5. Parameters appearing in the LPP are presumed to be constant.
Practically this may not be so.
6. LPP deals with single objective. For multiple objectives, Goal
Programming and objective programming tools are used.

Tally Prime Course

CA Pooja Garg

GST Litigation Course

CA Abhishek Raja

GST Practitioner Certificate Course 32nd Batch

CA Arun Chhajer