Nikhatshahin.files.wordpress.com
MB0048-Unit-01-Introduction to Operations Research
Unit-01-Introduction to Operations Research
Structure:
1.1 Introduction
Learning objectives
1.2 Historical Background
Definitions of Operations Research
1.3 Scope of Operations Research
1.4 Features of Operations Research
1.5 Phases of Operations Research
1.6 Types of Operations Research models
1.7 Operations Research Methodology
Definition
Construction
Solution
Validation
Implementation
1.8 Operations Research Techniques and Tools
1.9 Structure of the Mathematical Model
1.10 Limitations of Operations Research
1.11 Summary
1.12 Terminal Questions
1.13 Answers to SAQs and TQs
Answers to Self Assessment Questions
Answers to Terminal Questions
1.14 References
1.1 Introduction
Welcome to the unit on Operations Research Management. Operations Research Management focuses on the mathematical scoring of consequences of a decision aiming to optimise the use of time, effort and resources, and avoid blunders. The act of obtaining the best results under any given circumstances is known as optimising. The key purpose of Operations Research (OR) is to do preparative calculations that aid the decision-making process.
Now, you will agree that decision-making is a key part of our daily life. The ultimate goal of all decisions is to maximise benefits and minimise effort and time. OR gives decision makers the power to make effective decisions and improve day-to-day operations. Decision makers consider all the available options, study the outcomes and estimate the risks.
In simple situations, you use your common sense and judgement to take decisions. For example, if you are buying a microwave or washing machine, the decision-making process is not very complicated. You can simply compare the price, quality and durability of the well known brands and models in the market and take a decision based on it.
However, in complex situations, although it is possible to take decisions based on one’s common sense, a decision backed by mathematical calculations reduces the risk factor and increases the probability of success. Some such situations, where decision-makers have to reply on mathematical scoring and reasoning, are finding an appropriate product mix amidst competitor’s products or planning a public transportation network in a city.
Learning Objectives
By the end of this unit, you should be able to:
· List the significant features of Operations Research
· Describe the methodology of Operations Research
· Define the structure of a mathematical model in Operations Research
· Describe the significance of the function of Operations Research
1.2 Historical Background
During the World War II, scientists from United Kingdom studied the strategic and tactical problems associated with air and land defense of the country. The aim of this study was to determine the effective utilisation of limited military resources to win the battle. The technique was named Operations Research. After World War II, Operations Research techniques were developed and deployed in the decision making process in complicated situations in various fields, such as industrial, academic and government organisations.
1.2.1 Definitions of operations research
Churchman, Aackoff and Aruoff defined Operations Research as: “the application of scientific methods, techniques and tools to operation of a system with optimum solutions to the problems”, where ‘optimum’ refers to the best possible alternative.
The objective of Operations Research is to provide a scientific basis to the decision-makers for solving problems involving interaction of various components of the organisation. You can achieve this by employing a team of scientists from different disciplines, to work together for finding the best possible solution in the interest of the organisation as a whole. The solution thus obtained is known as an optimal decision.
You can also define Operations Research as “The use of scientific methods to provide criteria for decisions regarding man, machine, and systems involving repetitive operations”.
Self Assessment Questions
Fill in the blanks:
1. The main objective of OR is to provide a _______ ________ to the decision-makers.
2. OR employs a team of _________ from _________ __________.
1.3 Scope of Operations Research
Any problem, simple or complicated, can use OR techniques to find the best possible solution. This section will explain the scope of OR by seeing its application in various fields of everyday life.
i) In Defense Operations: In modern warfare, the defense operations are carried out by three major independent components namely Air Force, Army and Navy. The activities in each of these components can be further divided in four sub-components namely: administration, intelligence, operations and training and supply. The applications of modern warfare techniques in each of the components of military organisations require expertise knowledge in respective fields. Furthermore, each component works to drive maximum gains from its operations and there is always a possibility that the strategy beneficial to one component may be unfeasible for another component. Thus in defense operations, there is a requirement to co-ordinate the activities of various components, which gives maximum benefit to the organisation as a whole, having maximum use of the individual components. A team of scientists from various disciplines come together to study the strategies of different components. After appropriate analysis of the various courses of actions, the team selects the best course of action, known as the ‘optimum strategy’.
ii) In Industry: The system of modern industries is so complex that the optimum point of operation in its various components cannot be intuitively judged by an individual. The business environment is always changing and any decision useful at one time may not be so good some time later. There is always a need to check the validity of decisions continuously against the situations. The industrial revolution with increased division of labour and introduction of management responsibilities has made each component an independent unit having their own goals. For example: production department minimises the cost of production but maximises output. Marketing department maximises the output, but minimises cost of unit sales. Finance department tries to optimise the capital investment and personnel department appoints good people at minimum cost. Thus each department plans its own objectives and all these objectives of various department or components come to conflict with one another and may not agree to the overall objectives of the organisation. The application of OR techniques helps in overcoming this difficulty by integrating the diversified activities of various components to serve the interest of the organisation as a whole efficiently. OR methods in industry can be applied in the fields of production, inventory controls and marketing, purchasing, transportation and competitive strategies.
iii) Planning: In modern times, it has become necessary for every government to have careful planning, for economic development of the country. OR techniques can be fruitfully applied to maximise the per capita income, with minimum sacrifice and time. A government can thus use OR for framing future economic and social policies.
iv) Agriculture: With increase in population, there is a need to increase agriculture output. But this cannot be done arbitrarily. There are several restrictions. Hence the need to determine a course of action serving the best under the given restrictions. You can solve this problem by applying OR techniques.
v) In Hospitals: OR methods can solve waiting problems in out-patient department of big hospitals and administrative problems of the hospital organisations.
vi) In Transport: You can apply different OR methods to regulate the arrival of trains and processing times minimise the passengers waiting time and reduce congestion, formulate suitable transportation policy, thereby reducing the costs and time of trans-shipment.
vii) Research and Development: You can apply OR methodologies in the field of R&D for several purposes, such as to control and plan product introductions.
Self Assessment Questions
3. Mention two applications of OR.
4. How can a hospital benefit from the application of OR methods?
1.4 Features of Operation Research
Some key features of OR are as follows:
1. OR is system oriented. OR scrutinises the problem from an organisation’s perspective. The results can be optimal for one part of the system, while the same can be unfavourable for another part of the system.
2. OR imbibes an inter–disciplinary team approach. Since no single individual can have a thorough knowledge of all fast developing scientific know-how, personalities from different scientific and managerial cadre form a team to solve the problem.
3. OR makes use of scientific methods to solve problems.
4. OR increases effectiveness of the management’s decision-making ability.
5. OR makes use of computers to solve large and complex problems.
6. OR offers a quantitative solution.
7. OR also takes into account the human factors.
Self Assessment Questions
Fill in the blanks:
5. OR ________ inter-disciplinary approach.
6. OR increases the effectiveness of ________ ability.
1.5 Phases of Operations Research
The scientific method in OR study generally involves the following three phases.
[pic]
Figure 1.1: Phases of operations research
1. Judgment Phase: This phase includes the following activities:
a) Determination of the operations
b) Establishment of the objectives and values related to the operations
c) Determination of the suitable measures of effectiveness
d) Formulation of the problems relative to the objectives
2. Research Phase: This phase utilises the following methodologies:
a) Operations and data collection for a better understanding of the problems
b) Formulation of hypothesis and model
c) Observation and experimentation to test the hypothesis on the basis of additional data
d) Analysis of the available information and verification of the hypothesis using pre-established measure of effectiveness
e) Prediction of various results and consideration of alternative methods
3. Action Phase: The action phase involves making recommendations for the decision process. The recommendations can be made by those who identified and presented the problem or anyone who influences the operation in which the problem has occurred.
Self Assessment Questions
State True/False:
7. OR gives qualitative solution
8. One of the OR phases is Action phase
1.6 Types of OR Models
A model is an idealised representation or abstraction of a real-life system. The objective of a model is to identify significant factors that affect the real-life system and their interrelationships. A model aids the decision-making process as it provides a simplified description of complexities and uncertainties of a problem in a logical structure. The most significant advantage of a model is that it does not interfere with the real-life system.
1.6.1 A broad classification of OR models
You can broadly classify OR models into the following types.
[pic][pic]
Figure 1.2: Classification of models
a. Physical Models include all form of diagrams, graphs and charts. They are designed to tackle specific problems. They bring out significant factors and interrelationships in pictorial form to facilitate analysis. There are two types of physical models:
I. Iconic models
II. Analog models
Iconic models are primarily images of objects or systems, represented on a smaller scale. These models can simulate the actual performance of a product. Analog models are small physical systems having characteristics similar to the objects they represent, such as toys.
b. Mathematical or Symbolic Models employ a set of mathematical symbols to represent the decision variable of the system. The variables are related by mathematical systems. Some examples of mathematical models are allocation, sequencing, and replacement models.
c. By nature of Environment: Models can be further classified as follows:
I. Deterministic model in which everything is defined and the results are certain, such as an EOQ model.
II. Probabilistic Models in which the input and output variables follow a defined probability distribution, such as the Games Theory.
d. By the extent of Generality Models can be further classified as follows:
I. General Models are the models which you can apply in general to any problem. For example: Linear programming.
II. Specific Models on the other hand are models that you can apply only under specific conditions. For example: You can use the sales response curve or equation as a function of only in the marketing function.
Self Assessment Questions
State True/False
9. Diagram belongs to the physical model
10. Allocation problems are represented by iconic model
1.7 OR Methodology
The basic dominant characteristic feature of operations research is that it employs mathematical representations or models to analyse problems. This distinct approach represents an adaptation of the scientific methodology used by the physical sciences. The scientific method translates a real given problem into a mathematical representation which is solved and retransformed into the original context. The OR approach to problem solving consists of the following steps: Defining the problem, Constructing the model, Solving the model, Validating the model and Implementing the final result.
[pic]
Figure 1.3: Steps in the OR methodology
1.7.1 Definition
The first and the most important step in the OR approach of problem solving is to define the problem. You need to ensure that the problem is identified properly because this problem statement will indicate three major aspects:
1) A description of the goal or the objective of the study
2) An identification of the decision alternative to the system
3) The recognition of the limitations, restrictions and requirements of the system.
1.7.2 Construction
Based on the problem definition, you need to identify and select the most appropriate model to represent the system. While selecting a model, you need to ensure that the model specifies quantitative expressions for the objective and the constraints of the problem in terms of its decision variables. A model gives a perspective picture of the whole problem and helps tackling it in a well-organised manner. Therefore, if the resulting model fits into one of the common mathematical models, you can obtain a convenient solution by using mathematical techniques. If the mathematical relationships of the model are too complex to allow analytic solutions, a simulation model may be more appropriate. There are various types of models which you can construct under different conditions.
1.7.3 Solution
After deciding on an appropriate model you need to develop a solution for the model and interpret the solution in the context of the given problem. A solution to a model implies determination of a specific set of decision variables that would yield an optimum solution. An optimum solution is one which maximises or minimises the performance of any measure in a model subject to the conditions and constraints imposed on the model.
1.7.4 Validation
A model is a good representation of a system. However, the optimal solution must work towards improving the system’s performance. You can test the validity of a model by comparing its performance with some past data available from the actual system. If under similar conditions of inputs, your model can reproduce the past performance of the system, then you can be sure that your model is valid. However, you will still have no assurance that future performance will continue to duplicate the past behaviour. Secondly, since the model is based on careful examination of past data, the comparison should always reveal favourable results. In some instances, this problem may be overcome by using data from trial runs of the system. Note that such validation methods are not appropriate for non-existent systems, since data will not be available for comparison.
1.7.5 Implementation
You need to apply the optimal solution obtained from the model to the system and note the improvement in the performance of the system. You need to validate this performance check under changing conditions. To do so, you need to translate these results into detailed operating instructions issued in an understandable form to the individuals who will administer and operate the recommended system. The interaction between the operations research team and the operating personnel reaches its peak in this phase.
1.8 OR Techniques and Tools
The different techniques and tools used in OR are as follows:
1. Linear programming: You can use linear programming to find a solution for optimising a given objective. The objective may be to maximise profit or to minimise cost. You need to ensure that both the objective function and the constraints can be expressed as linear expressions of decision variables. You will learn about the various uses of linear programming in Chapter-2.
2. Inventory control methods: The production, purchasing and material managers are always confronted with questions, such as when to buy, how much to buy and how much to keep in stock. The inventory model aims at optimising these inventory levels.
3. Goal programming: In linear programming, you take a single objective function and consider all other factors as constraints. However, in real life there may be number of important objective functions. Goal programming has several objective functions, each having a target value Programme models are developed to minimise deviations from these targets.
4. Queuing model: The queuing theory is based on the concept of probability. It indicates the capability of a given system and the changes possible in the system when you modify the system. In formulating a queuing model you need not take into account all the constraints. There is no maximisation or minimisation of an objective function. Therefore, the application of queuing theory cannot be viewed as an optimisation process. You can use the queuing theory to estimate the required balance between customer waiting time and the service capability of the system. You need to first consider several alternatives, evaluate them through queuing models, study their effect on the system, and then make a choice. The criteria for evaluation will be measures of efficiency of the system, such as the average length of a queue, expected waiting time of a customer and the average time spent by the customer in the system. In this approach, your success primarily depends on the alternatives considered and not so much on the queuing models developed.
5. Transportation model: The transportation model is an important class of linear programs. The model studies the minimisation of the cost of transporting a commodity from a number of sources to several destinations. The supply at each source and the demand at each destination are known. The objective of the model is to develop an integral transportation schedule that meets all demands from the inventory at a minimum total transportation cost.
The transportation problem involves m sources, each of which has available ai (i = 1, 2, …..,m) units of homogeneous product and n destinations, each of which requires bj (j = 1, 2…., n) units of products. Here ai and bj are positive integers. The cost cij of transporting one unit of the product from the ith source to the jth destination is given for each
i and j. It is assumed that the total supply and the total demand are equal.
[pic] (1)
The condition (1) is guaranteed by creating either a fictitious destination with a demand equal to the surplus if total demand is less than the total supply or a (dummy) source with a supply equal to the shortage if total demand exceeds total supply. The cost of transportation from the fictitious destination to all sources and from all destinations to the fictitious sources are assumed to be zero so that total cost of transportation will remain the same.
6. In addition to the above there are tools, such as the sequence model, the assignment model, and network analysis which you will learn in detail in later units.
Self Assessment Questions
State True/False
11. OR methodology consists of definition, solution and validation only.
12. The interaction between OR team and Management reaches peak level in implementation phase.
1.9 The Structure of the Mathematical Model
Many industrial and business situations are concerned with planning activities. In each case of planning, there are limited sources, such as men, machines, material and capital at the disposal of the planner. One has to take decision regarding these resources to either maximise production, or minimise the cost of production or maximise the profit. These problems are referred as the problems of constrained optimisation.
Linear programming is a technique for determining an optimal schedule of interdependent activities, for the given resources. Therefore, you can say that programming refers to planning and the process of decision-making about a particular plan of action from a given set of alternatives.
Any business activity or production activity to be formulated as a mathematical model can best be discussed through its parts which are as follows:
1. Decision variables
2. Objective function
3. Constraints
4. Diet problem
Decision variables
Decision variables are the unknowns, which you need to determine from the solution of the model. The parameters represent the controlled variables of the system.
Objective function
The objective function defines the measure of effectiveness of the system as a mathematical function of its decision variables. The optimal solution to the model is obtained when the corresponding values of the decision variable yield the best value of the objective function whilst satisfying all constraints. Therefore, you can say that the objective function acts as an indicator for the achievement of the optimal solution.
While formulating a problem, the desire of the decision-maker is expressed as a function of ‘n’ decision variables. This function is a linear programming problem that is each of its items will have only one variable raised to the power one). Some of the objective functions in practice are:
· Maximisation of contribution or profit
· Minimisation of cost
· Maximisation of production rate or minimisation of production time
· Minimisation of labour turnover
· Minimisation of overtime
· Maximisation of resource utilisation
· Minimisation of risk to environment or factory
Constraints
To account for the physical limitations of the system, you need to ensure that the model includes constraints, which limit the decision variables to their feasible range or permissible values. These are expressed as constraining mathematical functions.
For example, in chemical industries, restrictions come from the government about throwing gases in the environment. Restrictions from sales department about the marketability of some products are also treated as constraints. A linear programming problem then has a set of constraints in practice.
The mathematical models in OR may be viewed generally as determining the values of the decision variables x J, J = 1, 2, 3, —— n, which will optimize Z = f (x 1, x 2, —- x n).
Subject to the constraints:
g i (x 1, x 2 —– x n) ~ b i, i = 1, 2, —- m
And xJ ³ 0 j = 1, 2, 3 —- n where ~ is £, ³ or =.
The function f is called the objective function, where xj ~ bi, represent the ith constraint for i = 1, 2, 3 —- m where b i is a known constant. The constraints x j ³ 0 are called the non-negativity condition, which restrict the variables to zero or positive values only.
Diet problem
Formulate the mathematical model for the following:
Vitamin – A and Vitamin – B are found in food –1 and food – 2.
One unit of food – 1 contains 5 units of vitamin – A and 2 units of vitamin–B.
One unit of food – 2 contains 6 units of vitamin – A and 3 units of vitamin–B.
The minimum daily requirement of a person is 60 units of vitamin – A and 80 units of Vitamin – B.
The cost per one unit of food – 1 is Rs. 5/- and one unit of food–2 is Rs. 6/-. Assume that any excess units of vitamins are not harmful. Find the minimum cost of the mixture (of food–1 and food–2) which meets the daily minimum requirements of vitamins.
Mathematical Model of the Diet Problem: Suppose x1 = the number of units of food–1 in the mixture and x2 = the number of units of food–2 in the mixture.
Let’s formulate the constraint related to vitamin-A. Since each unit of food–1 contains 5 units of vitamin– A, we have that x1 units of food–1 contains 5x1 units of vitamin– A. Since each unit of food– 2 contains 6 units of vitamin–A, we have that x2 units of food–2 contains 6x2 units of vitamin–A. Therefore, the mixture contains 5x1 + 6x2 units of vitamin-A. Since the minimum requirement of vitamin– A is 60 units, you can say that 5x1 + 6x2 ³ 60.
Now let’s formulate the constraint related to vitamin–B. Since each unit of food–1 contains 2 units of vitamin–B we have that x1 units of food–1 contains 2x1 units of vitamin-B. Since each unit of food–2 contains 3 units of vitamin–B, we have that x2 units of food–2 contains 3x2 units of vitamin–B.
Therefore the mixture contains 2x1 + 3x2 units of vitamin–B. Since the minimum requirement of vitamin–B is 80 units, you can say that
2x2 + 3x2 ³ 80
Next let’s formulate the cost function. Given that the cost of one unit of food–1 is Rs. 5/- and one unit of food – 2 is Rs. 6/-. Therefore, x1 units of food–1 costs Rs. 5x1, and x2 units of food – 2 costs Rs. 6x2.
Therefore, the cost of the mixture is given by Cost = 5x1 + 6x2.
If we write z for the cost function, then you can write z = 5x1 + 6x2.
Since cost is to be minimised, you can write min z = 5x1 + 6x2.
Since the number of units (x1 or x2) are always non-negative, therefore, you have x1 ³ 0, x2 ³ 0.
Therefore, the mathematical model is:
5x1 + 6x2 ³ 60
2x1 + 3x2 ³ 80
x1 ³ 0, x2 ³ 0, min z = 5x1 + 6x2.
1.10 Limitations of OR
The limitations are more related to the problems of model building, time and money factors.
i. Magnitude of computation: Modern problems involve a large number of variables. The magnitude of computation makes it difficult to find the interrelationship.
ii. Intangible factors: Non – quantitative factors and human emotional factor cannot be taken into account.
iii. Communication gap: There is a wide gap between the expectations of managers and the aim of research professionals.
iv. Time and Money factors: When you subject the basic data to frequent changes then incorporation of them into OR models becomes a costly affair.
v. Human Factor: Implementation of decisions involves human relations and behaviour.
Self Assessment Questions
Fill in the blanks:
13. OR imbibes _________ team approach.
14. Linear programming is tool of _______.
15. The three phases of OR are ________.
16. To solve any problem through OR approach the first step is _______.
17. _________ represents a real life system.
18. _________ represents the controlled variables of the system
1.11 Summary
The OR approach needs to be equally developed in various agricultural problems on a regional or international basis. With the explosion of population and consequent shortage of food, every country faces the problem of optimum allocation of land in various crops in accordance with climate conditions and available facilities. The problem of optimal distribution of water from a resource like a reservoir for irrigation purposes is faced by each developing country, and a good amount of scientific work can be done in this direction.
1.12 Terminal Questions
1. Define OR.
2. What are the characteristic features of OR?
3. What is a model in OR? Discuss different models available in OR.
4. Write short notes are different phases of OR.
5. What are the limitations of OR?
1.13 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. Scientific basis
2. Scientists, different disciplines
3. Industry Planning
4. To solve waiting problems
5. Imbibes
6. Decision making
7. True
8. True
9. True
10. False
11. False
12. False
13. Inter-disciplinary
14. OR
15. Judgement phase, Research phase & Action phase
16. Define the problem
17. Model
18. Parameters
Answers to Terminal Questions
1. Refer to 1.2.1
2. Refer to 1.4
3. Refer to 1.6
4. Refer to 1.5
5. Refer to 1.10
1.14 References
No external sources have been referred for this unit.
Copyright © 2009 SMU
Powered by Sikkim Manipal University
.
MB0048-Unit-02-Linear Programming
Unit 2 Linear Programming
Structure:
2.1 Introduction
Learning objectives
2.2 Requirements
Basic assumptions of linear programming problems
2.3 Linear Programming
Canonical forms
Case studies of linear programming problems
2.4 Graphical Analysis
Some basic definitions
2.5 Graphical Methods to Solve Linear Programming Problems
Working rule
Solved problems on mixed constraints LP problem
Solved problem for unbounded solution
Solved problem for inconsistent solution
Solved problem for redundant constraint
2.6 Summary
2.7 Terminal Questions
2.8 Answers to SAQs and TQs
Answers to Self Assessment Questions
Answers to Terminal Questions
2.9 References
2.1 Introduction
Welcome to the unit of Operations Research on Linear Programming. Linear programming focuses on obtaining the best possible output (or a set of outputs) from a given set of limited resources.
Minimal time and effort and maximum benefit coupled with the best possible output or a set of outputs is the mantra of any decision-maker. Today, decision-makers or managements have to tackle the issue of allocating limited and scarce resources at various levels in an organisation in the best possible manner. Man, money, machine, time and technology are some of these common resources. The management’s task is to obtain the best possible output (or a set of outputs) from these given resources.
You can measure the output from factors, such as the profits, the costs, the social welfare, and the overall effectiveness. In several situations, you can express the output (or a set of outputs) as a linear relationship among several variables. You can also express the amount of available resources as a linear relationship among various system variables. The management’s dilemma is to optimise (maximise or minimise) the output or the objective function subject to the set of constraints. Optimisation of resources in which both the objective function and the constraints are represented by a linear form is known as a linear programming problem (LPP).
Learning objectives
By the end of this unit, you should be able to:
· Construct linear programming problem and analyse a feasible region
· Evaluate and solve linear programming problems graphically
2.2 Requirements of LPP
The common requirements of a LPP are as follows.
i. Decision variables and their relationship
ii. Well-defined objective function
iii. Existence of alternative courses of action
iv. Non-negative conditions on decision variables
2.2.1 Basic Assumptions of LPP
1. Linearity: You need to express both the objective function and constraints as linear inequalities.
2. Deterministic: All co-efficient of decision variables in the objective and constraints expressions are known and finite.
3. Additivity: The value of the objective function and the total sum of resources used must be equal to the sum of the contributions earned from each decision variable and the sum of resources used by decision variables respectively.
4. Divisibility: The solution of decision variables and resources can be non-negative values including fractions.
Self Assessment Questions
Fill in the blanks
1. Both the objective function and constraints are expressed in _____ forms.
2. LPP requires existence of _______, _______, ____ and _______.
3. Solution of decision variables can also be ____________.
2.3 Linear Programming
The LPP is a class of mathematical programming where the functions representing the objectives and the constraints are linear. Optimisation refers to the maximisation or minimisation of the objective functions.
You can define the general linear programming model as follows:
Maximise or Minimise:
Z = c1 x1 + c2 x2 + - - - - + cn xn
Subject to the constraints,
a11 x1 + a12 x2 + —– + a1n xn ~ b1
a21 x1 + a22 x2 + —– + a2n xn ~ b2
——————————————-
am1 x1 + am2 x2 + ——- + amn xn ~ bm
and x1 ≥ 0, x2 ≥ 0, ——————– xn ≥ 0
Where cj, bi and aij (i = 1, 2, 3, ….. m, j = 1, 2, 3 ——- n) are constants determined from the technology of the problem and xj (j = 1, 2, 3 —- n) are the decision variables. Here ~ is either ≤ (less than), ≥ (greater than) or = (equal). Note that, in terms of the above formulation the coefficients cj, bi aij are interpreted physically as follows. If bi is the available amount of resources i, where aij is the amount of resource i that must be allocated to each unit of activity j, the “worth” per unit of activity is equal to cj.
2.3.1 Canonical forms
You can represent the general Linear Programming Problem (LPP) mentioned above in the canonical form as follows:
Maximise Z = c1 x1+c2 x2 + —— + cn
Subject to,
a11 x1 + a12 x2 + —— + a1n xn £ b1
a21 x1 + a22 x2 + —— + a2n xn £ b2
——————————————–
am1 x1+am2 x2 + …… + amn xn £ bm
x1, x2, x3, … xn ³ 0.
The following are the characteristics of this form.
1. All decision variables are non-negative.
2. All constraints are of ≤ type.
3. The objective function is of the maximisation type.
You can represent any LPP in the canonical form by using five elementary transformations, which are as follows:
1. The minimisation of a function is mathematically equivalent to the maximisation of the negative expression of this function. That is,
Minimise Z = c1 x1 + c2x2 + ……. + cn xn
is equivalent to
Maximise – Z = – c1x1 – c2x2 – … – cn xn
2. Any inequality in one direction (≤ or ≥) may be changed to an inequality in the opposite direction (≥ or ≤) by multiplying both sides of the inequality by –1. For example
2x1+3x2 ³ 5 is equivalent to –2x1–3x2 £ –5
3. An equation can be replaced by two inequalities in opposite direction. For example:
2x1+3x2 = 5 can be written as 2x1+3x2 ≤ 5 and 2x1+3x2 ≥ 5 or 2x1+3x2 ≤ 5 and – 2x1 – 3x2 ≤ – 5
4. An inequality constraint with its left hand side in the absolute form can be changed into two regular inequalities. For example:
2x1+3x2 ≤ 5 is equivalent to 2x1+3x2 ≤ 5 and 2x1+3x2 ≥ – 5 or – 2x1– 3x2 ≤ 5
5. The variable which is unconstrained in sign (≥ 0, ≤ 0 or zero) is equivalent to the difference between 2 non-negative variables. For example:
if x is unconstrained in sign then x = (x+ – x–) where x+ ≥ 0, x– ≤ 0
|Caselet |
|An automobile company has two units X and Y which manufacture three different models of cars - A, B and C. The|
|company has to supply 1500, 2500, and 3000 cars of A, B and C respectively per week (6 days). It costs the |
|company Rs. 1,00,000 and Rs. 1,20,000 per day to run the units X and Y respectively. On a day unit X |
|manufactures 200, 250 and 400 cars and unit Y manufactures 180, 200 and 300 cars of A, B and C respectively |
|per day. The operations manager has to decide on how many days per week should each unit be operated to meet |
|the current demand at minimum cost. |
|The operations manager along with his team uses a LPP model to arrive at the minimum cost solution. |
2.3.2 Case Studies of linear programming problems
[pic]
[pic]
[pic]
Self Assessment Questions
State True/False
4. One of the characteristics of canonical form in the objective function must be of maximisation.
5. 2x – 3y ≤ 10 can be written as -2x + 3y ≥-10
2.4 Graphical Analysis
You can analyse linear programming with 2 decision variables graphically.
Example
Let’s look at the following illustration.
Maximise Z = 700 x1+500 x2
Subject to 4x1+3x2 £ 210
2x1+x2 £ 90
and x1 ³ 0, x2 ³ 0
Let the horizontal axis represent x1 and the vertical axis x2. First, draw the line 4x1 + 3x2 = 210, (by replacing the inequality symbols by the equality) which meets the x1-axis at the point A (52.50, 0) (put x2 = 0 and solve for x1 in 4x1 + 3x2 = 210) and the x2 – axis at the point B (0, 70) (put x1 = 0 in 4x1 + 3x2 = 210 and solve for x2).
[pic]
Figure 2.1: Linear programming with 2 decision variables
Any point on the line 4x1+3x2 = 210 or inside the shaded portion will satisfy the restriction of the inequality, 4x1+3x2 £ 210. Similarly the line 2x1+x2 = 90 meets the x1-axis at the point C(45, 0) and the x2 – axis at the point D(0, 90).
[pic]
Figure 2.2: Linear programming with 2 decision variables
Combining the two graphs, you can sketch the area as follows:
[pic]
Figure 2.3: Feasible region
The 3 constraints including non-negativity are satisfied simultaneously in the shaded region OCEB. This region is called feasible region.
2.4.1 Some basic definitions
[pic]
[pic]
Note: The objective function is maximised or minimised at one of the extreme points referred to as optimum solution. Extreme points are referred to as vertices or corner points of the convex regions.
[pic]
Self Assessment Questions
Fill in the blanks
6. The collection of all feasible solutions is known as the ________ region.
7. A linear inequality in two variables is known as a _________.
2.5 Graphical Methods to Solve LPP
Solving a LPP with 2 decision variables x1 and x2 through graphical representation is easy. Consider x1 x2 – the plane, where you plot the solution space enclosed by the constraints. The solution space is a convex set bounded by a polygon; since a linear function attains extreme (maximum or minimum) values only on the boundary of the region. You can consider the vertices of the polygon and find the value of the objective function in these vertices. Compare the vertices of the objective function at these vertices to obtain the optimal solution of the problem.
2.5.1 Working rule
The method of solving a LPP on the basis of the above analysis is known as the graphical method. The working rule for the method is as follows.
Step 1: Write down the equations by replacing the inequality symbols by the equality symbols in the given constraints.
Step 2: Plot the straight lines represented by the equations obtained in step I.
Step 3: Identify the convex polygon region relevant to the problem. Decide on which side of the line, the half-plane is located.
Step 4: Determine the vertices of the polygon and find the values of the given objective function Z at each of these vertices. Identify the greatest and least of these values. These are respectively the maximum and minimum value of Z.
Step 5: Identify the values of (x1, x2) which correspond to the desired extreme value of Z. This is an optimal solution of the problem
[pic]
[pic]
2.5.2 Solved problems on mixed constraints LP problem
[pic]
[pic]
In linear programming problems, you may have:
i) a unique optimal solution or
ii) many number of optimal solutions or
iii) an unbounded solution or
iv) no solutions.
[pic]
2.5.3 Solved problem for unbounded solution
[pic]
2.5.4 Solved problem for inconsistent solution
[pic]
2.5.5 Solved problem for redundant constraint
[pic]
[pic]
Self Assessment Questions
State True/False
8. The feasible region is a convex set
9. The optimum value occurs anywhere in feasible region
2.6 Summary
In a LPP, you first identify the decision variables with economic or physical quantities whose values are of interest to the management. The problems must have a well-defined objective function expressed in terms of the decision variable.
The objective function is to maximise the resources when it expresses profit or contribution. Here, the objective function indicates that cost has to be minimised. The decision variables interact with each other through some constraints. These constraints arise due to limited resources, stipulation on quality, technical, legal or variety of other reasons.
The objective function and the constraints are linear functions of the decision variables. A LPP with two decision variables can be solved graphically. Any non-negative solution satisfying all the constraints is known as a feasible solution of the problem. The collection of all feasible solutions is known as a feasible region. The feasible region of a LPP is a convex set. The value of the decision variables, which maximise or minimise the objectives function is located on the extreme point of the convex set formed by the feasible solutions. Sometimes the problem may be unfeasible indicating that no solution exists for the problem.
2.7 Terminal Questions
1. Use the graphical method to solve the LPP.
Maximise Z= 5x1 + 3x2
Subject to:
3x1 + 5x2 £ 15
5x1 + 2x2 £ 10
x1, x2 ³ 0
2. Mathematically formulate the problem.
A firm manufactures two products; the net profit on product 1 is Rs. 3 per unit and the net profit on product 2 is Rs. 5 per unit. The manufacturing process is such that each product has to be processed in two departments D1 and D2. Each unit of product 1 requires processing for 1 minute at D1 and 3 minutes at D2; each unit of product 2 requires processing for 2 minute at D1 and 2 minutes at D2.
Machine time available per day is 860 minutes at D1 and 1200 minutes at D2. How much of products 1 and 2 should be produced every day so that total profit is maximum. Formulate this as a problem in L.P.P.
2.8 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. Linear
2. Alternate course of action
3. Fractious
4. True
5. True
6. Feasible
7. Half-plan
8. True
9. False
Answers to Terminal Questions
1. [pic]
2. Maximise 3x1 + 5x2, subject to x1 + 2x2 £ 800 (minutes)
3x1 + 2x2 £ 1200 (minutes) x1, x2 ³ 0
2.9 References
No external sources have been referred.
About the Author
[pic]
admin
Copyright © 2010 SMU.
Powered by WordPress.
MB0048-Unit-03-Simplex Method
Unit-03-Simplex Method
Structure:
3.1 Introduction
Learning objectives
3.2 Standard Form of LPP
The standard form of LPP
Fundamental theorem of LPP
3.3 Solution of LPP – Simplex Method
Initial basic feasible solution of a LPP
To solve problem by Simplex Method
3.4 The Simplex Algorithm
Steps
3.5 Penalty Cost Method or Big M-method
3.6 Two Phase Method
3.7 Solved Problems on Minimisation
3.8 Summary
3.9 Terminal Questions
3.10 Answers to SAQs & TQs
Answers to Self Assessment Questions
Answers to Terminal Questions
3.11 References
3.1 Introduction
Welcome to the third unit of Operations Research Management on the simplex method. The simplex method focuses on solving LPP of any enormity involving two or more decision variables.
The simplex algorithm is an iterative procedure for finding the optimal solution to a linear programming problem. The objective function controls the development and evaluation of each feasible solution to the problem. If a feasible solution exists, it is located at a corner point of the feasible region determined by the constraints of the system.
The simplex method simply selects the optimal solution amongst the set of feasible solutions of the problem. The efficiency of this algorithm is because it considers only those feasible solutions which are provided by the corner points, and that too not all of them. You can consider obtaining an optimal solution based on a minimum number of feasible solutions.
Learning objectives
By the end of this unit, you should be able to:
· Create a standard form of LPP from the given hypothesis
· Apply the simplex algorithm to the system of equations
· Interpret the big M-technique
· Discuss the importance of the two phase method
· Construct the dual from the primal (and vice versa)
3.2 Standard Form of LPP
The characteristics of the standard form of LPP are:
1. All constraints are equations except for the non-negativity condition, which remain inequalities [pic]only.
2. The right-hand side element of each constraint equation is non-negative.
3. All the variables are non-negative.
4. The objective function is of maximisation or minimisation type.
You can change the inequality constraints of equations by adding or subtracting the left hand side of each such constraint by a non-negative variable. The non-negative variable that has to be added to a constraint inequality of the form £ to change it to an equation is called a slack variable. The non-negative variable subtracted from a constraint inequality of the form ³ to change it to an equation is called a surplus variable.
To make the right hand side of a constraint equation positive, multiply both the sides of the resulting equation by (-1). Use the elementary transformations introduced with the canonical form to achieve the remaining characteristics.
3.2.1 The standard form of the LPP
[pic]
3.2.2 Fundamental theorem of LPP
A set of m simultaneous linear equations in n unknowns/variables, n [pic]m, AX = b, with r (A) = m.
If there is a feasible solution X [pic]0, then there exists a basic feasible solution.
Self Assessment Questions
State True or False
1. We add surplus variable for [pic]of constraint.
2. The right hand side element of each constraint is non-negative.
3.3 Solution of the Linear Programming Program – Simplex Method
Consider a LPP given in the standard form
To optimise z = c1 x1 + c2 x2 + —+ cn xn
Subject to
a11 x1 + a12 x2 + — + an x n ± S1 = b1
a21 x1 + a22 x2 + —-+ a2n xn ± S2 = b2
………………………………………………………………….
am1 x1 + am2 x2 + — + amn xn ± Sm = bm
x1, x2, — xn, S1, S2 —, Sm [pic]0.
To each of the constraint equations, add a new variable called an artificial variable on the left hand side of every equation which does not contain a slack variable. Subsequently every constraint equation will contain either a slack variable or an artificial variable.
The introduction of slack and surplus variables does not alter either the constraints or the objective function. Therefore, you can incorporate such variables in the objective function with zero coefficients. However, the artificial variables do change the constraints as these are added only to the left hand side of the equations.
The newly derived constraint equation is equivalent to the original equation, only if all the artificial variables have value zero. Artificial variables are incorporated into the objective function with very large positive coefficient M in the minimisation program and very large negative coefficient–M in the maximisation program guaranteeing optimal solutions. The large positive and negative coefficients represent the penalty incurred for making a unit assignment to the artificial variable.
Thus the standard form of LPP can be given as follows:
Optimise Z = CT X
Subject to AX = B,
And X [pic]0
Where X is a column vector with decision, slack, surplus and artificial variables, C is the vector corresponding to the costs; A is the coefficient matrix of the constraint equations and B is the column vector of the right hand side of the constraint equations.
[pic]
3.3.1 Initial basic feasible solution of a LPP
Consider a system of m equations in n unknowns x1, x2 - - an,
a11 x1 + a12 x2 + - - + a1n xn = b1
a21 x1 + a22 x2 + - - + a2n xn = b2
………………………………………………………
am1 x1 + am2 x2 + - - + amn xn = bn
Where m [pic]n
To solve this system of equations, you must first assign any of n – m variables with value zero. The variables assigned the value zero are called non-basic variables, while the remaining variables are called basic variables. Then, solve the equation to obtain the values of the basic variables. If one or more values of the basic variables are valued at zero, then solution is said to degenerate, whereas if all basic variable have non-zero values, then the solution is called a non-degenerate solution. A basic solution satisfying all constraints is said to be feasible.
[pic]
3.3.2 To solve problem by simplex method
To solve a problem by the simplex method, follow the steps below.
1. Introduce stack variables (Si’s) for “[pic]” type of constraint.
2. Introduce surplus variables (Si’s) and artificial variables (Ai) for “[pic]” type of constraint.
3. Introduce only Artificial variable for “=” type of constraint.
4. Cost (Cj) of slack and surplus variables will be zero and that of artificial variable will be “M”
5. Find Zj - Cj for each variable.
6. Slack and artificial variables will form basic variable for the first simplex table. Surplus variable will never become basic variable for the first simplex table.
7. Zj = sum of [cost of variable x its coefficients in the constraints – Profit or cost coefficient of the variable].
8. Select the most negative value of Zj - Cj. That column is called key column. The variable corresponding to the column will become basic variable for the next table.
9. Divide the quantities by the corresponding values of the key column to get ratios; select the minimum ratio. This becomes the key row. The basic variable corresponding to this row will be replaced by the variable found in step 6.
10. The element that lies both on key column and key row is called Pivotal element.
11. Ratios with negative and [pic]value are not considered for determining key row.
12. Once an artificial variable is removed as basic variable, its column will be deleted from next iteration.
13. For maximisation problems, decision variables coefficient will be same as in the objective function. For minimisation problems, decision variables coefficients will have opposite signs as compared to objective function.
14. Values of artificial variables will always is – M for both maximisation and minimisation problems.
15. The process is continued till all Zj - Cj [pic]0.
Self Assessment Questions
State True or False
3. A basic solution is said to be a feasible solution if it satisfies all constraints.
4. If one or more values of basic variable are zero then solution is said to be degenerate.
5. The right hand side element of each constraint is non-negative.
3.4 The Simplex Algorithm
To test for optimality of the current basic feasible solution of the LPP, use the following algorithm called simplex algorithm. Let’s also assume that there are no artificial variables existing in the program.
3.4.1 Steps
Perform the following steps to solve the simplex algorithm.
[pic]
Figure 3.1: Steps to solve simple algorithm
1) Locate the negative number in the last row of the simplex table. Do not include the last column. The column that has negative number is called the work column.
2) Next, form ratios by dividing each positive number in the work column, excluding the last row into the element in the same row and last column. Assign that element to the work column to yield the smallest ratio as the pivot element. If more than one element yields the same smallest ratio, choose the elements randomly. The program has no solution, if none of the element in the work column is non-negative.
3) To convert the pivot element to unity (1) and then reduce all other elements in the work column to zero, use elementary row operations.
4) Replace the x -variable in the pivot row and first column by x-variable in the first row pivot column. The variable to be replaced is called the outgoing variable and the variable that replaces it is called the incoming variable. This new first column is the current set of basic variables.
5) Repeat steps 1 through 4 until all the negative numbers in the last row excluding the last column are exhausted.
6) You can obtain the optimal solution by assigning the value to each variable in the first column corresponding to the row and last column. All other variables are considered as non-basic and have assigned value zero. The associated optimal value of the objective function is the number in the last row and last column for a maximisation program, but the negative of this number for a minimisation problem.
|Caselet |
|A manufacturing company discontinued production of an unprofitable product line. This created excess |
|production capacity. The company’s management is considering devoting this excess capacity to one or more |
|of the other ongoing products. |
|Knowing the capacity of the machines, the number of machine hours required to produce one unit of each |
|product and the unit profit per product, the management needs to find out how much of each product the |
|company should produce to maximise profit. |
|The management can use the simplex method to arrive at the required solution. |
[pic]
[pic]
[pic]
[pic]
Self Assessment Questions
State Yes or No
6. The key column is determined by Zj - Cj row.
7. Pivotal element lies on the crossing of key column and key row.
8. The negative and infinite ratios are considered for determining key row.
3.5 Penalty Cost Method or Big-M Method
Consider a LPP when at least one of the constraints is of type ³ or =. While expressing in the standard form, add a non negative variable to each of such constraints. These variables are called artificial variables.
Addition of artificial variables causes violation of the corresponding constraints as they are added to only one side of an equation. The new system is equivalent to the old system of constraints only if the artificial variables are valued at zero. To guarantee such assignments in the optimal solution, you can incorporate artificial variables into the objective function with large positive or large negative coefficients in a minimisation and maximisation programs respectively. You denote these coefficients by [pic]M. Whenever artificial variables are part of the initial solution X0, the last row of simplex table will contain the penalty cost M. You can make the following modifications in the simplex method to minimise the error of incorporating the penalty cost in the objective function. This method is called Big M-method or Penalty cost method.
[pic]
Figure 3.2: Big M-method
1) The last row of the simplex table is decomposed into two rows, the first of which involves those terms not containing M, while the second involves those containing M.
2) The step 1 of the simplex method is applied to the last row created in the above modification and followed by steps 2, 3 and 4 until this row contains no negative elements. Then step 1 of simplex algorithm is applied to those elements next to the last row that are positioned over zero in the last row.
3) Whenever an artificial variable ceases to be basic, it is removed from the first column of the table as a result of step 4; it is also deleted from the top row of the table as is the entire column under it.
4) The last row is removed from the table whenever it contains all zeroes.
5) If non-zero artificial variables are present in the final basic set, then the program has no solution. In contrast, zero valued artificial variables in the final solution may exist when one or more of the original constraint equations are redundant.
[pic]
[pic]
Self Assessment Questions
State Yes or No
9. The value of artificial value is “M”.
10. Artificial variables enter as basic variables.
3.6 Two Phase Method
The drawback of the penalty cost method is the possible computational error resulting from assigning a very large value to the constant M. To overcome this difficulty, a new method is considered, where the use of M is eliminated by solving the problem in two phases.
Phase I: Formulate the new problem. Start by eliminating the original objective function by the sum of the artificial variables for a minimisation problem and the negative of the sum of the artificial variables for a maximisation problem. The Simplex method optimises the ensuing objective with the constraints of the original problem. If a feasible solution is arrived, the optimal value of the new objective function is zero (suggestive of all artificial variables being zero). Subsequently proceed to phase II. If the optimal value of the new objective function is non-zero, it means there is no solution to the problem and the method terminates.
Phase II: Start phase II using the optimum solution of phase I as the base. Then take the objective function without the artificial variables and solve the problem using the Simplex method.
[pic]
[pic]
[pic]
|The first iteration gives the following table: |
|Table 3.20: The first iteration table |
| |
|x1 |
|x2 |
|S1 |
|S2 |
|A1 |
| |
| |
| |
|0 |
|0 |
|0 |
|0 |
|–1 |
| |
| |
|X2 0 |
|2 |
|1 |
|1 |
|0 |
|0 |
|2 |
| |
|A1 – 1 |
|– 5 |
|0 |
|– 4 |
|– 1 |
|1 |
|4 |
| |
| |
|5 |
|0 |
|4 |
|1 |
|0 |
|– 4 |
| |
|Since all elements of the last row are non negative, the procedure is complete. But the existence of |
|non-zero artificial variables in the basic set indicates that the problem has no solution. |
3.7 Solved Problems on Minimisation
[pic]
[pic]
3.8 Summary
This unit explains how to solve LPP using the simplex method. The unit also explains the constraints for which you need to introduce the slack, surplus and artificial variables. Examples are used to illustrate the method of solving LPP using the simplex method.
3.9 Terminal Questions
1. Maximise z = 3x1 – x2
Subject to the constraints
2x1 + x2 [pic]2
x1 + 3x2 [pic]3
x2 [pic]4,
x1, x2 [pic]0.
2. Minimise Z = 6x1 + 7x2
Subject to the constraints
x1 + 3x2 [pic]12
3x1 + x2 [pic]12
x1 + x2 [pic]8
x1 + x2 [pic]0
3.10 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. False
2. True
3. True
4. True
5. Yes
6. Yes
7. No
8. Yes
9. Yes
10. Yes
Answers to Terminal Questions
1. Z = 9 X1 = 3 X2 = 0
2. Z = 5.8 X1 = 8/3 X2 = 6
3.11 References
No external sources of content have been referred for unit 3
About the Author
[pic]
admin
Copyright © 2010 SMU.
Powered by WordPress.
MB0048-Unit-03-Simplex Method
Unit-03-Simplex Method
Structure:
3.1 Introduction
Learning objectives
3.2 Standard Form of LPP
The standard form of LPP
Fundamental theorem of LPP
3.3 Solution of LPP – Simplex Method
Initial basic feasible solution of a LPP
To solve problem by Simplex Method
3.4 The Simplex Algorithm
Steps
3.5 Penalty Cost Method or Big M-method
3.6 Two Phase Method
3.7 Solved Problems on Minimisation
3.8 Summary
3.9 Terminal Questions
3.10 Answers to SAQs & TQs
Answers to Self Assessment Questions
Answers to Terminal Questions
3.11 References
3.1 Introduction
Welcome to the third unit of Operations Research Management on the simplex method. The simplex method focuses on solving LPP of any enormity involving two or more decision variables.
The simplex algorithm is an iterative procedure for finding the optimal solution to a linear programming problem. The objective function controls the development and evaluation of each feasible solution to the problem. If a feasible solution exists, it is located at a corner point of the feasible region determined by the constraints of the system.
The simplex method simply selects the optimal solution amongst the set of feasible solutions of the problem. The efficiency of this algorithm is because it considers only those feasible solutions which are provided by the corner points, and that too not all of them. You can consider obtaining an optimal solution based on a minimum number of feasible solutions.
Learning objectives
By the end of this unit, you should be able to:
· Create a standard form of LPP from the given hypothesis
· Apply the simplex algorithm to the system of equations
· Interpret the big M-technique
· Discuss the importance of the two phase method
· Construct the dual from the primal (and vice versa)
3.2 Standard Form of LPP
The characteristics of the standard form of LPP are:
1. All constraints are equations except for the non-negativity condition, which remain inequalities [pic]only.
2. The right-hand side element of each constraint equation is non-negative.
3. All the variables are non-negative.
4. The objective function is of maximisation or minimisation type.
You can change the inequality constraints of equations by adding or subtracting the left hand side of each such constraint by a non-negative variable. The non-negative variable that has to be added to a constraint inequality of the form £ to change it to an equation is called a slack variable. The non-negative variable subtracted from a constraint inequality of the form ³ to change it to an equation is called a surplus variable.
To make the right hand side of a constraint equation positive, multiply both the sides of the resulting equation by (-1). Use the elementary transformations introduced with the canonical form to achieve the remaining characteristics.
3.2.1 The standard form of the LPP
[pic]
3.2.2 Fundamental theorem of LPP
A set of m simultaneous linear equations in n unknowns/variables, n [pic]m, AX = b, with r (A) = m.
If there is a feasible solution X [pic]0, then there exists a basic feasible solution.
Self Assessment Questions
State True or False
1. We add surplus variable for [pic]of constraint.
2. The right hand side element of each constraint is non-negative.
3.3 Solution of the Linear Programming Program – Simplex Method
Consider a LPP given in the standard form
To optimise z = c1 x1 + c2 x2 + —+ cn xn
Subject to
a11 x1 + a12 x2 + — + an x n ± S1 = b1
a21 x1 + a22 x2 + —-+ a2n xn ± S2 = b2
………………………………………………………………….
am1 x1 + am2 x2 + — + amn xn ± Sm = bm
x1, x2, — xn, S1, S2 —, Sm [pic]0.
To each of the constraint equations, add a new variable called an artificial variable on the left hand side of every equation which does not contain a slack variable. Subsequently every constraint equation will contain either a slack variable or an artificial variable.
The introduction of slack and surplus variables does not alter either the constraints or the objective function. Therefore, you can incorporate such variables in the objective function with zero coefficients. However, the artificial variables do change the constraints as these are added only to the left hand side of the equations.
The newly derived constraint equation is equivalent to the original equation, only if all the artificial variables have value zero. Artificial variables are incorporated into the objective function with very large positive coefficient M in the minimisation program and very large negative coefficient–M in the maximisation program guaranteeing optimal solutions. The large positive and negative coefficients represent the penalty incurred for making a unit assignment to the artificial variable.
Thus the standard form of LPP can be given as follows:
Optimise Z = CT X
Subject to AX = B,
And X [pic]0
Where X is a column vector with decision, slack, surplus and artificial variables, C is the vector corresponding to the costs; A is the coefficient matrix of the constraint equations and B is the column vector of the right hand side of the constraint equations.
[pic]
3.3.1 Initial basic feasible solution of a LPP
Consider a system of m equations in n unknowns x1, x2 - - an,
a11 x1 + a12 x2 + - - + a1n xn = b1
a21 x1 + a22 x2 + - - + a2n xn = b2
………………………………………………………
am1 x1 + am2 x2 + - - + amn xn = bn
Where m [pic]n
To solve this system of equations, you must first assign any of n – m variables with value zero. The variables assigned the value zero are called non-basic variables, while the remaining variables are called basic variables. Then, solve the equation to obtain the values of the basic variables. If one or more values of the basic variables are valued at zero, then solution is said to degenerate, whereas if all basic variable have non-zero values, then the solution is called a non-degenerate solution. A basic solution satisfying all constraints is said to be feasible.
[pic]
3.3.2 To solve problem by simplex method
To solve a problem by the simplex method, follow the steps below.
1. Introduce stack variables (Si’s) for “[pic]” type of constraint.
2. Introduce surplus variables (Si’s) and artificial variables (Ai) for “[pic]” type of constraint.
3. Introduce only Artificial variable for “=” type of constraint.
4. Cost (Cj) of slack and surplus variables will be zero and that of artificial variable will be “M”
5. Find Zj - Cj for each variable.
6. Slack and artificial variables will form basic variable for the first simplex table. Surplus variable will never become basic variable for the first simplex table.
7. Zj = sum of [cost of variable x its coefficients in the constraints – Profit or cost coefficient of the variable].
8. Select the most negative value of Zj - Cj. That column is called key column. The variable corresponding to the column will become basic variable for the next table.
9. Divide the quantities by the corresponding values of the key column to get ratios; select the minimum ratio. This becomes the key row. The basic variable corresponding to this row will be replaced by the variable found in step 6.
10. The element that lies both on key column and key row is called Pivotal element.
11. Ratios with negative and [pic]value are not considered for determining key row.
12. Once an artificial variable is removed as basic variable, its column will be deleted from next iteration.
13. For maximisation problems, decision variables coefficient will be same as in the objective function. For minimisation problems, decision variables coefficients will have opposite signs as compared to objective function.
14. Values of artificial variables will always is – M for both maximisation and minimisation problems.
15. The process is continued till all Zj - Cj [pic]0.
Self Assessment Questions
State True or False
3. A basic solution is said to be a feasible solution if it satisfies all constraints.
4. If one or more values of basic variable are zero then solution is said to be degenerate.
5. The right hand side element of each constraint is non-negative.
3.4 The Simplex Algorithm
To test for optimality of the current basic feasible solution of the LPP, use the following algorithm called simplex algorithm. Let’s also assume that there are no artificial variables existing in the program.
3.4.1 Steps
Perform the following steps to solve the simplex algorithm.
[pic]
Figure 3.1: Steps to solve simple algorithm
1) Locate the negative number in the last row of the simplex table. Do not include the last column. The column that has negative number is called the work column.
2) Next, form ratios by dividing each positive number in the work column, excluding the last row into the element in the same row and last column. Assign that element to the work column to yield the smallest ratio as the pivot element. If more than one element yields the same smallest ratio, choose the elements randomly. The program has no solution, if none of the element in the work column is non-negative.
3) To convert the pivot element to unity (1) and then reduce all other elements in the work column to zero, use elementary row operations.
4) Replace the x -variable in the pivot row and first column by x-variable in the first row pivot column. The variable to be replaced is called the outgoing variable and the variable that replaces it is called the incoming variable. This new first column is the current set of basic variables.
5) Repeat steps 1 through 4 until all the negative numbers in the last row excluding the last column are exhausted.
6) You can obtain the optimal solution by assigning the value to each variable in the first column corresponding to the row and last column. All other variables are considered as non-basic and have assigned value zero. The associated optimal value of the objective function is the number in the last row and last column for a maximisation program, but the negative of this number for a minimisation problem.
|Caselet |
|A manufacturing company discontinued production of an unprofitable product line. This created excess |
|production capacity. The company’s management is considering devoting this excess capacity to one or more |
|of the other ongoing products. |
|Knowing the capacity of the machines, the number of machine hours required to produce one unit of each |
|product and the unit profit per product, the management needs to find out how much of each product the |
|company should produce to maximise profit. |
|The management can use the simplex method to arrive at the required solution. |
[pic]
[pic]
[pic]
[pic]
Self Assessment Questions
State Yes or No
6. The key column is determined by Zj - Cj row.
7. Pivotal element lies on the crossing of key column and key row.
8. The negative and infinite ratios are considered for determining key row.
3.5 Penalty Cost Method or Big-M Method
Consider a LPP when at least one of the constraints is of type ³ or =. While expressing in the standard form, add a non negative variable to each of such constraints. These variables are called artificial variables.
Addition of artificial variables causes violation of the corresponding constraints as they are added to only one side of an equation. The new system is equivalent to the old system of constraints only if the artificial variables are valued at zero. To guarantee such assignments in the optimal solution, you can incorporate artificial variables into the objective function with large positive or large negative coefficients in a minimisation and maximisation programs respectively. You denote these coefficients by [pic]M. Whenever artificial variables are part of the initial solution X0, the last row of simplex table will contain the penalty cost M. You can make the following modifications in the simplex method to minimise the error of incorporating the penalty cost in the objective function. This method is called Big M-method or Penalty cost method.
[pic]
Figure 3.2: Big M-method
1) The last row of the simplex table is decomposed into two rows, the first of which involves those terms not containing M, while the second involves those containing M.
2) The step 1 of the simplex method is applied to the last row created in the above modification and followed by steps 2, 3 and 4 until this row contains no negative elements. Then step 1 of simplex algorithm is applied to those elements next to the last row that are positioned over zero in the last row.
3) Whenever an artificial variable ceases to be basic, it is removed from the first column of the table as a result of step 4; it is also deleted from the top row of the table as is the entire column under it.
4) The last row is removed from the table whenever it contains all zeroes.
5) If non-zero artificial variables are present in the final basic set, then the program has no solution. In contrast, zero valued artificial variables in the final solution may exist when one or more of the original constraint equations are redundant.
[pic]
[pic]
Self Assessment Questions
State Yes or No
9. The value of artificial value is “M”.
10. Artificial variables enter as basic variables.
3.6 Two Phase Method
The drawback of the penalty cost method is the possible computational error resulting from assigning a very large value to the constant M. To overcome this difficulty, a new method is considered, where the use of M is eliminated by solving the problem in two phases.
Phase I: Formulate the new problem. Start by eliminating the original objective function by the sum of the artificial variables for a minimisation problem and the negative of the sum of the artificial variables for a maximisation problem. The Simplex method optimises the ensuing objective with the constraints of the original problem. If a feasible solution is arrived, the optimal value of the new objective function is zero (suggestive of all artificial variables being zero). Subsequently proceed to phase II. If the optimal value of the new objective function is non-zero, it means there is no solution to the problem and the method terminates.
Phase II: Start phase II using the optimum solution of phase I as the base. Then take the objective function without the artificial variables and solve the problem using the Simplex method.
[pic]
[pic]
[pic]
|The first iteration gives the following table: |
|Table 3.20: The first iteration table |
| |
|x1 |
|x2 |
|S1 |
|S2 |
|A1 |
| |
| |
| |
|0 |
|0 |
|0 |
|0 |
|–1 |
| |
| |
|X2 0 |
|2 |
|1 |
|1 |
|0 |
|0 |
|2 |
| |
|A1 – 1 |
|– 5 |
|0 |
|– 4 |
|– 1 |
|1 |
|4 |
| |
| |
|5 |
|0 |
|4 |
|1 |
|0 |
|– 4 |
| |
|Since all elements of the last row are non negative, the procedure is complete. But the existence of |
|non-zero artificial variables in the basic set indicates that the problem has no solution. |
3.7 Solved Problems on Minimisation
[pic]
[pic]
3.8 Summary
This unit explains how to solve LPP using the simplex method. The unit also explains the constraints for which you need to introduce the slack, surplus and artificial variables. Examples are used to illustrate the method of solving LPP using the simplex method.
3.9 Terminal Questions
1. Maximise z = 3x1 – x2
Subject to the constraints
2x1 + x2 [pic]2
x1 + 3x2 [pic]3
x2 [pic]4,
x1, x2 [pic]0.
2. Minimise Z = 6x1 + 7x2
Subject to the constraints
x1 + 3x2 [pic]12
3x1 + x2 [pic]12
x1 + x2 [pic]8
x1 + x2 [pic]0
3.10 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. False
2. True
3. True
4. True
5. Yes
6. Yes
7. No
8. Yes
9. Yes
10. Yes
Answers to Terminal Questions
1. Z = 9 X1 = 3 X2 = 0
2. Z = 5.8 X1 = 8/3 X2 = 6
3.11 References
No external sources of content have been referred for unit 3
About the Author
[pic]
admin
Copyright © 2010 SMU.
Powered by WordPress.
MB0048-Unit-04-Duality in LPP
Unit-04-Duality in LPP
Structure:
4.1 Introduction
Learning Objectives
4.2 Importance of Duality Concepts
4.3 Formulation of Dual Concepts
4.4 Economic Interpretation of Duality
Economic interpretation of dual variables
4.5 Sensitivity Analysis
Changes in Cj of non-basic variable
Change in Cj of a basic variable
Change in available resources
Calculating the range
4.6 Summary
4.7 Terminal Questions
4.8 Answers to SAQs and TQs
Answers to self assessment questions
Answers to terminal questions
4.9 References
4.1 Introduction
Every linear programming problem (LPP) is associated with another linear programming problem involving the same data and optimal solutions. Such two problems are said to be duals of each other. One problem is called the primal, while the other problem is called the dual.
The dual formulation is derived from the same data and solved in a manner similar to the original ‘primal’ formulation. In other words, you can say that dual is the ‘inverse’ of the primal formulation because of the following reasons.
· If the primal objective function is ‘maximisation’ function, then the dual objective function is ‘minimisation’ function and vice-versa.
· The column co-efficient in the primal constraint is the row co-efficient in the dual constraint.
· The co-efficients in the primal objective function are the RHS constraint in the dual constraint.
· The RHS column of constants of the primal constraints becomes the row of co-efficient of the dual objective function.
The concept of duality is useful to obtain additional information about the variation in the optimal solution. These changes could be effected in the constraint co-efficient, in resource availabilities and/or objective function co-efficient. This effect is termed as post optimality or sensitivity analysis.
Learning objectives
By the end of this unit, you should be able to:
· Describe the duality concept
· Solve a dual problem
· Describe the economical interpretation
· Apply sensitivity analysis
4.2 Importance of Duality Concepts
The importance of duality concept is due to two main reasons:
i. If the primal contains a large number of constraints and a smaller number of variables, the labour of computation can be considerably reduced by converting it into the dual problem and then solving it.
ii. The interpretation of the dual variable from the loss or economic point of view proves extremely useful in programming future decisions in the activities.
Characteristics of dual solutions
If the primal problem possesses a unique non-degenerate, optimal solution, then the optimal solution to the dual is unique. However, dual solutions arise under a number of other conditions. Several of the cases which can arise are:
· When the primal problem has a degenerate optimal solution, the dual has multiple optimal solutions.
· When the primal problem has multiple optimal solutions, the optimal dual solution is degenerate.
· When the primal problem is unbounded, the dual is infeasible.
· When the primal problem is infeasible, the dual is unbounded or infeasible.
Self Assessment Questions
State Yes or No
1. Dual LPP always reduces the amount of computation.
2. It is possible to reverse the dual LPP to primal LPP
4.3 Formulation of Dual Concepts
Consider the following LPP
Maximise Z = c1x1 +c2x2 + . . .+ cnxn
Subject to the constraints
a11 x1 + a12 x2 + . . . + a1n xn ≤ b1
a21 x1 + a22 x2 + . . . + a2n xn ≤ b2
am1 x1 + am2 x2 + . . . + amn xn ≤ bm
x1, x2, . . ., xn ≥ 0
To construct a dual problem, you must adopt the following guidelines:
i. The maximisation problem in the primal becomes a minimisation problem in the dual and vice versa
ii. (≤) type of constraints in the primal become (≥) type of constraints in the dual and vice versa.
iii. The coefficients c1, c2, . . .,cn in the objective function of the primal become b1, b2,…,bm in the objective function of the dual.
iv. The constants b1, b2,…,bm in the constraints of the primal become c1, c2, . . .,cn in the constraints of the dual
v. If the primal has n variables and m constraints the dual will have m variables and n constraints
vi. The variables in both the primal and dual are non-negative
Thus the dual problem will be
Minimise W = b1 y1 + b2 y2 + . . . +bm ym
Subject to the constraints
a11 y1 + a21 y2 + . . . + am1 ym ≥ c1
a12 y1 + a22 y2 + . . . + am2 ym ≥ c2
a1n y1 + a2n y2 + . . . + amn ym ≥ cn
y1, y2, . . ., ym ≥ 0
Formation of dual LPP is easier when the standard form of LPP for maximisation problem must contain “≤” type of constraints, while for minimisation problem, it must contain “≥” type of constraints.
|Solved Problem 1 |
|Write dual of |
|Max Z = 4x1 + 5x2 |
|Subject to 3x1 + x2 ≤ 15 |
|x1 +2 x2 ≤ 10 |
|5x1 + 2x2 ≤ 20 |
|x1, x2, ≥ 0 |
|Solution: The given problem is in its standard form. Therefore, its dual is |
|Mini W = 15y1 + 10 y2 + 20 y3 |
|Subject to 3y1 + y2 + 5 y3 ≥ 4 |
|y1 + 2y2 + 2y3 ≥ 5 |
|y1, y2, y3, ≥ 0 |
|Solved Problem 2 |
|Write the dual of |
|Min Z = 10x1 + 12x2 |
|Subject to 2x1 +3 x2 ≥ 10 |
|5x1 +6 x2 ≥ 20 |
|x1 + 2x2 ≥ 15 |
|2x1 + 3x2 ≥ 12 |
|x1, x2, ≥ 0 |
|Solution: The given problem is in its standard form. Therefore, its dual problem is |
|Max W = 10y1 + 20 y2 + 15 y3 + 12y4 |
|Subject to 2y1 + 5y2 + y3 = 2y4 ≤ 12 |
|6y1 + 2y2 + 3 y3 ≤ 10 |
|y1, y2, y3, ≥ 0 |
|Solved Problem 3 |
|Write the dual of |
|Max Z = 100x1 + 200x2 |
|Subject to 3x1 – 10 x2 ≥ 15 |
|+4x1 +15 x2 ≤ 20 |
|x1, x2, ≥ 0 |
|Solution: First we convert |
|3x1 – 10x2 ≥ 15 |
|to “≤” type as shown here. |
|-3x1 + 10x2 ≤ -15 |
|Therefore, its dual is |
|Mini Z = -15y1 + 20 y2 |
|Subject to -3y1 + 4y2 ≥ 100 |
|10y1 + 15y2 ≥ 200 |
|y1, y2, ≥ 0 |
|Solved Problem 4 |
|When the constraints contain “=” sign, write the dual of |
|Max Z = 40x1 + 30x2 |
|Subject to 10x1 +6 x2 ≤ 15 |
|5x1 +6 x2 ≥ -10 |
|x1 + x2 = 9 |
|x1 + x2 ≥ 10 |
|x1, x2, ≥ 0 |
|Solution: Firstly, |
|5x1 – 7x2 ≥ -10 |
|is rewritten as |
|-5x1 +7x2 ≤ 10 |
|Secondly, |
|x1 + x2 = 9 |
|is written as |
|x1 + x2 ≤ 9 |
|Also |
|x1 + x2 ≥ 9 this is same as -x1 – x2 ≤ -9 |
|Therefore, the given problem is |
|Max Z = 40x1 + 30x2 |
|Subject to 10x1 + 6 x2 ≤ 15 |
|- 5x1 +7 x2 ≤ 10 |
|x1 +x2 ≤ 9 |
|- x1 – x2 ≥ – 9 |
|Therefore, its dual is |
|Mini W = -15y1 + 10 y2 + 9y31 – 9y311 |
|Subject to 10y1 – 5y2 + y31 – y311 ≥ 40 |
|6y1 + 7y2 + y31 – y311 ≥ 30 |
|y1, y2, y31 – y311 ≥ 0 |
|Let y31 – y311= y3 |
|Then the dual becomes |
|Max W = 15y1 -5 y2 + y3 |
|Subject to 10y1 – 5y2 + y3 ≥ 40 |
|6y1 + 7y2 + y3 ≥ 30 |
|y1, y2, ≥ 0 |
|y3 is unrestricted in sign |
|Solved Problem 5 |
|Write the dual of |
|Max Z = 12x1 + 15x2 |
|Subject to 5x1 +36 x2 ≥ 10 |
|x1 + x2 ≤ 5 |
|x1 ≥ 0 |
|x2 is unrestricted in sign |
|Solution: Let x2 =x21 – x211 ≥ 0. Therefore, its standard form is |
|Max Z = 12x1 + 15x21 -15x211 |
|Subject to 5x1 +3(x21- x211) ≥ 10 |
|- [x1 +(x21- x211)] ≥ -5 |
|Or x1 – x21+ x211 ≥ -5 |
|x1, x21, x211 ≥ 0 |
|Therefore, dual is |
|5y1 – y2 ≤ 12 ………….…(1) |
|3y1 – y2 ≤ 15 ………….…(2) |
|-3y1 + y2 ≤ – 15 ……………(3) |
|No.3 constraint is 3y1 – y2 ≥ 15 …………(4) |
|Constraints 2 and 4 give |
|3y1 – y2 = 15 |
|The dual problem is |
|Max W = 10y1 –15 y2 |
|Subject to 5y1 – y2 ≤ 12 |
|3y1 – y2 =15 |
|y1 ≥ 0 y2 unrestricted in sign |
|Solved Problem 6 |
|Write the dual of the following LPP |
|Minimise Z = 3x1 – 2x2 + 4x3 |
|Subject to 3x1 + 5x2 + 4x3 ≥ 7 |
|6x1 + x2 + 3x3 ≥ 4 |
|7x1 – 2x2 – x3 ≤ 10 |
|x1 – 2x2 + 5x3 ≥ 3 |
|4x1 + 7x2 – 2x3 ≥ 2, |
|x1, x2, x3 ≥ 0 |
|Solution: Since the problem is of minimisation, all constraints should be of ≥ type. Therefore, you have to |
|multiply the third constraint throughout by -1 so that -7x1 + 2x2 + x3 ≥ -10 |
|Let y1, y2, y3, y4 and y5 be the dual variables associated with the above five constraints. Then the dual |
|problem is given by |
|Maximise W = 7y1 + 4 y2 – 10 y3 + 3 y4 + 2y5 |
|Subject to 3y1 + 6y2 – 7 y3 + y4 + 4y5 ≤ 3 |
|5y1 + y2 + 2y3 – 2y4 + 7y5 ≤ -2 |
|4y1 + 3y2 + y3 + 5y4 – 2y5 ≤ 4 |
|y1, y2, y3, y4, y5 ≥ 0 |
|Solved Problem 7 |
|Find the dual of |
|Maximise 12x1 + 10x2 |
|Subject to 2x1 + 3x2 ≤ 18 |
|2x1 + x2 ≤ 14 |
|x1, x2 ≥ 0 |
|Solution: The ‘dual’ formulation for this problem will be |
|Minimise 18y1 + 14y2 |
|Subject to 2y1 + 2y2 ≥ 12 |
|3y1 + y2 ≥ 10 |
|y1 >= 0, y2 ≥ 0 |
|Points to be noted: |
|· The column coefficients in the primal constraint namely (2, 2) and (3, 1) have become the row co-efficient |
|in the dual constraints. |
|· The coefficient of the primal objective function namely, 12 and 10 have become the constants in the right |
|hand side of the dual constraints. |
|· The constants of the primal constraints, namely 18 and 14, have become the coefficient in the dual objective|
|function. |
|· The direction of the inequalities has been reserved. |
|· While the primal is a ‘maximisation’ problem the dual is a ‘minimisation’ problem |
|Solved Problem 8 |
|Obtain the dual problem of the following primal formulation. |
|Maximise Z = 2x1 + 5x2 + 6x3 |
|Subject to 5x1 + 6x2 -x3 ≤ 3 |
|-2x1 + x2 + 4x ≤ 4 |
|x1 – 5x2 + 3x3 ≤ 1 |
|-3x1 – 3x2 + 7x3≤ 6 |
|x1, x2, x3≥ 0 |
|Solution: Step 1: Write the objective function of the dual. As there are four constraints in the primal, the |
|objective function of the dual will have 4 variables. |
|Minimise r* = 3 w 1 + 4 w 2 + w 3 + 6 w 4 |
|Step 2: Write the constraints of the dual. As all the constraints in the primal are ‘’. The column COM+ efficient of the primal becomes the row co-efficient of the dual. |
|Constraints 5w1 – 2w2 + w3 – 3w4 ≥ 2 |
|6w1 + w2 – 5w3 -w4 ≥ 5 |
|-w1 + 4w2 + 3w3 + 7w4≥ 6 |
|Step 3 : Therefore the dual of the primal is : |
|Minimise Z = 3w1 + 4w2 + w3 + 6w4 |
|Subject to: 5w1 – 2w2 + w3 – 3w4 ≥ 2 |
|6w1+ w2 – 5w3 – 3w4 ≥ 5 |
|- w1 + 4w2 + 3w3 + 7w4≥ 6 |
|w1, w2, w3, w4 >= 0 |
|Solved Problem 9 |
|Obtain the dual of the following linear programming problem. |
|Minimise Z = 5x1 -6x2 + 4x3 |
|Subject to the constraints: 3x1 + 4x2 + 6x3 ≥ 9 |
|x1 + 3x2 + 2x3 ≥ 5 |
|7x1 – 2x2 – x3 ≤ 10 |
|x1 – 2x2 + 4x3 ≥ 4 |
|2x1 + 5x2 – 3x3≥ 3 |
|x1, x2, x3 ≥ 0 |
|Solution: As you can see, one of the primal constraints is a "≤ " constraint while the others are all "≥” |
|constraints. The dual cannot be worked out unless all the constraints are in the same direction. To convert |
|this into "≥” constraint, multiply both the sides of the equation by "-" sign. After multiplying the |
|constraint by "-" sign, it will become 7x1 + 2x2 + x3 ≥ -10. Now that all the constraints are in the same |
|direction and the dual can be worked out, the dual formulation is: |
|Maximise Z = 9w1 + 5w2 – 10w3 + 4w4 + 3w5 |
|Subject to: 3w1 + w2 – 7w3 + w4 + 2w5 ≤ 5 |
|4w1 + 3w2 + 2w3 – 2w4 + 5w5 ≤ -6 |
|6w1 + 2w2 + w3 + 4w4 + -3w5 ≤ 4 |
|w1, w2, w3, w4, w5 ≥ 0 |
Self Assessment Questions
Fill in the blanks
3. The coefficients of decision variables in the objective function become quantities on the right hand side of _________ __________.
4. “£” constraints changes to ________ type in dual LP.
5. For every LPP, there exists a unique ________ problem.
4.4 Economic Interpretation of Duality
The linear programming problem is thought of as a resource allocation model where the objective is to maximise revenue or profit subject to limited resources. The associated dual problem offers interesting economic interpretations of the LP resource allocation model. Consider a representation of the general primal and dual problems where primal takes the role of a resource allocation model.
[pic]
In the above resource allocation model, the primal problem has ‘n’ economic activities and ‘m’ resources. The coefficient cj in the primal represents the profit per unit of activity j. Resource i, whose maximum availability is bi, is consumed at the rate aij units per unit of activity j.
4.4.1 Economic interpretation of dual variables:
For any pair of feasible primal and dual solutions,
(Objective value in the maximisation problem) ≤ (Objective value in the minimisation problem).
At the optimum, the relationship holds as a strict equation.
Note: Here, the sense of optimisation is very important.
Hence, for any two primal and dual feasible solutions, the values of the objective functions, when finite, must satisfy the following inequality.
[pic]
The strict equality, z = w, holds true when both the primal and dual solutions are optimal. Consider the optimal condition z = w. Given that the primal problem represents a resource allocation model, you can think of z as representing the profit in rupees. bi represents the number of units available of the resource i. Therefore, we can express the equation z = w as profit (Rs) = å (units of resource i) x (profit per unit of resource i)
This means that the dual variables yi, represent the worth per unit of resource i.
Note: Variables yi are also called as dual prices, shadow prices and simplex multipliers.
With the same logic, the inequality z < w associated with any two feasible primal and dual solutions is interpreted as (profit) < (worth of resources).
This relationship implies that as long as the total return from all the activities is less than the worth of the resources, the corresponding primal and dual solutions are not optimal. Optimality is achieved only when the resources have been exploited to their fullest extent, which can happen only when the input equals the output (profit). Economically, the system is said to be unstable (non optimal) when the input (worth of the resources) exceeds the output (return). Stability occurs only when the two quantities are equal.
Self Assessment Questions
True or False
6. Dual variables represent the worth or unit of a resource.
7. Optimality is reached when the resources are not fully utilised.
8. At optimum level the relationship holds as a strict equation
4.5 Sensitivity Analysis
In linear programming, all model parameters are assumed to be constant. However; in real-life situations, the decision environment is always dynamic. Therefore, it is important for the management to know how profit would be affected by an increase or decrease in the resource level, by change in the technological process, and by change in the cost of raw materials. Such an investigation is known as sensitivity analysis or post optimality analysis.
The results of sensitivity analysis establishes upper and lower bounds for input parameter values within which they can vary without causing major changes in the current optimal solution.
Sensitivity analysis allows you to figure out which data offers a significant impact on the results. This in turn allows you to concentrate on getting accurate data for those items or at least running through several scenarios with various values of the crucial data to get an idea of the range of possible outcomes.
Sensitivity analysis is important because of the following reasons:
· Values of LP parameters might change
· LP parameters have an uncertainty factor attached to them
Any change in an LP’s parameters affects the optimality of the basic variable. This is because of the following two reasons.
· When a variable (or number of variables) in row 0 has a negative coefficient, we can obtain a better basic feasible solution of larger z-value by pivoting a non-basic variable with a negative coefficient in row 0. If this occurs, the basic variable becomes a sub-optimal basis.
· A constraint (or number of constraints) may have a negative RHS. In such a case, at least one member of basic variable will now be negative and will no longer yield a basic feasible solution. If this occurs, you can say that the basic variable is now an infeasible basis.
The following six types of changes in LP’s parameters cause changes in the optimal solution:
· Changing the objective function coefficient of a non-basic variable
· Changing the objective function coefficient of a basic variable
· Changing the right-hand side of a constraint
· Changing the column of a non-basic variable
· Adding a new variable or activity
· Adding a new constraint
|Caselet |
|Luminous lamps produce three types of lamps A, B and C. These lamps are processed on three machines X, Y and |
|Z. |
|To find out the optimal solution in order to maximise profit and minimise cost, first you find out whether a |
|previously determined optimal solution remains optimal if the contribution rate is changed. An increase in Cj |
|of a variable would mean that resources from other products should be diverted to this more profitable |
|product. |
|The reverse is true for a minimisation problem. |
[pic]
4.5.1 Changes in Cj of a non-basic variable
A non basic variable can be brought on the basis only if its contribution rate is attractive. Therefore, you need to determine the upper limit of the profit contribution (Cj) of each non basic variable. The reverse is true for a minimisation problem. Consider the final simplex table of the above problem.
Table 4.2: The final simplex table
[pic]
From the above final simplex table, you can see that profit contribution for product C is Re 1, which is not greater than its zj. Therefore, to bring x3 into the basis, its profit contribution rate cj must exceed Rs. [pic]to make zj – cj value negative or zero that is zj – cj [pic]0. Specifically,
· If cj* – cj > zj – cj, then a new optimal solution must be derived
· If cj* – cj = zj – cj, then alternative optimal solution exist.
· If cj* – cj < zj – cj, then current optimal solution remains unchanged.
In case of c3 = 1 and z3 – c3 = [pic],
C3* – 1 [pic][pic]
C3* [pic][pic]+1 = [pic]
x3 can be introduced in the basis, if its contribution rate c3 increases at least Rs [pic]. If it increases beyond that, then the current solution will no longer be optimal.
4.5.2 Change in Cj of a basic variable
Consider the case of product A (x1 column) and divide each zj – cj entry in the index row by the corresponding co-efficient in the x1 row as shown below:
- Minimum [pic]
Referring to the final simplex table, you observe that corresponding to the non basic variables x3 and x5, y13, y15 0, therefore,
Minimum [pic]= 5
Hence,
–5 [pic]c1* -12 [pic]3 i.e. 7 [pic]c1* [pic]15
Thus, you can say that the optimal solution is insensitive as long as the changed profit coefficient c1* varies between Rs 7 and Rs. 15
4.5.3 Change in available resources
If the available resources change, you need to investigate whether a previous optimal solution remains feasible or not. For long term planning, it is important to know the bounds within which each available resource (for instance machine hours) can vary without causing violent changes in the current optimal solution. To illustrate this, divide each quantity in the XB column by the corresponding coefficient in the X4 column of the table.
Table 4.3: Resources table
[pic]
The least positive ratio [pic]indicates the number of hours of machine M1 that can be decreased. The least negative ratio (–10) indicates the increase in the number of hours of machine M1.
4.5.4 Calculating the range
Lower limit = 100 – [pic]= [pic]
Upper limit = 100 – (–10) = 110
Therefore, the range of hours for M1 is [pic]to 110.
You can calculate the range of hours for machine M2 and M3 in the same manner. The management of a company rarely restricts its interest to the numerical values of an optimal solution. It is interested in knowing the impact of changes in the input parameter values on the optimal solution. This process is called sensitivity analysis.
Self Assessment Questions
Fill in the blanks
9. Sensitivity analysis is carried out on _______ simplex table.
10. It helps us to study the effect of changes in _______ _______ in objective function.
11. The results of sensitive analysis establish ___________ and ________ ___________ for input parameters value.
4.6 Summary
For every linear programming problem there exists a dual linear programming problem. The dual LPP helps us to reduce the amount of calculation involved in original the LPP. They also help us to interpret the economic variables more effectively.
4.7 Terminal Questions
1. Write the dual of the following linear programming problems.
a) Maximise 2 = 7x1 + 5x2
Subject to constraints x1 + 2x2 £ 6
4x1 + 3x2 £ 12
x1 x2 ³ 0
b) Maximise z = 3x1 + 4x2
Subject to constrains 5x1 + 4x2 £ 200;
3x1 + 5x2 £ 150;
5x1 + 4x2 ³ 100;
8x1 + 4x2 ³ 80,
x1 ³ 0, x2 ³ 0
c) Maximise z = 2x1 + x2
Subject to constraints 4x1 + 3x2 £ 12,
4x1 + x2 £ 8,
4x1 – x2 £ 8,
x1, x2 ³ 0
4.8 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. No
2. Yes
3. Dual
4. ≥
5. Dual
6. True
7. False
8. True
9. Final
10. Resource, levels
11. Upper, lower, bounce
Answers to Terminal Questions
1.
a. Minimise W = 6y1 + 12y2
Subject to constraints y1 + 4y2 ≥ 7
2y1 + 3y2 ≥ 5
y1 + y2 ≥ 0
b. Minimise w = 200y1 + 150y2 – 100y3 – 80y4
Subject to constraints 5y1 + 3y2 – 5y3 – 8y4 ≥ 3
4y1 + 5y2 – 4y3 – 4y4 ≥ 4
y1, y2, y3, y4 ≥ 0
c. Minimise w = 12y1 + 8y2 + 8y3
Subject to constraints 4y1 + 4y2 + 4y3 ≥ 2
3y1 + y2 – y3 ≥ 1
y1, y2, y3, ≥ 0
4.9 References
The following sources have been referred to for additional content for the unit.
·
·
· .
·
Copyright © 2009 SMU
Powered by Sikkim Manipal University
.
MB0048-Unit-05-Transportation Problem
Unit-05-Transportation Problem
Structure:
5.1 Introduction
Learning objectives
5.2 Formulation of Transportation Problem (TP)
5.3 Transportation Algorithm (MODI Method)
5.4 The Initial Basic Feasible Solution
North west corner rule
Matrix minimum method
Vogel’s approximation method
5.5 Moving Towards Optimality
Improving the solution
Modified distribution method / MODI method / U – V Method
Degeneracy in transportation problem
5.6 Summary
5.7 Terminal Questions
5.8 Answers to SAQs and TQs
Answers to Self Assessment Questions
Answers to Terminal Questions
5.9 References
5.1 Introduction
Welcome to the unit on transportation model in Operations Research Management. Transportation model is an important class of linear programs. For a given supply at each source and a given demand at each destination, the model studies the minimisation of the cost of transporting a commodity from a number of sources to several destinations.
The transportation problem involves m sources, each of which has available ai (i = 1, 2… m) units of homogeneous product and n destinations, each of which requires bj (j = 1, 2…., n) units of products. Here ai and bj are positive integers. The cost cij of transporting one unit of the product from the ith source to the jth destination is given for each i and j. The objective is to develop an integral transportation schedule that meets all demands from the inventory at a minimum total transportation cost.
It is assumed that the total supply and the total demand are equal.
[pic] (1)
The condition (1) is guaranteed by creating either a fictitious destination with a demand equal to the surplus if total demand is less than the total supply or a (dummy) source with a supply equal to the shortage if total demand exceeds total supply. The cost of transportation from the fictitious destination to all sources and from all destinations to the fictitious sources are assumed to be zero so that total cost of transportation will remain the same.
Learning objectives
By the end of this unit, you should be able to:
· Formulate the transportation problem
· Find the initial basic feasible solution
· Compare the advantages of various methods of finding initial basic feasible solution
· Solve the degeneracy in the transportation problem
· Apply the model to minimise the cost of transporting a commodity
5.2 Formulation of Transportation Problem
The standard mathematical model for the transportation problem is as follows.
Let xij be number of units of the homogenous product to be transported from source i to the destination j
Then objective is to
Minimise z = [pic]
Subject to
[pic] (2) (2) (2)
With all xij ³ 0 and integrals
Theorem: A necessary and sufficient condition for the existence of a feasible solution to the transportation problem (2) is:
[pic]
Self Assessment Questions
Fill in the blanks
1. Transportation problems are a special type of ___________.
2. The number of rows and columns need not always be ___________.
3. Transportation problem develops a schedule at _______ and ________.
5.3 Transportation Algorithm (MODI Method)
The first approximation to (2) is integral. Therefore, you always need to find a feasible solution. Rather than determining a first approximation by a direct application of the simplex method, it is more efficient to work with the transportation table given below. The transportation algorithm is the simplex method specialised to the format of table involving the following steps:
i) Finding an integral basic feasible solution
ii) Testing the solution for optimality
iii) Improving the solution, when it is not optimal
iv) Repeating steps (ii) and (iii) until the optimal solution is obtained
The solution to TP is obtained in two stages.
In the first stage, you find the basic feasible solution using any of the following methods a) North-west corner rule b) Matrix Minima Method or least cost method c) Vogel’s approximation method. In the second stage, you test the basic feasible solution for its optimality either by MODI method or by stepping stone method.
Table 5.1: Transportation Table
[pic]
Self Assessment Questions
State Yes or No
4. In transportation problems, [pic]is a sufficient and necessary condition for getting a feasible solution.
5. Transportation problems can also be solved by simplex method.
6. Matrix-minima method gives optimum solution.
5.4 The Initial Basic Feasible Solution
Let us consider a TP involving m-origins and n-destinations. Since the sum of origin capacities equals the sum of destination requirements, a feasible solution always exists. Any feasible solution satisfying m + n – 1 of the m + n constraints is a redundant one and hence it can be deleted. This also means that a feasible solution to a TP can have only m + n – 1 positive component; otherwise the solution will degenerate.
It is always possible to assign an initial feasible solution to a TP, satisfying all the rim requirements. This can be achieved either by inspection or by following some simple rules. You can begin by imagining that the transportation table is blank that is initial xij = 0. The simplest procedures for initial allocation are discussed in the following section.
5.4.1 North West Corner rule
Step1: The first assignment is made in the cell occupying the upper left hand (north-west) corner of the transportation table. The maximum feasible amount is allocated here is
x11 = min (a1, b1)
Either the capacity of origin O1 is used up or the requirement at destination D1 is satisfied or both. This value of x11 is entered in the upper left hand corner (small square) of cell (1, 1) in the transportation table.
Step 2: If b1 > a1, the capacity of origin O is exhausted and the requirement at destination D1 is still not satisfied. Then at least one variable in the first column will have to take on a positive value. Move down vertically to the second row and make the second allocation of magnitude:
x21 = min (a2, b1 – x21) in the cell (2, 1)
This either exhausts the capacity of origin O2 or satisfies the remaining demand at destination D1.
If a1 > b1 ,the requirement at destination D1 is satisfied, but the capacity of origin O1 is not completely exhausted. Move to the right in a horizontal position to the second column to make the second allocation of magnitude:
x12 = min (a1 – x11, b2) in the cell (1, 2)
This either exhausts the remaining capacity of origin O1 or satisfies the demand at destination D2.
If b1 = a1, the origin capacity of O1 is completely exhausted as well as the requirement at destination is completely satisfied, then there is a tie at the second allocation. An arbitrary tie breaking choice is made. Make the second allocation of magnitude
x12 = min (a1 – a1, b2) = 0 in the cell (1, 2)
OR
x21 = min (a2, b1 – b2) = 0 in the cell (2, 1)
Step 3: Start from the new north-west corner of the transportation table satisfying the destination requirements and exhausting the origin capacities one at a time, moving down towards the lower right corner of the transportation table until all the rim requirements are satisfied.
[pic]
[pic]
5.4.2 Matrix minimum method
Step 1: Determine the smallest cost in the cost matrix of the transportation table. Let it be cij . Allocate xij = min ( ai, bj) in the cell ( I, j )
Step 2: If xij = ai cross the ith row of the transportation table, decrease bj by ai and proceed to step 3.
If xij = bj cross the ith column of the transportation table, decrease ai by bj and proceed to step 3.
If xij = ai= bj cross either the ith row or the ith column, but not both.
Step 3: Repeat steps 1 and 2 to reduce transportation table until all the rim requirements are satisfied. Whenever the minimum cost is not unique, make an arbitrary choice among the minima.
[pic]
[pic]
5.4.3 Vogel’s approximation method
The Vogel’s approximation method (VAM) takes into account the least cost cij, but also the cost that just exceeds cij. The steps of the method are given below.
Step 1: For each row of the transportation table, identify the smallest and the next to smallest costs. Determine the difference between them for each row. Display them alongside the transportation table by enclosing them in parenthesis against the respective rows. Similarly, compute the differences for each column.
Step 2: Identify the row or column with the largest difference among all the rows and columns. If a tie occurs, use any arbitrary tie breaking choice. Let the greatest difference correspond to the ith row and let Cij be the smallest cost in the ith row. Allocate the maximum feasible amount xij = min (ai, bj) in the (i, j)th cell and cross off the ith row or the jth column in the usual manner.
Step 3: Recompute the column and row differences for the reduced transportation table and go to step 2. Repeat the procedure until all the rim requirements are satisfied.
Remarks:
1. A row or column “difference” indicates the minimum unit penalty incurred by failing to make an allocation to the last smallest cell in that row or column.
2. It is clear that VAM determines an initial basic feasible solution, which is very close to the optimum solution. But the number of iterations required to reach the optimal solution is small.
|Caselet |
|A company has four warehouses. Each warehouse supplies inventory to five stores. |
|The company needs to develop an integral transportation schedule that meets all demands from the inventory at |
|a minimum total transportation cost. |
|Assuming that the total supply and the total demand are equal, the company can use the transportation model of|
|a LPP to arrive at a basic feasible solution. |
[pic]
Self Assessment Questions
State True or False
7. In matrix-minima method, you start allocating from the left-top cell of the table.
8. In Vogel’s approximation method, you first construct penalty and then start allocating.
9. North-west corner rule gives optimum solution.
10. Vogel’s approximation method gives solution near to the optimum solution.
5.5 Moving Towards Optimality
After evaluating an initial basic feasible solution to a transportation problem, the next question is how to get the optimum solution. The basic techniques are illustrated below.
1. Determine the net evaluations for the non–basic variables (empty cells)
2. Determine the entering variable
3. Determine the leaving variable
4. Compute a better basic feasible solution
5. Repeat steps (1) to (4) until an optimum solution has been obtained
5.5.1 Improving the solution
Definition: A loop is the sequence of cells in the transportation table such that:
i) Each pair of consecutive cells lie either in the same row or same column
ii) No three consecutive cells lies in the same row or same column
iii) The first and the last cells of the sequence lies in the same row or column
iv) No cell appears more than once in the sequence
Consider the non-basic variable corresponding to the most negative of the quantities cij – ui – vj, calculated in the test for optimality; it is made the incoming variable. Construct a loop consisting exclusively of this incoming variable (cell) and current basic variables (cells). Then allocate the incoming cell to as many units as possible after appropriate adjustments have been made to the other cells in the loop. Avoid violating the supply and demand constraints, allow all allocations to remain non-negative and reduce one of the old basic variables to zero (where upon it ceases to be basic).
5.5.2 Modified distribution method / Modi method / U–V method
Step 1: Under this method, you construct penalties for rows and columns by subtracting the least value of row / column from the next least value.
Step 2: Then select the highest penalty constructed for both row and column. Enter that row/column and select the minimum cost and allocate min (ai, bj)
Step 3: Delete the row or column or both if the rim availability/ requirements are met.
Step 4: You repeat steps 1 to 2 to till all allocations are over.
Step 5: For allocating all forms of equations ui + vj = cj, set one of the dual variable ui / vj to zero and solve for others.
Step 6: Use this value to find Dij = cij - ui - vj. If all Dij ³ 0, then it is the optimal solution.
Step 7: If any Dij £ 0, select the most negative cell and form loop. Starting point of the loop is positive and alternative corners of the loop are negative and positive. Examine the quantities allocated at negative places. Select the minimum, add it to the positive places and subtract from the negative places.
Step 8: Form new table and repeat steps 5 to 7 till Dij ³ 0
Balanced TP
[pic]
Unbalanced T.P
[pic]
5.5.3 Degeneracy in transportation problem
It is shown that a basic solution to an m-origin, n destination; transportation problem can have at the most m+n-1 positive basic variables (non-zero), otherwise the basic solution degenerates. It follows that whenever the number of basic cells is less than m + n – 1, the transportation problem is a degenerate one. The degeneracy can develop in two ways:
Case 1: The degeneracy develops while determining an initial assignment via any one of the initial assignment methods discussed earlier.
To resolve degeneracy, you must augment the positive variables by as many zero-valued variables as is necessary to complete the required m + n – 1 basic variable. These zero-valued variables are selected in such a manner that the resulting m + n – 1 variable constitutes a basic solution. The selected zero valued variables are designated by allocating an extremely small positive value ε to each one of them. The cells containing these extremely small allocations are then treated like any other basic cells. The ε’s are kept in the transportation table until temporary degeneracy is removed or until the optimum solution is attained, whichever occurs first. At that point, we set each ε = 0.
Case 2: The degeneracy develops at the iteration stage. This happens when the selection of the entering variable results in the simultaneous drive to zero of two or more current (pre-iteration) basic variables.
To resolve degeneracy, the positive variables are augmented by as many zero-valued variables as it is necessary to complete m+n-1 basic variables. These zero-valued variables are selected from among those current basic variables, which are simultaneously driven to zero. The rest of the procedure is exactly the same as discussed above in case 1.
Note: The extremely small value ε is infinitely small and it never affects the value it is added to or subtracted from. Introduce ‘Î’ in unallocated minimum cost cell to avoid forming a loop.
[pic]
Self Assessment Questions
Fill in the blanks
11. All the values of [pic]should be __________ or _________ for the solution to be optimum.
12. In unbalanced transportation problem [pic].
13. If the number of allocation is less than _________ then it is said to be a degenerate transportation problem.
5.6 Summary
The transportation problem is a special type of linear programming problem in which the objective is to transport a homogeneous product manufactured at several plants (origins) to a number of different destinations at a minimum total cost. In this unit, you have learnt several different techniques for computing an initial basic feasible solution to a transportation problem, such as north-west corner rule, matrix minimum method and Vogel’s approximation method. Further, you studied the degeneracy in transportation problem with examples on obtaining an optimum basic feasible solution.
5.7 Terminal Questions
1. Solve the following transportation problem.
[pic]
2. A company has three cement factories located in cities 1,2,3 which supply cement to four projects located in towns 1,2,3,4. Each plant can supply daily 6,1,10 truck loads of cement respectively and the daily cement requirements of the projects are respectively 7,5,3,2 truck loads. The transportation cost per truck load of cement (in hundreds of rupees) from each plant to each project site is as follows.
[pic]
Determine the optimal distribution for the company so as to minimise the total transportation cost.
3. Solve the following transportation problem.
|9 |12 |9 |6 |9 |10 |5 |
|7 |3 |7 |7 |5 |5 |6 |
|6 |5 |9 |11 |3 |11 |2 |
|6 |8 |11 |2 |2 |10 |9 |
|4 |4 |6 |2 |4 |2 |22 |
5.8 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. LPP
2. Equal
3. Minimum cost
4. Yes
5. Yes
6. No
7. False
8. True
9. False
10. True
11. zero
12. Not equal to
13. m + n – 1
Answers to Terminal Questions
1. The optimal transportation cost is Rs. 796
2 Optimal transportation cost is Rs. 10, 000
3 The minimum transportation cost is Rs. 112 as [pic]
5.9 References
No external sources have been referred for this unit.
About the Author
[pic]
admin
Copyright © 2010 SMU.
Powered by WordPress.
MB0048-Unit-06-Assignment Problem
Unit-06-Assignment Problem
Structure:
6.1 Introduction
Learning Objectives
6.2 Mathematical Formulation of the Problem
6.3 Hungarian Method Algorithm
6.4 Routing Problem
Unbalanced AP
Infeasible Assignments
Maximisation in AP
6.5 Travelling Salesman Problem
6.6 Summary
6.7 Terminal Questions
6.8 Answers to SAQs and TQs
Answers to Self Assessment Questions
Answers to Terminal Questions
6.9 References
6.1 Introduction
Welcome to unit six of Operations Research Management on Assignment Problem. The assignment problem is a special case of the transportation problem, where the objective is to minimise the cost or time of completing a number of jobs by a number of persons, maximise revenue and sales efficiently.
In other words, when the problem involves the allocation of ‘n’ different facilities to ‘n’ different tasks, it is often termed as an assignment problem. This model is mostly used for planning. The assignment model is useful in solving problems, such as assignment of machines to jobs, assignment of salesman to sales territories, travelling salesman problem and many more similar situations. It may be noted that with ‘n’ facilities and ‘n’ jobs, there are ‘n’ possible assignments.
One way of finding an optimal assignment is to write all the ‘n’ possible arrangements, evaluate their total cost and select the assignment model offering minimum cost. This method can be unfeasible due to involvement of computational procedures. In this unit, we will study an efficient method for solving assignment problems.
Let’s say there are ‘n’ jobs in a factory having ‘n’ machines to process the jobs. A job i (=1… n), when processed by machine j (=1… n) is assumed to incur a cost Cij. The assignment is to be made in such a way that each job can associate with one and only one machine. You can then determine an assignment of jobs to the machines to minimise the overall cost.
The cost data is given as a matrix where rows correspond to jobs and columns to machines and there are as many rows as the number of columns. The number of jobs and number of machines should be equal.
Assignment becomes a problem because each job requires different skills and the capacity or efficiency of each person with respect to these jobs can be different. This gives rise to cost differences. If each person is able to do all jobs with same efficiency then all costs will be the same and each job can be assigned to any person. When assignment is a problem it becomes a typical optimisation problem. Therefore, you can compare an assignment problem to a transportation problem. The cost element is given and is a square matrix and requirement at each destination is one and availability at each origin is also one.
Additionally, you have number of origins, which equal the number of destinations. Therefore, the total demand is equal to the total supply. There is only one assignment in each row and each column. However if you compare this to a transportation problem, you will find that a general transportation problem does not have the above mentioned limitations. These limitations are peculiar to assignment problems only.
An assignment problem can be either balanced or unbalanced. Let’s first focus on a balanced assignment problem. A balanced assignment problem is one where the number of rows = the number of columns (comparable to a balanced transportation problem where total demand =total supply).
Balanced assignment problem: No. of rows = No. of columns
Minimisation case for an assignment problem: You need to perform the following steps to solve the minimisation case for an assignment problem:
[pic]
Figure 6.1: Steps to solve the minimisation case for an assignment problem
Step 1: Determine the total opportunity cost matrix
a) Arrive at a column opportunity cost matrix by subtracting the lowest entry of each column of the given payoff matrix from all the entries in the column.
b) Then subtract the lowest entry of each row of the matrix obtained in
(a) from all the entries in its row.
The result of step 1b gives the total-opportunity-cost matrix.
Step 2: Determine whether an optimal assignment can be made
a) Cover all the zeroes of the current total-opportunity-cost matrix with the minimum possible number of horizontal and vertical lines.
b) If the number of lines in step 2a equals the number of rows (or columns) of the matrix, the problem can be solved. Make a complete assignment so that the total opportunity cost involved in the assignment is zero.
c) If the number of lines drawn in step 2a is less than the number of rows (or columns) of the matrix, proceed to step 3.
Step 3: Revise the total opportunity cost matrix
a) Subtract the lowest entry in the uncovered cells of the current total opportunity cost matrix from all the uncovered cells.
b) Add the same lowest entry to only those cells in which the covering lines of step 2 cross.
The result of steps 3a and 3b is a revised total opportunity cost matrix.
Step 4: Repeat steps 2 and 3 until an optimal assignment having a total opportunity cost of zero can be made.
You can solve an assignment problem by any of the following four methods.
· Enumeration method
· Simplex method
· Transportation problem
· Hungarian method
However, in this unit, we will focus on the most commonly used method, that is the Hungarian method to solve the assignment problems.
[pic]
Figure 6.2: Methods to solve assignment problem
Learning objectives
By the end of this unit, you should be able to:
· Formulate mathematically an assignment problem
· Solve a routing problem
· Describe the travelling salesman problem
· State the significance of the assignment problem
· Compute the problem using the Hungarian method
· Solve practical problems, such as routing problems and travelling salesman problems
6.2 Mathematical Formulation of the Problem
Let xij be a variable defined by
[pic]
Since only one job is assigned to each machine, you have
[pic]xij = 1 and [pic]xij = 1
Hence, the total assignment cost is given by
z = [pic]xij cij
Thus the assignment problem takes the following mathematical form
Determine xij ≥ 0 (i, j =1… n).
Minimise z = [pic]xij cij
Subject to the constraints
[pic]xij = 1 j =1, 2, n
And [pic]xij = 1 i = 1, 2… n
With xij = 0 or 1
Note: In an assignment problem, if you add or subtract a real number to or from each element of a row or column of the cost matrix, then the optimum assignment for the modified matrix is also optimum for the original one.
Self Assessment Questions
State True or False
1. In an AP, the constraints are of equality type.
2. The number of facilities should be equal to the number of resources.
3. The decision variables can take on any value.
6.3 Hungarian Method Algorithm
Hungarian method algorithm is based on the concept of opportunity cost and is more efficient in solving assignment problems. Adopt the following steps mentioned below to solve an AP using the Hungarian method algorithm:
Step 1: Prepare row ruled matrix by selecting the minimum values for each row and subtract it from other elements of the row.
Step 2: Prepare column reduced matrix by subtracting minimum value of the column from the other values of that column.
Step 3: Assign zero row-wise if there is only one zero in the row and cross (cancel) (X) other zeros in that column.
Step 4: Assign column wise if there is only one zero in that column and cross other zeros in that row.
Step 5: Repeat steps 3 and 4 till all zeros are either assigned or crossed. If the number of assignments is equal to number of rows present, you have arrived at an optimal solution, if not, then proceed to step 6.
Step 6: Mark (P) the unassigned rows. Look for crossed zero in that row. Mark the column containing the crossed zero. Look for assigned zero in that column. Mark the row containing assigned zero. Repeat this process till all makings are over.
Step 7: Draw straight line through unmarked rows and marked column. The number of straight line drawn will be equal to number of assignments made.
Step 8: Examine the uncovered elements. Select the minimum.
a) Subtract it from uncovered elements.
b) Add it at the point of intersection of lines.
c) Leave the rest as it is.
d) Prepare a new table.
Step 9: Repeat steps 3 to 7 till optimum assignment is obtained.
Step 10: Repeat steps 5 to 7 till number of allocations = number of rows.
The assignment algorithm applies the concept of opportunity costs. The cost of any kind of action or decision consists of the opportunities that are sacrificed in taking that action. If we do one thing, we cannot do another.
[pic]
Self Assessment Questions
State Yes or No
4. In Hungarian method, you prepare row-reduced matrix.
5. The number of assignments should be equal to the number of rows for an optimum solution.
6. There can be more than one allocation in a row.
6.4 Routing Problem
Network scheduling is a technique for planning and scheduling of large projects. It has successfully been applied in transportation and communication problems. A typical network problem involves finding route from one node (origin) to another (destination) between which alternative paths are available at various stages of the journey. The problem is to select the route that yields minimum cost. A number of different constraints may be placed on acceptable routes for instance, not returning to the node passed or passing through each node just once. These kinds of problems are called as routing problems.
A wide variety of problems other than routing may be developed in connection with the construction and utilisation of networks. Here, you are going to consider the special type of routing problem that occurs frequently in OR – the travelling salesman problem.
6.4.1 Unbalanced AP
Unbalanced assignment is an assignment where the number of rows is not equal to the number of columns and vice versa. For example, the number of machines may be more than the number of jobs or the number of jobs may be more than the number of machines. In such a situation, you have to introduce dummy row/column(s) in the matrix. The dummy rows or columns will contain all costs elements as zero. This balances the problem and then you can use Hungarian method to find optimal assignment.
Unbalanced assignment problem: No. of rows ≠ No. of columns.
[pic]
6.4.2 Infeasible assignments
It is sometimes possible that a particular person is incapable of doing certain work or a specific a specific job cannot be performed on a particular machine. The solution of the assignment problem should take into account these restrictions so that the infeasible assignment can be avoided. This can be achieved by assigning a very high cost (say ∞ or M) to the cells where assignments are prohibited, thereby, restricting the entry of this pair of job – machine or resource – activity into the final solution. After inserting a high value a at the cell we need to apply Hungarian method to solve the problem.
[pic]
6.4.3 Maximisation in AP
Some assignment problems are phrased in terms of maximising the profit or effectiveness or payoff of an assignment of people to tasks or of jobs to machines. You cannot apply the Hungarian method to such maximisation problems. Therefore, you need to reduce it to a minimisation problem.
It is easy to obtain an equivalent minimisation problem by converting every number in the table to an opportunity loss. To do so, you need to subtract every value from the highest value of the matrix and then proceed as usual
You will notice that minimising the opportunity loss produces the same assignment solution as the original maximisation problem.
[pic]
|Caselet |
|A tailoring unit has four sewing machines of different makes. Each machine is capable of stitching all the |
|required designs and patterns. However, the profit factor differs for each assignment. The unit is looking at|
|maximising profit. |
|To do so, the unit needs to carry out an optimal assignment exercise of assigning the right jobs to the right|
|machines. |
[pic]
[pic]
[pic]
Self Assessment Questions
Fill in the blanks
7. In unbalanced AP, the number of rows ________ to number of column.
8. Hungarian method cannot be applied directly to _________ problem.
9. If some jobs cannot be assigned to some machines, then it is called _________ assignment problem.
6.5 Travelling Salesman Problem
Suppose a salesman has to visit ‘n’ number of cities. He wishes to start from a particular city, visit each city once and then return to his starting point. The objective is to select the sequence to visit the cities in such a way that his total travelling time is minimised. Starting from a given city, the salesman will have total of (n-1) different sequences. Further, since the salesman has to visit all the ‘n’ number of cities; the optimal solution remains independent of selection of the starting point.
The problem can be represented as a network where the nodes and arcs represent the cities and the distance between them respectively. Assume that in a five city problem, a round trip of the salesman is given by the following arcs.
(3,1), (1,2), (2,4), (4,5), (5,3)
These arcs in order are the first, second, third, fourth and fifth directed arcs for the trip. Generally the kth directed arc represents the kth leg of the trip that is on leg k, the salesman travels from city i to city j
(i, j = 1, 2… n;[pic])
To formulate the problem, whose solution will yield the minimum travelling time, let the variables xijk be defined as:
[pic]
Where, i, j and k are integers that vary between 1 and n
Following are the constraints of the problem.
a) Only one directed arc may be assigned to a specific k, thus [pic]
[pic]xijk = 1 k =1, 2, 3…n
[pic]
b) Only one other city may be reached from a specific city i, thus
[pic]xijk =1, i = 1, 2…, n
c) Only one other city can initiate a direct arc to a specified city j, thus
[pic]xijk =1, j =1, 2… n
d) Given the kth directed arc ends at some specific city j, the (k+1)th directed arc must start at the same city j; thus
[pic]xijk = [pic]xjr ( k +1) for all j and k.
[pic][pic]
These constraints ensure that the round trip will consist of connected arcs. The objective function is to minimise
z = [pic][pic]dij xijk [pic]
Where dij is the distance from city i to city j
Self Assessment Questions
Fill in the blanks
10. In travelling salesman problem, the objective is to visit each cities ________ __________.
11. Salesman has ________ different sequences if n are the number of cities to be visited.
6.6 Summary
This unit on assignment problems focuses on a special type of transportation problem, where the objective is to allocate ‘n’ number of different facilities to ‘n’ number of different tasks. Although an assignment problem can be formulated as a linear programming problem, it is solved by a special method know as Hungarian method. If the number of persons is the same as the number of jobs, the assignment problem is said to be balanced. The unit also explains the travelling salesman problem in brief.
6.7 Terminal Questions
1. Four jobs are to be done on four different machines. The cost in (rupees) of producing ith on the j th machine is given below:
[pic]
Assign the jobs to different machines to minimise the total cost.
2. A marketing manager has 5 salesmen and 5 sales districts. Considering the capabilities of the salesman and the nature of districts, the marketing manager estimates that sales per month (in hundred rupees) for each salesman in each district would be as follows.
[pic]
Find the assignment of salesman to districts that will result in maximum sales.
3. In a plant layout, there are five vacant places. The plant orders four machines to be installed in the vacant places. The cost of installing is as follows:
|M/G |A |B |C |D |E |
|M1 |9 |11 |15 |10 |11 |
|M2 |12 |9 |- |10 |9 |
|M3 |- |11 |14 |11 |7 |
|M4 |14 |8 |12 |7 |8 |
Find the optimum assignment.
4. Find the assignment that maximises the total sale.
Zone
|Sales men |1 |2 |3 |4 |
|M1 |42 |35 |28 |21 |
|M2 |30 |25 |20 |15 |
|M3 |30 |25 |20 |15 |
|M4 |24 |20 |16 |12 |
6.8 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. True
2. True
3. False
4. True
5. True
6. False
7. ≠
8. Maximisation problem
9. Infeasible
10. Only once
11. (n-1)
Answers to Terminal Questions
1. The optimum assignment policy is
Job1 to machine 2, Job 2 to machine 4
Job 3 to machine1, Job 4 to machine 3.
And the minimum assignment cost = Rs. (11+13+14+11) = Rs. 49
2. Optimal assignment policy is salesman 1 to district B, 2 to A, 3 to E,
4 to C and 5 to D.
Hence the maximum sales = Rs. (38+40+37+41+35)[pic]100 = Rs. 19,100.
3. M1 – A2; M2 – B; M3 – E; M4 – D Total 38
4. M1 – 1; M2 – 2; M3 – 3; M4 – 4 Total 99
6.9 References
The following resources have been referred to for additional content for the unit.
·
·
· Formatted.pdf
Copyright © 2009 SMU
Powered by Sikkim Manipal University
.
MB0048-Unit-07-Integer Programming Problem
Unit-07-Integer Programming Problem
Structure:
7.1 Introduction
Learning Objectives
7.2 All and Mixed Integer Programming Planning
7.3 Gomory’s all IPP Method
Construction of Gomory’s constraints
7.4 All IPP Algorithms
7.5 Branch and Bound Technique
Branch and bound algorithm
7.6 Summary
7.7 Terminal Questions
7.8 Answers to SAQs and TQs
Answers to self assessment questions
Answers to terminal questions
7.9 References
7.1 Introduction
Welcome to the seventh unit on Integer Programming Problem in Operations Research Management. The Integer Programming Problem (IPP) is a special case of Linear Programming Problem (LPP), where all or some variables are constrained to assume non-negative integer values. You can apply this problem to various situations in business and industry where discrete nature of the variables is involved in many decision-making situations. For instance, in manufacturing, the production is frequently scheduled in terms of batches, lots or runs; in distribution, a shipment must involve a discrete number of trucks or aircrafts or freight cars.
Learning objectives
By the end of this unit, you should be able to:
· Write an integer programming problem (IPP)
· Solve an integer programming problem (IPP) using Gomory’s method
· Apply the branch and land technique
7.2 All and Mixed Integer Programming Problem (IPP)
An integer programming problem can be described as follows:
Determine the value of unknowns x1, x2, … , xn
So as to optimise z = c1x1 +c2x2 + . . .+ cnxn
Subject to the constraints
ai1 x1 + ai2 x2 + . . . + ain xn =bi , i = 1,2,…,m
and xj [pic]0 j = 1, 2, … ,n
Where xj being an integral value for j = 1, 2, … , k [pic]n.
If all the variables are forced to take only integral value that is k = n, it is called an all (or pure) integer programming problem. If some of the variables are restricted to take integral value and the remaining (n – k) variables take any non-negative value, then the problem is known as a mixed integer programming problem.
Self Assessment Questions
True or False:
1. Integer programming is applied to problems that involve discrete variables.
2. If some variables take on non-negative values, then it is known as pure IPP.
7.3 Gomory’s All – IPP Method
An optimum solution to an IPP is obtained by using the simplex method, ignoring the restriction of integral values. In the optimum solution, if all the variables have integer values, the current solution will be the required optimum integer solution.
Otherwise, the given IPP is modified by inserting a new constraint called Gomory’s constraint or secondary constraint. This constraint represents necessary conditions for integrability and eliminates some non-integer solution without losing any integral solution. On addition of the secondary constraint, the problem is solved using dual simplex method to obtain an optimum integral solution.
If all the values of the variables in the solution are integers, then an optimum inter-solution is obtained, or else a new constraint is added to the modified LPP and the procedure is repeated till the optimum solution is derived. An optimum integer solution will be reached eventually after introducing enough new constraints to eliminate all the superior non-integer solutions. The construction of additional constraints, called secondary or Gomory’s constraints is important and needs special attention.
7.3.1 Construction of Gomory’s constraints
Consider a LPP or an optimum non–integer basic feasible solution. With the usual notations, let the solution be displayed in the following simplex table.
Table 7.1: Simplex table
|yB |xB |y1 |y2 |y3 |y4 |
|y2 |y10 |y11 |y12 |y13 |y14 |
|y3 |y20 |y21 |y22 |y23 |y24 |
| |y00 |y01 |y02 |y03 |y04 |
The optimum basic feasible solution is given by
xB = [x2, x3 ] = [y10, y20]; max z = y00
Since xB is a non-integer solution, we can assume that y10 is fractional. The constraint equation is
y10 = y11 x1 + y12 x2 + y13 x3+ y14 x4 [pic]
It reduces to
y10 = y11 x1 + x2 + y14 x4 [pic]_____ (1)
Because x2 and x3 are basic variables (which implies that y12 = 1 and
y13 = 0). The above equation can be rewritten as
x2 = y10 - y11 x1 - y14 x4
This is a linear combination of non-basic variables.
Now, since y10 [pic]0 the fractional part of y10 must also be non-negative. You can split each of yij in (1) into an integral part Iij , and a non-negative fractional part, f1j for j = 0,1,2,3,4. After the breakup (1) above, you can write it as:
I10 + f10 = (I11 + f11) x2 + (I14 + f14) x4
Or
f10 - f11 x2 - f14 x4 = x2 + I11 x1 + I14x4 - I10 _____ (2)
If you compare (1) and (2), you will see that if you add an additional constraint in such a way that the left-hand side of (2) is an integer; then you will be forcing the non-integer y10 towards an integer.
The desired Gomory’s constraint is
f10 – f11 x1 – f11 x4 ≤ 0
It is possible to have f10 – f11 x1 – f11 x4 = h where h > 0 is an integer. Then f10 = h + f11 x1 + f14 x4 is greater than one. This contradicts that 0 < fij < 1 for j = 0, 1, 2, 3, 4.
Thus Gomory’s constraint is
[pic]
Where Gsla (1) is a slack variable in the above first Gomory’s constraint
The additional constraint to be included in the given LPP is towards obtaining an optimum all integer solution. After adding the constraint, the optimum simplex table looks like table 7.2 given below.
Table 7.2: Optimum simplex table
|yB |xB |y1 |y2 |y3 |y4 |Gsla(1) |
|y1 |y10 |y11 |y12 |y13 |y14 |0 |
|y2 |y20 |y21 |y22 |y23 |y24 |0 |
|Gsla(1) |– f10 |– f11 |0 |0 |– f14 |1 |
| |y00 |y01 |y02 |y03 |y04 |y05 |
Since – f10 is negative, the optimal solution is unfeasible. Thus the dual simplex method is to be applied for obtaining an optimum feasible solution. After obtaining this solution, the above referred procedure is applied for constructing second Gomory’s constraint. The process is to be continued till all the integer solution has been obtained.
Self Assessment Questions
Fill in the blanks:
3. An optimum solution to IPP is first obtained by using ______________.
4. With the addition of Gomory’s constraint, the problem is solved by ______ ______ ________.
7.4 All IPP Algorithm
The iterative procedure for the solution of integer programming problem is as follows.
[pic]
Figure 7.1: Iterative procedure of IPP
Step 1: Convert the minimisation IPP into maximisation, if it is in minimisation form. Ignore the integrality condition.
Step 2: Introduce the slack or surplus variables, if needed to convert the inequations into equations and obtain the optimum solution of the given LPP by using simplex algorithm.
Step 3: Test the integrality of the optimum solution
a) If the optimum solution contains all integer values, an optimum basic feasible integer solution has been obtained.
b) If the optimum solution does not include all integer values, then proceed to the next step.
Step 4: Examine the constraint equations corresponding to the current optimum solution. Let these equations be represented by
[pic]
Where [pic]denotes the number of variables and [pic]the number of equations. Choose the largest fraction of bis to find [pic][pic]
Let it be [pic]or write is as [pic]
Step 5: Express the negative fractions if any, in the kth row of the optimum simplex table as the sum of a negative integer and a non-negative fraction.
Step 6: Find the Gomorian constraint
[pic]
And add the equation
[pic]
To the current set of equation constraints
Step 7: Start with a new set of equation constraints. Find the new optimum solution by dual simplex algorithm so that Gsla (1) is the initial leaving basic variable.
Step 8: If the new optimum solution for the modified LPP is an integer solution, it is also feasible and optimum for the given IPP. If it is not an integer solution, then return to step 4 and repeat the process until an optimum feasible integer solution is obtained.
[pic]
[pic]
Self Assessment Questions
True or False:
5. Do you select the variable for Gomory’s constraint whose fractional value is more?
6. Optimum values in an pure IPP can be x=2 and y=3.5.
7.5 Branch and Bound Technique
Sometimes a few or all the variables of an IPP are constrained by their upper or lower bounds or by both. The most general technique for a solution of such constrained optimisation problems is the branch and bound technique. The technique is applicable to both all (or pure) IPP as well as mixed IPP. The technique for a maximisation problem is discussed below:
Let the IPP be
Maximise [pic]–––––––––––––––––––––––––––– (1)
Subject to the constraints
[pic]––––––––––––––––––– (2)
xj is integer valued , j = 1, 2, …….., r (< n) –––––––––––––––––- (3)
xj > 0 …………………. j = r + 1, …….., n ––––––-––––––––––––––– (4)
Further let us suppose that for each integer valued xj, we can assign lower and upper bounds for the optimum values of the variable by
Lj ≤ xj ≤ Uj j = 1, 2, …. r –––––––––––––––––––––––––– (5)
This is the main idea behind “the branch and bound technique”.
Consider any variable xj, and let I be some integer value satisfying Lj £ I £ Uj – 1. Then clearly an optimum solution (1) through (5) also satisfies either linear constraint.
x j ³ I + 1 –––––––––––––––––––––––––––––– (6)
Or the linear constraint xj ≤ I –––––––––––––––––––––––––––––– (7)
To explain how this partitioning helps, let’s assume that there were no integer restrictions (3), and it yields an optimal solution to LPP – (1), (2), (4) and (5). This indicates x1 = 1.66 (for example).
Then you formulate and solve two LPPs each containing (1), (2) and (4). But (5) for j = 1 is modified to be 2 ≤ x1 ≤ U1 in one problem and L1 ≤ x1 ≤ 1 in the other. Further to each of these problems, process an optimal solution satisfying integer constraint (3).
Then the solution having the larger value for z is clearly the optimum for the given IPP. However, it usually happens that one (or both) of these problems have no optimal solution satisfying (3), and thus some more computations are required. Now let us discuss, step wise, the algorithm that specifies how to apply the partitioning (6) and (7) in a systematic manner to finally arrive at an optimum solution.
Let’s start with an initial lower bound for z, say z(0) at the first iteration, which is less than or equal to the optimal value z*. This lower bound may be taken as the starting Lj for some xj.
In addition to the lower bound z(0), you also have a list of LPPs (to be called master list) differing only in the bounds (5). To start with (the 0th iteration) the master list contains a single LPP consisting of (1), (2), (4) and (5). Let us now discuss the procedure that specifies how the partitioning (6) and (7) can be applied systematically to eventually get an optimum integer-valued solution.
7.5.1 Branch and bound algorithm
At the tth iteration (t = 0, 1, 2 …), apply the following steps to get an optimum integer.
Step 0: If the master list is not empty, choose an LPP from it. Otherwise stop the process, go to step 1.
Step 1: Obtain the optimum solution to the chosen problem. If either
i) It has no feasible solution or
ii) The resulting optimum value of the objective function z is less than or equal to z(t), then let z(t+1) = z(t) and return to step 0; otherwise go to step 2
Step 2: If the obtained optimum solution satisfies the integer constraints (3) then record it. Let z(t+1) be the associated optimum value of z; return to step 0. Otherwise move to step 3.
Step 3: Select any variable xj, j = 1, 2, …., p. that does not have an integer value in the obtained optimum solution to the LPP, chosen in step 0. Let [pic]denote this optimal value of xj. Add two LPPs to the master list. These LPPs are identical to the LPPs chosen in step 0, except that, the lower bound on xj is replaced by [pic]+ 1. Let z(t+1) = z(t); return to step 0.
Note: At the termination of the algorithm, if a feasible integer valued solution yielding z(t) has been recorded, it is optimum, or else no integer valued feasible solution exists.
[pic]
Self Assessment Questions
True or False:
7. Branch and bound technique is applied when some variables have upper or lower bounds.
8. We start the technique with lower bound.
7.6 Summary
This chapter examines the programming model in which the assumption of divisibility is weakened. This unit also describes two algorithms to determine the optimal solution for an integer programming problem. One is the cutting plane algorithm devised by Gomory and the other is the branch and bound algorithm developed by Land Doig.
7.7 Terminal Questions
1. Use Branch and Bound technique to solve the following problem
Maximise z = 3x1 + 3x2 + 13 x3
Subject to
– 3x1 + 6x2 + 7x3 ≤ 8
6x1 – 3x2 + 7x3 ≤ 8
0 ≤ xj ≤ 5
And xj are integer j = 1, 2, 3
2. What is integer programming?
3. Explain the Gomory’s cutting plane all integer algorithm of an IPP?
7.8 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. True
2. False
3. Simplex method
4. Dual simplex method
5. Correct
6. Wrong
7. True
8. False
Answers to Terminal Questions
1. At the end of the 8th iteration we get the optional solution to the I.P.P. is x1 = x2 = 0, x3 = 1, z* = 13.
2. Refer to Section 7.2
3. Refer to Section 7.3
7.9 References
No external sources have been referred for this unit.
Copyright © 2009 SMU
Powered by Sikkim Manipal University
.
MB0048-Unit-08-Infinite Queuing Models
Unit-08-Infinite Queuing Models
Structure:
8.1 Introduction
Learning objectives
8.2 Queuing Theory
8.3 Analysis of Queuing Process
8.4 Constituents of Queuing System
Arrival pattern
Completely random arrivals
8.5 Service Facility
8.6 Queue Discipline
Customer behaviour
Server behaviour
8.7 Mathematical Analysis of Queuing Process
Properties of the system
Notations
8.8 Single Channel Models
8.9 Multiple Service Channels
8.10 Erlang Family of Distribution of Service Times
8.11 Summary
8.12 Terminal Questions
8.13 Answers to SAQs and TQs
Answers to Self Assessment Questions
Answers to Terminal questions
8.14 References
8.1 Introduction
Welcome to the eighth unit of Operations Research on Infinite Queuing Models. This unit talks about how a queuing model used to approximate a queuing situation for the queuing method is to be analysed mathematically.
Who isn’t familiar with queues in our daily existence? On way to your work place, you have to wait at the bus stop, wait for the traffic light to turn green, wait for your turn to enter the lift. You come across cars in line at petrol pumps for service, queues to deposit cash at the bank, mobile subscriber waiting for a new connection, customers waiting at the checkout counter, goods in production/warehouse waiting to be shipped; even aircrafts waiting for a free runway to take off.
The one thing common to all the above mentioned examples is that customers arrive at a service centre and wait for their turn to receive the service. Though the arrival of customers is irregular and time taken for service is not consistent, queues build up during hours of demand and disappear during the lull period. Personally we do not like to wait.
In commercial or industrial situations, it may not be economical to have waiting lines. On the other hand, it may not be feasible or economical to totally avoid queues. An executive dealing with the system then would like to find the optimal facilities to be provided
Learning objectives
By the end of this unit, you should be able to:
· Describe the queuing process
· Evaluate the queuing process mathematically
· Apply different models to practical problems
8.2 Queuing Theory
The queuing theory is based on probability concepts. It gives an indication of the capability of a given system and the possible changes in its performance with modification to the system.
All the constraints of the process are not taken into account in the formulation of a queuing model. The application of queuing theory cannot be viewed as an optimisation process as there is no maximisation or minimisation of an objective function.
Help on hand in the form of queuing theory allows the executive to make an informed guess of what the balance between customer waiting time and service capability should be. The executive first considers several alternatives, evaluates their effect on the system through queuing models and makes his choice. The evaluation criteria will measure efficiency of the system by measuring the average length of a queue, expected waiting time of a customer and the average time spent by the customer in the system. The success in using this approach primarily depends on the alternatives considered and not on the queuing models developed.
Therefore, it is essential for the executive to have a succinct understanding of the process, so that he can consider the right alternatives and formulate the correct models.
Self Assessment Questions
True or False:
1. Customers arrive at a bank at regular intervals.
2. Queuing identifies the optimal service facilities to be provided.
3. Queuing theory is based on the deterministic model.
8.3 Analysis of a Queuing Process
The management is often interested in finding out the quality of service rendered to the customers. An indicator of efficiency of a system involving flow of customers for service is the speed which they are served.
Augmenting the physical facilities to provide service will enhance service leading to customer satisfaction. However, these facilities cannot be increased randomly as they are expensive. If the queuing process involves waiting of machines for service, it is possible to find the economic level of the maintenance facilities by balancing the cost of machine downtime against the cost of maintenance facilities. Such evaluation in monetary terms is not always possible when the customers are people. Then some measures of efficiency of the system as mentioned above may prove helpful.
A typical investigation of a queuing system would comprise the following steps:
Step 1: Preliminary study
This stage involves an analysis of the process created through a flow diagram. An attempt is made to identify the points, which restrict service or the characteristics, which indicate scope for improvement.
Step 2: Exploration of the various alternatives
By introducing changes in the constituents of the queuing system, it is possible to effect improvement. The arrival pattern may be altered by withdrawing service facilities to certain categories of customers or by introducing an appointment system. The time taken for providing service can be improved by increasing the capacity of the system, that is, by increasing the number of service channels or the working hours. Providing additional service facilities to relieve congestion during peak periods is a common feature. Also, modifying the queue discipline may change the characteristics of the system.
Priority has to be given to the arrivals involving high cost of waiting time. In multi channel queues, separate channels of service are provided for different types of customers. The fixed change counter at the Churchgate railway station manned by Western Railway authorities is said to have cut down the waiting time for a majority of customers.
Step 3: Collection of data and analysis
Direct observation of the system in terms of customer’s arrival time, service rate, length of queue and waiting time is done during the collection stage. The data is analysed in detail to determine the statistical pattern of the variables. The measures of efficiency of the system are computed on the basis of queuing theory. These are counterchecked with the results obtained through direct observation to confirm the validity of the formulae applied. It may be necessary to collect additional data regarding the process.
Step 4: Evaluation of alternatives
Effect of modifying the constituents of the system on the basis of the selected alternatives is evaluated through application of queuing theory. Simulation technique is another alternative. Based on the results obtained, the best combination of the changes to be made in the existing system is selected.
Step 5: Implementation
Formulated proposals are implemented and tested on a small scale. If the need arises, further changes are made and rechecked before implementing them on full scale. It is advisable to observe the functioning of the system periodically to ensure that the desired results are maintained.
Self Assessment Questions
Fill in the blanks:
4. One of the indicators of efficiency of a system is ________ factor.
5. Analysis of queuing system explores ________ ________.
6. ____________ technique can also be used for analysis.
8.4 Constituents of a Queuing System
The constituents of a Queuing System include arrival pattern, service facility and queue discipline.
· Arrival pattern: It is the average rate at which the customers arrive as well as the statistical pattern of arrival
· Service facility: Examining the number of customers served at a time and the statistical pattern of time taken for service at the service facility
· Queue discipline: The common method of choosing a customer for service amongst those waiting for service is ‘First Come First Serve’
Let us examine each of these constituents in detail.
8.4.1 Arrival pattern
The arrival of customers can be regular as in case of an appointment system of a doctor or flow of components on a conveyor belt. The regular pattern of arrivals is neither very common nor very easy to deal with mathematically. Our primary concern is the pattern of completely random arrivals.
8.4.2 Completely random arrivals
If the number of potential customers is infinitely large, then probability of an arrival in the next interval of time will not depend upon the number of customers already in the system. (The assumption is valid by and large, except for queues involving a small finite number of customers.) When the arrivals are completely random, they follow the Poisson distribution, which equals to the average number of arrivals per unit time.
Sometimes it is necessary to distinguish between groups of customers, such as male and female callers, or large and small aircrafts during the arrivals. There are several other types of arrival patterns which shall not be dealt with due to their restricted applications.
Self Assessment Questions
True or False:
7. Every queuing process has an arrival pattern, a service facility and a queue discipline as its constituents.
8. If the arrivals are completely random, then it follows Poisson distribution.
8.5 Service Facility
Service Facility is based on three parameters – Availability of Service, Number of Service Centres and Duration of Service.
i) Availability of service
It is necessary to examine if there are any constraints that reduce the number of customers to be served at a time, apart from specifying the time span of the availability of service. For example, in a waiting line for a suburban train, apart from the timings of the train services, the probability distribution of the number of passengers that can be accommodated in a train that arrives is relevant.
ii) Number of service centres
If only one service centre is referred to as a service channel, obviously only one customer can be served at a time. There will definitely be more than one service centre and the behaviour of the queues will vary with the number of channels available for service. Multiple service channels may be arranged in series or in parallel.
Multiple service channels are arranged in series when a customer has to go through several counters one after another with each providing a different part of the service. For instance, bank counters where a customer has to go to at least two counters to withdraw is an example of arrangement in series.
On the other hand ticket booths in a railway station have multiple channels with parallel arrangement.
iii) Duration of service
This is the length of time taken to serve a customer. This can be constant or varying.
(a) Constant service time: Though not in practice, an assumption that service time is constant holds true, if the pattern of arrivals is very irregular.
(b) Completely random service time: The service time can be considered completely random when:
· The server does not distinguish between the various arrivals
· The server does not deliberately change the duration of service on the basis of the time taken to serve the previous arrival.
· The server forgets the time for which he has been serving a customer.
Under the above mentioned conditions, the service time follows exponential distribution which means equal to reciprocal of the average rate of service.
(c) Service time following Erlang Distribution
Sometimes, the assumption of an exponential distribution for service time is not valid; hence Erlang family of service time distributions is used.
Table 8.1: Erlang Distribution of service time
|Sr.No. |Situation |Arriving Customers |Service Facility |
|1. |Passage of customers through supermarket |Shoppers |Checkout counters |
| |checkout | | |
|2. |Flow of automobile traffic through a road|Automobiles |Road Network |
| |network. | | |
|3. |Transfer of electronic messages |Electronic messages |Transmission lines |
|4. |Banking transactions |Bank patrons |Bank tellers |
|5. |Flow of computer programmers through a |Computer Programmers |Central processing unit |
| |computer system. | | |
|6. |Sale of theatre tickets |Theatre-goers |Ticket booking windows |
|7. |Arrival of trucks to carry fruits and |Trucks |Loading crews and facilities |
| |vegetables from a central market | | |
|8. |Registration of unemployed at employment |Unemployed personnel |Registration assistants |
| |exchange | | |
|9. |Occurrences of fires |Fires |Firemen and equipment |
|10. |Flow of ships to the seashore |ships |Harbour and docking facilities |
|11 |Calls at police control room |Service calls |policemen |
Self Assessment Questions
Fill in the blanks:
9. Multiple service channels may be arranged in ___________ or in _________.
10. The service time can be __________ or _________.
8.6 Queue Discipline
The pattern of selection for service from the pool of customers is of two types. The common pattern is to select in the order in which the customers arrive. “First come first served” is a common example. In issuing materials from a store’s inventory sometimes the storekeeper follows the “Last in First Out” principle because of the convenience it offers for removal from stocks and handling.
There are queues according to priority to certain types of customers. This type of queuing can have two approaches: non pre-emptive and pre-emptive. In case of non pre-emptive priority, the customer getting service is allowed to continue with service till completion, even if a “priority customer” arrives midway during his service. This is a common form of priority. Pre-emptive priority involves stopping the service of the non priority customers as soon as the priority customer arrives.
Priority given to repairs of a production holding machine over an auxiliary unit for allocation of maintenance labour force is a typical example. Preference is given to larger ships over the smaller ones irrespective of the order in which they arrive for allocation of berths.
8.6.1 Customer behaviour
a) Balking: Arriving customers are said to “balk” if they do not join a queue because of their reluctance to wait.
b) Collusion: Customers may be in collusion meaning that only one person would join the queue, but demand service on behalf of several customers.
c) Reneging: Impatient customers who would not wait beyond a certain time and leave the queue are said to renege.
d) Jockeying: Some customers keep on switching over from one queue to another in a multiple service centre. This is called jockeying.
8.6.2 Server behaviour
Although the service timings have been specified, the server may not be available through the entire span of time. For instance, in every one hour the server may disconnect from the service centre for 5 minutes so that it can go through its daily updates or cleanup routine.
Self Assessment Questions
Fill in the blanks:
11. When customers keep on switching over from one queue to another then it is called ________.
12. _____ ________ ______ ______ are the types of customer behaviour.
8.7 Mathematical Analysis of Queuing Process
Statistical Equilibrium: While analysing the queuing process, our main interest is in developing a mathematical model which represents the system. This implies that changes occurring in the characteristics of the system are not to be considered if they are of short durations. When we specify the statistical distributions of the arrivals or service times, we want to ensure an equilibrium state.
In a queuing process, at each point of time, there is a probability distribution for the length of the queue. Compare the number of customers arrived at the post office, 15 minutes after the counter is opened to that after one hour. After the initial rush, you’ll find the system with the same type of probabilities of arrivals.
The probability distribution of the arrivals will then be different from that of the initial state. The state, in which the probability distribution remains the same, is called the steady state and the system is said to have acquired a state of statistical equilibrium.
In the steady state, there will be variations in the queue from time to time but the probability distributions representing the queuing process will remain the same and are independent of the time at which the system is examined.
8.7.1 Properties of the system
While developing queuing models, we will confine our discussion to queuing systems with the following properties.
Arrivals
· Customers are discrete entities
· Population – Finite/Infinite
· No simultaneous arrivals
· Pattern of arrivals in a time period t0 follows Poisson distribution with average arrival rate λ
[pic]x = 0, 1, 2 ……..
Service
· Single serve channel/Multiple channels
· Single queue/Infinite capacity
Pattern discipline
· First come first serve
Note: When the number of arrivals follows Poisson distribution (discrete), the inter-arrival time; that is the time between arrivals follows exponential distribution (continuous).
8.7.2 Notations
The queuing systems with which you are concerned are denoted by M/M/1 and M/M/c where Ms stand for exponential inter arrival and exponential service time distributions, and the third figure indicates the number of channels (or servers) available (1 or c).
Here is a list of notations which are commonly used.
[pic]
Self Assessment Questions
Fill in the blanks:
13. E (m) refers to ________ _________ ________ _________.
14. Probability density function of the time spent by a customer in the system is denoted by _____________.
15. ___________ arrivals are allowed.
8.8 Single Channel Models
The formulae are listed in tables 8.2 and 8.3. The examples illustrate the computation of various measures of efficiency of a queuing system, but give an idea of the areas of application as well.
Table 8.2: Formulae for Poisson Arrivals, Exponential Service, Single Channel Queuing Models – Infinite Population
[pic]
Table 8.3: Formulae for Poisson Arrivals, Exponential Service, Single Channel Queuing Models – Number of customers linked to N.
[pic]
Solved Problem 1:
Patrons arrive at a small post office at the rate of 30 per hour. Service by the clerk on duty takes an average of 1 minute per customer
a) Calculate the mean customer time
(i) Spent waiting in line
(ii) Spent receiving or waiting for service
b) Find the mean number of persons
(i) In line
(ii) Receiving or waiting for service
Solution:
Mean arrival rate l = 30 customers per hour
= [pic]customer per minute
Mean service rate [pic]= 1 per minute
Traffic intensity [pic]
(a) (i) Mean customer time spent waiting in line minute
[pic]
(ii) Mean customer time receiving or waiting for service
[pic]= 2 minutes
(b) (i) Mean number of persons in line
[pic]customer
(ii) Mean number of persons receiving or waiting for service
[pic]customer
Solved Problem 2:
The Tool Company’s quality control department is manned by a single clerk, who takes an average of 5 minutes in checking parts of each of the machines coming for inspection. The machines arrive once in every 8 minutes on the average. One hour of machine is valued at Rs. 15 and a clerk’s time is valued at Rs. 4 per hour. What is the average hourly queuing system costs associated with the quality control department?
Solution:
Mean arrival rate l = 1/8 per minute = [pic]per hour
Mean service rate p[pic]er minute = 12 per hour
Average time spent by a machine in the system E (v) = [pic]= [pic]hours
Average queuing cost per machine is [pic]
An average arrival of[pic] machines per hour costs [pic]
= Rs. 25 per hour
Average hourly queuing cost = Rs. 25
Average hourly cost for the clerk = Rs. 4
Hence total hourly cost for the department = Rs. 29
[pic]
[pic]
[pic]
Self Assessment Questions
Fill in the blanks:
16. The expected number of customers in non empty queue is given by ___________.
17. The probability that an arriving customer has to wait for receiving service is given by ___________.
8.9 Multiple Service Channels
The analysis of systems involving several service channels is more complex. The major practical utility of these models are the ways of improving to provide additional service facilities. The list of formulae to be used is given in table below followed by few examples.
Table 8.4: Formulae for Poisson Arrivals, Exponential Service Multi channel Queuing Models – Infinite Population
[pic]
[pic]
[pic]
[pic]
[pic]
Self Assessment Questions
Write the formula :
18. Expected number of customers in the system.
19. Average waiting time of the customer in the queue.
8.10 Erlang Family of Distribution of Service Times
The queuing processes discussed till now are mathematically simple. Assuming that the service time follows negative exponential distribution, you are also taking the standard deviation equal to its mean. There would be situations, where the mean and the standard deviation substantially differ, the models have to be made more general by using a distribution system, which coincide closely to the practical problems, but yet retains the simplicity of the properties of negative exponential distribution. A.K. Erlang first studied such a distribution system.
Consider the distribution of a service time involving a fixed number of phase’s k, each phase having a negative exponential distribution. If there are k phases, and the average time taken by a customer through each phase is [pic]units, the service time distribution f (t) is given by
[pic]
The mean of this distribution is [pic]and standard deviation is [pic].
If k = 1, f (f) = me–m1 which is the negative exponential distribution; same as the models considered earlier.
For k = 2, f (f) = 4m 2te – 2 m f and so on.
The mode is located at t = [pic].
If k = ¥ the variance is zero and this corresponds to a case where the service time is constant and has value [pic].
The figure below shows the way the density functions vary as k increases.
[pic]
Figure 8.1: Density functions vary as k increases
The measures of efficiency should take into account the number of customers getting service, number having entered during any one or more of the phases, and the number yet to join. For arrivals following Poisson distribution, with mean l and service time following the kth Erlang distribution with mean, [pic]the formulae applicable are given below.
Average queue length [pic]
Average number of units in the system [pic]
Average waiting time [pic]
Average time spent in the system [pic]
For constant service time, equating k to ¥
[pic]
[pic]
Self Assessment Questions
Write the formula for:
20. E (m)
21. E (w)
8.11 Summary
The waiting line theory or queuing theory analysis suggests the number of facilities required and the cost of customers waiting time and the optimum service level. The queuing theory contributes vital information required for balancing the cost of service and cost associated with waiting time of the customer. This unit discusses all the different models used under different conditions.
8.12 Terminal Questions
1. If in a particular single-server system, the arrival rate, l = 5 per hour and service rate, m = 8 per hour. Assuming the conditions for use of the single channel queuing model, find out:
a. The probability that the server is idle.
b. The probability that there are at least two customers in the system.
c. Expected time that a customer is in the queue.
2. Customers arrive at the first class ticket counter of a theatre at a rate of 12 per hour. There is one clerk serving the customers at a rate of 30 per hour. Assuming the conditions for use of the single – channel queuing model, evaluate:
a. The probability that an arriving customer has to wait for the service.
b. The expected number of customers in the system.
c. The average waiting time of the customer in the system.
3. In a bank, every 15 minutes, one customer arrives for cashing the cheque. The clerk takes 10 minutes to service. Assuming the usual conditions find.
a. The ideal time of the clerk in 8 working hours.
b. Expected no. of customers in the queue.
c. The probability that a customer has to wait for 15 minutes or more to receive the service.
8.13 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. False
2. True
3. False
4. Utilization
5. Various alternatives
6. Simulation
7. Yes
8. Yes
9. Series, parallel
10. Constant, varying
11. Jockeying
12. Balancing
13. Average length of queue
14. F (µ)
15. Simultaneous
16. m / m – l
17. l / µ
18. Refer to section 8.9
19. Refer to section 8.9
20. Refer to section 8.10
21. Refer to section 8.10
Answers to Terminal Questions
1. a) 3 /8 b)125 / 512 c)12.5 minutes
2. a) 3 /5 b) 2 / 3 per hour c) 10 /3 minutes
3. a) 8 /3 hrs b) 4 /3 c) 0.4043
8.14 References
No external sources of content have been referred for this unit.
Copyright © 2009 SMU
Powered by Sikkim Manipal University
.
MB0048-Unit-09-Finite Queuing Models
Unit-09-Finite Queuing Models
Structure:
9.1 Introduction
Learning objectives
9.2 Finite Queuing Models
Finite queuing tables
Measures of system efficiency
Use of finite queuing tables
9.3 Summary
9.4 Terminal Questions
9.5 Answers to SAQs and TQs
Answers to self assessment questions
Answers to terminal questions
9.6 References
9.1 Introduction
Welcome to unit nine of Operations Research Management on Finite Queuing Models. The models discussed so far relate to situations involving infinite population of customers, that is, the queue can increase indefinitely. However, you may come across scenarios where the possible number of arrivals is limited and small. In this unit, we will discuss such scenarios.
In a production shop, if the machines are considered as customers requiring service from repair crews or operators, the population is restricted to the total number of machines in the shop. In a hospital ward, the probability of the doctors or nurses being called for service is governed by the number of beds in the ward. Similarly, in an aircraft the number of seats is finite and the number of stewardesses provided by the airlines will be based on the consideration of the maximum number of passengers who can demand service.
In case of a queuing system with infinite population, you can improve the efficiency of the system in terms of reduced average length of queues, average waiting time and time spent by the customer in the system. To do this, you need to increase the number of service channels. However, such increases mean additional cost and will have to be balanced with the benefits likely to accrue. If the queuing system in a machine shop is under study, the cost of providing additional maintenance crews or operators can be compared with the value of additional production due to reduced downtime of the machines. Sometime it is not possible to quantify the benefits, the management will have to base its decisions on the desired standards for customer service.
Learning objectives
By the end of this unit, you should be able to:
· Describe queuing models and various queuing disciplines
· Interpret and apply finite queuing tables to solve problems
9.2 Finite Queuing Models
Basic concept of queuing models
You use a queuing model to approximate a real queuing situation or system, so that you can analyse the queuing behaviour mathematically. Queuing models allow you to determine a number of useful steady state performance measures. These measures are:
· Average number in the queue, or the system
· Average time spent in the queue, or the system
· Statistical distribution of those numbers or times
· Probability of the queue being empty or full
· Probability of finding the system in a particular state
Analysis of the relevant queuing models allows you to identify the cause of a queuing issue and assess the impact of the proposed changes. Typically, you need to analyse a queuing model to minimise the sum of:
· Customer waiting cost
· Service capacity cost
In a finite queuing model, the system processes incoming requests or messages at a certain rate. Any newly arrived request or message is added to the queue only if the number of requests or messages waiting in the queue is less than the maximum.
The model is based on the following assumptions:
· The number of requests/messages in the queue uniquely characterises the state of the queue.
· Each source has a well-defined arrival pattern over time, i.e., inter-arrival or interval times are constant or randomly spaced over time with a known inter-arrival time probability distribution (Poisson distribution).
· The service times at each channel may be constant or random with a known service distribution (negative exponential distribution).
· The potential arrivals may balk if the length of waiting line becomes excessive and decide not to join or arrivals may join the waiting line and subsequently renege, i.e., become impatient and leave before being served. They are lost by the service system.
· In a steady state, the average rate of departure is equal to average rate of arrivals.
A queue is characterised by the maximum permissible number of customers that it can contain. This also could be finite or infinite. In most of the practical situations, it is finite. Queuing discipline determines the manner in which the system handles calls from the customers. It defines the way in which they are served, the order in which they are served, and the way in which resources are divided between the customers.
A finite queuing process may follow any of the following queuing disciplines.
[pic]
Fig. 9.1: Queue discipline route in a finite queuing process
i. First come-first served (FIFS): This principle states that customers are served one at a time and that the customer that has been waiting the longest is served first. In most queuing models, the order is usually first come-first served.
ii. Priority: Priority-discipline models give priority to rush jobs and important customers over others. For instance, machines of high cost may be given priority for maintenance while others may be kept waiting even if they had broken down before.
iii. Random: The principle states that the system may randomly select a customer for service. For example, in a machine shop if a single operator is attending to several machines and several machines call for his attention at a time, he may attend first to the one nearest to him.
iv. Last Come-First Served (LIFS): This discipline is based on the stack method.
Most quantitative parameters, such as the average queue length and average time spent in the system do not depend on the queuing discipline. That’s why most models either do not take the queuing discipline into account at all or assume the normal FIFS queue. The only parameter that depends on the queuing discipline is the variance (or standard deviation) of the waiting time.
The analysis of finite queuing models is more complex than those with infinite population although the approach is similar. L.G. Peck and R. N. Hazelwood have provided solutions to such problems in their book “Finite Queuing Tables” (John Wiley & Sons Inc – 1958).
Simple Waiting Line Model
The simplest waiting line model assumes that arrivals join a queue that is of unlimited size, waiting in line until their turn for service comes on a first-cum-first-serve basis and then enter a service facility consisting of a single channel.
If, W = Average time spent in queue (i.e., sum of the expected waiting time and expected service time) = Average rate of units passing through the system per unit λ time L = Average number of units in the system
Then, L= λ W
If μ = Average service rate
1/ λ = Expected inter arrival time
1/μ = Expected service time
Further, the utilisation factor, ρ (i.e. the expected fraction of time the server is busy is given by:
ρ = λ / sμ
Where, (s μ) is the fraction of the system’s service capacity that being utilised on the average by arriving customers Cλ)
The crux of the queuing theory is to ‘achieve a trade off between excessive waiting by customers (i.e., too much demand) and cost due to excessive idle time at the service facility (i.e., too little demand). Lending system in a library is an example of single facility channel waiting line.
9.2.1 Finite queuing tables
Given below are different notations used in finite queuing tables:
Consider a machine shop with N machines. The inter breakdown time of these machines follows a negative exponential distribution with mean U. The number of breakdowns follows Poisson distribution with mean [pic]
[pic]
Fig. 9.2: Notations used in finite queuing tables
It is assumed that machines are kept running (or in operation) all the time, except when in repairs or waiting for repair crew to attend. If M repair crews are available, the time taken by any crew follows a negative exponential distribution with mean T. Naturally, a machine which has broken down will have to wait for repairs if all the repair crews are busy.
9.2.2 Measures of system efficiency
For a given set of machines, the efficiency of the repair system may be judged by the extent to which machines have to wait for repairs. If W is the average time for which a machine has to wait, the efficiency factor F is defined as
[pic]
At any point of time, a machine will either be running or under repair or waiting for repairs. Therefore, the total number of machines N = J + H + L.
[pic], correspond to the probability that a machine is being
repaired, running or waiting for repairs respectively. In the finite queuing tables, service factor X is defined as [pic]. X is an indicator of the utilisation of repair crew.
The formulae for other properties of the system are given below:
[pic]
9.2.3 Use of finite queuing tables
The above table gives values of F and D for different values of N, M and X. They are arranged in the ascending order of the values of the population. For each N, the value of X increases from .001 to .950. For a given service factor X, several values of M can be found. For each value of X and M, values of D and F are tabulated. The steps for finite queuing tables are as follows:
i) Find mean service time T and mean running time U.
ii) Compute the service factor.
iii) Select the table corresponding to the population N.
iv) For the given population, locate the service factor value.
v) Read off from tables, values of D and F for the number of service crews M.
vi) If necessary, these values may be interpolated between relevant values of X.
vii) Calculate the other measures L, W, H, and J from the formulae given.
[pic]
Figure 9.3: Finite queuing tables steps
The overall efficiency F of the system will increase with the number of service channels (M) provided. As mentioned earlier, addition of service crews involves cost, which should be justified by the increase in the efficiency of the system that is additional running time of machines. However, it will be seen from the table that as M increases the rate of increase in efficiency decreases. The practical significance is that beyond a certain value of M, it is not worthwhile increasing M as there would be no appreciable increase in the efficiency of the system.
|Caselet |
|In a chemical factory, there are five hoppers of identical size which feed material to grinding mills. Due to |
|changes in the requirement of material, there are variations in the time taken for emptying the hoppers. On |
|the basis of past experience, it was found to follow negative exponential distribution with an average of 10 |
|hours between getting emptied. Whenever a hopper gets empty, it has to be filled by a pay loader. Although the|
|capacity of the hopper is the same, the time taken to fill the hoppers varies due to different locations from |
|where the material is to be loaded. |
|The time for filling the hopper also was found to follow negative exponential distribution with an average of |
|2.5 hours. The company hires the pay loaders at a cost of Rs. 100 per hour irrespective of whether it is |
|operated or not. If the mill has to be stopped due to the empty hopper, it costs Rs. 1000 per hour in terms of|
|loss of profits. To determine the number of pay loaders which the company should engage to minimise overall |
|cost you need to create a finite queuing table. |
[pic]
Self Assessment Questions
True or False
1. When the possible number of arrivals is limited, then we apply infinite queuing model.
2. The queue discipline in a finite queuing process can be random.
3. The efficiency factor for this model is HJ / H + J + L.
9.3 Summary
This unit on finite queuing theory deals with situations where customers arrive, wait for the service, get the service and leave the system. Customers may come individually or in groups from large/small population, at known/variable times, form one or more queues and move in a certain order to the service station(s) to avail of services whose speed may be fixed or variable. Queuing systems are analysed for determining the optimal service level, where the total cost of providing service and waiting, is minimised. An increase in the service level increases the cost of providing service, but reduces the cost of waiting, while a decrease in the service level induces opposite changes.
9.4 Terminal Questions
1. Customers arrive at the first class ticket counter of a theatre at a rate of 12 per hour. There is one clerk serving the customers at a rate of 30 per hour.
i) What is the probability that there is no customer in counter (for instance, the system is idle)?
ii) What is the probability that there are more than 2 customers in the counter?
iii) What is the probability that there is no customer waiting to be served?
iv) What is the probability that a customer is being served and nobody is waiting?
2. Assume that at a bank teller window, the customers arrive in their cars at the average rate of twenty per hour according to the Poisson distribution. Also assume that the bank teller spends an average of two minutes per customer to complete a service, and the service time is exponentially distributed. Customers, who arrive from an infinite population, are served on a first come first served basis and there is no limit to possible queue length.
i) What is the expected waiting time in the system per customer?
ii) What is the mean number of customers waiting in the system?
iii) What is the probability of zero customers in the system?
iv) What value is the utilisation factor?
9.5 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. False
2. True
3. False
Answers to Terminal Questions
1.
i. P (the system is idle) = 1- r = 1-0.4 = 0.6.
ii. P (n > 2) = 1 – P (n £ 2) = 1 – [P (0) + P (1) + P (2)] = 1- 0.936 = 0.064.
iii. P (no customer waiting to be served) = P (0) + P (1) = 0.84.
iv. P (a customer is being served and none is waiting) = P (1) = 0.24.
2.
i. Expected waiting time in the system per customer,
Ws = 1/ (m-l) = 1/ (30-20) =1/10 hr.
ii. Mean number of customers waiting in the system,
Lq =[pic].
iii. Probability of zero customers in the system,
P (0) = [pic].
iv. Utilisation factor, [pic]
9.6 References
The following external sources have been referred to for additional content for unit 9:
·
·
·
·
Copyright © 2009 SMU
Powered by Sikkim Manipal University
.
MB0048-Unit-10-Simulation
Unit 10 Simulation
Structure:
10.1 Introduction
Learning objectives
10.2 Basic Concepts
10.3 Simulation Procedure
Allocation of random numbers
Use of random number tables
10.4 Sample Size
10.5 Application of Simulation
Limitations
Solved problems
10.6 Summary
10.7 Terminal Questions
10.8 Answers to SAQs and TQs
Answers to self assessment questions
Answers to terminal questions
10.9 Reference
10.1 Introduction
Welcome to the tenth unit of Operations Research Management on Simulation.
While formulating mathematical models of various systems or situations, the statistical distribution of the variables conform to a standard pattern. However, it is not always true. In a typical pricing problem, the management cannot risk changing the price of the product without evaluating the various alternatives. Representing the terms of a mathematical model is virtually impossible because of the complexity of the interaction of several variables having a bearing on the final outcome. One of the approaches to the problem is to assign probabilities of achieving various sales targets under different conditions of completion. These different conditions may be related to changes in price, demand and choose the alternative giving the maximum profit. Where formulating a mathematical model is difficult, simulation is of great help for decision making.
Learning objectives
By the end of this unit, you should be able to:
· Define simulation
· Demonstrate the application of simulations in business problems
· Describe the Monte Carlo Method
10.2 Basic Concepts
Simulation is also called experimentation in the management laboratory. While dealing with business problems, simulation is often referred to as ‘Monte Carlo Analysis’. Two American mathematicians, Von Neumann and Ulan, in the late 1940s found a problem in the field of nuclear physics too complex for analytical solution and too dangerous for actual experimentation. They arrived at an approximate solution by sampling. The method they used had resemblance to the gambler’s betting systems on the roulette table, hence the name ‘Monte Carlo’ has stuck.
Imagine a betting game where the stakes are based on correct prediction of the number of heads, which occur when five coins are tossed. If it were only a question of one coin; most people know that there is an equal likelihood of a head or a tail occurring, that is the probability of a head is ½. However, without the application of probability theory, it would be difficult to predict the chances of getting various numbers of heads, when five coins are tossed.
Why don’t you take five coins and toss them repeatedly. Note down the outcomes of each toss after every ten tosses, approximate the probabilities of various outcomes. As you know, the values of these probabilities will initially fluctuate, but they would tend to stabilise as the number of tosses are increased. This approach in effect is a method of sampling, but is not very convenient. Instead of actually tossing the coins, you can conduct the experiment using random numbers. Random numbers have the property that any number is equally likely to occur, irrespective of the digit that has already occurred.
Let us estimate the probability of tossing of different numbers of heads with five coins. We start with set random numbers given below:
Table 10.1: Random number set
|78466 |71923 |
|78722 |78870 |
|06401 |61208 |
|04754 |05003 |
|97118 |95983 |
By following a convention that “even” digits signify a head (H) and the “odd” digits represent a tail (T), the tossing of a coin can be simulated. The probability of occurrence of the first set of digits is ½ and that of the other set is also ½ - a condition corresponding to the probability of the occurrence of a head and the probability of occurrence of a tail respectively.
It is immaterial as to which set of five digits should signify a head. The rule could be that the digits 0, 1, 2, 3 and 4 represent a head and the digits 5, 6, 7, 8 and 9 a tail. It is only necessary to take care that the set of random numbers allotted to any event matches with its probability of occurrence. For instance, if you’re interested in allotting random numbers to three events A, B and C with respective probabilities 0.24, 0.36 and 0.40, choose two digit random numbers 00 to 99.
The numbers 00 to 23 signify event A, 24 to 59 signify B and 60 to 99 signify C. The first set of five random digits in the list of random numbers implies that the outcome of the first toss of 5 coins is as follows:
Table 10.2: Outcome of first toss of 5 coins
|Coin |1 |2 |3 |4 |5 |
|Random Number |7 |8 |4 |6 |6 |
|Outcome |T |H |H |H |H |
Hence it is 4 heads and 1 tail.
Proceeding in the same way, you can tabulate the results of the first ten tosses.
Table 10.3: Results of first ten tosses
[pic]
Based on the ten tosses of the coins, the estimates of probabilities of occurrence of different numbers of heads are:
[pic]
Continue experimenting further, as these estimates come closer to the theoretical value with increasing sample size.
The results for obtaining 2 heads and 3 tails for 100 throws are shown below:
Table 10.4: Results for 100 throws
|10 throws |0 |
|20 throws |6 |
|30 throws |11 |
|40 throws |14 |
|50 throws |18 |
|60 throws |19 |
|70 throws |21 |
|80 throws |22 |
|90 throws |24 |
|100 throws |27 |
Table 10.5 compares the final results at the end of 100 throws with the theoretical probabilities.
Table 10.5: Final results at the end of 100 throws
|No. of heads |Estimated Probability |Theoretical Probabilities |
|0 |0.03 |0.03 |
|1 |0.21 |0.16 |
|2 |0.27 |0.31 |
|3 |0.33 |0.31 |
|4 |0.12 |0.16 |
|5 |0.04 |0.03 |
It is observed that the results obtained with the large sample of 100, when compared are more in favour with the theoretical values than with a sample of ten sets of numbers.
Self Assessment Questions
Fill in the blanks
1. Simulation may be called experimentation in the _________ _______.
2. Random numbers have the property that any number has ____to occur.
3. The totality of probability assigned to the variable should always be equal to _______.
10.3 Simulation Procedure
The approach to solve a gambling problem can be extended to decision-making in business where risk is a common feature. The probabilities associated with the variables can be estimated on the basis of availability of previous data or by inputting subjective values.
In any simulation problem, the variables to be studied will be given with associated probabilities. The initial conditions will also be specified. You can choose random numbers from table. However, to get uniform results, the random numbers will be specified. The first step involves coding the data that is, you assign random numbers to the variable. Then you identify the relationship between the variables and run the simulation to get the results
Let us illustrate this by a simple example of a queuing process.
[pic]
10.3.1 Allocation of random numbers
The following tables show the allocation of random numbers based on time between arrivals and service time.
Table 10.8 Allocation of random number – time between arrivals
[pic]
Table 10.9 Allocation of random numbers – service time
|Service |Frequency |Cumulative |Cumulative |Random Nos. |
|Time |(2) |Frequency |Probability |Allocated |
|(1) | |(3) |(4) |(5) |
|0.5 |12 |12 |0.12 |00 to 11 |
|1.0 |21 |33 |0.33 |12 to 32 |
|1.5 |36 |69 |0.69 |33 to 68 |
|2.0 |19 |88 |0.88 |69 to 87 |
|2.5 |7 |95 |0.95 |88 to 94 |
|3.0 |5 |100 |1.00 |95 to 99 |
Note that the upper bound of random numbers allocated for each value of the parameter is one less than the corresponding cumulative frequency, since you have chosen a range of random numbers from 00 to 99
Table 10.10 Arrival and service time
[pic]
The service facility is made available at clock time zero and the server has to be idle for 3.5 minutes, when the service for first arrival starts. The service is completed at 5.0 minutes and again the server is idle for 2 minutes till the second arrival joins the system. The first three arrivals get immediate service and they don’t have to wait, as the server is idle when they arrive. The fourth arrival that joins at 9.0 minutes has to wait for 0.5 minute, while the service to the third is completed. Similarly the waiting time and idle time can be computed for further arrivals.
Total elapsed time = 29 minutes
Waiting time of arrival = 1 minute
Percentage of waiting time = [pic]
Idle time for server = 14.5 minutes
Percentage of idle time = [pic]
10.3.2 Use of random number tables
The random numbers can be selected by any random process, similar to drawing numbered chips from a hat. However, it is convenient to use a table of random numbers prepared on the basis of some physical phenomenon. The grouping of random numbers in the tables has no significance and one should be concerned with individual digits only. The first random number could be picked at random from any point in the tables and the subsequent ones are to be selected proceeding sequentially either in a vertical or horizontal direction. Depending upon the number of digits required, the random numbers will be chosen in sets of single digit or two–digit numbers, that is pseudo–random numbers
Truly random numbers cannot be produced by an algorithm and hence random numbers generated using recursive equations are referred to as pseudo–random numbers.
There are several methods of generating pseudo–random numbers, but you will briefly learn only the mid square method. Operation starts with an arbitrary four digit integer called the seed. To obtain the first random number, the seed is squared and all digits except the middle four are ignored. This process is repeated each time using the previous random number as the new seed.
Seed [pic]= 8695
[pic]
= 75603025
Taking the middle 4 digits,
[pic]= 6030
[pic]= 36360900
[pic]= 3609
Repeating the above procedure:
[pic]
[pic]
One of the disadvantages of the mid square method is that the generated numbers start cycling after a short set of random numbers is obtained.
There are methods by which the seed can be chosen to obtain a fairly long sequence of numbers before cycling starts. Statistical tests check whether the generated sequence is truly random.
Self Assessment Questions
True or False:
4. In any simulation problem, initial conditions are stated.
5. Random numbers are assigned for cumulative probability values.
6. Without identifying any relationship between variables, you can solve the simulation problem.
10.4 Sample Size
As you have seen with the coin-tossing experiment, the larger the number of trials, the more confident you can be in your estimates. The question that arises is “how many trials for simulation?” If the experiment is as simple as tossing a coin involving only one variable, you can work out the sample size required for a given confidence level.
[pic]
Usually, a simulation model involves several variables making it impossible to determine the number of trials required to obtain the desired accuracy at a specified confidence level.
One can only say that the accuracy associated with simulation improves as the square root of the number of trials, which results in large number of trials.
This requires a great deal of computational effort and the use of computer becomes inevitable. In fact, special simulation languages such as GPSS and SIMSCRIPT have been developed to save time and effort required to structure and debug simulation models.
A practical indicator of when to stop simulation trials is when the results that violently fluctuate initially tend to stabilise if the simulation is continued. If the successive cumulative results tally reasonable well, the simulation may be stopped. The degree of accuracy required varies with the problem on hand and calls for analyst judgment.
Self Assessment Questions
True or False:
7. Standard error for percentage of success = (P (1-P) / N) 1/2.
8. It is possible to determine the number of trials.
9. The accuracy of results increases as the square of number of trials.
10.5 Application of Simulation
The range of application of simulation in business is extremely wide. Unlike other mathematical models, simulation can be easily understood by the users and thereby facilitates their active involvement. This makes the results more reliable and also ensures easy acceptance for implementation. The degree to which a simulation model can be made close to reality is dependent upon the ingenuity of the OR team who identifies the relevant variables as well as their behaviour.
You have already seen by means of an example how simulation could be used in a queuing system. It can also be employed for a wide variety of problems encountered in production systems – the policy for optimal maintenance in terms of frequency of replacement of spares or preventive maintenance, number of maintenance crews, number of equipment for handling materials, job shop scheduling, routing problems, stock control and so forth. The other areas of application include dock facilities, facilities at airports to minimise congestion, hospital appointment systems and even management games.
In case of other OR models, simulation helps the manager to strike a balance between opposing costs of providing facilities (usually meaning long term commitment of funds) and the opportunity and costs of not providing them.
10.5.1 Limitations
The simulation approach is recognised as a powerful tool for management decision-making. One should not ignore the cost associated with a simulation study for data collection, formation of the model and the computer time as it is fairly significant.
A simulation application is based on the premise that the behaviour pattern of relevant variables is known, and this very premise sometimes becomes questionable. Not always can the probabilities be estimated with ease or desired reliability. The results of simulation should always be compared with solutions obtained by other methods wherever possible, and “tempered” with managerial judgment.
10.5.2 Solved problems
[pic]
[pic]
[pic]
[pic]
[pic]
[pic]
Self Assessment Questions
True or False:
10. Simulation gives optimum solution.
11. Simulation interrupts real system activities.
12. This technique can be easily understood by non-technical managers.
10.6 Summary
This unit explains the basic concepts concerned with simulations and simulation procedures. The unit explains allocation of random numbers with the use of random number tables, the sample size and the application of simulation.
10.7 Terminal Questions
1. Briefly write down the basic concepts concerned with simulation.
2. What do you mean by simulation procedure?
3. Briefly explain the use of random number tables.
4. Discuss the different applications of simulation.
5. Two components have to be produced in M/C A and M/C B and then finally assembled. The time taken to assemble on two machines varies with the following probability distribution. Using simulation technique and the ordered pair of random numbers, first for M/C A and second for M/C B, find the average time taken for production.
[pic]
Random Numbers (10, 92); (25, 83); (36, 76); (44, 15); (57, 25); (62, 67); (04, 99); (72, 53); (81, 35); (94, 07)
10.8 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. Management laboratory
2. Equally likely
3. 1
4. True
5. True
6. False
7. Agree
8. Agree
9. Disagree
10. False
11. False
12. True
Answers to Terminal Questions
1. Refer to section 10.2
2. Refer to section 10.3
3. Refer to section 10.3.3
4. Refer to section 10.5
5. 57.7 minutes
10.9 Reference
No external sources of content have been referred for this unit.
About the Author
[pic]
admin
Copyright © 2010 SMU.
Powered by WordPress.
MB0048-Unit-11- Project Scheduling and PERT-CPM
Unit-11- Project Scheduling and PERT-CPM
Structure:
11.1 Introduction
Learning objectives
11.2 Basic Difference between PERT and CPM
PERT
CPM
Project scheduling by PERT-CPM
11.3 PERT/CPM Network Components and Precedence Relationship
Critical path calculations
Determination of the critical path
Determination of floats
11.4 Project Management – PERT
11.5 Summary
11.6 Terminal Questions
11.7 Answers to SAQs and TQs
Answers to Self Assessment Questions
Answers to Terminal Questions
11.8 References
11.1 Introduction
Welcome to the unit on Project Scheduling and PERT-CPM in Operations Research Management.
Some projects may be defined as a collection of inter-related activities (or tasks) which must be completed in a specified time according to a specified sequence and require resources, such as personnel, money, materials, facilities etc. Some examples of such projects are construction of a bridge, a highway, a power plant, repair and maintenance of an oil refinery or designing of an air plane, development and marketing of a new product, and research and development.
The growing complexities of today’s projects had demanded more systematic and more effective planning techniques with the objective of optimising the efficiency of executing the project. Efficiency here refers to effecting the utmost reduction in the time required to complete a project while ensuring optimum utilisation of the available resources.
Project management has evolved as a new field with the development of two analytic techniques for planning, scheduling and controlling projects. These are the Critical Path Method (CPM) and the Project Evaluation and Review Technique (PERT). PERT and CPM are basically time-oriented methods in the sense that they both lead to the determination of a time schedule.
Learning objectives
By the end of this unit, you should be able to:
· Define a project
· Describe project management
· Apply PERT-CPM method to network analysis
11.2 Basic Difference between PERT and CPM
Though there are no essential differences between PERT and CPM as both of them share in common the determination of a critical path. Both are based on the network representation of activities and their scheduling that determines the most critical activities to be controlled so as to meet the completion date of the project.
11.2.1 PERT
Some key points about PERT are as follows:
1. PERT was developed in connection with an R&D work. Therefore, it had to cope with the uncertainties that are associated with R&D activities. In PERT, the total project duration is regarded as a random variable. Therefore, associated probabilities are calculated so as to characterise it.
2. It is an event-oriented network because in the analysis of a network, emphasis is given on the important stages of completion of a task rather than the activities required to be performed to reach a particular event or task.
3. PERT is normally used for projects involving activities of non-repetitive nature in which time estimates are uncertain.
4. It helps in pinpointing critical areas in a project so that necessary adjustment can be made to meet the scheduled completion date of the project.
11.2.2 CPM
1. CPM was developed in connection with a construction project, which consisted of routine tasks whose resource requirements and duration were known with certainty. Therefore, it is basically deterministic.
2. CPM is suitable for establishing a trade-off for optimum balancing between schedule time and cost of the project.
3. CPM is used for projects involving activities of repetitive nature.
11.2.3 Project scheduling by PERT-CPM
It consists of three basic phases: planning, scheduling and controlling.
[pic]
Figure 11.1: Phases of PERT-CPM
1. Project Planning: In the project planning phase, you need to perform the following activities:
[pic]
Figure 11.2: Activities in project planning phase
i) Identify various tasks or work elements to be performed in the project.
ii) Determine requirement of resources, such as men, materials, and machines, for carrying out activities listed above.
iii) Estimate costs and time for various activities.
iv) Specify the inter-relationship among various activities.
v) Develop a network diagram showing the sequential inter-relationships between the various activities.
2. Project Scheduling: Once the planning phase is over, scheduling of the project is when each of the activities required to be performed, is taken up. The various steps involved during this phase are listed below:
1. Estimate the durations of activities. Take into account the resources required for these execution in the most economic manner.
2. Based on the above time estimates, prepare a time chart showing the start and finish times for each activity. Use the time chart for the following exercises.
· To calculate the total project duration by applying network analysis techniques, such as forward (backward) pass and floats calculation
· To identify the critical path
· To carry out resource smoothing (or levelling) exercises for critical or scarce resources including re-costing of the schedule taking into account resource constraints
3. Project Control: Project control refers to comparing the actual progress against the estimated schedule. If significant differences are observed then you need to re-schedule the project to update or revise the uncompleted part of the project.
Self Assessment Questions
True or False
1. Project consists of inter-related activities.
2. Project activities are to be completed in a specified time according to a specified sequence.
3. PERT and CPM identifies non-critical activities.
4. PERT is an activity-oriented network.
5. CPM is used for projects that are repetitive in nature.
11.3 PERT/CPM Network Components and Precedence Relationship
PERT/CPM networks consist of two major components as discussed below:
a) Events: An event represents a point in time that signifies the completion of some activities and the beginning of new ones. The beginning and end points of an activity are thus described by 2 events usually known as the tail and head events. Events are commonly represented by circles (nodes) in the network diagram. They do not consume time and resource.
b) Activities: Activities of the network represent project operations or tasks to be conducted. An arrow is commonly used to represent an activity, with its head indicating the direction of progress in the project. Activities originating from a certain event cannot start until the activities terminating at the same event have been completed. They consume time and resource.
Events in the network diagram are identified by numbers. Numbers are given to events such that the arrow head number is greater than the arrow tail number. Activities are identified by the numbers of their starting (tail) event and ending (head) event.
In figure 11.3 the arrow (P.Q) extended between two events represents the activity. The tail event P represents the start of the activity and the head event Q represents the completion of the activity.
[pic]
Figure 11.3: Basic PERT-CPM network
Figure 11.4 is example of another PERT-CPM network with activities (1, 3), (2, 3) and (3, 4). As the figure indicates, activities (1, 3) and (2, 3) need to be completed before activity (3, 4) starts.
[pic]
Figure 11.4: A PERT-CPM network
The rules for constructing the arrow diagram are as follows:
1. Each activity is represented by one and only one arrow in the network.
2. No two activities can be identified by the same head and tail events.
3. To ensure the correct precedence relationship in the arrow diagram, you need to answer the following questions as you add every activity to the network:
a) What activities must be completed immediately before these activity can start?
b) What activities must follow this activity?
c) What activity must occur concurrently with this activity?
This rule is self-explanatory. It actually allows for checking (and rechecking) the precedence relationships as one progresses in the development of the network.
[pic]
Note: A dummy activity in a project network analysis has zero duration.
11.3.1 Critical path calculations
The application of PERT/CPM should ultimately yield a schedule specifying the start and completion time of each activity. The arrow diagram is the first step towards achieving that goal. The start and completion timings are calculated directly on the arrow diagrams using simple arithmetic. The end result is to classify the activities as critical or non-critical.
An activity is said to be critical if a delay in the start of the course makes a delay in the completion time of the entire project.
A non-critical activity is such that the time between its earliest start and its latest completion time is longer than its actual duration. A non-critical activity is said to have a slack or float time.
11.3.2 Determination of the critical path
A critical path defines a chain of critical activities that connects the start and end events of the arrow diagram. In other words, the critical path identifies all the critical activities of a project.
The critical path calculations are done in two phases.
The first phase is called the Forward Pass. In this phase all calculations begin from the start node and move to the end node. At each node a number is computed representing the earliest occurrence time of the corresponding event. These numbers are shown in squares. Here we note the number of heads joining the event. We take the maximum earliest timing through these heads.
The second phase is called the Backwards Pass. It begins calculations from the “end” node and moves to the “start” node. The number computed at each node is shown in a triangle D near the end point, which represents the latest occurrence time of the corresponding event. In backward pass, we see the number of tails and take minimum value through these tails.
Let ESi be the earliest start time of all the activities emanating from event i. Then ESi represents the earliest occurrence time of event i.
If i = 1 is the “start” event then conventionally for the critical path calculations, ESi = 0.
Let Dij be the duration of the activity (i, j).
Then the forward pass calculations for all defined (i, j) activities with ESi=0 is given by the formula:
ESi = maxi {ESi+Dij}
Therefore, to compute ESj for event j, you need to first compute ESi for the tail events of all the incoming activities (i, j).
With the computation of all ESj, the forward pass calculations are completed. The backward pass starts from the “end” event. The objective of the backward pass phase is to calculate LCi, the latest completion time for all the activities coming into the event i.
Thus, if i = n is the end event, LCn = ESn initiates the backward pass.
In general for any node i, you can calculate the backward pass for all defined activities using the formula
LCi = min {LCj-Dij}
You can now identify the critical path activities using the results of the forward and backward passes. An activity (i, j) lies on the critical path if it satisfies the following conditions:
A) ESi = LCi
B) ESj = LCj
C) ESj-ESi = LCj-LCi = Dij
These conditions actually indicate that there is no float or slack time between the earliest stand and the latest start of the activity. Thus, the activity must be critical.
Thus, the activity must be critical. In the arrow diagram these are characterised by same numbers within rectangles and triangles at each of the head and tail events. The difference between the numbers in rectangles or triangles at the head event and the number within rectangles or triangles at the tail event is equal to the duration of the activity. Thus, we will get a critical path, which is a chain of connected activities, spanning the network from start to end.
[pic]
11.3.3 Determination of floats
Following the determination of the critical path, you need to compute the floats for the non-critical activities. For the critical activities this float is zero. Before showing how floats are determined, it is necessary to define two new times that are associated with each activity. These are as follows:
· Latest Start (LS) time and
· Earliest Completion (EC) time
You can define activity (i, j) for these two types of time by
LSij= LCj – Dij
ECij = ESi + Dij
There are two important types of floats namely:
· Total Float (TF)
· Free Float (FF)
The total float TFij for activity (i, j) is the difference between the maximum time available to perform the activity (= LCj – ESi) and its duration (= Dij)
TFij = LCj – ESi– Dij = LCj – ECij = LSij – ESi
The free float is defined by assuming that all the activities start as early as possible. In this case FFij for activity (i, j) is the excess of available time
(= ESi – ESi) over its deviation (= Dij); that is,
FFij = ESi – ESi = Dij
Note: For critical activities float is zero. Therefore, the free float must be zero when the total float is zero. However, the converse is not true, that is, a non-critical activity may have zero free floats.
Let us consider the example taken before the critical path calculations. The floats for the non-critical activities can be summarised as shown in the following table:
Table 11.1: Floats for non-critical activities
[pic]
Note: Total float = ESij = LFij – ESij
Free float = Total float – - Head slack
* Critical activity *
|Caselet |
|A project consists of a series of 10 tasks. Some of these tasks need to be performed in a certain sequence, |
|while some of them can be carried out simultaneously. |
|The tasks are bound by certain constraints, such as; the completion time of the first must be lesser than the|
|second. |
|For a specified time of completion for each task, you can find the minimum time of completion of the project,|
|the critical path, and the total floats of each task using the network analysis diagram and the critical path|
|table. |
[pic]
Self Assessment Questions
Fill in the blanks:
6. Events do not consume ________ and _________.
7. Arrow’s head number is _________ than its tail number.
8. Dummy activity is introduced in a network to keep proper _________ relationship.
9. Critical path calculation includes both _________ and _________.
11.4 Project Management – PERT
Probability and Cost Consideration in Project Scheduling
The analysis in CPM does not take in the cases where time estimates for the different activities are probabilistic. It also does not consider explicitly the cost of schedules. Here we will consider both probability and cost aspects in project scheduling.
Probability considerations are incorporated in project scheduling by assuming that the time estimate for each activity is based on 3 different values. They are as follows:
a = The optimistic time, which will be required if the execution of the project goes extremely well.
b = The pessimistic time, which will be required if everything goes bad.
m = The most likely time, which will be required if execution is normal.
The most likely estimate m need not coincide with the mid-point [pic]of a and b.
Then the expected duration of each activity D can be obtained as the mean of [pic]and 2 m.
Therefore,
[pic]
You can use this estimate to study the single estimate D in the critical path calculation.
The variance of each activity denoted by V is defined by,
Variance V = [pic]
The earliest expected times for the node i is denoted by E(mi). For each node i, E(mi) is obtained by taking the sum of expected times of all activities leading to the node i, when more than one activity leads to a node i, then the greatest of all E(mi) is chosen. Let mi be the earliest occurrence time of the event i, we can consider mi as a random variable. Assuming that all activities of the network are statistically independent, we can calculate the mean and the variance of mi as follows:
E{mi } = ESi and Var{mi } = [pic]
where, k defines the activities along the largest path leading to i.
For the latest expected time, we consider the last node. Now for each path move backwards and substitute the [pic]for each activity (i, j).
Thus we have,
E(Lj) = E(ma)
E(mi) = L(Lj) – Dij
if only one path events from j to i or if it is the minimum of {E[Lj) – Dij] for all j for which the activities (i, j) is defined.
Note: The probability distribution of times for completing an event can be approximated by the normal distribution due to central limit theorem.
Since mi represents the earliest occurrence time, event will meet a certain schedule time STi (specified by an analyst) with probability
Pr (mi £ STi) = Pr [pic]
= Pr (Z £ Ki)
where, Z ~N(01) and Ki = [pic]
It is a common practice to compute the probability that event i will occur no later than its LCe. Such probability will represent the chance that the succeeding events will occur within the (ESe, LCe) duration.
[pic]
Self Assessment Questions
True or False
10. In a project network, a sequence of activities may form a loop.
11. A critical activity must have its total and free floats equal to zero.
12. A non-critical activity cannot have zero total float.
13. The critical path of project network represents the minimum duration needed to complete the network.
14. A network may include more than one critical path.
11.5 Summary
Critical path computations are quite simple, yet they provide valuable information that simplifies the scheduling of complex projects. The result is that PERT-CPM techniques enjoy tremendous popularity among practitioners in the field. The usefulness of the techniques is further enhanced by the availability of specialised computer systems for executing, analysing and controlling network projects.
11.6 Terminal Questions
1. Write down the basic difference between PERT and CPM.
2. Explain project management (PERT).
3. A project has 10 activities. The following table shows the information about the activities.
Table 11.5: Activities information
|Activity |Preceding activity |Duration in weeks |
|A |– |6 |
|B |– |3 |
|C |A |5 |
|D |A |4 |
|E |A |3 |
|F |C |3 |
|G |D |5 |
|H |B, D, E |5 |
|I |H |2 |
|J |I, G, F |3 |
a. Draw the network
b. Find the project duration
c. Identify the CPM
d. Prepare the schedule
4. A small project consisting of eight activities has the following characteristics:
Table 11.6: Time estimates (in weeks)
|Activity |Preceding activity |Most optimistic time |Most likely time (m) |Most pessimistic |
| | |(a) | |time (b) |
|A |None |2 |4 |12 |
|B |None |10 |12 |26 |
|C |A |8 |9 |10 |
|D |A |10 |15 |20 |
|E |A |7 |7.5 |11 |
|F |B, C |9 |9 |9 |
|G |D |3 |3.5 |7 |
|H |E, F, G |5 |5 |5 |
a. Draw the PERT network for the project.
b. Determine the critical path.
c. If a 30-week deadline is imposed, what is the probability that the project will be finished within the time limit?
d. If the project manager wants to be 99% sure that the project is completed on this schedule date, how many weeks before that date should he start the project work?
11.7 Answers to SAQs and TQs
Answers to Self Assessment Questions
1. True
2. True
3. True
4. False
5. True
6. Time, resource
7. Greater than
8. Precedence
9. Forward pass & backward pass
10. False
11. True
12. True
13. True
14. False
Answers to Terminal Questions
1. Refer to section 11.2
2. Refer to section 11.4
3. b) 20 weeks c) A – D – H – I – J
4. b) A – D – G – H c) 0.6591 d) 34.7 weeks
11.8 References
No external sources have been referred for this unit.
Copyright © 2009 SMU
Powered by Sikkim Manipal University
.
MB0048-Unit-12-Game Theory
Unit-12-Game Theory
Structure:
12.1 Introduction
Learning Objectives
12.2 Competitive Situations
Marketing different brands of commodity
Campaigning for elections
Fighting military battles
12.3 Characteristics of Competitive Games
N-person game
Zero sum game
Two-person-zero-sum game (rectangular game)
Strategy
Pure strategy
Mixed strategy
12.4 Maximin – Minimax Principle
Saddle point
Solution to a game with a saddle point
12.5 Dominance
Solving games using dominance
12.6 Summary
12.7 Terminal Questions
12.8 Answers to SAQs and TQs
Answers to Self Assessment Questions
Answers to Terminal Questions
12.9 References
12.1 Introduction
Welcome to unit twelve of Operations Research Management on Game Theory. John Von Newman developed the Game Theory in the year 1928. The theory gained importance after 1944, when John Von Newman along with Morgenstern published their work on ‘Theory of games and economic behaviour’. This highly resourceful field of study is developing fast.
Learning Objectives
By the end of this unit, you should be able to:
· Comprehend competitive situations
· Apply game theory to such situations
· Compute a solution using saddle point and dominance principle
12.2 Competitive Situations
Competitive situations arise when two or more parties with conflicting interests operate. The following competitive situations may occur.
[pic]
Figure 12.1: Types of competitive situations
12.2.1 Marketing different brands of a commodity
Two or more brands of detergents/soaps trying to capture the market by adopting various methods (courses), such as ‘advertising through electronic media’, ‘providing cash discounts to consumers’ or ‘offering larger sales commission to dealers’ are said to be in a competitive situation.
12.2.2 Campaigning for elections
Two or more candidates contesting in elections are in a competitive situation. They adopt various methods (courses), such as ‘campaigning through TV’, ‘door to door campaigning’ or ‘campaigning through public meetings’ to capture more votes.
12.2.3 Fighting military battles
Another example of a competitive situation is where two forces are fighting a war to gain supremacy over one another. They adopt various courses of action, such as ‘direct ground attack on enemy camp’, ‘ground attack supported by aerial attack’ or ‘playing defensive by not attacking’. The above mentioned situations can be considered as a competitive game where the parties (players) adopt a course of action (play the game).
Self Assessment Questions
Fill in the blanks:
1. Competitive situations arise when _______ or ________ parties with ___________ operate.
12.3 Characteristics of a Competitive Game
A competitive game has the following characteristics:
1. The number of players or competitors is finite.
2. Each player has finite number of courses of action or moves.
3. A game is played when each player adopts any one course of action.
4. Every time a game is played, the corresponding combination of courses of action leads to a transaction or payment to each player. The payment is called pay-off or gain. The pay-off may be monetary (money) or some benefit, such as increased sales.
5. The players do not communicate with each other.
6. The players are aware of the rules before starting the game.
12.3.1 N – person game
A game having ‘n’ players participating is called ‘n-person’ game. A two-player game is called 2-person game (two person game).
12.3.2 Zero – sum game
If the sum of the gains (pay-off) of the players in a game is zero, the game is called zero-sum game.
A zero-sum game with two players is called two-person zero-sum game. It is also called rectangular game.
In a two-person zero-sum game, the gain of one player is the loss of the other.
12.3.3 Two – person zero – sum game (rectangular game)
A two-person zero-sum game is a game where
· Two players participate
· The gain of one player is the loss of the other.
In a two-person zero-sum game with the players A and B. Let [pic]be the m courses of action for player A. Let [pic]be the n courses of action for player B. Let [pic]be the pay-off (gain) of player A when he plays the course of action, [pic]and player B plays the course of action[pic]. Then, the following matrix is the pay-off (gain) matrix of player A.
[pic]
This is a [pic](read as m by n) game. Here, [pic]is A’s gain and B’s loss. Therefore, (-[pic]) is the gain of B. To obtain the pay-off matrix of B, write
(-[pic]) in the place of [pic]in the above matrix and then write the transpose of the matrix.
12.3.4 Strategy
In a game, the strategy of a player is predetermined. The player uses this strategy to select a course of action during the game. The strategy of a player may be ‘pure’ or ‘mixed’.
[pic]
Figure 12.2: Types of strategy
12.3.5 Pure strategy
During the game, if a player’s strategy is to adopt a specific course of action, irrespective of the opponent’s strategy, the player’s strategy is called pure strategy.
12.3.6 Mixed strategy
If a player chooses his course of action according to pre-assigned probabilities, then the player’s strategy is called mixed strategy. Thus, if player A decides to adopt courses of action [pic]with perspective probabilities 0.4 and 0.6, it is mixed strategy.
[pic]
Self Assessment Questions
Write one line answers
2. State any one characteristics of a competitive game.
3. When do you call a game ‘zero-sum game’?
4. What is a rectangular game?
5. What is pure strategy?
6. How many courses of actions are available to the players in a competitive game?
12.4 Maximin – Minimax Principle
Solving a two-person zero-sum game
Player A and player B are to play a game without knowing the other player’s strategy. However, player A would like to maximise his profit and player B would like to minimise his loss. Also each player would expect his opponent to be calculative.
Suppose player A plays[pic].
Then, his gain would be [pic]accordingly B’s choice would be[pic].Let[pic].
Then, [pic]is the minimum gain of A when he plays [pic]([pic] is the minimum pay-off in the first row.)
Similarly, if A plays[pic], his minimum gain is[pic], the least pay-off in the second row.
You will find corresponding to A’s play[pic], the minimum gains are the row minimums[pic].
Suppose A chooses the course of action where [pic]is maximum.
Then the maximum of the row minimum in the pay-off matrix is called maximin.
The maximin is
[pic]
Similarly, when B plays, he would minimise his maximum loss.
The maximum loss to B is when [pic]is[pic].
This is the maximum pay-off in the [pic]column.
The minimum of the column maximums in the pay-off matrix is called minimax.
The minimax is
[pic]
If[pic], the maximin and the minimax are equal and the game is said to have saddle point. If[pic], then the game does not have a saddle point.
Note: [pic]cannot be greater than[pic].
12.4.1 Saddle point
In a two-person zero-sum game, if the maximin and the minimax are equal, the game has saddle point.
Saddle point is the position where the maximin (maximum of the row minimums) and minimax (minimum of the column maximums) coincide.
If the maximin occurs in the [pic]row and if the minimax occurs in the [pic]column, the position (r, s) is the saddle point.
Here, [pic]is the common value of the maximin and the minimax.
It is called the value of the game.
The value of a game is the expected gain of player A, when both the players adopt optimal strategy.
Note 1: If a game has saddle point, (r, s), the player’s strategy is pure strategy. For player A and B, the suggested solutions are [pic]and [pic]respectively.
Note 2: If a game does not have saddle point, the solution offers a mixed strategy.
Note 3: A game is said to be fair if its value is zero.
12.4.2 Solution to a game with saddle point
Consider a two-person zero-sum game with players A and B. Let [pic]be the courses of action for player A. Let [pic]be the courses of action for player B.
The saddle point of the game is as follows:
1. The minimum pay-off in each row of the pay-off matrix is encircled as shown in example 2.
2. The maximum pay-off in each column is written within a box as shown in example 2.
3. If any pay-off is circled as well as boxed, that pay-off is the value of the game. The corresponding position is the saddle point.
Let (r, s) be the saddle point. Then, the suggested pure strategy for player A is[pic]. The suggested pure strategy for player B is[pic]. The value of the game is[pic].
Note: However, if none of the pay-offs is circled or boxed, the game does not have a saddle point. Hence, the suggested solution for the players is mixed strategy.
[pic]
[pic]
[pic]
[pic]
Self Assessment Questions
True or False:
7. Saddle point occurs at row minimum and column maximum.
8. If the value of the game is zero, then it is called zero-sum game.
9. The pay off matrix represents the gain for top player.
12.5 Dominance
In a rectangular game, the pay-off matrix of player A is pay-off in one specific row [pic]exceeding the corresponding pay-off in another specific row[pic]. This means that whatever course of action is adopted by player B, for A, the course of action [pic]yields greater gains than the course of action[pic]. Therefore, [pic]is a better strategy than [pic]irrespective of B’s strategy. Hence, you can say that[pic] dominates[pic].
Alternatively, if each pay-off in a specific column [pic]is less than the corresponding pay-off in another specific column[pic], it means strategy [pic]offers minor loss than strategy [pic]irrespective of A’s strategy. Hence you can say that [pic]dominates[pic]. Therefore, you can say that:
a) In the pay-off matrix, if each pay-off in [pic]is greater than
(or equal to) the corresponding pay-off in the[pic], [pic]dominates[pic].
b) In the pay-off matrix, if each pay-off in [pic]is less than
(or equal to) the corresponding pay-off in the[pic], [pic]dominates[pic].
At times, a convex combination of two or more courses of action may dominate another course of action. Whenever a course of action (say [pic]or[pic]) is dominated by others, then that course of action ([pic]or[pic]) can be deleted from the pay-off matrix. Such a deletion will not affect the choice of the solution, but it reduces the order of the pay-off matrix. Successive reduction of the order using dominance property helps in solving games.
12.5.1 Solving games using dominance
Consider a two-person zero-sum game with players A and B. Let[pic]be the courses of action for player A. Let [pic]be the courses of action for player B.
Suppose the game has a saddle point. Use the dominance property in sequence to delete the courses of action of A as well as B till the pair comprising the saddle point remains alone. The procedure to arrive at the saddle point is as follows:
a) In the pay-off matrix, if each pay-off in [pic]is greater than (or equal to) the corresponding pay-off in the[pic], [pic]dominates[pic], hence [pic]is deleted.
b) In the pay-off matrix, if each pay-off in [pic]is less than (or equal to) the corresponding pay-off in the[pic], [pic]dominates[pic], hence so, [pic]is deleted.
c) Repeat the above steps in succession to achieve the saddle point.
Note: Sometimes, a convex combination of two or more courses of action may dominate another course of action.
|Solved Problem 6: |
|Solve the following game using dominance property. |
|[pic] |
|Solution: In the pay-off matrix, each pay-off in the first row exceeds the corresponding pay-off in the third |
|row. Therefore, [pic]dominates[pic]. So, [pic]is deleted. Hence the reduced matrix is as follows: |
|[pic] |
|Here, each pay-off in the third column is less than the corresponding |
|pay-off in the first column. Therefore, [pic]dominates[pic]. Similarly, [pic]dominates[pic]. Also, |
|[pic]dominates[pic]. Thus, the matrix reduces to |
|[pic] |
|Here, since 12>8, [pic]dominates[pic]. And so, finally the matrix reduces to – |
|[pic] |
|Thus, (1, 3) is the saddle point and the solution to the game is as follows: |
|a) Strategy for A is[pic]. |
|b) Strategy for B is[pic]. |
|c) Value of the game is v = 12 |
|Solved Problem 7: |
|Solve the following zero-sum game and find its value. |
|[pic] |
|Solution: In the pay-off matrix, each pay-off in the second column is less than (or equal to) the corresponding |
|pay-off in the third column. And so, the course of action Q dominates R. Similarly, Q dominates S. After |
|deleting R and S, the reduced matrix is as follows. |
|[pic] |
|Here, pay-off in the second row is greater than (or equal to) the corresponding pay-offs in the first, third as |
|well as fourth rows. Therefore, B dominates A, C and D. After deleting A, C and D, the reduced matrix is as |
|follows: |
|[pic] |
|Here, 1 ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- wordpress passing data between pages
- wordpress business templates
- wordpress rss feed not working
- wordpress jquery is not defined
- create wordpress blog
- wordpress roles editor
- wordpress full rss feed
- wordpress rss feed settings
- wordpress rss feed plugin
- wordpress display rss feed
- wordpress rss feed link
- wordpress rss feed to post