Operation
Research - Definition
Operations
research is essentially a collection of mathematical techniques and tools which
in conjunction with a system’s approach, are applied to solve practical
decision problems of an economic or engineering nature.
General Structure of an LP Model
The general
structure of an LP model consists of the following three basic components (or
parts).
·
Decision variables (activities)
·
The objective function
·
The constraints
Decision Variables
To arrive at the optimal value of the objective
function, certain activities (also called decision variables) usually denoted
by x1, x2, . . ., xn are conducted. In an LP model, all decision variables are
continuous, controllable and non-negative. That is, x1 ≥ 0, x2 ≥ 0, . . ., xn ≥
0.
Objective Function
The objective function of each LP problem
is expressed in terms of decision variables to optimize the criterion of
optimality (also called measure-of-performance) such as profit, cost, revenue,
distance etc.
In its general form, it is represented as:
Optimize (Maximize
or Minimize) Z = c1x1 + c2x2 + . .
. + cnxn
There are always
certain limitations (or constraints) on the use of resources, such as: labour,
machine, raw material, space, money, etc. Such constraints must be expressed as
linear equalities or inequalities in terms of decision variables. The solution
of an LP model must satisfy these constraints.
IMPORTANT
DEFINITIONS
Solution
The set of values of decision variables xj
(j = 1, 2, . . ., n) that satisfy the constraints of an LP problem is said to
constitute the solution to that LP problem.
Feasible solution
The set of
values of decision variables xj (j = 1, 2, . . ., n) that satisfy all the
constraints and non-negativity conditions of an LP problem simultaneously is
said to be the feasible solution of the LPP.
Infeasible solution
The set of
values of decision variables xj ( j = 1, 2, . . ., n) that do not satisfy all
the constraints and non-negativity conditions of an LP problem simultaneously
is said to be the infeasible solution of the LPP.
Basic solution
For a set of m
simultaneous equations in n variables (n > m) in an LP problem, a solution
obtained by setting (n – m) variables equal to zero and solving for remaining m
equations in m variables is called a basic solution of that LP problem.
A feasible
solution to an LP problem which is also the basic solution is called the basic
feasible solution. That is, all basic variables assume non-negative values.
The basic
feasible solution is of two types:
(a) Degenerate A basic feasible
solution is called degenerate if the value of at least one basic variable is
zero.
(b) Non-degenerate A basic feasible
solution is called non-degenerate if the value of all m basic
variables are non-zero and positive.
Optimum basic feasible
solution
A basic feasible
solution that optimizes (maximizes or minimizes) the objective function value
of the given LP problem is called an optimum basic feasible solution.
Unbounded solution
A solution that
can increase or decrease infinitely the value of the objective function of the
LP problem is called an unbounded solution.
Definition of Linear Programming
Linear programming is a mathematical technique for determining the optimal allocation of resources among
alternative uses of the resources to achieve a particular objective. The objective includes profit maximization or cost minimization.
Optimal condition
For maximization problems if all Cj - Zj are less than equal to 0, then the optimal condition is reached otherwise select the variable with the maximum Cj - Zj as the entering variable.
For minimization problems if all Cj - Zj are greater
than equal to 0, then the optimal condition is reached; otherwise, select the variable with the most negative value as the entering variable.
The
canonical form of LPP
The given LPP can be written
in a canonical form as follows;
1) The
objective function is of maximization type. If the given objective function is of minimization type, convert it into maximization type by multiplying throughout by -1.
2) All the constraints are of ≤ type. The inequalities of ≥ type are converted to ≤ type by multiplying both sides of the inequality by -1.
3) All the variables are non-negative.
If a variable is unrestricted in sign, replace it with the difference between
two positive variables. For example, if xi is unrestricted in sign, replace it with xi' - xi''
Standard form of LPP
1) All constrains / inequalities are written as equations.
To convert a ≤ inequality to an equation add a variable to the left-hand side of the constraint. This variable is called a slack variable.
To convert a ≥ inequality to an equation subtract a variable from the left-hand side of the constraint. This variable is called a surplus
variable.
If the right-hand side is negative,
then multiply both sides of the constraint by -1 in which
case the ≤ inequality will be changed
to ≥ and vice-versa.
Simplex Method
Step 1: Rewrite the given LPP in the standard form.
a) Check whether the objective function is of maximization type.
b)
Check whether all the right-hand
side values of the constraints are non-negative.
c)
Convert all the inequalities into equations.
Step 2: Obtain an initial basic
feasible solution and put it under the Basic Variable(BV) column of the initial
Simplex table.
Step 3: Compute the net evaluations zj = ∑(CBi - yij). Then calculate Cj-Zj
Step 4: Check for optimal conditions. If at least one (Cj-Zj) is negative, then choose the most negative
of them and the corresponding column variable is taken as the entering column
variable.
Step 5 : To find the leaving variable,
find the ratio of bi / xi (xi positive values in the entering
column).
Step 6: The minimum
ratio is taken as the leaving variable. This variable in the BV column
will be replaced with the entering
column variable.
Step 7 : The element at the intersection of the Key column and key row is called the pivot element.
Step 8: Construct the next simplex
table in such a way that the pivot element
must be 1 and the other
elements in the key column
must be 0.
Step 9 : Repeat steps 3 to 8, till the optimal condition is obtained.
Artificial Variable
While converting ≥ inequality to an equation,
a variable called surplus variable is subtracted from the left-hand
side of the equation. The addition of this variable
will not satisfy the feasibility condition. Hence, to find the optimal
solution using the Simplex method, a variable called an Artificial
Variable is added to the left-hand side of
the equation.
While using the Simplex method to find
the optimal solution to the LPP, the artificial variables must be removed.
•
Two-Phase Method
•
Big-M Method or Method of Penalties
Two Phase Simplex Method
Phase I
Step 1 (a):
If the constraints in the given LP problem are (≥) type, then the necessary number of surplus and artificial variables are added to convert constraints
into equality constraints.
(b) If the given LP problem is of minimization, then convert it to maximization
Step 2: Assign zero coefficient to each of the decision variables (xj ) and the slack
and surplus variables; and
assign – 1 coefficient to each of the artificial variables. This yields
the following auxiliary LP problem.
Step 3: Apply the simplex algorithm to solve this auxiliary LP problem.
(a) Max Z * = 0 and at least one artificial variable
is present in the basis with a positive value. This means that no feasible
solution exists for the original LP problem.
(b) Max Z * = 0 and no artificial variable is
present in the basis. This means that
only decision variables (xj ’s) are present in the basis and hence
proceed to Phase II to obtain
an optimal basic feasible solution on the original LP problem.
(c) Max Z * = 0 and at least one artificial variable
is present in the basis at zero value. This means that a feasible solution
exists and proceed directly to Phase II or else eliminate the artificial basic
variable and then proceed to Phase II.
Phase II:
Assign actual coefficients to the
variables in the objective function and zero coefficient to the artificial
variables which appear at zero value in the basis at
the end of Phase I.
The last simplex table of Phase I can
be used as the initial simplex table for Phase II.
Then
apply the usual simplex algorithm
to the modified simplex table to
get the optimal solution to the original
problem.
Artificial variables that do not appear
in the basis column can be removed
from the table.
Big-M Method
Big-M method is another method of removing artificial variables from the basis.
In this method, a large penalty (M) is added as
coefficient to artificial variables in the objective function. The penalty
is supposed to be designated by – M, for a maximization problem, and + M, for a minimization problem,
where M > 0.
The Big-M method for solving an LP problem can be summarized in the following steps:
Step 1:
Express the LP problem in the standard form by adding slack
variables, surplus variables and artificial variables.
Assign a zero coefficient to both slack and surplus
variables.
Then assign a very large
coefficient + M (minimization case)
and – M (maximization
case) to artificial variable in the objective function.
Step 2:
The initial basic feasible solution is obtained by assigning zero
value to decision variables, x1, x2, ..., etc.
Step 3:
Calculate the values
of cj – zj in last row of the simplex table
and examine these values.
(i)
If all cj – zj ≥ 0, then the current basic feasible solution is optimal.
(ii) If for a column,
k, ck – zk is most negative
and all entries
in this column are negative, then the problem has an unbounded optimal solution.
(iii) If one or more cj – zj < 0 (minimization case),
then select the variable
with the largest negative cj – zj value (largest value) as the entering variable.
Step 4: Determine
the key row and key element in the same manner as done in the simplex algorithm for the
maximization case.
Step 5: Continue
with the procedure
to update solution
at each iteration till the optimal
solution is obtained.
No comments:
Post a Comment