Operations Research Applications and algorithms lecture notes
operations research models and methods operations research quantitative techniques for management and lecture notes on operations research pdf free download
Dr.FlynnHanks,United States,Teacher
Published Date:26-07-2017
Your Website URL(Optional)
Comment
MBA-H2040 Quantitative Techniques for Managers
UNIT I
1 INTRODUCTION TO OPERATIONS RESEARCH
LESSON STRUCTURE
1.1 Introduction
1.2 History of Operations Research
1.3 Stages of Development of Operations
Research
1.4 Relationship Between Manager and
OR Specialist
1.5 OR Tools and Techniques
1.6 Applications of Operations Research
1.7 Limitations of Operations Research
1.8 Summary
Objectives
1.9 Key Terms After Studying this lesson, you should be able
1.10 Self Assessment Questions to:
1.11 Further References Understand the meaning, purpose, and
tools of Operations Research
Describe the history of Operations
Research
Describe the Stages of O.R
Explain the Applications of Operations
Research
Describe the Limitations of Operation
Research
Understand the OR specialist and
Manager relationship
LESSON MBA-H2040 Quantitative Techniques for Managers
1.1 Introduction
The British/Europeans refer to "operational research", the Americans to "operations research" - but both
are often shortened to just "OR" - which is the term we will use.
Another term which is used for this field is "management science" ("MS"). The Americans
sometimes combine the terms OR and MS together and say "OR/MS" or "ORMS". Yet other terms
sometimes used are "industrial engineering" ("IE") and "decision science" ("DS"). In recent years there
has been a move towards a standardization upon a single term for the field, namely the term "OR".
Operation Research is a relatively new discipline. The contents and the boundaries of the OR are
not yet fixed. Therefore, to give a formal definition of the term Operations Research is a difficult task.
The OR starts when mathematical and quantitative techniques are used to substantiate the decision being
taken. The main activity of a manager is the decision making. In our daily life we make the decisions
even without noticing them. The decisions are taken simply by common sense, judgment and expertise
without using any mathematical or any other model in simple situations. But the decision we are
concerned here with are complex and heavily responsible. Examples are public transportation network
planning in a city having its own layout of factories, residential blocks or finding the appropriate product
mix when there exists a large number of products with different profit contributions and production
requirement etc.
Operations Research tools are not from any one discipline. Operations Research takes tools from
different discipline such as mathematics, statistics, economics, psychology, engineering etc. and
combines these tools to make a new set of knowledge for decision making. Today, O.R. became a
professional discipline which deals with the application of scientific methods for making decision, and
especially to the allocation of scarce resources. The main purpose of O.R. is to provide a rational basis
for decisions making in the absence of complete information, because the systems composed of human,
machine, and procedures may do not have complete information.
Operations Research can also be treated as science in the sense it describing, understanding and
predicting the systems behaviour, especially man-machine system. Thus O.R. specialists are involved in
three classical aspect of science, they are as follows:
i) Determining the systems behaviour
ii) Analyzing the systems behaviour by developing appropriate models
iii) Predict the future behaviour using these models
The emphasis on analysis of operations as a whole distinguishes the O.R. from other research
and engineering. O.R. is an interdisciplinary discipline which provided solutions to problems of military
operations during World War II, and also successful in other operations. Today business applications are
MBA-H2040 Quantitative Techniques for Managers
primarily concerned with O.R. analysis for the possible alternative actions. The business and industry
befitted from O.R. in the areas of inventory, reorder policies, optimum location and size of warehouses,
advertising policies, etc.
As stated earlier defining O.R. is a difficult task. The definitions stressed by various experts and
Societies on the subject together enable us to know what O.R. is, and what it does. They are as follows:
1. According to the Operational Research Society of Great Britain (OPERATIONAL RESEARCH
QUARTERLY, l3(3):282, l962), Operational Research is the attack of modern science on
complex problems arising in the direction and management of large systems of men, machines,
materials and money in industry, business, government and defense. Its distinctive approach is to
develop a scientific model of the system, incorporating measurements of factors such as change
and risk, with which to predict and compare the outcomes of alternative decisions, strategies or
controls. The purpose is to help management determine its policy and actions scientifically.
2. Randy Robinson stresses that Operations Research is the application of scientific methods to
improve the effectiveness of operations, decisions and management. By means such as analyzing
data, creating mathematical models and proposing innovative approaches, Operations Research
professionals develop scientifically based information that gives insight and guides decision-
making. They also develop related software, systems, services and products.
3. Morse and Kimball have stressed O.R. is a quantitative approach and described it as “ a scientific
method of providing executive departments with a quantitative basis for decisions regarding the
operations under their control”.
4. Saaty considers O.R. as tool of improving quality of answers. He says, “O.R. is the art of giving
bad answers to problems which otherwise have worse answers”.
5. Miller and Starr state, “O.R. is applied decision theory, which uses any scientific, mathematical
or logical means to attempt to cope with the problems that confront the executive, when he tries
to achieve a thorough-going rationality in dealing with his decision problem”.
6. Pocock stresses that O.R. is an applied Science. He states “O.R. is scientific methodology
(analytical, mathematical, and quantitative) which by assessing the overall implication of various
alternative courses of action in a management system provides an improved basis for
management decisions”.
1.2 History of Operations Research
Operation Research is a relatively new discipline. Whereas 70 years ago it would have been possible to
study mathematics, physics or engineering (for example) at university it would not have been possible to
study Operation Research, indeed the term O.R. did not exist then. It was really only in the late 1930's
that operational research began in a systematic fashion, and it started in the UK. As such it would be
interesting to give a short history of O.R.
1936
MBA-H2040 Quantitative Techniques for Managers
Early in 1936 the British Air Ministry established Bawdsey Research Station, on the east coast, near
Felixstowe, Suffolk, as the centre where all pre-war radar experiments for both the Air Force and the
Army would be carried out. Experimental radar equipment was brought up to a high state of reliability
and ranges of over 100 miles on aircraft were obtained.
It was also in 1936 that Royal Air Force (RAF) Fighter Command, charged specifically with the
air defense of Britain, was first created. It lacked however any effective fighter aircraft - no Hurricanes
or Spitfires had come into service - and no radar data was yet fed into its very elementary warning and
control system.
It had become clear that radar would create a whole new series of problems in fighter direction
and control so in late 1936 some experiments started at Biggin Hill in Kent into the effective use of such
data. This early work, attempting to integrate radar data with ground based observer data for fighter
interception, was the start of OR.
1937
The first of three major pre-war air-defence exercises was carried out in the summer of 1937. The
experimental radar station at Bawdsey Research Station was brought into operation and the information
derived from it was fed into the general air-defense warning and control system. From the early warning
point of view this exercise was encouraging, but the tracking information obtained from radar, after
filtering and transmission through the control and display network, was not very satisfactory.
1938
In July 1938 a second major air-defense exercise was carried out. Four additional radar stations had been
installed along the coast and it was hoped that Britain now had an aircraft location and control system
greatly improved both in coverage and effectiveness. Not so The exercise revealed, rather, that a new
and serious problem had arisen. This was the need to coordinate and correlate the additional, and often
conflicting, information received from the additional radar stations. With the outbreak of war apparently
imminent, it was obvious that something new - drastic if necessary - had to be attempted. Some new
approach was needed.
Accordingly, on the termination of the exercise, the Superintendent of Bawdsey Research Station, A.P.
Rowe, announced that although the exercise had again demonstrated the technical feasibility of the radar
system for detecting aircraft, its operational achievements still fell far short of requirements. He
therefore proposed that a crash program of research into the operational - as opposed to the technical -
aspects of the system should begin immediately. The term "operational research" RESEARCH into
MBA-H2040 Quantitative Techniques for Managers
(military) OPERATIONS was coined as a suitable description of this new branch of applied science.
The first team was selected from amongst the scientists of the radar research group the same day.
1939
In the summer of 1939 Britain held what was to be its last pre-war air defence exercise. It involved some
33,000 men, 1,300 aircraft, 110 antiaircraft guns, 700 searchlights, and 100 barrage balloons. This
exercise showed a great improvement in the operation of the air defence warning and control system.
The contribution made by the OR team was so apparent that the Air Officer Commander-in-Chief RAF
Fighter Command (Air Chief Marshal Sir Hugh Dowding) requested that, on the outbreak of war, they
should be attached to his headquarters at Stanmore in north London.
Initially, they were designated the "Stanmore Research Section". In 1941 they were redesignated
the "Operational Research Section" when the term was formalised and officially accepted, and similar
sections set up at other RAF commands.
1940
On May 15th 1940, with German forces advancing rapidly in France, Stanmore Research Section was
asked to analyses a French request for ten additional fighter squadrons (12 aircraft a squadron - so 120
aircraft in all) when losses were running at some three squadrons every two days (i.e. 36 aircraft every 2
days). They prepared graphs for Winston Churchill (the British Prime Minister of the time), based upon
a study of current daily losses and replacement rates, indicating how rapidly such a move would deplete
fighter strength. No aircraft were sent and most of those currently in France were recalled.
This is held by some to be the most strategic contribution to the course of the war made by OR
(as the aircraft and pilots saved were consequently available for the successful air defense of Britain, the
Battle of Britain).
1941 onward
In 1941, an Operational Research Section (ORS) was established in Coastal Command which was to
carry out some of the most well-known OR work in World War II.
The responsibility of Coastal Command was, to a large extent, the flying of long-range sorties by
single aircraft with the object of sighting and attacking surfaced U-boats (German submarines). The
technology of the time meant that (unlike modern day submarines) surfacing was necessary to recharge
batteries, vent the boat of fumes and recharge air tanks. Moreover U-boats were much faster on the
surface than underwater as well as being less easily detected by sonar.
MBA-H2040 Quantitative Techniques for Managers
Thus the Operation Research started just before World War II in Britain with the establishment
of teams of scientists to study the strategic and tactical problems involved in military operations. The
objective was to find the most effective utilization of limited military resources by the use of quantitative
techniques. Following the end of the war OR spread, although it spread in different ways in the UK and
USA.
In 1951 a committee on Operations Research formed by the National Research Council of USA,
and the first book on “Methods of Operations Research”, by Morse and Kimball, was published. In 1952
the Operations Research Society of America came into being.
Success of Operations Research in army attracted the attention of the industrial mangers who
were seeking solutions to their complex business problems. Now a days, almost every organization in all
countries has staff applying operations research, and the use of operations research in government has
spread from military to wide variety of departments at all levels. The growth of operations research has
not limited to the U.S.A. and U.K., it has reached many countries of the world.
India was one the few first countries who started using operations research. In India, Regional
Research Laboratory located at Hyderabad was the first Operations Research unit established during
1949. At the same time another unit was set up in Defense Science Laboratory to solve the Stores,
Purchase and Planning Problems. In 1953, Operations Research unit was established in Indian Statistical
Institute, Calcutta, with the objective of using Operations Research methods in National Planning and
Survey. In 1955, Operations Research Society of India was formed, which is one of the first members of
International Federation of Operations Research societies. Today Operations Research is a popular
subject in management institutes and schools of mathematics.
1.3 Stages of Development of Operations Research
The stages of development of O.R. are also known as phases and process of O.R, which has six
important steps. These six steps are arranged in the following order:
Step I: Observe the problem environment
Step II: Analyze and define the problem
Step III: Develop a model
Step IV: Select appropriate data input
Step V: Provide a solution and test its reasonableness
Step VI: Implement the solution
MBA-H2040 Quantitative Techniques for Managers
Step I: Observe the problem environment
The first step in the process of O.R. development is the problem environment observation. This step
includes different activities; they are conferences, site visit, research, observations etc. These activities
provide sufficient information to the O.R. specialists to formulate the problem.
Step II: Analyze and define the problem
This step is analyzing and defining the problem. In this step in addition to the problem definition the
objectives, uses and limitations of O.R. study of the problem also defined. The outputs of this step are
clear grasp of need for a solution and its nature understanding.
Step III: Develop a model
This step develops a model; a model is a representation of some abstract or real situation. The models
are basically mathematical models, which describes systems, processes in the form of equations,
formula/relationships. The different activities in this step are variables definition, formulating equations
etc. The model is tested in the field under different environmental constraints and modified in order to
work. Some times the model is modified to satisfy the management with the results.
Step IV: Select appropriate data input
A model works appropriately when there is appropriate data input. Hence, selecting appropriate input
data is important step in the O.R. development stage or process. The activities in this step include
internal/external data analysis, fact analysis, and collection of opinions and use of computer data banks.
The objective of this step is to provide sufficient data input to operate and test the model developed in
Step_III.
Step V: Provide a solution and test its reasonableness
This step is to get a solution with the help of model and input data. This solution is not implemented
immediately, instead the solution is used to test the model and to find there is any limitations. Suppose if
the solution is not reasonable or the behaviour of the model is not proper, the model is updated and
modified at this stage. The output of this stage is the solution(s) that supports the current organizational
objectives.
Step VI: Implement the solution
MBA-H2040 Quantitative Techniques for Managers
At this step the solution obtained from the previous step is implemented. The implementation of the
solution involves mo many behavioural issues. Therefore, before implementation the implementation
authority has to resolve the issues. A properly implemented solution results in quality of work and gains
the support from the management.
The process, process activities, and process output are summarized in the following Table 1-1.
Process Activities Process Process Output
Site visits, Conferences, Sufficient information and
Step 1:
Observations, Research support to proceed
Observe the problem
environment
Define: Use, Objectives, Clear grasp of need for and
limitations Step 2: nature of solution requested
Analyze and define
the problem
Define interrelationships, Models that works under stated
Formulate equations, environmental constraints
Step 3:
Develop a Model
Use known O.R. Model ,
Search alternate Model
Analyze: internal-external data, Sufficient inputs to operate and
Step 4:
facts test model
Select appropriate data
input
Collect options,
Use computer data banks
Test the model Solution(s) that support current
Step 5:
organizational goals
Provide a solution and
find limitations
test its reasonableness
update the model
Step 6:
Implement the
solution MBA-H2040 Quantitative Techniques for Managers
Resolve behavioural issues Improved working and
Management support for longer
Sell the idea
run operation of model
Give explanations
Management involvement
Table 1-1: Process, Process activities, Process output of O.R. development stages
1.4 Relationship between the Manager and O.R. Specialist
The key responsibility of manager is decision making. The role of the O.R. specialist is to help the
manager make better decisions. Figure 1-1 explains the relationship between the O.R. specialist and the
manager/decision maker.
STEPS IN PROBLEM RECOGNITION, INVOLVEMENT: O.R. SPECIALIST or
FORMULATION AND SOLUTION MANAGER
Recognize from organizational
Manager
symptoms that a problem exists.
Decide what variables are involved; state
the problem in quantitative relationships Manager and O.R. Specialist
among the variables.
Investigate methods for solving the
O.R. Specialist
problems as stated above; determine
appropriate quantitative tools to be used.
Attempt solutions to the problems; find
various solutions; state assumptions
O.R. Specialist
underlying these solutions; test
alternative solutions.
Determine which solution is most
effective because of practical constraints
Manager and O.R. Specialist
within the organization; decide what the
solution means for the organization.
MBA-H2040 Quantitative Techniques for Managers
Choose the solution to be used.
Manager
‘Sell’ the decision to operating managers;
Manager and O.R. Specialist
get their understanding and cooperation.
Figure 1-1 Relationship between Manager/Decision Maker and O.R. Specialists
1.5 O.R. Tools and Techniques
Operations Research uses any suitable tools or techniques available. The common frequently used
tools/techniques are mathematical procedures, cost analysis, electronic computation. However,
operations researchers given special importance to the development and the use of techniques like linear
programming, game theory, decision theory, queuing theory, inventory models and simulation. In
addition to the above techniques, some other common tools are non-linear programming, integer
programming, dynamic programming, sequencing theory, Markov process, network scheduling
(PERT/CPM), symbolic Model, information theory, and value theory. There is many other Operations
Research tools/techniques also exists. The brief explanations of some of the above techniques/tools are
as follows:
Linear Programming:
This is a constrained optimization technique, which optimize some criterion within some constraints. In
Linear programming the objective function (profit, loss or return on investment) and constraints are
linear. There are different methods available to solve linear programming.
Game Theory:
This is used for making decisions under conflicting situations where there are one or more
players/opponents. In this the motive of the players are dichotomized. The success of one player tends to
be at the cost of other players and hence they are in conflict.
Decision Theory:
Decision theory is concerned with making decisions under conditions of complete certainty about the
future outcomes and under conditions such that we can make some probability about what will happen
in future.
Queuing Theory:
MBA-H2040 Quantitative Techniques for Managers
This is used in situations where the queue is formed (for example customers waiting for service, aircrafts
waiting for landing, jobs waiting for processing in the computer system, etc). The objective here is
minimizing the cost of waiting without increasing the cost of servicing.
Inventory Models:
Inventory model make a decisions that minimize total inventory cost. This model successfully reduces
the total cost of purchasing, carrying, and out of stock inventory.
Simulation:
Simulation is a procedure that studies a problem by creating a model of the process involved in the
problem and then through a series of organized trials and error solutions attempt to determine the best
solution. Some times this is a difficult/time consuming procedure. Simulation is used when actual
experimentation is not feasible or solution of model is not possible.
Non-linear Programming:
This is used when the objective function and the constraints are not linear in nature. Linear relationships
may be applied to approximate non-linear constraints but limited to some range, because approximation
becomes poorer as the range is extended. Thus, the non-linear programming is used to determine the
approximation in which a solution lies and then the solution is obtained using linear methods.
Dynamic Programming:
Dynamic programming is a method of analyzing multistage decision processes. In this each elementary
decision depends on those preceding decisions and as well as external factors.
Integer Programming:
If one or more variables of the problem take integral values only then dynamic programming method is
used. For example number or motor in an organization, number of passenger in an aircraft, number of
generators in a power generating plant, etc.
Markov Process:
Markov process permits to predict changes over time information about the behavior of a system is
known. This is used in decision making in situations where the various states are defined. The
probability from one state to another state is known and depends on the current state and is independent
of how we have arrived at that particular state.
MBA-H2040 Quantitative Techniques for Managers
Network Scheduling:
This technique is used extensively to plan, schedule, and monitor large projects (for example computer
system installation, R & D design, construction, maintenance, etc.). The aim of this technique is
minimize trouble spots (such as delays, interruption, production bottlenecks, etc.) by identifying the
critical factors. The different activities and their relationships of the entire project are represented
diagrammatically with the help of networks and arrows, which is used for identifying critical activities
and path. There are two main types of technique in network scheduling, they are:
Program Evaluation and Review Technique (PERT) – is used when activities time is not known
accurately/ only probabilistic estimate of time is available.
Critical Path Method (CPM) – is used when activities time is know accurately.
Information Theory:
This analytical process is transferred from the electrical communication field to O.R. field. The
objective of this theory is to evaluate the effectiveness of flow of information with a given system. This
is used mainly in communication networks but also has indirect influence in simulating the examination
of business organizational structure with a view of enhancing flow of information.
1.6 Applications of Operations Research
Today, almost all fields of business and government utilizing the benefits of Operations Research. There
are voluminous of applications of Operations Research. Although it is not feasible to cover all
applications of O.R. in brief. The following are the abbreviated set of typical operations research
applications to show how widely these techniques are used today:
Accounting:
Assigning audit teams effectively
Credit policy analysis
Cash flow planning
Developing standard costs
Establishing costs for byproducts
Planning of delinquent account strategy
Construction:
Project scheduling, monitoring and control
Determination of proper work force
Deployment of work force
Allocation of resources to projects
Facilities Planning:
Factory location and size decision
Estimation of number of facilities required
Hospital planning
MBA-H2040 Quantitative Techniques for Managers
International logistic system design
Transportation loading and unloading
Warehouse location decision
Finance:
Building cash management models
Allocating capital among various alternatives
Building financial planning models
Investment analysis
Portfolio analysis
Dividend policy making
Manufacturing:
Inventory control
Marketing balance projection
Production scheduling
Production smoothing
Marketing:
Advertising budget allocation
Product introduction timing
Selection of Product mix
Deciding most effective packaging alternative
Organizational Behavior / Human Resources:
Personnel planning
Recruitment of employees
Skill balancing
Training program scheduling
Designing organizational structure more effectively
Purchasing:
Optimal buying
Optimal reordering
Materials transfer
Research and Development:
R & D Projects control
R & D Budget allocation
Planning of Product introduction
1.7 Limitations of Operations Research
Operations Research has number of applications; similarly it also has certain limitations. These
limitations are mostly related to the model building and money and time factors problems involved in its
application. Some of them are as given below:
i) Distance between O.R. specialist and Manager
Operations Researchers job needs a mathematician or statistician, who might not be aware of
the business problems. Similarly, a manager is unable to understand the complex nature of
Operations Research. Thus there is a big gap between the two personnel.
ii) Magnitude of Calculations
MBA-H2040 Quantitative Techniques for Managers
The aim of the O.R. is to find out optimal solution taking into consideration all the factors. In
this modern world these factors are enormous and expressing them in quantitative model and
establishing relationships among these require voluminous calculations, which can be
handled only by machines.
iii) Money and Time Costs
The basic data are subjected to frequent changes, incorporating these changes into the
operations research models is very expensive. However, a fairly good solution at present may
be more desirable than a perfect operations research solution available in future or after some
time.
iv) Non-quantifiable Factors
When all the factors related to a problem can be quantifiable only then operations research
provides solution otherwise not. The non-quantifiable factors are not incorporated in O.R.
models. Importantly O.R. models do not take into account emotional factors or qualitative
factors.
v) Implementation
Once the decision has been taken it should be implemented. The implementation of decisions
is a delicate task. This task must take into account the complexities of human relations and
behavior and in some times only the psychological factors.
1.8 Summary
Operations Research is relatively a new discipline, which originated in World War II, and became very
popular throughout the world. India is one of the few first countries in the world who started using
operations research. Operations Research is used successfully not only in military/army operations but
also in business, government and industry. Now a day’s operations research is almost used in all the
fields.
Proposing a definition to the operations research is a difficult one, because its boundary and
content are not fixed. The tools for operations search is provided from the subject’s viz. economics,
engineering, mathematics, statistics, psychology, etc., which helps to choose possible alternative courses
of action. The operations research tool/techniques include linear programming, non-linear programming,
dynamic programming, integer programming, Markov process, queuing theory, etc.
Operations Research has a number of applications. Similarly it has a number of limitations,
which is basically related to the time, money, and the problem involves in the model building. Day-by-
day operations research gaining acceptance because it improve decision making effectiveness of the
managers. Almost all the areas of business use the operations research for decision making.
1.9 Key Terms
MBA-H2040 Quantitative Techniques for Managers
OR: Operations Research.
MS: Management Science.
Symbolic Model: An abstract model, generally using mathematical symbols.
Criterion: is measurement, which is used to evaluation of the results.
Integer Programming: is a technique, which ensures only integral values of variables in the problem.
Dynamic Programming: is a technique, which is used to analyze multistage decision process.
Linear Programming: is a technique, which optimizes linear objective function under limited
constraints.
Inventory Model: these are the models used to minimize total inventory costs.
Optimization: Means maximization or minimization.
1.10 Self Assessment Questions
Q1. Define Operations Research.
Q2. Describe the relationship between the manager and O.R. specialist.
Q3. Explain the various steps in the O.R. development process.
Q4. Discuss the applications of O.R.
Q5. Discuss the limitation of O.R.
Q6. Describe different techniques of O.R.
Q7. Discuss few areas of O.R. applications in your organization or organization you are familiar with.
1.11 Further References
Hamdy A Taha, 1999. Introduction to Operations Research, PHI Limited, New Delhi.
Sharma, J.K., 1989. Mathematical Models in Operations Research, Tata McGraw Hill Publishing
Company Ltd., New Delhi.
Beer, Stafford, 1966. Decision and Control, John Wiley & Sons, Inc., New York.
Levin, Rubin, Stinson, Gardner, 1992. Quantitative Approaches to Management, Tata McGraw Hill
Publishing Company Ltd. New Delhi.
Wagner, Harvery M., 1975. Principles of Operations Research, PHI, Egnlewood Cliffs, N.J.
MBA-H2040 Quantitative Techniques for Managers
UNIT I
2 LINEAR PROGRAMMING –GRAPHICAL METHOD
LESSON STRUCTURE
2.1 Introduction to Linear Programming
2.2 Linear Programming Problem
Formulation
2.3 Formulation with Different Types of
Constraints
2.4 Graphical Analysis of Linear
Programming
2.5 Graphical Linear Programming Solution
2.6 Multiple Optimal Solutions
2.7 Unbounded Solution
2.8 Infeasible Solution
2.9 Summary
2.10 Key Terms
2.11 Self Assessment Questions
2.12 Key Solutions
2.13 Further References
LESSON MBA-H2040 Quantitative Techniques for Managers
Objectives
After studying this lesson, you should be able
to:
Formulate Linear Programming Problem
Identify the characteristics of linear
programming problem
Make a graphical analysis of the linear
programming problem
Solve the problem graphically
Identify the various types of solutions
MBA-H2040 Quantitative Techniques for Managers
2.1 Introduction to Linear Programming
Linear Programming is a special and versatile technique which can be applied to a variety of
management problems viz. Advertising, Distribution, Investment, Production, Refinery Operations, and
Transportation analysis. The linear programming is useful not only in industry and business but also in
non-profit sectors such as Education, Government, Hospital, and Libraries. The linear programming
method is applicable in problems characterized by the presence of decision variables. The objective
function and the constraints can be expressed as linear functions of the decision variables. The
decision variables represent quantities that are, in some sense, controllable inputs to the system being
modeled. An objective function represents some principal objective criterion or goal that measures the
effectiveness of the system such as maximizing profits or productivity, or minimizing cost or
consumption. There is always some practical limitation on the availability of resources viz. man,
material, machine, or time for the system. These constraints are expressed as linear equations involving
the decision variables. Solving a linear programming problem means determining actual values of the
decision variables that optimize the objective function subject to the limitation imposed by the
constraints.
The main important feature of linear programming model is the presence of linearity in the
problem. The use of linear programming model arises in a wide variety of applications. Some model
may not be strictly linear, but can be made linear by applying appropriate mathematical transformations.
Still some applications are not at all linear, but can be effectively approximated by linear models. The
ease with which linear programming models can usually be solved makes an attractive means of dealing
with otherwise intractable nonlinear models.
2.2 Linear Programming Problem Formulation
The linear programming problem formulation is illustrated through a product mix problem. The product
mix problem occurs in an industry where it is possible to manufacture a variety of products. A product
has a certain margin of profit per unit, and uses a common pool of limited resources. In this case the
linear programming technique identifies the products combination which will maximize the profit
subject to the availability of limited resource constraints.
Example 2.1:
Suppose an industry is manufacturing tow types of products P1 and P2. The profits per Kg of the two
products are Rs.30 and Rs.40 respectively. These two products require processing in three types of
machines. The following table shows the available machine hours per day and the time required on each
18MBA-H2040 Quantitative Techniques for Managers
machine to produce one Kg of P1 and P2. Formulate the problem in the form of linear programming
model.
Profit/Kg P1 P2 Total available Machine
Rs.30 Rs.40 hours/day
Machine 1 3 2 600
Machine 2 3 5 800
Machine 3 5 6 1100
Solution:
The procedure for linear programming problem formulation is as follows:
Introduce the decision variable as follows:
Let x = amount of P1
1
x = amount of P2
2
In order to maximize profits, we establish the objective function as
30x + 40x
1 2
Since one Kg of P1 requires 3 hours of processing time in machine 1 while the corresponding
requirement of P2 is 2 hours. So, the first constraint can be expressed as
3x + 2x ≤ 600
1 2
Similarly, corresponding to machine 2 and 3 the constraints are
3x + 5x ≤ 800
1 2
5x + 6x ≤ 1100
1 2
In addition to the above there is no negative production, which may be represented algebraically as
x ≥ 0 ; x ≥ 0
1 2
Thus, the product mix problem in the linear programming model is as follows:
Maximize
30x + 40x
1 2
Subject to:
3x + 2x ≤ 600
1 2
3x + 5x ≤ 800
1 2
5x + 6x ≤ 1100
1 2
x ≥ 0, x ≥ 0
1 2
2.3 Formulation with Different Types of Constraints
19MBA-H2040 Quantitative Techniques for Managers
The constraints in the previous example 2.1 are of “less than or equal to” type. In this section we are
going to discuss the linear programming problem with different constraints, which is illustrated in the
following Example 2.2.
Example 2.2:
A company owns two flour mills viz. A and B, which have different production capacities for high,
medium and low quality flour. The company has entered a contract to supply flour to a firm every month
with at least 8, 12 and 24 quintals of high, medium and low quality respectively. It costs the company
Rs.2000 and Rs.1500 per day to run mill A and B respectively. On a day, Mill A produces 6, 2 and 4
quintals of high, medium and low quality flour, Mill B produces 2, 4 and 12 quintals of high, medium
and low quality flour respectively. How many days per month should each mill be operated in order to
meet the contract order most economically.
Solution:
Let us define x1 and x2 are the mills A and B. Here the objective is to minimize the cost of the machine
runs and to satisfy the contract order. The linear programming problem is given by
Minimize
2000x + 1500x
1 2
Subject to:
6x + 2x ≥ 8
1 2
2x + 4x ≥ 12
1 2
4x + 12x ≥ 24
1 2
x ≥ 0, x ≥ 0
1 2
2.4 Graphical Analysis of Linear Programming
This section shows how a two-variable linear programming problem is solved graphically, which is
illustrated as follows:
Example 2.3:
Consider the product mix problem discussed in section 2.2
Maximize
30x + 40x
1 2
Subject to:
3x + 2x ≤ 600
1 2
3x + 5x ≤ 800
1 2
5x + 6x ≤ 1100
1 2
x ≥ 0, x ≥ 0
1 2
20
Advise:Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.