Unit.2. linear programming

This is a course offered for Agricultural Economics

1. Chapter Two
Linear Programming
By;-Dagnaygebaw Goshme(MSc.)

2. 2.1.Basic Concepts in Linear Programming
Mathematicalprogrammingisusedtofindthe
bestoroptimalsolutiontoaproblemthatrequires
adecisionorsetofdecisionsabouthowbestto
useasetoflimitedresourcestoachieveastate
goalofobjectives.
Stepsinvolvedinmathematicalprogramming
1
st
.Conversionofstatedproblemintoamathematical
model;
2
nd
.Explorationofdifferentsolutionsoftheproblem.
3
rd
.Findingoutthemostsuitableoroptimumsolution.

3. Linear programmingrequires that all the mathematical
functions in the model be linear functions.
It is a mathematical process that as bee developed to help
management in decision making involving the efficient
allocation of scares resources to achieve a certain
objective.
It is planning of activities to obtain an optimal result.
It maximizeor minimize a linear function, subject to a
set of linear constraints.
The linear model consists of the following
components:
A set of decision variables
An objective function
A set of constraints

4. Decision variables: variables that we used in the model, whose
values are unknown .
Objective function:The function that is to be maximized or
minimized is called the objective function. E.gmax profit and min
cost.
Constraints:are limitations or restrictions imposed by the
problems. include:
A. Resource constraints: Are restrictions that should be clearly
identifiable and measurable in quantitative terms, which arise
from limitation of available resources.
Examples of limited resources:
=>Plant capacity
=>Raw materials availability
=>Labor power
=>Market demand, etc.
B. Non-negativity constraints:Are constraints that require the
decision variables not to take on negative values
Linearity: The Objective Function and the constraints must be linear

5. Linear Programming Problems can be solved by
using:
i.The Geometric method called”
Graphical Method”
ii.The Algebraic method called” Simplex
Method”
Feasible region/solution/for an LP is the set of
all pointsthat satisfies all the LP’sconstraints
and sign restrictions.
For a maximizationproblem, an optimal solution to
an LP is a point in the feasible region with the largest
objective function value.
For a minimizationproblem, an optimal solution is a
point in the feasible region with the smallest objective
function value.

6. 2.2. Formulations of LPP
Application of linear programming involves
allocating resources to activities.
The amount available of each resource is limited, so a
careful allocation of resources to activities must
be made.
Determining this allocation involves choosing the
levels of the activities that achieve the best
possible valueof the overall measure of performance.

7. Stepsin Formulating a Linear Programming Problem
Understand the problem
Identify the Decision Maker (DM)
Identify the decision variables
State the obj. function as a linear combination
of the decision variables
State the constraintsas a linear combination of
the decision variables
Identify upper or lower bounds on DV’s

8. Standard form of Lpp
Maximization
Max z = c
1x
1+ c
2x
2+ ... + c
nx
n objective function
subject to:
a
11x
1+ a
12x
2+ ... + a
1nx
n≤ b
1
a
21x
1+ a
22x
2+ ... + a
2nx
n≤ b
2 constraint
Functions
:
a
m1x1 + a
m2x
2+ ... + a
mnx
n≤b
m
x
1,…x
n>0 non-negativity constraints
x
j= decision variables
b
i= constraint levels
c
j= objective function coefficients
a
ij= constraint coefficients

9. Minimization
Min z = c
1x
1+ c
2x
2+ ... + c
nx
n objective function
subject to:
a
11x
1+ a
12x
2+ ... + a
1nx
n≥ b
1
a
21x
1+ a
22x
2+ ... + a
2nx
n≥ b
2
constraint
functions
:
a
m1x1 + a
m2x
2+ ... + a
mnx
n≥ b
m
x
1,…x
n>0 non-negativity constraints
x
j= decision variables
b
i= constraint levels
c
j= objective function coefficients
a
ij= constraint coefficients

10. Example1: formulate the following LPP
A firm manufactures twoproducts, Xand Y.For
each product, it is necessary to use threedifferent
machines: A, B, and C. To manufacture one unit of
product X, machine Amust be used for three
hours, machine Bfor 1 hour and machine C for 1
hour. To manufacture one unit of product Y
requires two hours on A, 2 hours on B, and 1
hour on C. The profit on X is $500 per unit while
the profit on Y is $350 per unit. Machine A is
available for 24 hours a day, B for 16 hours, and C
for 9 hours. Determine the number of units of X
and Y that should be produced to maximize profit.

11. Machine Required hours Hours available
X Y
A 3 2 24
B 1 2 16
C 1 1 9
Max Z=500X+350Y Objectivefunction
Max Z=500X+350Y => objective function profit max
Subject to
3x + 2y ≤ 24
x + 2y ≤ 16 constraint functions time resource
x + y ≤ 9
X,Y>0 non negativity constraints

12. Example 2: a Chemical manufacture produce three
chemicals: A, B, and C. These chemicals are
produced via two production processes: 1 and 2.
Running process1for an hour costs $4 and yields
3 units of A, 1unit of B, and 1 unit of C. Running
process 2for an hour costs $1 and produces 1
unit of A and 1 of B.To meet customer demands,
at least 10 units of A, 5 of B, and 3 of Cmust be
produced daily. determine a daily production plan
that minimizes the cost of meeting Leary Chemical’s
daily demands.

13. Chemicals Production process minimum
Resources
1== let X2== let Y
A 3 1 10
B 1 1 5
C 1 0 3
Min z 4 1
Min Z=4X+Y objective function, cost min
Subject to
3X+Y>10
X+Y>5
X>3
X,Y >0

14. Example 3: Farmer Geteowns 45 acres of land. She is
going to plant each with wheat or maize. Each acre
planted with wheat yields $200 profit; each with maize
yields $300 profit. 3 workers for wheat and 2 workers for
maize are required labor force while 2 tons & 4 tons of
fertilizer required for wheat and maize respectivly.One
hundred workers and 120 tons of fertilizer are available.
Use linear programming to determine how Jane can
maximize profits from her land.
Max Z= 200W+300M
Subject to
3W+2M<100
2W+4M<120
W,M>0

15. 2.2.1. Assumptions of linear programming
A linear programming model is based on the
following assumptions;
1.Proportionality assumption:exists in the
objective function and the constraints.
Contribution of each activity to the value of the objective
function Z is proportionalto the level of the activity
X
j,as represented by the CjX
jterm in the objective
function.
Resource consumption of each activity in each functional
constraint is proportionalto the level of the activity X
j,
as represented by the a
ijX
jterm in the constraint.
If not hold? use nonlinear programming

16. 2. Additivityassumption: every function in a linear
programming model (whether the objective function or the
left-hand side of the a functional constraint) is the sum of the
individual contributions of the respective activities. i.e
linearity .
If not hold? In most cases we use nonlinear programming.
3. Divisibility assumption:decision variables are allowed to
have any values, including non-integer values, which satisfy the
functional and non-negativity constraints.
Thus, since each decision variable represents the level of
some activity, it is being assumed that the activities can be run
at fractional levels.
In certain situations, the divisibility assumption does not
hold because some of or all the decision variables must be
restricted to integer values. For this restrictions integer
programming model will be used.

17. 4. Certainty assumption:various parameters (namely, the
objective function coefficients, the coefficients in the
functional constraints a
ijand resource values in the
constraints b
i are certainly and precisely known and that their
values do not change with time.
However, in real applications, the certainty assumption is
rarely satisfied precisely. For this reason it is usually important
to conduct sensitivity analysis after a solution is found that is
optimal under the assumed parameter values.
5. Finiteness: A LP model assumes that a finite (limited) number
of choices (alternatives) are available to the decision-maker and
that the decision variables are interrelated and non negative.
The non-negativity condition shows that LP deals with real-
life situations as it is not possible to produce/use negative
quantities.
6. Optimality:In LP, the optimal solution always occurs at the
corner pointof the set of feasible solutions.

18. 2.3.Methods of Solving LP
A linear programming problem can be solved by graphic method or
by applying algebraic method, called the simplex method.
1.Graphic method
it can be used when only two variables are involved. This method
consists of the following steps:
1
st
. Represent the given problem in mathematical form.
2
nd
. Plot each of the constraint on the graph.
3
rd
. Identify the feasible region (or solution space) that satisfies all
the constraints simultaneously. Any point on or within the
shaded region represents a feasible solution to the given
problem.
4
th
. Locate the solution points (identify the corner points from the
solution space).
5
th
.Determine the optimal solution. A solution that optimizes the
objective function.
6
th
.Interpret the results

19. Important Definitions
Solution:The set of values of decision variables X
i (i=1, 2,
….,n)which satisfy the constraints of an LP problem is said
to constitute solution to that LP problem
Feasible solutions:The set of values of decision variables X
i
(i=1, 2… n) which satisfy all the constraints and non-
negativity conditionsof an LP simultaneously.
Infeasible solution:The set of values of decision variables
which do not satisfy all the constraints and non-
negativity conditionsof an LP simultaneously.
Optimum solution:A feasible solution which optimizes
(maximizes or minimizes) the objective function value of
the given LP problem is called an optimum basic feasible
solution.
Unbounded solution:A solution which can increase or
decrease the value of the objective function of LP problem
indefinitelyis called unbounded solution.

20. Example 1.
Consider two models of color TV sets; Model Aand B, are
produced by a company to maximize profit. The profit
realized is $300 from A and $250 from set B. The
limitations are
a.availability of only 40hrs of labor each day in the
production department.
b.a daily availability of only 45 hrs on machine time
c. ability to sale 12 set of model A.
How many sets of each model will be produced each day
so that the total profit will be as large as possible?
solution
It is maximization LPP. i.e, profit

21. Constraints Model A== X1Model B==X2 Max available
hr
Labor hr 2 1 40
Machine hr 1 3 45
Marketing hr 1 0 12
Profit 300 250
1. Formulation of mathematical modeling of LPP
Max Z=300X
1
+250X
2
St:
2X
1+X
2<40
X
1+3X
2<45
X
1<12
X
1,X
2 >0
2. Convert constraints inequalities into equalities to draw graph
2X
1+X
2 = 40
X
1+3X
2= 45
X
1= 12

22. 3. Draw the graph by intercepts
2X
1
+X
2
= 40 ==> (0, 40) and (20, 0)
X
1
+3X
2
= 45==> (0, 15) and (45, 0)
X
1
= 12==> (12, 0)
C
B
15
40
12 20 45
X
1
X
2
A
D
X
1
+3X
2
= 45
(12, 11)
X
1
=12
X
1
=0
X
2
=0
Feasible
Region
4.Identifythefeasibleareaofthesolutionwhichsatisfiesall
constrains.
5.Identifythecornerpointsinthefeasibleregion
A(0,0),B(0,15),C(12,11)andD(12,0)
6.Identifytheoptimalpoint
7.Interprettheresult

23. CornersCoordinatesMaxZ=300 X
1+250X
2
A (0, 0) $0
B (0, 15) $3750
C (12, 11) $6350
D (12, 0) $3600
Interpretation:
12 units of product A and 11 units of product B
should be produced so that the total profit will be
$6350.

24. Example 2;
Suppose that a machine shop has two different types of machines;
machine 1 and machine 2, which can be used to make a single
product .These machines vary in the amount of product produced
per hr., in the amount of labor used and in the cost of operation.
Assume that at least a certain amount of product must be produced
and that we would like to utilize at least the regular labor force. How
much should we utilize each machine in order to utilize total costs
and still meets the requirement?
Resource machine 1
(X1)
Machine2
(X2)
Minimum
required hours
Product
produced/hr
20 15 100
Labor/hr 2 3 15
Operation Cost 25 30

25. solution
It is minimizationLPP. i.e, cost
1. Formulation of mathematical modeling of LPP
Min Z=25X
1+30X
2
St.
20X
1+15X
2>100
2X
1+3X
2>15
X
1,X
2>0
2. Convert constraints inequalities into equalities to draw
graph
20X
1+15X
2=100
2X
1+3X
2=15
X
1,X
2=0

26. 3. Draw the graph by intercepts
20X
1
+15X
2
=100 ==> (0, 20/3) and (5, 0)
2X
1
+3X
2
=15==> (0, 5) and (7.5, 0)

27. CornersCoordinatesMinZ=25 X
1+ 30X
2
A (0, 20/3) 200
B (2.5, 3.33) 162.5
C (7.5, 0) 187.5
we utilize X
1
=2.5 hr and X
2
=3.33 hrto operate in
minimum cost of 162.5

28. Special Cases in Graphics Methods
1. Redundant Constraint:-If a constraint when plotted on a
graph doesn’t form part of the boundary making the feasible
region of the problem that constraint is said to be redundant.
Example:
AfirmisengagedinproducingtwoproductsAandB.Each
unitofproductArequires2Kgofrawmaterialand4labor-
hoursforprocessing;whereaseachunitofproductB
requires3Kgofrawmaterialsand3hrsoflabor.Everyunit
ofproductAneeds4hrstopackagingandeveryunitof
productBneeds3.5hrsforpackaging.Everyweekthefirm
hasavailabilityof60Kgofrawmaterial,96labor-hoursand
105hrs.Ithepackagingdepartment.1unitofproductAsold
yields$40profitand1unitofBsodyields$35profit.
Required:
a. Formulate this problem as a LPP
b. Find the optimal solution

29. Solution Products Res. av. / week
Resources A B
Raw materials (Kg)2 3 60
Labor (hr) 4 3 96
Packaging (hr) 4 3.5 105
Profit per unit$40 $35
Let X
1=The N
o
ofunits of product A produced / week
X
2=The N
o
ofunits of product B produced per week
Max Z=40 X
1 +35 X
2
St.
2 X
1 +3 X
2 <60
4 X
1 +3 X
2 <96
4 X
1 +3.5 X
2 <105
X
1,X
2> 0

30. By changing the inequality into equality and plot the graph

31. CornersCoordinatesMaxZ=40 X
1+ 35X
2
A (0, 0) 0
B (0, 20) 700
C (18, 8) 1000
D (24, 0) 960
X
1=18
X
2=8 and
Max Z=1000
Interpretation:
The company should produce and sale 18 units of
product A and 8 units of product B per week so as
to get a maximum profit of 1000.

32. By this production plan the entire raw material will be consumed.
2X
1+3X
2 <60
2(18) +3(8)=60
60=60==> No idle or unused raw material
4X
1+3X
2 <96
4(18) +3(8)<96
96=96 ==>the entire labor hour will be consumed
4X
1+3.5X
2 <105
100<105==>There is to be idle or unused capacity of 5hrs in
the packaging department.
Note:
The packaging hour’s constraint does not form part of the
boundary making the feasible region.
Thus, this constraint is of no consequence and is therefore,
redundant.
The inclusion or exclusion of a redundant constraint does not
affectthe optimal solutionof the problem.

33. 2. Multiple optimal Solutions
==>We may have unlimited number of optimal solution without
increasing or decreasing the objective function.
Example:
The information given below is for the products A and B.
Machine hours per week Maximum
available
Department Product A Product B per week
Cutting 3 6 900
Assembly 1 1 200
Profit per unit $8 $16
Assume that the company has a marketing constraint on selling
products B and therefore it can sale a maximum of 125units of this
product.
Required:
a. Formulate the LPP of this problem
b. Find the optimal solution

34. Solution:
Let X
1=The N
o
ofunits f product A produced per week
X
2=The N
o
ofunits f product B produced per week
The LPP Model of the problem is:
Max Z=8X
1 +16X
2
St.
3X
1 +6X
2 <900
X
1 +X
2 <200
X
2 <125
X
1,X
2 >
By changing the inequality into equality and plot the graph

35. CornersCoordinates Max Z=8 X
1
+ 16X
2
A (0, 0) 0
B (0,125) 2000
C (50,125) 2400
D (100,100) 2400
E (200,0) 1600
Both C and D are optimal solutions. Any point on the line segment CD will also
lead to the same optimal solution.
==>Multiple optimal solutions provide more choices for management to reach
their objectives.

36. 3. Infeasible Solution
It is sometimes possible that the constraints may be inconsistent so that there is no feasible
solution to the problem. Such a situation is called infeasibility.
Example:
MaxZ=20X
1+30X
2
St:
2X
1+X
2<40
4X
1+X
2<60
X
1>30
X
1, X
2 >0
4. Mix of constraints
5. Unbounded Solution
Example:
Max Z=3X
1+4X
2
St:
X
1-X
2<-1==> -X
1+X
2>1
since the quantity solution is positive
-X
1+X
2<0
X
1, X
2 >0
Max Z =
30x
1+50x
2,
Subject to:
3x
1+x
2≥ 9,
x
1+ 2x
2≥12,
x
1+ 2x
2≥9,
x
1, x
2≥ 0.
Max Z = 3x
1+2x
2,
Subject to:
-2x
1+ 3x
2≤ 9,
3x
1-2x
2≤ -20,
x
1, x
2≥ 0.

37. 2. The Simplex Method
When a number of variables in a linear
programming are more than two, graphic method
cannot be used because of the difficulty precisely
representing the variables using more than a two
dimensional plane.
That means it is impossible to represent these
variables in the graph and evaluate the corner
points.
In such cases, there is a comprehensive method
of solving a linear programming problem which is
called the simplex method (simplex algorithm).

38. Algorithmis a process where a systematic
procedure is repeated (iterated) over and over
again until the desired result is obtained.
Simplex method (algorithm) is an iterative
procedure that consists of moving from one
basic feasible to anotherin such a way that the
values of the objective function doesn’t decrease
(in case of maximization problem) and doesn’t
increase (in case of minimization problem).
The process continuesuntil an optimal solution is
reached if it exists, otherwise, the problem may be
unbounded or not feasible and the simplex
method can’t find the solution.

39. Comparison Between Graphical And
Simplex Methods
1. The graphical method is used when we have two
decision variables in the problem. Whereas in
Simplex method, the problem may have any
number of decision variables.
2. In graphical method, the inequalities are assumed
to be equations, so as to enable to draw straight
lines. But in Simplex method, the inequalities are
converted into equations by:
Addinga Slack Variable in maximization
problem and
subtractinga Surplus Variable in case of
minimization problem.

40. 3. In graphical solution the Iso-profit line moves
away from the origin to towards the far off
point in maximization problem and in minimization
problem, the Iso-cost line moves from far off
distance towards origin to reach the nearest
point to origin.
4. In graphical method, the areas outside the feasible
area (area covered by all the lines of constraints in
the problem) indicates idlecapacity of resource
where as in Simplex method, the presence of slack
variable indicates the idle capacity of the
resources.

41. 1. Maximization LPP
Step 1: Formulate LP Model
Step 2: Convert the LP to standard form.
The given problem is said to be expressed in standard
form if the decision variables are non-negative, R.H.S of
the constraints are non-negative and the constraints
are expressed as equations.
A slack variable(s) is addedto the left hand side of a <
constraint to covert the constraint inequality in to equality.
The value of the slack variable shows unused resource.
Slack variables represent unused resource or idle
capacity. Thus, they don’t produce any product and their
contribution to profit is zero.
Slack variables are added to the objective function with
zero coefficients.

42. Step 3: Obtain the initial simplex tableau &Perform
optimality test
To represent the data, the simplex method uses a table
called the simplex tableor the simplex matrix.
After that find Zjand Zj-Cj
Z
j=∑C
bvia
ij(the sum of product of coefficient of
basic variables and coefficient of constraint in
the left side).
Zj-Cj( the difference between Zjand coefficient of
objective function in standard form).
Optimality test: is the current solution optimal?
Depending on the value of Zj-Cj, if all values in this row
are zero and positive, then we get optimum solution
shortly and stop, if not Perform an iteration

43. Step4.Selectpivotcolumnandpivotrow
pivotcolumn:Thecolumnwiththe“mostnegative
value”elementinthelastrow(Zj-Cj)
pivotrow:Therowwiththesmallestnon-negative
resultwhenbiisdividedbythecorrespondingin
thepivotcolumn.)
Theelementlyingattheintersectionofkeycolumn
andkeyrowiscalledkey/pivotelement.
Step5.Useelementaryrowoperationstocalculate
newvaluesofnexttable.
New1
st
rowofnexttable=
eachnumbersinoldpivotrow/pivot
element

44. The new values of the elements in the remaining
rows for the new simplex table can be obtained
by performing elementary row operations on all
rows.
Remaining new rows either above or below the
pivot row are calculated in the form of:
New row= each numbers in old row-coefficient
of pivot column * each numbers in pivot row
Again calculate Zjand Zj-Cj&Perform optimality
test. If get stop if not continue iteration until
you get the optimal solution

45. Example:1, step one is already finished.
Max Z = 3x
1+4x
2,
Subject to:
x
1+ x
2≤ 450,
2x
1+x
2≤ 600,
Where x
1, x
2≥ 0.
Convert in standard form by introducing slack variables
Max Z = 3x
1+4x
2 +0S
1+0S
2
Subject to:
x
1+ x
2+ S1+ 0S
2 =450,
2x
1+ x
2+0S
1+S2= 600,
Where x
1, x
2, S
1,S
2≥ 0
Tabulateboth the body matrix and identity matrix

46. Cj 3 4 0 0
Body matrix Identity
matrix
C
Bv BV x
1 x
2 S1 S2bi
0 S1 1 (1) 1 0 450==450/1=450
0 S2 2 1 0 1 600==600/1=600
Zj=∑C
bvia
ij0 0 0 0
Zj-Cj -3 -4 0 0
Pivot column
High negative value
from
Zj-Cjrow
Pivot row
Lower
replacement
ratio =
bi/p.element
Pivot element
The intersection
point of pivot
row and column
X
2is entering variable while S1 is leaving
variable

47. Useelementaryrowoperationstocalculatenewvaluesofnext
table.
New1
st
rowofnexttable=
eachnumbersinoldpivotrow/pivotelement
New 1
st
row of next table=1, (1), 1, 0, 450
1
= 1, 1, 1, 0, 450
New row remaining S2 = each numbers in old row-(coefficient of
pivot column )* (each numbers in New 1
st
row) .
2, 1, 0, 1, 600
--
(1)*(1, 1, 1, 0, 450 )
___________________________
New row of S2= 1, 0, -1, 1, 150
Then tabulate the next iteration table by using the above
information and check the optimality by calculating Zjand Zj-
Cj

48. Cj 3 4 0 0
Body matrix Identity
matrix
C
Bv BV x
1 x
2 S1 S2bi
4 X2 1 1 1 0 450
0 S2 1 0 -1 1 150
Zj=∑C
bvia
ij4 4 4 0 1800
Zj-Cj 1 0 4 0
Values in the Zj-Cjrow are positive and
zero so, the given solution is optimal. Hence
the optimal solution is
x
1=0, x
2= 450, Z
max=1800.

49. Example 2:
Maximize Z = 3X
1+ 5X
2
Subject to
X
1 4
2 X
212
3X
1+2X
218
X
1, X
2 0
Standard form
Maximize Z = 3X
1+ 5X
2 +0S
1+ 0 S
2 +0 S
3
Subject to
X
1 + S
1+0 S
2 + 0 S
3=4
2 X
2+ 0S
1+ S
2
+ 0 S
3=12
3X
1+2X
2
+0S
1+ 0 S
2+ S
3 = 18
X
1, X
2, S
1, S
2, S
3 0
Tabulateboth the body matrix and identity matrix

50. Cj 35 0 0 0
C
Bv BV x
1x
2S1S2S3 bi
0 S1 10 1 00 4==---
0 S2 0(2)0 10 12== 12/2=6
0 S3 32 0 01 18== 18/2=9
Zj=∑C
bvia
ij00 0 00
Zj-Cj -3-50 0 0
Pivot column
High negative value
from
Zj-Cjrow
Pivot row
Lower
replacement ratio
= bi/p.element
Pivot element
The intersection
point of pivot
row and column
X
2is entering variable while S2 is leaving
variable

51. Useelementaryrowoperationstocalculatenewvaluesofnexttable.
New1
st
rowofnexttableforenteringvariable=
eachnumbersinoldpivotrow/pivotelement
0, (2), 0, 1, 0, 12 = [0, 1, 0, ½, 0, 6]
2
New row remaining S2 = each numbers in old row-(coefficient of pivot
column )* (each numbers in New 1
st
row) .
For S
1
1 0 1 0 0 4
-
0 (0 1 0 1/2 0 6)
[ 1 0 1 0 0 4]
For S
3
3 2 0 0 1 18
-
2 (0 1 0 1/2 0 6)
[ 3 0 0 -1 1 6]

52. Cj 35 0 0 0
C
Bv BV x
1x
2S1S2S3 bi
0 S1 10 1 00 4== 4/1=4
5 X2 01 01/20 6== ----
0 S3 (3)0 0 -11 6== 6/3= 2
Zj=∑C
bvia
ij05 05/20
Zj-Cj -30 05/20
Pivot column
High negative value
from
Zj-Cjrow
Pivot row
Lower
replacement ratio
= bi/p.element
Pivot element
The intersection
point of pivot
row and column
X
1is entering variable while S3 is leaving
variable

53. Useelementaryrowoperationstocalculatenewvaluesofnext
table.
New1
st
rowofnexttableforenteringvariable=
eachnumbersinoldpivotrow/pivot
element
(3),0,0,-1,1,6=[1,0,0,-1/3,1/3,2]
3
NewrowremainingS2=eachnumbersinoldrow-(coefficientof
pivotcolumn)*(eachnumbersinNew1
st
row).
ForS1. 1,0,1,0,0,4
-
(1)[1,0,0,-1/3,1/3,2]
[0,0,1,1/3,-1/3,2]
ForX2 0,1,0,½,0,6
-
(0)[1,0,0,-1/3,1/3,2]
[0,1,0,½,0,6]

54. Cj 35 0 0 0
C
Bv BV x
1x
2S1S2S3 bi
0 S1 00 11/3-1/32
5 X2 01 01/20 6
3 X1 10 0-1/31/32
Zj=∑C
bvia
ij35 03/21 36
Zj-Cj 00 03/21
This solution is optimal; since there is no
negative solution in the last row: basic variables
are X
1= 2, X
2= 6 and S
1= 2; the non-basic
variables are S
2= S
3= 0max Z = 36

55. Artificial Variables Technique
There are many linear programming problems where slack variables
cannot provide a solution in case of maximization.
In these problems at least one of the constraints is of (≥) or (=)
type. In such cases we introduce another type of variables called
artificial variables.
Artificial variables are fictitious and have no any physical or
economic meaning.
They assume the role of slack variables in the first iteration, only to
be replaced at a later iteration.
Are merely a device to get the starting basic feasible solution and
then the usual simplex procedure will be adopted until the optimal
solution is obtained.
are expressed by capital letter “A” and used for “≥” type of
inequalities and “=” equations.
Artificial variables enter in to the objective function with “M”
coefficient i.e., it inter in to the objective function with –vevalue
(-M) for maximization and +vevalue (+M) for
minimization, where M >0.
M denotes some huge positive number (very huge penalty), for that
firm manipulates the artificial variables.

56. Steps of the big M-method algorithm
Step 1:Express the LP problem in the standard
form by introducing slack variables.
These variables are addedto the L.H S of the
constraints of (≤)and subtractedfrom the
constraints of(≥) type.
Step 2:Add non-negative artificial variable (A)
corresponding to constraints having “≥” and “=”
equations.
Step 3:determine the basic and non-basic variables
Step 4:Solve the modified LPP by the simplex
method.

57. While making iterations, using the simplex method,
one of the following three cases may arise:
If no artificial variable remains in the basis
and the optimality condition is satisfied, then
the solution is an optimal feasible
solution.
If at least one artificial variable appears in the
basis at zero level and optimality condition is
satisfied, then the solution is optimal feasible
solution. But it is a degenerate solution. The
constraints are consistent though redundancy
may exist in them.

58. Redundancymeans that the problem has more
than the required number of constraints.
If at least one artificial variable appears in
the basis at a non-zero level (with +ve
value in b-column) and the optimality
condition is satisfied, then the original
problem has no feasible solution.
Therefore, the original problem doesn’t
have feasible solution because it
contains artificial variable (a very
large penalty M).

59. NB:
1. Slack variables are added to the constraints of (≤) type
and subtracted from the constraints of (≥) type.
2. Artificial variables are added to the constraints of (≥)
and (=)type. Equalityconstraints require neither slack
nor surplus variables.
3. Variables, other than the artificial variables, once driven out
in iteration, may re-inter in a subsequent iteration.
Example:
Max Z = 3x
1-x
2
Subject to:
2x
1+ x
2≤ 2,
x
1+ 3x
2≥3,
x
2≤ 4,
x
1, x
2≥ 0.
Step 1: Set up the problem in
standard form
Max Z = 3x
1-x
2 +0s
1+0s
2+0s
3-MA
1,
Subject to:
2x
1+ x
2+ s
1= 2,BV=s
1,A
1, s
3
x
1+ 3x
2-s
2+A
1=3,
x
2+ s
3= 4,
x
1, x
2, s
1, s
2, s
3, A
1≥ 0.

61. Therefore, optimal solution is given by:
X
1
=3/5, x
2
=4/5, Z
max
=1

62. Special Cases in the Simplex Method Application
Tie Breaking in Simplex Method
While operating the simplex iteration, tie may occur
and we may face indifference in choosing the entry or
the leaving variable. When tie may occur, the following
are important to do:
1. Tie in the choice of entering variables:the non-
basic variable that enters the basis is the one that gives
the largest per unit improvement in the objective function.
Variable having maximum –vevalue in a maximization
problem and the maximum +vevalue in the
minimization problem in Z
j-Cjrow is the entering
variable.

63. A tie in the entering variable exists when more than
one variable has same largest (or smallest) value.
To break the tie any one of them is selected
arbitrarily as the entering variable.
2.Tie in the choice of leaving variables:This
is the case when the ratio is the same.This tie
can be resolved by choosing one of the
variables arbitrarily.
No leaving basic variable (unbounded
objective function)
This is the case when all elements of the
pivot column are –veor zero that no
variable qualifies to be a leaving basic variable.
In this case no finite solution can be
determined.

64. 3. Multiple optimal solutions
This is the case when the LPP have more than one
optimal solution.
In the simplex table if the Z
j-Cjvalue is zero for a
non-basic variable, it indicates that the existence
of more than one optimal solution.
4. Infeasible solution
If all the constraints are not satisfied
simultaneously, the model has no feasible solution.
In the case of big M method if at least one of the
artificial variables has positive value and the
solution is optimal, then this is the indication of no
feasible solution.

65. 2. Minimization LPP
Similarityof maximization and minimization LPP
Maximization LPP Minimization LPP
It has an objective function.has also an objective function.
It has structural constraints.has also structural constraints.
Linear relationship between
variables and constraints
Also Linear relationship
between variables and constraints
It has non-negativity constraint.This too has non-negativity
constraints.
The coefficients of variables may
be positive or negative or zero.
The coefficient of variables may
be positive, Negative or zero.
For selecting out going variable
(key row) lowest replacement ratio
is selected.
For selecting out going variable
(key row) lowest replacement ratio
is selected.

66. Differenceb/n maximization and minimization LPP
Maximization LPP Minimization LPP
The objective function is of
maximization type.
The objective function is of
minimization type.
The inequalities are of ≤ type.
Use at most .
The inequalities are of ≥ type. Use
at least.
To convert inequalities into
equations, slack
variables are added.
To convert inequalities into
equations, surplus Variables are
subtractedand artificial surplus
variables are added with big M
coefficients.
While selecting, incoming
variable, lowest element in the net
evaluation row is selected (highest
number with negative sign).
While selecting incoming variable,
highest positive Opportunity cost is
selected from net evaluation Row.
When the element of net
evaluation row are either positive
or zeros the solution is optimal.
When the elements of net
evaluation row are either Negative
or zeros, the solution is optimal

67. The other alternative method of solving minimization
problem is by converting it to maximization. i.e., Min
Z=Max (-Z).
Example
Min Z = 12x
1+20x
2
Subject to:
6x
1+ 8x
2≥100,
7x
1+ 12x
2≥120,
x
1, x
2≥ 0.
Standard form:
Min Z = 12x
1+20x
2+0s
1+0s
2+MA
1+MA
2
Subject to:
6x
1+ 8x
2-s
1+A
1=100,
7x
1+ 12x
2 –s
2+A
2=120,
x
1, x
2, s
1, s
2, A
1, A
2≥ 0.

69. Since all values in Z
j-Cjrow are zeros
and negative ,so that we get optimal
solution X1=15, X2=5/4 and min Z=205

70. Example 2.
Minimize Z=25x
1+30x
2
Subject to:
20x
1+15x
2 >100
2x
1+ 3x
2 >15
x
1,x
2 >0
Standardize the problem
Minimize Z=25x
1+30x
2 +0s
1+0s
2 +MA
1+MA
2
Subject to:
20x
1+15x
2-s
1+A
1 = 100
2x
1+ 3x
2 –s
2+A
2 = 15
x
1,x
2, s
1, s
2,A
1 ,A
2 >0

71. Cj 25 30 00 M M
CbvBv X1 X2 S1S2A1A2 biRatio
M A1 20 15 -10 1 01005
MA2 2 3 0-10 1157.5
Zj 22M 18M -M-MM M
Zj-Cj22M-2518M-30-M-MM M
Once an artificial variablehas leftthe basis, it has served its
purpose and can therefore be removed from the simplex tableau. An
artificial variable is never considered for re-entry into the basis.
Cj 2530 0 0 M
CbvBv X1X2 S1 S2 A2 biRatio
25X1 13/4 -1/20 0 0520/3
M A2 03/2 1/10 -1 1510/3
Zj 2575/4+3/2M5/4+1/10M-M M
Zj-Cj0-45/4+3/2M
5/4+1/10 M
-M M

72. Cj 2530 0 0
CbvBv X1X2 S1 S2 bi
25 X1 1 0 -1/10 1/2 5/2
30 X2 0 1 1/15 -2/3 10/3
Zj 2530 -1/2 -15/2 162.5
Zj-Cj 0 0 -1/2 -15/2
Since all values in Z
j-Cjrow are zeros
and negative ,so that we get optimal
solution X1=5/2 X2= 10/3 and
min Z= 162.5