OPTIMIZATION TECHNIQUES

Unit 1
Definition: Operations Research:
Operations Research is the study of optimizations techniques. It is applied decision theory.

Scope or Uses or Applications of O.R.

OR is useful for solving :
1. Resource allocation problems
2. Inventory control problems
3. Maintenance and Replacement Problems
4. Sequencing and Scheduling Problems
5. Assignment of jobs to applicants to maximize total profit or minimize total cost.
6. Transportation Problems
7. Shortest route problems like travelling sales person problems.
8. Marketing Management problems
9. Finance Management problems
10. Production, Planning and control problems
11. Design Problems
12. Queuing Problems etc.

Scope of Operations Research

The scope of OR is not only confined to any specific agency like defence services but today it is widely
used in all industrial organisations. It can be used to find the best solution to any problem be it simple or
complex. It is useful in every field of human activities, where optimisation of resources is required in the
best way. Thus, it attempts to resolve the conflicts of interest among the components of organization in a
way that is best for the organisation as a whole. The main fields where OR is extensively used are given
below, however, this list is not exhaustive but only illustrative.
(i) National Planning and Budgeting
OR is used for the preparation of Five Year Plans, annual budgets, forecasting of income and expenditure,
scheduling of major projects of national importance, estimation of GNP, GDP, population, employment and
generation of agriculture yields etc.
(ii) Defence Services
Basically formulation of OR started from USA army, so it has wide application in the areas such as:
development of new technology, optimization of cost and time, tender evaluation, setting and layouts
 of defence projects, assessment of “Threat analysis”, strategy of battle, effective maintenance and
replacement of equipment, inventory control, transportation and supply depots etc.
(iii) Industrial Establishment and Private Sector Units
OR can be effectively used in plant location and setting finance planning, product and process planning,
facility planning and construction, production planning and control, purchasing, maintenance management
and personnel management etc. to name a few.
(iv) R & D and Engineering
Research and development being the heart of technological growth, OR has wide scope for and can be
applied in technology forecasting and evaluation, technology and project management, preparation of
tender and negotiation, value engineering, work/method study and so on.
(v) Business Management and Competition
OR can help in taking business decisions under risk and uncertainty, capital investment and returns,
business strategy formation, optimum advertisement outlay, optimum sales force and their distribution,
market survey and analysis and market research techniques etc.
(vi) Agriculture and Irrigation
In the area of agriculture and irrigation also OR can be useful for project management, construction of
major dams at minimum cost, optimum allocation of supply and collection points for fertilizer/seeds and
agriculture outputs and optimum mix of fertilizers for better yield.
(vii) Education and Training
OR can be used for obtaining optimum number of schools with their locations, optimum mix of
Students/teacher student ratio, optimum financial outlay and other relevant information in training of
graduates to meet out the national requirements.
(viii) Transportation
Transportation models of OR can be applied to real life problems to forecast public transport
requirements, optimum routing, forecasting of income and expenses, project management for railways,
railway network distribution, etc. In the same way it can be useful in the field of communication.
(ix) Home Management and Budgeting
OR can be effectively used for control of expenses to maximize savings, time management, work study
methods for all related works. Investment of surplus budget, appropriate insurance of life and
properties and estimate of depreciation and optimum premium of insurance etc.

Features / Characteristics of OR

The significant features of operations research include the followings:

(i) Decision-making. Every industrial organisation faces multifacet problems to identify best possible solution
to their problems. OR aims to help the executives to obtain optimal solution with the use of OR techniques. It
also helps the decision maker to improve his creative and judicious capabilities, analyse and understand the
problem situation leading to better control, better co-ordination, better systems and finally better decisions.
(ii) Scientific Approach. OR applies scientific methods, techniques and tools for the purpose of analysis and
solution of the complex problems. In this approach there is no place for guess work and the person bias of the
decision maker.
(iii) Inter-disciplinary Team Approach. Basically the industrial problems are of complex nature and therefore
require a team effort to handle it. This team comprises of scientist/mathematician and technocrates. Who jointly
use the OR tools to obtain a optimal solution of the problem. The tries to analyse the cause and effect
relationship between various parameters of the problem and evaluates the outcome of various alternative
strategies.
(iv) System Approach. The main aim of the system approach is to trace for each proposal all significant and
indirect effects on all sub-system on a system and to evaluate each action in terms of effects for the system as a
whole. The interrelationship and interaction of each sub-system can be handled with the help of
mathematical/analytical models of OR to obtain acceptable solution.
(v) Use of Computers. The models of OR need lot of computation and therefore, the use of computers becomes
necessary. With the use of computers it is possible to handle complex problems requiring large amount of
calculations.

ROLE OF OPERATIONS RESEARCH IN BUSINESS AND MANAGEMENT

1. Marketing Management Operations research techniques have definitely a role to play in

(a) Product selection
 (b) Competitive strategies
(c) Advertising strategy etc.
2. Production Management
The O.R. techniques are very useful in the following areas of production management.
(a) Production scheduling
(b) Project scheduling
(c) Allocation of resources
(d) Location of factories and their sizes
(e) Equipment replacement and Maintenance
(f) Inventory policy etc.
3. Finance Management
The techniques of OR are applied to Budgeting and Investment areas and especially to
(a) Cash flow analysis
(b) Capital requirement
(c) Credit policies
(d) Credit risks etc.
4. Personal Management
(a) Recruitment policies and
(b) Assignment of jobs are some of the areas of personnel management where OR techniques are useful.
5. Purchasing and Procurement
(a) Rules for purchasing
(b) Determining the quantity
(c) Determining the time of purchaser are some of the areas where OR techniques can be applied.
6. Distribution
In determining
(a) Location of warehouses
(b) Size of the warehouses
(c) Rental outlets
(d) Transportation strategies OR techniques are useful.
ROLE OF O.R. IN ENGINEERING
1. Optimal design of water resources systems
2. Optimal design of structures
3. Production, Planning, Scheduling and control
4. Optimal design of electrical networks
5. Inventory control
6. Planning of maintenance and replacement of equipment
7. Allocation of resources of services to maximize the benefit
8. Design of material handling
9. Optimal design of machines
10. Optimum design of control systems
11. Optimal selection of sites for an industry.

CLASSIFICATION OF MODELS

The first thing one has to do t use O.R. techniques after formulating a practical problem is to construct a suitable
model to represent he practical problem. A model is a reasonably simplified representation of a real-world
situation. It is an abstraction of reality. The models can broadly be classified as
Iconic (Physical) Models
Analogue Models
Mathematical Models
Also as
Static Models
Dynamic Models and in addition as
Deterministic Models
 Stochastic Models
Models can further be subdivided as
Descriptive Models
Prescriptive Models
Analytic Models
Simulation Models
Iconic Model:
This is a physical, or pictorial representation of various aspects of a system.
Eg. Toy, Miniature model of a building, scaled up model of a cell in biology etc.
Analogue or Schematic Model:
This uses one set of properties to represent another set of properties which a system under study has. Eg. A
network of water pipes to represent the flow of current in an electrical network or graphs, organisational charts
etc.
Mathematical model or Symbolic Model:
This uses a set of mathematical symbols (letters, numbers etc) to represent the decision variables of a system
under consideration. These variables related by mathematical equations or inequalities which describes the
properties of the system.
Eg. A linear programming model. A system of equatons representing an electrical network or differential equations
representing dynamic systems etc.
Static Model:
This is a model which does not take time into account. It assumes that the values of the variables do not change
with time during a certain period of time horizon.
Eg. A linear programming problem, an assignment problem, transportation problem etc.
Dynamic Model:
It is a model which considers time as one of the important variables.
Eg. A dynamic programming problem, A replacement problem.
Deterministic Model:
It is a model which does not take uncertainty into account.
Eg. A linear programming problem, an assignment problem etc.
Stochastic Model:
It is a model which considers uncertainty as an important aspect of the problem.
Eg. Any stochastic programming problem, stochastic inventory models etc.
Descriptive Model:
It is one which just describes a situation or system.
Eg. An opinion poll, any survey.
Predictive Model:
It is one which predicts something based on some data. Eg. Predicting election results before actually the
counting is completed.
Prescriptive Model:
It is one which prescribes or suggests a course of action for a problem.
Eg. Any programming (linear, nonlinear, dynamic, geometric etc.) problem.
Analytic Model:
It is a model in which exact solution is obtained by mathematical methods in closed form.
Simulation Model:
It is a representation of reality through the use of a model or device which will reach in the same manner as
reality under a given set of conditions. It is usually less mathematical and less time consuming and generally
least expensive as well. Eg. Queuing problems, inventory problems.
Some characteristic of a good model:
1) It should be reasonably simple.
2) A good model should be capable of taking into account new changes in the situation affecting its frame
significantly with ease.
3) Assumptions made to simplify the model should be as small as possible.
4) Number of variables used should be as small in number as possible.
5) The model should be open to parametric treatment.
Principles of Modelling:
1) Do not build up a complicated model while a simple one will suffice.
2) Beware of moulding the problems to fit a technique.
3) Deductions must be made carefully.
 4) Models should be validated prior to implementation.
5) A model should neither be pressed to do nor criticized for failing to do that for which it was never
intended.
6) Models are only aids in decision making.
7) Model should be a accurate as possible.

General methods of solving O.R. models:

1) Analytic Procedure: Solving models by classical Mathematical techniques like differential calculus,
finite differences etc. to obtain analytic solutions.
2) Iterative Procedure: Starts with a trial solution and a set of rules for improving it by repeating the
procedure until further improvement is not possible.
3) Monte-carlo technique: Taking sample observations, computing probability distributions for the variable
using random numbers and constructing some functions to determine values of the decisions variables.
Main Phases of O.R.
(1) Formulation of the Problems: Identifying the objective, the decision variables involved and the
constraints that arise involving the decision variables.
(2) Construction of a Mathematical Model: Expressing the measure of effectiveness which may be total
profit, total cost, utility etc., to be optimized by a Mathematical function called objective function.
Representing the constraints like budget constraints, raw materials constraints, resource constraints,
quality constraints etc., by means of mathematical equations or inequalities.
(3) Solving the Model constructed:
Determining the solution by analytic or iterative or Monte-Carlo method depending upon the structure of
the mathematical model.
(4) Controlling and updating: A solution which is optimum today may not be so tomorrow. The values of
the variables may change, new variables may also undergo a change. All these are determined in
updating.
(5) Testing the model and its solution i.e., validating the model: Checking as far as possible either from
the past available data or by expertise and experience whether the model gives a solution which can be
used in practice
(6) Implementation: Implement using the solution to achieve the desired goal.

4. Role of Operations Research in decision Making

Operations research plays an important role in almost all areas of decision making. Some areas where
operational research (OR) techniques can be used as listed below:
Financing and Investment Polices: This category includes the analysis of credit and loan policy, fund
flow and cash flow and also considers the dividend, share and bonus policy. It reflects the portfolio of
investment too.
Selling, Promotion, Marketing & Publicity: It emphasis on selection of the product and timing which
means what type of commodity should be manufactured at the proper passage of the time. It focuses on
the media of publicity like print media and electronic media may be chosen. It also used to know about
how many number of sales persons are required to some specific area. More over OR also use to select
the product mixed which include product, price, place and promotions.
Acquisition, Investigation, Manufacturing and Personnel Management:
The operational research techniques being used to purchase, substitute and reorganize the most
advantageous policies. These techniques also include location and manufacturing size of retail outlets,
factories and warehouses, loading and unloading facilities for trucks, allocation and scheduling of
resources and optimum to merge the products, recruitment and selection of best suitable employee for a
company and job assignments etc.
Research and Development:
The methods currently available in literature for numerically solving operational research problems may
be broadly classified as deterministic methods and probabilistic methods. The deterministic methods try
to guarantee that a neighborhood of the solution of a problem is attained. Such methods do not use any
stochastic techniques, but rely on a thorough search of the feasible domain. They are applicable,
however, to a restricted class of problems only. On the other hand the probabilistic methods make use of
probabilistic or stochastic approach to search for the solutions for the problems. Although probabilistic
methods do not give an absolute guarantee of the exact solution having been obtained, these methods are
 sometimes preferred over the deterministic methods because they are applicable to wider class of
problems. There does not exist any operational research technique which can say I am the best.
Therefore there is always a need to investigate and develop an operational research technique for better
solution.

Limitations of Operations Research

OR has some limitations however, these are related to the problem of model building and the time and money
factors involved in application rather than its practical utility. Some of them are as follows:
(i) Magnitude of Computation. Operations research models try to find out optimal solution taking into account
all the factors. These factors are enormous and expressing them in quantity and establishing relationships among
these require voluminous calculations which can be handled by computers.
(ii) Non-Quantifiable Factors. OR provides solution only when all elements related to a problem can be
quantified. All relevant variables do not lend themselves to quantification. Factors which cannot be quantified,
find no place in OR study. Models in OR do not take into account qualitative factors or emotional factors which
may be quite important.
(iii) Distance between User and Analyst. OR being specialist’s job requires a mathematician or
statistician, who might not be aware of the business problems. Similarly, a manager fails to understand the
complex working of OR. Thus there is a gap between the two. Management itself may offer a lot of resistance
due to conventional thinking.
(iv) Time and Money Costs. When basic data are subjected to frequent changes, incorporating
them into the OR models is a costly proposition. Moreover, a fairly good solution at present may be more
desirable than a perfect OR solution available after sometime. The computational time increases depending upon
the size of the problem and accuracy of results desired.
(v) Implementation. Implementation of any decision is a delicate task. It must take into account
the complexities of human relations and behavior. Sometimes, resistance is offered due to psychological
factors which may not have any bearing on the problem as well as its solution.

LINEAR PROGRAMMING PROBLEM

1. BASIC ASSUMPTIONS OF LINEAR PROGRAMMING PROBLEMS

The linear programming problems are formulated on the basis of the followingassumptions:

1. Proportionality: the contribution of each variable in the objective functionor its usage of
resources is directly proportional to the value of the variable. ie., if resource availability
increases by some percentage, then the output shall also increase by the same percentage.

2. Additivity: sum of the resources used by different activities must be equalto the total quantity
of resources used by each activity for all the resources individually or collectively.

3. Divisibility: The variable is not restricted to integer values.

4. Certainty or Deterministic: Co-efficient on the objective function and constraints are

completely known and do not change during the periodunder study in all the problems
considered.

5. Finiteness: Variables and constraints are finite in number.

6. Optimality: In a linear programming problem we determine the division variables so as to

extermise (optimize) the objective function of the LPP.

7. The problem involves only one objective namely profit maximization orcost minimization.

2. Definitions based on graphical method:

Solution: a set of values x1,x2,……xn which satisfies the constraints of the LPP iscalled its
 solution.

Feasible solution: Any solution to an LPP which satisfies the non-negativity

restrictions of the LPP is called its feasible solution.

Optimum solution: Any feasible solution which optimizes(maximizes or minimizes)the

objective function of the LPP is called its optimum solution or optimal solution.

Unique optimal solution: Since the problem is of maximization type and the maximum
value of Z is attained at a single vertex, this problem has a unique optimalsolution.

Multiple optimal solution: An LPP having more than one optimal solution is said tohave
alternative or multiple optimal solutions.

Unbounded solution: But there are points in this convex region for which z will havemuch
higher values. In fact, the maximum value of z occurs at infinity. Hence this problem has
unbounded solution.

No feasible solution: There being no point(x1,x2) common to both the shaded regions. That
is, we can not find a convex region for this problem. So the problemcannot be solved. Hence
the problem have no feasible solution.

THE SIMPLEX METHOD

The most commonly used method forlocating the optimal vertex is the simplex method or
simplex technique or simplex algorithm which was developed by G.Dantzig in 1947.

The simplex method provides an algorithm that consists in moving fromone vertex of the
region of feasible solutions to another vertex in such a way that the value of the objective
function at the succeeding vertex is more (or less, as the case may be) than at the preceding
vertex. This procedure of jumping from one vertex to another is then repeated. Sincethe
number of vertices is a finite number of steps or indicates the existence of an unbounded
solution.

• Definition: Given a system of m linear equations with n variables (m<n). The solution
obtained by setting (n-m) variables equal to zero andsolving for the remaining m variables is
called a Basic solution.
o The m variables are called basic variables and they form the basissolution. The (n-
m) variables that are put to zero are called a non- basic solutions.
• Definition: A basic solution is said to be a non - degenerate basicsolution if none of the
basic variables is zero.
• Definition: A basic solution is said to be a degenerate basic solution
If one or more of the basic variables are zero.
• Definition: A feasible solution which is also basic is called basicfeasible solution.
 Unit 4 – Network Analysis
1. Project:

A project is defined as a combination of interrelated activities all of which must be executed in a

certain order to achieve a set goal. A large and complex projectinvolves usually a number of
interrelated activities requiring men, machines, and materials. A number of methods that apply
network scheduling techniques

have been developed. Programme Evaluation Review Technique (PERT) and Critical Path Method
(CPM) are two of the many network techniques which arewidely used for planning, scheduling, and
controlling large complex projects.
2. The three main managerial functions for any project are:

1. Planning
2. Scheduling
3. Control

Planning :
This phase involves a listing of tasks or jobs that must be performed to complete a project
under consideration. In this phase, men , machines andmaterials required for the project in
addition to the estimates of costs and durations of various activities of the project are also
determined.

Scheduling:
This phase involves the laying out of the actual activities of the projectsin a logical sequence
of time in which they have to be performed.
Men and material requirements as well as the expected completion time ofeach activity at each
stage of the project are also determined.

Control:
This phase consists of reviewing the progress of the project whether the actual performance
is according to the planned schedule and finding the reasons for difference, in any between the
schedule and performance. Thebasic aspect of control is to analyse and correct this difference
by taking remedial action wherever possible.
PERT and CPM are especially useful for scheduling and controlling.

3. BASIC TERMINOLOGIES:
1. Activity: Activity is a task or an item of work to be done in a project. An activity consumes
resources like time, money, labour etc.
An activity is represented by an arrow with a node (event) at the beginningand a node (event) at
the end indicating the start and termination (finish) of the activity, Nodes are denoted by circles.

2. Immediate predecessor and immediate successor:

A is called the Immediate predecessor of B and B is called the immediate successor of A. If C
can start only after completing activities A and B thenit is diagrammatically represented as
follows:
 If the project contains two or more activities which have some of their immediate predecessors
in common then there is a need for introducing what is called dummy activity.
3. Dummy activity:
Dummy activity is an imaginary activity which does not consume any resource and which
serves the purpose of indicating the predecessor or successor relationship clearly in any activity
on arrow diagram.

4. Project network:
The diagram denoting all the activities of a project by arrows taking into account the technological sequence
of the activities is called the project network represented by “activity on arrow diagram or arrow diagram”.

5. Rules for constructing a project network:

Nodes may be numbered using the rule given below:

(Ford and Fulkerson’s Rule)

1. Number the start node which has no predecessor activity as 1.

2. Delete all the activities emanating from this node1.
3. Number all the resulting start nodes without any predecessor as 2,3,..
4. Delete all the activities originating from the start nodes 2,3,….. in step 3.
5. Number all the resulting new start nodes without any predecessor nextto the last number
used in step (3).

6. Repeat the process until the terminal node without any successor activityis reached and
number this terminal node suitably.

6. CRITICAL PATH:

Path, connecting the first initial node to the very last terminal node, of thelongest duration in
any project network is called a critical path.
7. Total Float:
Total float of an activity (T.F.) is defined as the difference between the latest finish and the earliest finish of
the activity or the difference between the latest start and the earliest start of the activity.
8. Slack of the event:
(L - E) of an event of i-j is called the slack of the event j.
9. Free Float:
Free Float of an activity (F.F) is that portion of the total float which can be used for rescheduling that activity
without affecting the succeeding activity.
Free float of an activity = (T.F. of i-j) – (Slack of head event).
10. Independent Float (I.F.):
I.F. of an activity is the amount of time by which the activity can be rescheduled without affecting the
preceding or succeeding activities of that activity.
Independent Float of an activity = (F.F. of i-j) – (Slack of tail event).
11. Interference Float = T.F – F.F

12. PROGRAMME EVALUATION REVIEW TECHNIQUE (PERT):

This technique, unlike CPM, takes into account the uncertainty of projectdurations into account.
PERT calculations depend upon the following three-time estimates.
13. Optimist (least) time estimate: (t0 or a) is the duration of any activity wheneverything goes
on very well during the project i.e., labourers are available and come in time, machines are working
properly, money is available whenever needed, there is no scarcity of raw material needed, etc.
14. Pessimistic (greatest) time estimate: (tp or b) is the duration of any activity whenalmost everything
goes against our will and a lot of difficulties are faced while doing a project.
15. Most likely time estimate: (tm or m) is the duration of any activity when sometimes things go on
very well, and sometimes things go on very badly whiledoing the project.

16. BASIC DIFFERENCES BETWEEN PERT AND CPM:

1. PERT was developed in a brand new R and D project it had to considerand deal with the
uncertainties associated with such projects. Thus the project duration is regarded as a
random variable and therefore probabilities are calculated so as to characterize it.

2. Emphasis is given to important stages of completion of tasks rather than the activities required
to be performed to reach the particular event or taskin the analysis of the network. ie., PERT
network is essentially an event- oriented network.

3. PERT is usually used for projects in which time estimates an uncertain.Example: R & D
activities which are usually non-repetitive.
4. PERT helps in identifying critical areas in a project so that suitable necessary adjustments
may be made to meet the scheduled completiondate of the project.

CPM

1. CPM was developed for conventional projects like construction project which consists of
well-known routine tasks whose resource requirementand duration were known with
certainty.

2. CPM is suited to establish a trade-off for optimum balancing between thescheduled time and
cost of the project.
3. CPM is used for projects involving well-known activities of repetitive in nature.