Operations Research
Operations Research
Operations Research
Build model
Acquire the required data
REQUIREMENTS
Cont....
For instance, in the context of a production problem, a
solution like the one given earlier to make 5 2/3 units
of A and 10 1/3 units of B per week, can be adopted
without any difficulty. The fractional amount of
production would be taken to be the work-in-progress
and become a portion of the production of the
following week. In this case, an output of 17 units of
A and 31 units B over a three –week period would
imply 5 2/3 units of A and 10 1/3 units of B per week.
Lastly, if we must insist on obtaining only integer
value of the decision variables, we may restate the
problem as an integer programming problem,
forcing the solutions to be in integers only.
4. Certainty: A further assumption underlying
a Linear Programming model is that the
various parameters, namely, the objective
function coefficients, the coefficients of the
inequality/equality constraints and the
constraint (resource) values are known with
certainty. Thus, the profit per unit of the product,
requirements of materials and labour per unit,
availability of materials and labour, etc. are
given or known in a problem involving these. The
linear programming is obviously deterministic
in nature.
5. Finite Choices: A Linear Programming
model also assumes that a limited number of
choices are available to a decision-maker and the
decision variables do not assume negative values.
Thus, only non-negative levels of activity are
considered feasible. This assumption is indeed a
realistic one. For instance, in the production
problems, the output cannot obviously be
negative, because a negative production implies
that we should be able to reverse the production
and convert the finished output back into the raw
materials.
ADVANTAGES OF LINEAR
PROGRAMMING
1. Linear Programming can be used to solve
allocation type problems. Such problems are very
common and extremely important in organization.
Their solution is difficult due it the fact that an
infinite number of possible solutions may exist. An
LP Model not only provides the optimal solution
but does so in a very efficient manner. Further, it
provides additional information concerning the
value of the resources to be allocated.
2. Linear Programming gives possible and practical solution
as there might be other constraints operating outside the
problem which must be taken into account. Just because we
can produce so many units does not mean that they can be
sold. It allows modification of its mathematical solution for
the sake of convenience to the decision-maker.
3. Linear Programming improves the quality of decisions. It
makes decisions more objective rather then subjective.
4. Linear Programming helps in highlighting the bottlenecks
in the production processes.
5. Linear Programming helps in attaining optimum use of
productive factors. It also indicates the significance and
utility of these factors more effectively.
APPLICATION AREAS OF LINEAR
PROGRAMMING
Linear Programming is the most widely used
technique of decision-making in business, industry
and in various other fields. Few broad application
areas of L.P are as under.
R1 60 20 1200
R2 40 50 2000
Contribution per Rs. 3 Rs. 2
Unit
As cost per unit of food F1 and F2 are Rs. 3 and Rs. 2.50,
respectively, then the objective function will become
Minimize Z = 3X1 + 2.5X2
As cost per unit of food F1 and F2 are Rs. 3 and Rs. 2.50,
respectively, then the objective function will become
Minimize Z = 3X1 + 2.5X2
Equality Sign
So far, we have discussed only those constraints which are
either expressed by ( < ) sign or by (>) sign. If there exists a
situation, when some of the constraints are expressed by
equations, each of the equations may be replaced by two
inequalities. For example,
• a11X1 + a12X2 = b1
is equivalent to the two simultaneous constraints
a11X1 + a12X2 < b1
and a11X1 + a12X2 > b1
or - a11X1 - a12X2 < - b1
Unrestricted Variables
In certain problems, situations may exist, when some decision
variables are unrestricted in sign (positive, negative or zero).
In all such cases, the decision variables can always be
expressed as the difference in sign, then we define two non-
negative variables Xi+ and Xi- such that
Xi = Xi+ - Xi-
Xi+, Xi- > 0
SOLUTION TO LP PROBLEM
Several methods or algorithms have been developed to get the
optimal solution to LP problem like graphical method and
Simplex method
Graphical Method
Graphical method is used for solving those LP problems which
involve only two variables. Consider example of furniture
manufacturer mentioned above. On our graph, let the
horizontal axis represent the number of tables manufactured
and the vertical axis the number of chairs manufactured. We
will plot a line for each of the two constraints and the two non-
negativity restrictions. We shall begin by plotting the lines
corresponding to the non-negativity restrictions. This plotting
suggests that the graphical method always starts with the first
quadrant of the graph.
Now in order to plot the constraints on the graph, temporarily
we consider inequalities as equations, i.e,
30X1 + 20X2 = 300
5X1 + 10X2 = 110
When plotted on the graph, these will represent straight lines.
All points on these straight lines represent combinations of
tables and chairs quantities that consumer the exact amount of
resource that is available. In other worlds, points on these lines
are satisfying the equality and any point below the line will
include the inequality part of the constraint.
A straight line is completely specified by knowing
any point that falls on that line. Therefore, to plot any
constraint, we need only to specify two points on that
line and then draw the line by connecting these two
points. To illustrate let X1 =0 in the availability wood
constraint, then we get:
30(X1 = 0) + 20X2 = 300
Or
X2 = 15
Figure I Graphical Solution for Maximization Problem
This represents the vertical interceptor on X2 axis and is
written as (0, 15), i.e., o tables and 15 chairs. Similarly,
horizontal interceptor on X1 axis is obtained by putting X2
= 0 we get
20X1+ 20(0) = 300
Or
X1 = 10
It is also written as (10, 0) and represents 10 tables and 0
chairs. Join the two interceptors to draw the constraint line.
Thus, the points on or below the line represent the region
satisfied by this constraint. Any point which does not lie on
or below the line gives infeasible solution.
Similarly, the availability (labour) constraint can also be
plotted on the graph as shown in the Figure.
Any combination of value of X1 and X2 which
satisfies the given constraints is called a “feasible
solution”. The OABC in the figure satisfied by the
constraints is shown by shaded area and is also called
feasible solution region or space. The coordinates of
the points on the corners of the region OABC can be
obtained by solving equations intersecting on these
points.
The shaded region may contain an infinite number of
points which would satisfy the constraints of the
given LP problem. However, it can be proved that the
optimal solution of any LP problem corresponds to
one of the corner points (also called extreme points)
of the feasible solution region. Thus we confine only
to those points which correspond to corners of
feasible solution region to get an optimal value of the
objective function of given LP problem.
• In the present example, value of objective function on
the corner points can be evaluated as follows:
Coordinates of corner point Objective function Value
Z= 6X1 + 8x2
O (0, 0) 600 (0) + 800 (0) 0
A (10, 0) 600 (10) + 800 (0) 6000
B (4, 9) 600(4) + 800 (9) 9600
C (0, 11) 600 (0) + 800 (11) 8800
Unbounded Solution
When a LP solution is permitted to be infinitely large, it is
known to be unbounded. For example, in a maximization
problem at least one of the constraints should be an equality or
less than or equal to (<) type. If all of the constraints are
greater than or equal to (>) type, then there will be no upper
limit on the feasible region. Similarly, for minimization, there
must be equality or a greater than or equal to (>) type
constraint if a solution is to be found.
Infeasible Solution
If there is no solution that satisfies all the constraints, it is said
to be infeasible. Such a condition generally indicates that the
LP problem has been wrongly formulated. The only way to
arrive at a feasible solution is to reformulate one or more of
the constraints.
Redundant Constraint
In a properly formulated LP problem, each of the corner will
define a portion of the boundary of the feasible solution
region. Whenever, a constraint does not define a portion of the
boundary of the feasible solution region, it is called a
redundant constraint. A redundant constraint is unnecessary for
the problem and may be omitted from the problem
formulation.
LIMITATIONS OF THE GRAPHICAL METHOD
The graphical method is widely used as an academic exercise
because it enables the student to visualize the LP solution
process. The method is severely limited in application by the
fact that the number of variables should be restricted to two
dimensions. For three variables problem, it becomes very
difficult as one must be familiar with three dimensional space.
Of course, the method breaks down completely for four or
more variables.
Other methods of solution which avoid the limitations of the
graphical method have been developed. The most widely used
method is known as Simplex Method.
USE OF COMPUTER
Net contribution per unit (Cj - Zj) = contribution per unit – contribution
loss per unit
In our example, the values of net contribution per unit (Cj - Zj) for X 1
column are determined as given below:
Net contribution per unit (Cj - Zj) = 6-0 = 6 and similarly we can calculate
the other values of (Cj - Zj) for other columns as shown in Table.
The positive value in the (Cj - Zj) row indicate improvement possibility
in the existing solution. The objective is to maximize profit. Therefore,
consider that column where per unit contribution is the largest. In our
case, we notice that in X2 column, contribution per unit (i.e., Rs. 8) is
maximum. This criterion helps us to know the variable to be entered into
the solution basis. Thus X2 is the entering variable. The column
corresponding to entering variable is termed as ‘key column’. Since we
have decided to enter one variable as the basic variable into the solution
basis, therefore, we replace one of the existing basic variables to depart
from the solution basis. The variable to depart is identified by forming
the ratios of solution values to physical rates of substitution of entering
variable. Thus, in our example, we have
For S1; ratio = 300/20 = 15
For S2 : ratio = 110/10 = 11
The one with minimum ratio (S2) represents the variable to depart
from the solution basis. Thus S2 is the departing variable. This
procedure of selecting the departing variable guarantees that no
basic variable will ever be negative. The row corresponding to the
departing variable is called ‘key row’. The element on the inter-
section of key row and key column is called the ‘key element’ and
is denoted by making a box ( ) in the simplex table.
At this point, develop a new improved solution by revising Table I.
Now have two tables to carry out the calculation: the old table and a
new table.
To revise the key row divide all values in the key row (S2) by the
value of the key element (i.e.10) and replace departing variable (S2)
by the entering variable (X2).
Also replace the new values in Cj column accordingly. Pull all
other values so obtained at the appropriate places. In our
example, this new row becomes:
8 X2 11 5 /10 1 0 1 /10
For other non-key rows, new values can be obtained as given
below:
X1 = 4; X2 = 9; S1=0; S2 =0 and Z = 96
2X1 + 4 X2 – S1 = 40
5X1 + 2 X2 – S2 = 50
The surplus variables take negative values, which violates the non-
negativity restrictions. To overcome this problem, we need to add an
additional variable to each constraint that has a positive value with a
surplus variable. These new variables are called artificial variables
because they are used to convert the origin artificially from infeasible
to feasible. It is emphasized that the use of an artificial variable is not
limited to minimization problems. An artificial variable may be
used in maximization problems as well. In general, as long as at
least one greater–than or equal–to constraint is involved,
regardless of minimization or maximization problem, artificial
variable is used. In our example, introducing artificial variables, the
constraints become;
2X1 + 4 X2 – S1 + A1 = 40
5X1 + 2 X2 – S2 + A2 = 50
The simplex method then selects the artificial variables as the initial
basic variables. Therefore, the decision and surplus variables are non-
basic variables and can be set equal to zero. It is noted that with the
addition of the artificial variable the origin stands converted from
infeasible point to feasible one. To correct this problem, we must add each
artificial variable to the objective function. To ensure that the artificial
variables are not basic variables in the optimal solution, we assign
them very high costs. One convenient way of doing this is to assign each
artificial variable a cost of M, where M is defined to be a very large
number. It is emphasized that the artificial variables are used only as a
mathematical convenience to obtain an initial basic feasible solution.
This is the reason why the name artificial has been given to these
variables since they are fictitious and have no physical meaning for the
original problem. Introducing artificial variables in the objective function,
we get
Min Z = 3X1 + 2.25X2 + 0S1 + 0S2 + MA1 + MA2
The modified problem is now to
Min Z = 3X1 + 2.25X2 + 0S1 + 0S2 + MA1 + MA2
Subject to 2X1 + 4X2 - S1 + A1 = 40
5X1 + 2X2 – S2 + A2 = 50
And X1, X2, S1, S2, A1, A2 > 0
Now set up the initial simplex table exactly the way it was
done for maximization problem. This is shown below:
The entering variable will be selected for that variable for
which the value of (Cj – Zj) is the largest negative. In the
case, variable X1 has the largest negative value. Thus X2 is
selected as the entering variable. The selection of the
departing variable is made exactly the same way as in the
case of maximization. Thus artificial variable A2 is chosen as
the departing variable. Therefore, the element which
corresponds to the intersection of key row and key column,
i.e., 5 becomes the key element. Having selected the key
element, the computation procedure is the same as for the
maximization case. The revised improved solution is shown in
Table II.
Proceeding in the same manner, Table III as shown below is
obtained:
In the (Cj – Zj) row of Table III, there are no negative
values. Thus the solution is optimal. Hence to meet the
daily vitamins requirement, one should have 7.5 units of
food F1 and 6.25 units of food F2 and the minimum cost is
Rs. 36.5625.
Problem: Use simplex method to solve the following LP
problem:
Min Z = 80 X1 + 100 X2
Subject to 80 X1 + 60 X2 > 1500
20 X1 + 90 X2 > 1200
and X1, X2 > 0
THE SIMPLEX METHOD (MIXED TYPE
CONSTRAINTS)
Let us now consider a situation when the constraints are
of mixed type i.e. not merely of either > type or < type.
The LP problem as given below is of this type.
Min Z= 60 X1 + 80X2
X2 > 200
X1 < 400
X1+ X2 = 500
And X1, X2 > 0
The problem can be converted into the standard
form by adding slack, surplus and artificial
variables in the set of constraints and assigning
appropriate cost to these variables in the objective
function. Thus the problem can be stated as follows: