Or

2007

Shantilal Shah Engineering College

[ ] Production Engineering Department

OPERATIONS RESEARCH

CERTIFICATE This

is

to

certify

that

Mr./Miss

_______________________________________________________________ Student

of

semester

-

VIII

Production

Engineering,Roll No. _______ of S.S.Engineering College has Satisfactorily accomplished his/her term work by submitting this file of ______________________________________ on Date: ___________

Examinor

PRODUCTION ENGINEERING DEPT.

Head of the Dept

2

OPERATIONS RESEARCH

INDEX Sr.

Name of Experiment

From

No. 1. 2.

3. 4. 5. 6.

7. 8. 9. 10. 11.

Page To

Date of

Date of

Start

Complet -ion

Sign

OPERATION RESEARCH STUDY OF LINEAR PROGRAMMING METHODS, MODELS FORMULATION & ITS ROLE IN OPERATION RESEARCH STUDY & IMPORTANCE OF SIMPLEX METHOD IN LINEAR PROGRAMMING STUDY OF DUAL PROBLEM, ITS INTERPRETATION & SENSITIVITY ANALYSIS SPECIAL CASE OF SIMPLEX METHOD PROJECT EVALUATION AND REVIEW TECHNIQUES & CRITICAL PATH METHOD (PERT/CPM) GAMES THEORY INVENTORY MANAGEMENT QUEUING THEORY REPLACEMENT THEORY STUDY ABOUT SEQUENCING PROBLEM.

PRODUCTION ENGINEERING DEPT.

3

OPERATIONS RESEARCH

EXPERIMENT.NO: 1

OPERATION RESEARCH  HISTORICAL DEVELOPMENT It is generally agreed that Operation Research (OR) came into existence as a discipline during World War II. However, a particular model and technique of Operation Research can be traced back much earlier. The term Operation Research was coined as a result of research on military operations during this war. Since the war involved strategic and tactical problems, which were so complicated, that to expecting adequate solution from individuals Operation Research specialists in a single discipline was unrealistic. Therefore, groups of individuals who collectively and physical science were formed as special units within the armed forced to deal with strategic and tactical problems of various military operations. Such groups were first in England and the United States. One of the groups in England came to be known as Blackett‟s Circus. This group under the leadership of Prof. P.M.S.Blackett was attached to the Radar Operation Research unit and assigned the problem of analyzing the co-ordination of Radar equipment at gun sites. Following the success of this group, such mixed team approach was adopted in other allied nations. A key person in post war development of Operation Research was George B Dantzig. In 1947, he developed linear programming and its solution methods known as simplex method. Besides linear programming, many others were well developed before the end of 1950‟s. During the 1950‟s, there was substantial progress in the applications of Operation Research techniques for civilian activities along with a great interest in the professional development and education in Operation Research. Many college and universities introduce Operation Research in their curricula. They were generally schools of engineering, public administration, business management, applied mathematics, economics, computer services, etc. Today, however service organization such as banks, hospitals, libraries, airlines, railways, etc. recognize the usefulness for in improving their efficiency. In 1948, an Operation Research was formed in England which later changed the name to Operation Research Society of America (ORSA) was found in 1952 and its journal, Operation Research, first published in 1953. In the same year, the Institute of Management Science (TIMS) was founded as an International Society to identify, extend and unify scientific knowledge pertaining to management. Its journals, Management, Science, first appeared in 1954. In India, Operation Research came into existence in 1949 when an Operation Research unit was established at Regional Research Laboratory, Hyderabad. At the same time, Prof. R S PRODUCTION ENGINEERING DEPT.

4

OPERATIONS RESEARCH

Verma, also ser up an Operation Research team at Defence Science Laboratory to solve problems of store, purchase and planning. In 1933, Prof. P C Mahalanobis established an Operation Research team in the Indian statistical institute, Calcutta to solve to solve problems related to national planning and survey. The Operation Research Society of India was founded in 1957 and started publishing its journal OPSEARCH. In same year, India along with Japan became in London. The other member of IFORS was USA, UK, FRANCE and what was when WEST GERMANY. Because of OR‟s multi disciplinary character and application in varied fields, it has a good future provided people devoted to OR study can help meet the needs of society. Some of the problems the area of hospital management, energy conservation, environmental pollution etc. which have been solved by OR specialists is an indication that OR can also contribute towards the improvements in the pattern of social life and areas of global need. However, in order to make the future of OR more bright, it specialists have to make good use of the avenues open to them.

 SIGNIFICANCE OF OPERATIONS RESEARCH As the term implies OR involves research in military operations. This indicates the approach as well as the area of its application. The OR approach is particularly useful in balancing conflicting objectives (goals OR interests) where there are many alternatives courses of action available to the decision makers. In view of any problem situation involving the whole system, the decision maker, whatever his specialization will need help and it is in the attempt to provide this assistance that OR has been developed. OR attempts to resolve the conflicts of interest among various sections of the organization and seeks the optimal solution which may not be acceptable to one department but is in the interest of the organization as a whole. Further, OR is concerned with providing the decision maker with decision aids (or rules) derived from:

  

A total system orientation. Scientific methods of investigation. Models of reality generally based on quantitative measurement technique.

Thus, successful application of Operation Research technique for solving a problem must involve:

 

Constructing mathematical, economic and statistical model of the problem under study to treat situations of complexity and uncertainly. This helps to view the problem in it‟s entirely. Analyzing the relationships among different variables and parameters associated with the problem so as to determine consequences of decision alternative.

PRODUCTION ENGINEERING DEPT.

5

OPERATIONS RESEARCH



Suggesting suitable measures of desirability in order to evaluate the relative merit of decision alternatives.

 OPERATION RESEARCH APPROACH The future of Operation Research approach to any decision and control problems can be considered under the following methodologies: 1. INTERDISCIPLINARY APPROACH: Interdisciplinary teamwork is essential because while attempting to solve a complex management problem one person may not have the complete knowledge of all aspect (such as economic, social, political, psychological, engineering etc.) of it. This means we should not expect a desirable solution to managerial problems. Therefore, a team of individuals specializing in that field in order to arrive at an appropriate and desirable solution of the problem. However, there are certain problem situations, which may be analyzed even by one individual. 2. METHODOLOGICAL APPROACH: “Operation Research is the application of scientific methods, techniques and tools to problem involving the operation of system so as to provide those in control of operations with optimum solutions to the problems”. The scientific method consist of observing and defining the problems; formulating and testing the hypothesis; and analyzing the results of the test. The data so obtained are then used to decide whether the hypothesis is accepted, then the results should be implemented. Otherwise, an alternative hypothesis has to be formulated. 3. WHOLISTIC APPROACH: Arriving at a decision, an operation research team examines the relative importance of all confliction and multiple objectives and validity of the claims of various departments of the organization from the perspective of the whole organization. 4. OBJECTIVE APPROACH: An Operation Research approach seeks to obtain an optimal solution to the problem under analysis. For this a measure of desirability is defined based on the objectives of the organization. A measure of desirability so defined is then used to compare alternative course of action with respect to their out come.

 SCIENTIFIC METHOD IN OPERATION RESEARCH The most important feature of Operation Research is the use of the scientific method and building of decision models. There are three phases of the scientific method on which Operation Research practice is based. 1. JUDGMENT PHASE: This phase includes a) Identification of the real-life problem.

PRODUCTION ENGINEERING DEPT.

6

OPERATIONS RESEARCH

b) Selection of an appropriate objective and the values of various variables related to these objectives. c) Application of the appropriate scale of measurement, i.e. deciding the measures of effectiveness. d) Formulation of an appropriate model of the problem, abstracting the essential information‟s so that a solution at the decision maker‟s goals can be sought. 2. RESEARCH PHASE: This phase is the largest and longest between other two phases. However, the remaining two also equally important as they provide the basis for a scientific method. This phase utilize: a) Observations and data collection for a better understanding of the problem. b) Formulation and experimentation to test the hypothesis on the basis of additional data. c) Analysis of the available information and verification of the hypothesis using preestablished measures of desirability. d) Predictions of various results form the hypothesis. e) Generalization of the result and consideration of alternative method. 3. ACTION PHASE: This phase consists of making recommendation for implementing the decision by an individual who is the position to implement results. This man must be aware of the environment in which the problem occurred objective, assumption and omissions of the model of the problem.

 MODELS OF OPERATION RESEARCH  PHYSICAL MODELS These models provide a physical appearance of the real object under study either reduced in size/scaled up. Physical models are useful only in design problems because they are easy to observe, build and describe. Problem such as portfolio selection, media selection, production scheduling etc. cannot be analyzed with a physical model. Physical model are classified into the following two categories: 1.

Iconic Model: Iconic models retain some of the physical properties and characteristics of the system they represent. An iconic model is either in an idealized formula scaled version of the system. In other words, such models represent the system as it is by scaling it up Operation Research down. The iconic models are simple to conceive, specific and concrete. An iconic model is used to describe the characteristics of the system rather than explanatory. This means such models are used to represent a static event and characteristics, which are not used in determining/predicting effects due to certain changes in actual system.

PRODUCTION ENGINEERING DEPT.

7

OPERATIONS RESEARCH

For example, color of an atom does not play any vital role in the scientific study of its structure. 2.

Analogue Model: These models represent a system by the set properties different from that of the original system does not resemble physically. After the problem is solved, the solution is reinterpreted in terms of the original system. For example, the organizational chart represents the state of formal relationships existing between members of the organization. Map in different colors may represent water, desert and other geographical features. These models are less specific and concrete but easier to manipulate and more general than iconic models.

 SYMBOLIC MODELS: These models use letters, numbers and other symbols to represent the properties of the system. These models are also used to represent relationship, which can be represented in a physical form. Symbolic models can be classified into two categories: 1.

Verbal Models: These models describe a situation in written Operation Research spoken language. Written sentences, books, etc. are examples of a verbal model.

2.

Mathematical Models: These models involve the use of mathematical symbols, letters, numbers, and mathematical operators (+, -, *, /) to represent relationship among various variable of the system to describe its properties Operation Research behavior. The solution to such models is then obtained by applying suitable mathematical techniques. Symbolic models are precise and abstract and can be manipulated by using laws of mathematics.

 BASIC OPERATIONS RESEARCH MODELS There is no unique set of problems, which can be solved by using Operation Research models Operation Research techniques. Several Operation Research models/techniques can be grouped into some basic categories as given below: 1. ALLOCATION MODEL: Allocation model are used to allocate resources to activate in such a way that some measure of effectiveness is optimized. Mathematical programming is the broad term for the Operation Research technique solves allocation problems. When the solution values Operation Research decision variables for the problem are restricted to being integer values / just zero-one values, the problem is classified as an integer programming problem Operation Research a zero-one programming problem respectively. PRODUCTION ENGINEERING DEPT.

8

OPERATIONS RESEARCH

The problem having multiple, conflicting and incommensurable objective functions subject to linear constraints is called a goal-programming problem. If the decision variables in the linear programming problem depend on chance, then such a problem is called a stochastic programming problem. 2. INVENTORY MODELS: Inventory models deal with the problem of determination of how much to order at a point in time and when to place an order. The main objective is to minimize the sum three conflicting inventory costs: the cost of holding Operation Research carrying extra inventory, the cost of storage Operation Research delay in the delivery of items when it is needed, a cost of ordering or set-up. These are also useful in dealing with quantity discounts and selective inventory control. 3. WAITING LINE MODELS (QUEUING): These models have been developed to establish a trade-off between costs of providing service and the waiting time of a customer in the queuing system. Constructing a models entails describing the components of the system: arrival process, queue structural and service process and solving for the measure of performance – average length of waiting time, average time spent by the customer in the line, traffic intensity, etc. of the waiting system. 4. COMPETITIVE MODELS (GAME THEORY): These models are used to characterize the behaviors of two/more opponents who compete for the achievement of conflicting goals. These models are classified according to several factors such as number of competitors, sum of loss and gain and type of strategy which would yield him the best / the worst outcomes. 5. NETWORK MODELS: These models are applied to the management of large-scale projects. PERT/CPM technique help in identifying potential trouble spots in project through the identification of the critical path. These techniques improve project coordination and enable the efficient use of resources. Network methods are also used to determine time-close trade off, resource allocation and updating of activity times. 6. SEQUENCING MODELS: These models are used whenever there is program in determining the sequence in which a number of tasks can be performed by a number of service facilities such as hospital, plant etc. in such a way that some measure of performance, for example, total time to process all the jobs on all the machines, is optimized. 7. REPLACEMENT MODELS: These models are use when one must decide the optimal time to replace equipment for one reason Operation Research the other-for instance, in the case of equipment whose efficiency deteriorates with time Operation Research fails immediately and completely. For example, in case of an automobile the user has his own measure of effectiveness. So there will not be single optimal answer for everyone even if each automobile gives exactly the same service.

PRODUCTION ENGINEERING DEPT.

9

OPERATIONS RESEARCH

8. DYNAMIC PROGRAMMING MODELS: Dynamic programming may be considered as an out growth of mathematical programming and involves the optimization of multistage decision processes. The method starts by dividing a given problem into stages Operation Research sub-problems and then solves that sub-problem sequentially until the solution to the original problem is obtained. 9. MARKOV-CHAIN MODELS: These models are used for analyzing a system that changes over a period of time among various possible outcomes/states. The models while dealing with such systems describe transitions in terms of transition probabilities of various states. These models have been used to test brand-loyalty and brandswitching tendencies of consumers, where each system state is considered to be a particular brand purchase. These have also been used in reliability analysis, where the states of the system are the various levels of performance of the equipment being monitored. 10. SIMULATION MODELS: These models are used to develop a method to evaluate the merit of alternative courses of action by experimenting with a mathematical model of the problems where various variables are random. That is, these provide a means of or generating representative samples of the measures of performance variable. Thus, repetition of the process by using the simulation model provides an indication of the merit of alternative course of action with respect to the decision variable.

 GENERAL METHODS In general, the following three models are used solving Operation Research models. In all these methods, values of decision variables are obtained that optimize the given objectives function. 1. ANALYTICAL METHOD (DEDUCTIVE): In this method, classical optimization techniques such as calculus, finite difference and graphs are used for solving and Operation Research model. In this case, we have a general solution specified by symbol and we can obtain the optimal solution in a non-iterative manner. For example, in inventory models, in order to calculate economic order quantity the analytical method requires that the first derivative of the mathematical expression TC = (D/Q) Cp + (Q/2) Ch Where,

TC = Total variable inventory cost; Cp = Ordering cost per; Q = size of an order; D = annual demand;

PRODUCTION ENGINEERING DEPT.

10

OPERATIONS RESEARCH

Ch = carrying cost per time period. Be taken and equated to zero as the first step toward identifying optimum value of Q* = sqrt (2DCp/Ch). This is because of the concept of maximum and minimum for optimality. Here, it may be noted that the validity of the conclusion depends only on the validity of the mathematical approach that is being used. 2. NUMERICAL METHODS (ITERATIVE): When analytical methods fail to obtain the solution of a particular problem due to its complexity in terms of constraints/number of variables, then numerical methods is used to get the solution. In this method instead of solving the problem directly, a general is applied to obtain a specific numerical solution. The numerical methods starts with a solution obtained by trail and error and as set of rules for improving it towards optimally. The solution so obtained is then replaced by the improved solution and the process of getting improved solution is repeated until such improvement is not possible/ the cost of further calculation cannot be justified. 3. MONTE CARLO METHOD: This method is based upon the idea of experimenting on a mathematical model by inserting into the model specific values of decision variables at different points of time and under different conditions and then observing their effect on the criterion chosen for variables. In this method, random samples of specified random variables are drawn to know what is happening to the system for a selected period of time under different conditions. The random samples form a probability distribution that represents the real life system and from this probability distribution, the value of the desired random variable can be estimated.

 APPLICATION AND SCOPE OF OPERATON RESEARCH Some of the industrial/ government/ business problems which can be analyzed by Operation Research approach have been arranged functional area wise as follows: 1. FINANCE AND ACCOUNTING:

  

Divided policies, investment and portfolio management, auditing balance sheet, cash flow analysis. Break-even analysis, capital budgeting, cost allocation and control, financial planning. Claim and complaint procedure, public accounting.

2. MARKETING:

  

Selection of product – mix, marketing planning, exports planning Sales effort allocation and assignment. Advertising and media planning.

PRODUCTION ENGINEERING DEPT.

11

OPERATIONS RESEARCH

3. PURCHASING, PROCUREMENT AND EXPLORATION:

    

Optimal buying and recording under price quantity discount. Bidding policies. Transportation planning. Vendor analysis. Replacement policies.

4. PRODUCTION MANAGEMENT:

  

Facilities Planning Manufacturing Maintenance and project scheduling

5. PERSONNEL MANAGEMENT:

  

Manpower planning, wage/salary administration Skills and wages balancing Scheduling of training programmers

6. TECHNIQUES AND GENERAL MANAGEMENT:

  

Decision support system and MIS; forecasting Organizational design and control Project Management, strategic planning

7. GOVERNMENT:

  

Economic planning, natural resources, social planning, energy Urban and housing problem Military, police, pollution control etc.

PRODUCTION ENGINEERING DEPT.

12

OPERATIONS RESEARCH

EXPERIMENT.NO: 2

STUDY OF LINEAR PROGRAMMING METHODS, MODELS FORMULATION & ITS ROLE IN OPERATION RESEARCH  GUIDELINES ON LINEAR PROGRAMING MODEL FORMULATION The usefulness of linear programming as a tool for optimal decision making on resource allocation is based on its applicability to many diversified decision problems. The effective use and application require, as a first step, the mathematical formulation of the LP model when the problem in words.

 STEPS OF LP MODEL FORMULATION Step 1: - Define Decision Variable: a)

Express each constraint in words. For this first see, whether the constraint is of form,  (at least than). Operation Research of the for  (no longer than) Operation Research = (Exactly equal to) b) Then express the objective function in words. c) Step 1(a) and 1(b) should then allow you to verbally identify the decision variable. Step 2: - Formulate the Constraints: Formulate all the constraints imposed buy the resource availability and express them as linear equality Operation Research inequality in terms of the decision variables defined in step 1. Step 3: - Formulate the Objective Function: Define the objective function. That is, determine whether the objective function is to be maximized /minimized. Then express it as a linear function of decision variables multiplied by their profit/cost contributions.

 INTRODUCTION An optimal as well as feasible solution an LP problem is obtained by choosing among several values of decision variables X1, X2,…., Xn the one set of values that satisfy the given set of constraints simultaneously and also provides the optimal values of the given objective function.

PRODUCTION ENGINEERING DEPT.

13

OPERATIONS RESEARCH

 GRAPHICAL SOLUTION METHODS OF LP PROBLEMS While obtaining the optimal solution to the LP problem with the graphical method, the statement of the following theorems of linear programming is used. 1. The collection of all feasible solutions to an LP problem constitutes a convex set whose extreme points correspond to the basic feasible solutions. 2. There are finite numbers of basic feasible solutions within the feasible solution space. 3. If the optimal solution occurs at feasible solutions on the system Ax = b, x>0, is a convex polyhedron, then at least one of the extreme points gives an optimal solution. 4. If the optimal solution occurs at more than one extreme point, then the value of objective function will be the same for all convex combinations of these extreme points.

 EXTREME POINT ENUMERATION APPROACH This solution method for an LP problem divided into five steps. Step 1:- State the given problem in the mathematical form as illustrated previously. Step 2:- Graph the constraints, by temporarily ignoring inequality sign and decide about the area of feasible solutions according to the inequality sign of the constraints. Indicate the area of feasible solutions by a shaded area, which forms a convex polyhedron. Step 3:- Determine the co-ordinate so the extreme points of the feasible solution space. Step 4:- Evaluate the values of the objective function at each extreme point. Step 5:- Determine the extreme point to obtain the optimum value of the objective function.

 SOME SPECIAL CASES IN LINEAR PROGRAMMING 1. ALTERNATIVE OPTIMAL SOLUTION: So far we have seen that the optimal solution of any linear programming problem occurs at extreme point of the feasible region and the solution is unique, i.e. no other solution yields the same value of the objective function. However, in certain cases a given LP problems may have more than one optimal solution yielding the same objective function value. There are two conditions that should satisfy in order that an alternative optimal solution exists.





The given objective function is parallel to a constraint that forms the boundary of the feasible solutions region. In other words, the slope of the objective function is same as that of the constraint forming the objective function is same as that of the constraint forming the boundary of the feasible solutions region. The constraint should form a boundary on the feasible region in the direction of optimal movement of the objective function. In other words, the constraint should

PRODUCTION ENGINEERING DEPT.

14

OPERATIONS RESEARCH

be an active constraint. Graphically an active constraint is one that passes through one of the extreme points of the feasible solution space. 2. AN UNBOUNDED SOLUTION: When the value of decision variables in linear programming is permitted to increase infinitely without violation the feasibility condition, then the solutions said to be unbounded. The objective function value can be increased infinitely. However, an unbounded feasible region may yield some definite value of the objective function. 3. AN INFEASIBLE SOLUTION: If it is not possible to find a feasible solution that satisfies all the constraint, then LP problem, I said to have an infeasible solution / alternatively inconsistency. Infeasibility depends mainly on the constraints and has nothing to do with the objective function.

 LINEAR PROGRAMMING WITH THE HELP OF SIMPLEX METHOD  STANDARD FORM OF LP The use of the simplex method to solve an LP problem requires that the problem be converted into its standard form. The standard form of the LP problem should have the following characteristics:

  

All the constraints should be expressed as equations by adding slack operation research surplus and artificial variables. The right hand side of each constraint should be made non-negative, if kit is not; multiplying both sides of the resulting constraint by –1 should do this. The objective function should be of the maximization is expressed as: For your ready reference the standard for of the LP problem is expressed as, Optimize (Max/Min) Z = C1X1 + C2X2 +….+ CnXn + 0S1 +….+ 0Sm Subject to the linear constraints A11X1 + A12X2 + …+ A1nXn + S1 = B1 A21X1 + A22X2 + … + A2nXn +S2 = B2 | | Am1X1 + Am2X2 + … + AmnXn +Sm = Bm And X1, X2,…, Xn, S1, S2,…,Sm 0 In matrix notation the standard form is expressed as:

PRODUCTION ENGINEERING DEPT.

15

OPERATIONS RESEARCH

Optimize Z = CX + 0S Subject to the linear constraints AX + S = B and X, S 0 Where C = (C1,C2,…,Cn) is the row vector; X = (X1,X2,…,Xn), B = (B1,B2,…,Bm) S = (S1,S2,…,Sn) are columns vectors and A11

A12…

A1n

A21

A22…

A2n

…

…

Am1 Am2

… Amn

is the (m x n) matrix of coefficients of variables X 1, X2,…, Xn in the constraints.

There types of additional a variables, namely 1. Slack variable (S) 2. Surplus variables (-S) 3. Artificial variables (A)

 TWO PHASE METHOD In the first phase of the method the sum of the artificial variables is minimized subject to the given constraints to get a basic feasible solution of the LP problem. The second phase minimizes the original objective function starting with the basic feasible solution obtained at the first phase. Since the solution of the LP problem is completed in two phases, this is called the two-phase method.

 STEPS OF ALGORITHM PHASE 1: Step 1: a)

If all the constraints in the give LP problem are (<) type, then phase II can be directly use to solve the problem. Otherwise, a sufficient number of artificial variables are added to get a basis matrix (identity matrix). b) If the given LP problem is of minimization, then convert it to the maximization type by the usual method. Step 2: Solve the following LP problem by assigning a coefficient of –1 to each artificial variable and zero to all other variable and zero to all other variables in the objective PRODUCTION ENGINEERING DEPT.

16

OPERATIONS RESEARCH

function and with the basic feasible solution X1 = X2 = … = Xn = 0 and Ai = b1; i = 1,2,…,m Maximization Z* =  (-1) A1 Subject to the constraints Z* =  aij xj = Aj = bi; i = 1,2,…,m; and xj , Aj > 0 Apply the simplex algorithm to solve this LP problem. The following three cases may arise at optimally:

  

Max Z* = 0 and at least one artificial variable is present in the basis with position value. Then no feasible solution exists for the original LP problem. Max Z* = 0 and no artificial variable is present in the basis. Then the basis consists of only decision variables (Xjs) and hence we may move to phase II to obtain an optimal basic feasible solution to the original problem. Max Z* = 0 and at least one artificial variable is present in the basis at zero value. The feasible solution to the above LP problem is also a feasible solution to the original LP problem. Now orders to arrive at the basic feasible solution we may proceed directly to phase II operation research else eliminate the artificial basic variables and then proceed to phase II.

 THE BIG – M METHOD The big – M method is another method of removing artificial variables from the basis. In this method, we assign coefficients to artificial variables, under sizable from the objective function point of view. If objective function Z is to be minimized, then a very large positive price is assigned to each artificial variable. Similarly, if Z is to be maximized then a very large negative price is assigned to each of these variables. The penalty will be designated by = M for a maximization problem and +M for a minimization problem where M>0. The big – M method for solving an LP problem can be summarized in the following steps: Step 1: Express the LP problem in the standard form by adding surplus variables and artificial variables. Assign a zero coefficient to surplus variables and a very large positive number +M to artificial variables in the objective function. Step 2: The initial basic feasible solution is obtained by assigning zero value to original variables. Step 3: Calculate the values of Cj – Zj in last row of the simplex table and examine these values:



If all Cj – Zj  0 then the current basic feasible solution is optimal.

PRODUCTION ENGINEERING DEPT.

17

OPERATIONS RESEARCH

 

If for a column, k, Ck – Zk is most negative and all entries in this column are negative, then the problem has an unbounded optimal solution. If one or more Cj – Zj < 0 then select the variables to enter into the basic with the largest negative Cj – Zj value. That is, Ck – Zk = Min(Cj – Zj:Cj – Zj < 0) The column to enter is called key or pivot column.

Step 4: Determine the key row and key element in the same manner as discussed in the simplex algorithm of the maximization case.

 LINEAR PROGRAMMING FORMULATION OF DUAL PROBLEM The term „dual‟ in a general sense implies two/double. The concept of duality is very useful in mathematics, physics, and statistics and engineering. In context of linear programming duality implies that each linear programming problem can be analyzed in two different ways but having equality solutions. Each LP problem stated in its original form has associated with another linear-programming problem, which is unique based on the same data. In general it is immaterial which of the two problems is called primal / dual since the dual is primal.



SYMMETRICAL FORM

Suppose the primal LP problem is given in the form, Maximize Zx = C1X1 + C2X2 +…+ CnXn Subject to the constraints A11X1 + A12X2 +…+ A1nXn + S1 = B1 A21X1 + A22X2 +…+ A2nXn + S2 = B2 | Am1X1 + Am2X2 +…+ AmnXn +Sm = Bm And X1 ,X2,… ,Xn  0 Then corresponding dual LP problem is defined as: Minimize Zy = B1Y1 + B2Y2 +…+ BmYm Subject to the constraints A11Y1 + A12Y2 +…+A1nYn + S1 = B1 A21Y1 + A22Y2 +…+ A2nYn +S2 = B2 | Am1Y1 + Am2Y2 +…+ AmnYn + Sm = Bm PRODUCTION ENGINEERING DEPT.

18

OPERATIONS RESEARCH

And Y1, Y2,…,Yn  0 Therefore above pair of LP problem can be expressed in the general LP model form as: PRIMAL

DUAL

n Max Zx =  CjXj

n Min Zy =  BiYi

j=1 Subject to

j=1 Subject to

n

n

 AjiXj  Bi; i = 1,2,…,m

 AjiYi  Cj; j = 1,2,…,n

j=1

j=1

And Xj  0; j = 1,2,..,m

And Yi  0; i = 1,2,..,m

A summary of the general relationship between primal and dual LP problem is given in table below: IF PRIMAL Objective is to maximize Variable Xj Constraint i Variables Xj unrestricted in sing Constraint i is = type sign  type constraints  0 variables  inequality constraints



THEN DUAL Objective is to minimize Constraint j Variable Yi Constraint j is = type Variable Yi is restricted in sign  type constraints  inequality constraints  0 variable

ECONOMIC INTERPRETATION

In the primal LP model we may define each parameter as follows: Z = return Xj = units of variable j Cj = return per unit of variable Xj Aij = requirement of resource I by per unit of variable j Bi = units of resource i The new parameters introduced in the dual problem are Z y and Yi. Since Zx = Zy so Zy is also in terms of “return”. The interpretation associated with the dual variables Yi, i = 1,2,…,m is discussed below: PRODUCTION ENGINEERING DEPT.

19

OPERATIONS RESEARCH

Rewriting the primal LP problem in terms of new terminology PRIMAL: n Maximize Zx =  { return / units of variable Xj}(units of variable Xj) j=1 Subject to the constraints { units of resource I / units of variable Xj}(units of variable)  unit of resource i; i = 1,2,…,m and Xj  0 DUAL: n Minimize Zy =  (units of resource i) Yi j=1

, subject to the constraints

n  { units of resource i/ units of variable Xj} Yi  {return / units of variables Xj} j=1 i = 1,2,…,n and Yi  0

 TRANSPORTATION MODEL One important application of linear programming has been in the area of physical distribution of resources, from one place to another to meet a specific set of requirements. It is easy to express a transportation problem mathematically in terms of an LP model, which can be solved by simplex method. Since transportation problem involves a large number of variables and constraints it takes a very long time to solve it by the simplex ways, involving transportation algorithm, namely the stepping stone method, MODI method have been involved for this purpose. The transportation algorithm discussed in this chapter is applied to minimize the total cost of transporting a homogeneous commodity from one plane to another. However, it can also be applied to the minimization of some total value / utility, for example, financial resources are distributed in such a way that the profitable return is maximized.

 TRANSPORTATION PROBLEM The transportation problem applied to situation in which a single product is to be transported form several sources to several sinks. In general, let there be m sources, S 1, S2,…,Sm having Ai units of supplies or capacity respectively table transported among n destination D1,D2,…,Dn with Bj units of requirement respectively. Let Cij be the cost of shipping one unit of commodity from sources i to destination j for each route. If Xij represents the units shipped per route from source i to destination j, the problem is to PRODUCTION ENGINEERING DEPT.

20

OPERATIONS RESEARCH

determine the transportation schedule so as to minimize the total transportation cost satisfying supply and demand conditions. Mathematically the problem can be stated as: m n Minimize (total cost) =   Cij Xij i=1 j=1 Subject to the constraints n  Xij = Ai, i = 1,2,…,m j=1 m  Xij = Bj, j = 1,2,…,n i=1 And Xij  0 for all i and j.

PRODUCTION ENGINEERING DEPT.

21

OPERATIONS RESEARCH

EXPERIMENT.NO: 3

STUDY & IMPORTANCE OF SIMPLEX METHOD IN LINEAR PROGRAMMING  GRAPHICAL SOLUTION  INTODUCTION An optimal as well as feasible solution to an LP problem is obtained by choosing among several values of decision variables x1, x2, …., xn. The one set of values that satisfies the given set of constraints simultaneously and also provide the optimal values of a given objective function. For LP problems that have only two variables it is possible that the center set of feasible solution can be displayed graphically by plotting linear constraints to locate a best optimal solution. A technique used to identify the optimal solution is called the graphical solution technique for an LP problem with two variables.

 DEFINITION Basic Solution: In a system of m equations and n unknowns where n>m, AX= b and XT belongs to Rn When A is a (m x n) matrix of rank m. Let B be any x sub matrix formed by linearly independent columns of A, then the solution is obtained by setting n-m variables, not associated with the columns of B, equal to zeroes and solving the resultant system is called a Basic Solution to the given system of equations. The n-m variables whose values did not appear in the solution are called non-basic variables and the remaining m variables are called basic variables. Solution: Solution values of decision variables xj(j=1,2,…n) which satisfy the constraint of general LP model is called the solution of the LP model. Feasible Solution: Solution values of decision variables xj (j=1,2,…n) which satisfy the constraints and nonnegativity condition of general LP model are said to constitute the feasible solution to that LP model.

PRODUCTION ENGINEERING DEPT.

22

OPERATIONS RESEARCH

Basic Feasible Solution: A feasible solution to an LP problem, which is also the basic solution, is called the Basic Feasible Solution. That is, all basic variables assume non-negative values. Basic Feasible Solution are of two types:

 

Degenerate: A basic feasible solution is called Degenerate if at least one basic variable possesses zero value. Non-Degenerate: A basic feasible solution is called Non-degenerate if all m basic variables are positive and non-zero. Optimum Basic Feasible Solution:

A basic feasible solution which optimizes the objective function of the given LP models called an Optimum Basic Feasible Solution. Unbounded Solution: A solution which can be increased operation research decreased the value of objective function of LP problem indefinitely is called Unbounded Solution. This solution method for an LP problem is divided into five steps: Step1: State the given problem in the mathematical form. Step2: Graph the constraints, by temporarily ignoring the inequality sign and decide about the area of feasible solution according to the inequality sign of constraints. Indicate the area of feasible solutions by a shaded area which forms a convex polyhedron. Step3: Determine the coordinate so the extreme points of the feasible solution space. Step4: Evaluate the value of the objective function at each extreme point. Step5: Determine the extreme points to obtain the optimum value of the objective function.

 SIMPLEX METOD:  STANDARD FORM OF LP: The use of the simplex method to solve an LP problem requires that the problem be converted into its standard form. The standard of the LP problem should have the following characteristic. 1. All the constraints should be expressed as equations by adding slack, operation research surplus and artificial variables. 2. The right hand side of each constraint should be made non-negative, if it is not, this should be done by multiplying both sides of the resulting constraints by-1. 3. The onjective function should be of the maximization is expressed as: Optimize (max/min) Z = C1X1 + C2X2 +…..+ CnXn + 0S1 +….+ 0Sm PRODUCTION ENGINEERING DEPT.

23

OPERATIONS RESEARCH

Subject to linear constraints, A11X1 + A12X2 +…..+ A1nXn + S1 = B1 A21X1 + A22X2 +…..+ A2nXn +S2 = B2 | Am1X1 + Am2X2 +…..+ AmnXn + Sm = Bm And X1,X2,……..,Xn,S1,S2 0 In matrix notation the standard form is expressed as: Optimize Z = CX+0S Subject to linear constraints AX+S = b and X,S  0 Where C=[C1,C2,…..Cn]is the row vector. X=[X1,X2,….Xn], B=[B1,B2,…..Bm]T S= [S1, S2, …. Sn]

are column vectors.

A11 A12 A1n A21 A22 A2n | | | Am1 Am2 Amn Is the matrix of coefficients of variables X1, X2, …, Xn in the constraints. Three types of additional variables namely 1. 2. 3.

Slack variables [S] Surplus variables [-S] artificial variables [A]

 STEPS IN SIMPLEX METHOD: Step1: Formulation of LPP Step2: Convert constraints into equality form. Step3: Construct the starting simplex table. Step4: Test optimality by analysis. Step5: Find “incoming” and “outgoing” variables and rewrite the table as per given set of rules. Step6: Repeat step 4 onwards again till optimum basic feasible solution is obtained.

 THE BIG - M METHOD Big- M method is another method of removing artificial variables from the basis. In this method, we assign coefficients to artificial variables, undesirable from the objective PRODUCTION ENGINEERING DEPT.

24

OPERATIONS RESEARCH

function point of view, if objective function Z is to be minimized, then a very large positive price is assigned to each artificial variable. Similarly, if Z is to be maximized, then a very large negative price is assigned to each of this variable. The penalty will be designated by =M for maximization problem and +M for a minimization problem, where M>0. The big M method for solving and LP problem can be summarized in the following steps: 1.

Express the LP problem in the standard form by adding surplus variables and artificial variables. Assign a zero coefficients to surplus variables and a very large positive number +M and-M to artificial variables in the objective function. 2. The initial basic feasible solution is obtained by assigning zero value to original variables. 3. Calculate the values of Cj-Zj in fast row of the simplex table and examine these values. a) [a] If all Cj-Zj>0, then the current basic feasible solution optimal. b) [b] If for a column, k, Ck-Zk is most negative and all entries in this column are negative then the problem has an Unbounded Optimal Solution. c) [c] If one / more Cj-Zj<0 then select the variable to enter into the basic with the largest negative Cj-Zj value. That is, d) Ck-Zk= Min{Cj-Zj; Cj-Zj<0} e) The column to be entered is called the key / pivot column. 4.

Determine the key row and key element in the same manner as discussed in the simplex procedure of the maximization case.

PRODUCTION ENGINEERING DEPT.

25

OPERATIONS RESEARCH

EXPERIMENT.NO: 4

STUDY OF DUAL PROBLEM, ITS INTERPRETATION & SENSITIVITY ANALYSIS  DEFINATION The dual is an auxiliary LP problem defined directly and systematically from the original of primal LP model. In most LP treatments, the dual is defined for various forms of the primal depending on the types of the constraints, the signs of the variables and the sense of optimization. The general standard for the primal is defined as n Maximize or Minimize Z =  CjXj j =1 Subject to n  AijXj = Bi, j=1

i = 1,2,……,m

Xj  0, j = 1,2,….,n

 CONSTRUCTION OF DUAL PROBLEM Following steps are as under:

  



If the primal problem has its objective function of maximization its all constraints must have type of inequality. Like that, the primal problem having its objective function to be minimized should have all its constraints  type of inequality. The nature of optimization is changed, i.e. if objective of primal problem is to be maximized, the objective of dual problem is to be minimized and vice versa. Right hand constants of primal problem become objective function coefficients of dual problem. This demands that for each constraint in primal problem there is a separate dual variable. And vice versa objective function coefficients of primal problem become right hand constants of dual problem giving a constraint of each variable in the primal problem. For example, if primal problem ha m number of constraints and n number of variables then its dual problems has n number of constraints and m number of variables, i.e. if primal is of order m x n the dual is of order n x m. Inequalities of constraints are reversed.

PRODUCTION ENGINEERING DEPT.

26

OPERATIONS RESEARCH

 

Row coefficients of the matrix of primal problem become column coefficients of the matrix of dual problem in the same order i.e. 1 st row of primal become 1 st column of dual. Primal as well as dual variables are non-negative.

 INTERPRETATION AND PROPERTIES OF DUAL Following are a few important interpretation and properties of dual problem:

   

The objective function value of any feasible solution to the primal will be less than or equal to the objective function value of every feasible solution to the dual i.e. ZZmin. If either the primal or the dual has an unbounded solution, the solution to the other problem is infeasible. If both primal and dual problems have feasible solution then both also have optimum solution and Zmax = Zmin. If the primal has a feasible solution but the dual has no feasible solutions, then the primal does not have a finite optimum solution. Likewise, if the dual has a optimum solution.

The above conclusions are derived as the statements of dual theorems. Some of the important of Prima-Dual are:

 

The index row coefficient under the slack variables in primal optimal solution is the optimal values of the dual variables. The index row coefficient under variable in the primal optimal gives the difference between the left and right hand sides of the associated optimal dual corresponding dual constraints.

 DUAL SIMPLEX METHOD In simplex method we start with initial feasible solution and through stages of iteration along simplex algorithm we improve the solution till optimal solution is one, in terms of algorithm for maximization in which index row coefficients are non-negative i.e. dual variables are feasible. Now, from our understanding of Primal-Dual relations, we know that index row coefficients are the values of dual variables and hence it suggests dual feasible solution. There are situations where a primal solution may be infeasible, but corresponding variables indicate that dual is feasible. Thrust solution is primal infeasible but optimum. In a dual simplex method, initial solution is infeasible but optimum, and through iteration, it reaches feasibility at which stage it also reaches true optimum. To summaries the procedure:



The solution associated with a basis is optimal if all index row coefficients are  0.

PRODUCTION ENGINEERING DEPT.

27

OPERATIONS RESEARCH



The basic variable having the largest negative value is the departing variable and its row is the key row.

 SENSITIVITY ANALYSIS Management‟s interest in optimization is not confined to obtaining optimum solutions for the given set of data. In fact, management for its decision-making in changing situations has interest in analyzing the present optimal solutions for projecting its future picture. Such an investigative analysis is called sensitivity analysis. As this analysis is based on the optimal solution presently obtained, it is called post-optimally analysis. Sensitivity analysis will seek answers to the following questions: (these questions are put in relation to a product-mix problem for profit maximization with the given set of constraints due to resources. However, the analysis will draw general conclusion.) …. if objective coefficient of a particular basic variable in optimal solution changes, does the present solution remain optimal? If objective coefficient of a particular non-basic variable in optimal solution changes, does the present solution remains optimal? …. when will happen to the present optimal solution if a certain resources is augmented or curtailed? …. what will happen to the present optimal solution, if a product is added or dropped?

 CHANGE IN THE OBJECTIVE FUNCTION COEFICIENT Variation in the objective function coefficient may belong to a basic variable or to a nonbasic variable. We shall take the two cases separately. Consider a change in the objective function coefficient of the non-basic variable in the optimal solution. Any change in the objective function coefficient of the non-basic variable will affect only its index row coefficient and not others. Here X3 is non-basic variable. Any decrease in its coefficient will not affect the present solution. Now consider a change in the objective coefficient of the basic variable in the optimal solution. Here, it affects the index now coefficients of all the variable. Hence, as soon as the index row coefficient of basic variable becomes positive, it leaves the solution, and that of non-basic variable becomes negative, it qualifies for entry into the solution. In either case, the present optimal solution changes.

 CHANGES IN RIGHT HAND SIDE CONSTANTS The right hand side constants denote present level of availability of resources. When this is increased or decreased, it will have the effect on objective function. Besides, it may also change the basic variables in the solution. PRODUCTION ENGINEERING DEPT.

28

OPERATIONS RESEARCH

EXPERIMENT.NO: 5

SPECIAL CASE OF SIMPLEX METHOD Special applications of simplex methods are:

1) Transportation technique. 2) Assignment model. 1. TRANSPORTATION TECHNIQUE This is a special case of linear programming. The aim of this technique is that within a given time period, a single homogenous specified commodity to be transported form „m‟ number of sink on destination available units so that, total cost of transportation is minimum. Here size and location of plant are decided. The technique helps to determining optimal solution. Consider „m‟ number of source and „n‟ number of destination, also consider ith source of availability of Ai number of units of a product and n number of destinations as jth destination requires Bj number of units for the same product. Let the cost associated with transportation is Cij and decision variable is Xij. Let mathematical statement of problem, m n Minimize Z = Cij Xij

………………… (1)

i=1 j=1 equation (1) is called objective function. m Subject to Xij = Bj i=1 n & Xij = Ai j=1 These are called constraints of the function. For a balanced problem, suppose there are 4 sources and 3 destinations, minimize, Z = C11X11 + C12X12 + C13X13 + C21X21 + C22X22 + C23X23 + C31X31 + C32X32 + C33X33 + %S C41X41 + C42X42 + C43X43 Subject to X11 + X12 + X13 = A1 X21 + X22 + X23 = A2 PRODUCTION ENGINEERING DEPT.

29

OPERATIONS RESEARCH

X31 + X32 + X33 = A3 X41 + X42 + X43 = A4 X11 + X12 + X13 + X14 = B1 X21 + X22 + X23 + X24 = B2 X31 + X32 + X33 + X34 = B3 For balance problem, A1 + A2 + A3 + A4 = B1 + B2 + B3 It can be represented in matrix as under:

Origin

Destination 1

Availability 2

3

1

X11

C11

X12

C12

X13

C13

A1

2

X21

C21

X22

C22

X23

C23

A2

3

X31

C31

X32

C32

X33

C33

A1

4

X41

C41

X42

C42

X43

C43

A4

Requirement

B1

B2

B3

 TECHNIQUES OF FEASIBLE SOLUTION 1) North-West Corner Method: It may be recalled that feasible solution is the one, which satisfies the given set of constraints. Here first, the north-west corner is selected and the availability of with source utilized and the row is eliminated. Again after Ath row is utilized next new north-west corner is selected and its availability and requirement is satisfied, and this is done until all the requirement is satisfied, and as the allocation done, cost of respective allocation is known and total cost of transportation is calculated.

2) Vogel‟s Approximation Method: This method is an improved algorithm to obtain better feasible solution. The process is to evaluate penalty number for each row and column. It is given, as the difference between the lowest cost coefficients is each row and column. The penalty number physically amounts to cost penalty associated with by not accepting that row or column for assigning an allocation to its lowest cost cell. Select largest of these penalty numbers and determine the row or column to which an allocation has to be make. Thus row or column selected against largest PRODUCTION ENGINEERING DEPT.

30

OPERATIONS RESEARCH

penalty cost will be assigned more possible units and its lowest cost. The process will be repeated for each allocation to be made after eliminating row or column.

3) Inspection Method: If size of problem is small, inspection method is used. Here dummy row or column will be allocated. Select lowest cost cell and assign more feasible units to it. Repeat this until Ai < Bj or Ai > Bj and until availability and requirement become equal.

 DIFFERENT METHODS FOR OPTIMAL SOLUTION Before any other method is used for optimally test a check has to be made over number of allocations assigned in the solution; which must be equal to (m + n) having non-degenerate solution.

1) Stepping Stone Method: Any empty cell in the feasible solution gives non-basic variables. Each vacant on unfilled cell has X ij = 0. We never know if any one or more of them may become basic variables there by reducing the transportation cost or improving solution further. Each empty cell must be evaluated. Opportunity cost of an empty cell is the net increase or decrease in the total transportation cost if a unit is assigned to it. As sum conditions are to be honored, one unit from the present allocation in the row as well as column of this empty cell has to be deducted and some unit has to be added to the present allocation in the column as well as row at which deduction took place and whole orthogonal path is completed.

2) Modi Method: This method is also called modified method. In this method, we generate a column under beading of Ui and Vj of respectively right of the solution and row of at the bottom of the solution. Here number of variables „m‟ and „n‟ at U i and Vj are determined. Select any one of the Ui variables and assign any arbitrary value (normally zero) to it and determine rest of them the relationship. Ui + Vj = Cij After all the values Ui and Vj are determined, opportunity costs of empty cells are evaluated using the relationship. Dij = Cij – (Ui + Vj)

2. ASSIGNMENT MODEL Consider that there are „n‟ persons having varying degrees of proficiency to accomplish „n‟ different tasks in an organization. These „n‟ tasks are to be assigned to each one of „n‟ persons in such a manner that the effective performance of the organization as a whole is maximized. This is called assignment problem. The objective function to be optimized may be effective performance (more) total cost of finishing „n‟ jobs or total time of PRODUCTION ENGINEERING DEPT.

31

OPERATIONS RESEARCH

completing „n‟ jobs or any other suitable criteria for objective function depending upon the assignment problem.

 MATHEMATICAL STATEMENT OF ASSIGNMENT MODEL With „n‟ tasks and „n‟ agents, let Cij be the cost of its agent, performing jth task. n

n

Min Cij Xij i=1 j=1 n Sub to Xij = 1 j=1 The statement appears similar to that of transportation techniques and X ij takes value either 0 or 1. Xij = 1 (if task is assigned to agent 1) Xij = 1 (if task is not assigned to agent 1)

 TECHNIQUE FOR ASSIGNMENT MODEL Hungarian method follows steps as under:



   

Add as many dummy rows on dummy column to make matrix square. This corresponds to balancing of transportation problem. In a problem of assignment, each of the origin has availability of a unit and each of destinations has requirement of a unit. Take the first row and subtract its smallest cost element from all the elements. Repeat this for all the rows. Similar do for column. In this there will be at least one zero element in each row and column. Starting with the row that has only one zero give assignment there and cross mark there. If there are more than one zero, start with column and find the solution.

PRODUCTION ENGINEERING DEPT.

32

OPERATIONS RESEARCH

EXPERIMENT.NO: 6

PROJECT EVALUATION AND REVIEW TECHNIQUES & CRITICAL PATH METHOD (PERT/CPM) In real world time can‟t be known with total certainty. Particularly there are several projects involving research, innovation, and design, development where there is no previous experience or record of handling such activities. For such activities forecasting of time estimates will involve uncertainty. This necessitates probabilistic approach and is popularly known as PERT. This is its one and only feature which distinguishes it from CPM. Time t for an activity is assumed top have its probability density p(t) following Beta distribution in PERT; thus it is P(t) = k (t-to)tp-t) where to = the optimistic time, tp = the pessimistic time, = exponents values of which are decided on the basis of the mode and mean ab of the distribution Optimistic time means estimated duration of activity where all factors concerning the activity operate favorably. Although it is easier said than obtained, optimistic time presumes that everything goes all right for the activity right from the word „get-set-go‟. Pessimistic time means estimated duration of activity where in all factors concerning the activity operate unfavorably. Both of these estimates are qualified guesses and are additionally consider the concept of most likely time, t m that is the mode of the distribution. Figure 1 shows beta distribution followed by activity times, where T E is the average time in which activity is expected to be completed. The value of TE depends on how close the values of to and tp are relative to t m. Expected time of an activity TE = ( to + 4tm + tp )/6 Since the actual time of an activity is likely to vary form mean value (TE), we need the variance of the activity time distribution. Being unimodal distribution, it spread PRODUCTION ENGINEERING DEPT.

33

OPERATIONS RESEARCH

may be approximated to six times the standard deviation value. Thus, 6= tp - to Having three time estimates for all the activities in a project, we can compute average time and variance for each activity. Considering average time as actual time, the critical path is found. Project time will then be the sum of all the activity times in the critical path. But the activity time is random variable, sum of all such times is also a random variable, and we must give average time of the project and its variance. The variance of the project duration is the sum of all the variances of the activities in the critical path.



PERT & CPM Attempt is often made to bring out difference between PERT and CPM, besides that of time-estimates being probabilistic in PERT and deterministic in CPM. In fact, all other aspects are common. Historically PERT came up from different problem area. This was in relation to plan and accelerate development of the Polaris ballistic missile. When activity durations are uncertain, attention is principally focused on vents of activity. This is because events are identified. For example, to develop a process for synthetic cryogenic rubber. Here terminal point-event is known, though activity duration is not known with certainty. It is in this context of more familiarity of events involved and less certainty of activities. The PERT is called event-oriented. In fact, the difference is not organic but that of focus.



EXPECTED DURATION OF CPM-PERT By calculating expected activity time for each activity from three times estimates, PERT network is prepared and critical path is found on that. As each activity time has standard deviation and variance, the project duration obtained is also expected duration having standard deviation and variance. The critical path length is the summation of activities on the path. As the variance of a sum of independent activities is equal to the sum of their residual variance, the variance of critical path duration can be calculated, VT = variance of critical path = variances of critical activities VT = Vt1 + Vt2 + Vt3 VT = variance of any activity in PERT = ()2 Where is the standard deviation of each activity time =(tp – to) / 6 ST = standard deviation of the project = VT PRODUCTION ENGINEERING DEPT.

34

OPERATIONS RESEARCH

Variance VT standard deviation ST of the project gives the measure of uncertainty of the expected duration of the project TE.



CRASHING Being more practical on scheduling problems, know if the activities involved in the project can be reduced in duration by providing extra resources. These added resources will increase the cost of completing the activity, but other advantage out weigh this increased cost, the activity should be expedited, or crashed. The duration of the project will be reduced, only if duration of one or more critical activities is reduced. If there are activities using similar resources and if these activities have slack, they can be carried out at their normal or most efficient pace, with allocation of less resource, so that part of these can be diverted to the activity on the critical path without additional cost. In general, this is not possible for all activities and thus we use the concept of criticality to apply extra resources to project activities selectively, so that maximum reduction of project time is achieved with the least additional cost. The increased cost of an activity and is stated in terms of additional expenditure required for reduction in activity duration of one unit time period. The total cost of a project is not merely the sum of all direct costs of all the activities in the project, but other indirect expenses, which depend on the duration of project, must also be included. Thus, project schedules influence two types of costs – direct cost of all activities in the project, which increases when activities are expedited and indirect cost which decreases when the project duration is reduced.

PRODUCTION ENGINEERING DEPT.

35

OPERATIONS RESEARCH

Figure 2-a gives the relation of direct cost of the activity versus activity duration, presuming linear relationship. On the other hand, relation of indirect costs with respect to project duration assumed linear is given in figure 2-b. If activity „A‟ has the direct cost defined by the slope A any reduction of the duration of the activity by time TA will involve additional cost of (TA) *A. As against that it will reduce the indirect cost of the project by (TA) * . Thus, crashing of activity A is beneficial only if (TA) * (TA) *A i.e., A It, therefore, suggests that it is possible to have an optimum schedule – the lower – cost schedule, which strikes a balance between direct costs and indirect costs. For simplicity, time cost relationships is approximated as linear one. For better understanding, activity time-cost relationship is further elaborated. Initially, the time estimate is so set that the resources required are used in the most efficient way to accomplish the task at minimum cost. These are known as normal time and normal cost. Suppose there is an activity, which requires three men for its completion in normal time. In order to expedite it, every time one more man may be added and reduction in time and increase in cost may be noted and plotted on graph. Every time the slope will be steeper.

PRODUCTION ENGINEERING DEPT.

36

OPERATIONS RESEARCH

Finally it reaches to the point, where increase in number of men does not reduce the time further, thus this is the shortest time in which this activity can be completed. This is called crash time and cost against it as crash cost. By joining the crash and normal points, the line is accepted as entire relationship. Beyond normal time, if the activity is delayed, the cost may remain constant for small duration but will increase if the activity is excessively delayed. Figure 3 shows the activity time cost relationship. There is no reason to believe that every contractor should have some normal and crash points for a selected activity. Thee tow points will depend on experience of the ken, available equipments, teamwork, administrative ability that differ from organization to organization. The CPM model finds the least cost schedule after verifying the possible crashing of the project. To begin with, a preliminary schedule is generated with each activity at its normal point. This is the maximum length schedule. Then activities on critical part are marked as critical activities. For each of these critical activities, direct cost versus reduction in activity duration relation established. At the same, relation between project duration versus indirect cost of project is also known. If for one or more activities increase in direct cost is less than the saving in the indirect cost, then a less expensive schedule can be obtained. While considering critical activities, the activity that has the highest potential for affecting reduction in duration are the lowest additional cost is chosen first. The improvements are made in steps. New schedules are generated as long as activities can be crashed with the net reduction in total project costs.



NETWORK MODELS Example: Routine problem on telecom networks. At a given time some links are available, from the available ones, select the cheapest/fastest/non reliable/shortest path from a given origin to a destination.

PRODUCTION ENGINEERING DEPT.

37

OPERATIONS RESEARCH

 REPRESENTATION Label the modes 1,2,…..,m. Label the links 1,2,…..,m.

 DISCRETE FORMULATION For a minimally connected network, n = m – 1. Each link may change attributes [cost, capacity, etc.]. Each node may have same attributes [demand, capacity, etc.]. Put 1 for end mode. Put –1 for beginning mode. A useful concept is to define flows on links of a network. Let Xj be the row on link j, if Cj is the cost of flow on j.

 OBJECTIVE Xj = 1 Cj = 1

j leaving j entering General minimum cost flow problem (also called optimum distribution problem) Min CjXj Subject to CijXj = Bi for each i Is Xj Cij

j = arcs, i = nodes.

The shortest path problem is a special case of this with Bi = 1 for the origin Bi = -1 for the destination Bi = 0 for all other nodes Cij = cost / time for traveling link j, ij = 0, ij = 1. The bound constraints are treated separately. This Cp has integer solution (if the data is integer). This is because of the constraint matrix.

PRODUCTION ENGINEERING DEPT.

38

OPERATIONS RESEARCH

EXPERIMENT.NO: 7

GAMES THEORY  INTRODUCTION In business and economics literature, the term „games‟ refers to the general situation of conflict and competition in which two or more competitions are engages din decisionmaking activities in anticipation of certain outcomes over time. The competitors are called players. A player may be an individual, a group of individuals, or an organization. A few examples of the competitive and conflict situations where techniques of theory of games may be used to resolve them are; two or more candidates contesting and election with the objective of winning with more votes; advertising and other marketing campaigns between competing business firm; contractors filling bid to win business contract etc theoretically theory of games provides mathematical models that can be quite useful in explaining interactive decision-making concept. But as a practical tool, theory of games is limited in scope. However, it is one type of decision-making technique where on competitor‟s choice of course of actions does determined after taking in to account all possible alternative courses of action of another competitor engaged in the competition. The models in the theory of games can be classified depending upon the following factors: 1. NUMBER OF PLAYERS: If a game involving only two players, then it is called a two – person game. However, if the numbers of players are more than two, the game is referred to as n-person game. 2. SUM OF GAINS & LOSSES: If in a game the gains to one player are exactly equal to the losses to another player, so that sum of the gains and losses equal zero, then the game is said to be a zero-sum game of it said to be non-zero game. 3. STRATEGY: The strategy for a player is the list of all possible actions that the he will take for every payoff that might arise. Here it is on necessary that players have definite information about each other‟s strategies. The particular strategy by which a player optimizes his gains or losses without knowing the competitor‟s strategies is called optima strategy. The expected out come per play when players follow their optimal strategy is called the value of game. Generally, players in a game employ two types of strategies as given below: 1. PURE STRATEGY: It is decision rule, which is always used by the player to select the particular course of action. Thus, each player knows in advances of all strategies out of which he always selects only one particular strategy irrespective of the strategy

PRODUCTION ENGINEERING DEPT.

39

OPERATIONS RESEARCH

others may choose and the objective of the players is to maximize gains or minimize losses. 2. MIXED STRATEGY: When both the players are guessing as to which course of action is to be selected on a particular occasion with some fixed probability, it is mixed strategy game.

 TWO – PERSONS – ZERO – SUM – GAME A game with only two players, say player A ands B is called Two – persons - Zero – Sum – Game, if say player A‟s gain is equal to the loss of player B, so that total sum is zero. The payoffs in terms of gains or losses, when players select their particular strategies, can be represented in the form of a matrix, called the payoff matrix.

 ASSUMPTIONS OF THE GAME 1. Each player has available to him a finite number of possible courses of action. The list may not be same for each player. 2. Player A attempts to maximize gains and Player B minimize losses. 3. The decisions of both players are made simultaneously and announce simultaneously so that neither player has an adventives resulting from direct knowledge of the other player‟s decision. 4. Both the players know not only possible to themselves by also of each other

 PURE STRATEGIES  GAMES WITH SADDLE POINT The selection of an optimal strategy by each player without the knowledge of the competitor‟s strategy is the basis problem of playing games. Since the payoff for either player provides all the essential information, therefore only one player‟s payoff table to required evaluating the decisions. By convention, the payoff table for the player whose strategies are represented by (say player A) rows is constructed. Now the objective of the study 1 to know how these players select their respective strategies so that they may optimize their payoff. Such a decision making criterion is referred to as the minimax – maximin principle. Such principle I pure strategies game always leads to the best possible selection of a strategies game always leads to the best possible selection of a strategy for both players.

 RULES TO DETERMING THE SADDLE POINT The readers are advised to follow the following steps in order to determine the saddle point in the payoff matrix.

PRODUCTION ENGINEERING DEPT.

40

OPERATIONS RESEARCH

1. Select the minimum element in each row of the payoff matrix and write them under row minima heading. Then select a largest element among these elements and enclose it in a rectangle. 2. Select the maximum elements in each column of the payoff matrix and write them under column maxima heading. Then select a lowest element among these elements and enclose it in a circle. 3. Find out the elements that are same in the circle as well as rectangle and mark the position of such elements in the matrix. This element represents the value of the games and it is called the saddle point.

 MIXED STRATEGIES There are certain payoffs where pure strategies do not lead to saddle point and hence it is not possible to decide optimal strategies. There is no stable solution of the payoff matrix. The shifting from one strategy to another in case of unstable solution results in selection of the strategies by both players on random basis. The two players have to decide their plans for playing the game and assign probability values X and Y by which they will play their respective strategies. These plans are referred as mixed strategies.

 ARITHMETIC MODEL This method enables us to decide odd elements of each strategy in mixed strategies. From odd elements, we can calculate the optimal frequency of each strategy and also the value of the game. Consider the following payoff matrix:

A1 A2

B1 a11 a21 3 = a11 – a21

B2 a12 a22 4 = a12 – a22

1 = a11 – a12 2 = a21 – a22

Odd elements of a given row are obtained by the numerical difference of elements in another row. Similarly, oddments of a given column are obtained by the numerical differences of elements in another column. Optimal frequency of the strategy Optimal frequency of the strategy Optimal frequency of the strategy Optimal frequency of the strategy

A1, X1 A2, X2 B1, Y1 B2, Y2

= = = =

1 / (1 + 2) 2 / (1 + 2) 3 / (3 + 4) 4 / (3 + 4)

If total of oddments of rows is equal to the total of oddments of columns, the value of the game, V will be Vb1 = a11X1 + a21X2 ….. value if B plays 1 PRODUCTION ENGINEERING DEPT.

41

OPERATIONS RESEARCH

Vb2 = a12X1 + a22X2 ….. value if B plays 2 Va1 = a11Y1 + a12Y2 ….. value if A plays 1 Va2 = a21Y1 + a22Y2 ….. value if A plays 2

 METHOD OF SUB – GAMES This is applicable to any m x 2 or 2 x n game. The whole game is split into several 2 x 2 sub-games, which are then solved by pure strategy, arithmetic method or algebraic method as applicable. From amongst these sub-games, a sub-game which gives maximum game value m x 2 game (where row player has more than 2 strategies) or minimum game value in 2 x n games (where column player has more than 2 strategies) is selected as the solution.

 METHOD OF MATRICES Previously we discussed arithmetic method as applicable 2 x 2 payoff matrix. In fact, it can also be extended 3 x 3 matrix, as under, which is self – explanatory.

A1 A2 A3

B1 a11 a21 a31

B2 a12 a22 a32

B3 a13 a23 a33

Differences of column 1 & 2 1 = a11 – a12 2 = a21 – a22 3 = a31 – a32

Differences of column 2 & 3 4 = a12 – a13 5 = a22 – a23 6 = a32 – a33

Oddments 1 2 3

Differences of row 1 & 2 7 = a11 – a21 8 = a12 – a22 9 = a13 – a23

Differences of row 2 & 3 10 = a21 – a31 11 = a22 – a32 12 = a23 – a33

Oddments 1 2 3

If sum of row oddments is equal to sum of column oddments, optimum frequencies are: X1 = 1 / (1 + 2 + 3); Y1 = 1 / (1 + 2 + 3);

X2 = 2 / (1 + 2 + 3); Y2 = 2 / (1 + 2 + 3);

X3 = 1 / (1 + 2 + 3). Y3 = 3 / (1 + 2 + 3).

If sum of row oddments is not equal to sum of column oddments, the methods of matrices fail.

PRODUCTION ENGINEERING DEPT.

42

OPERATIONS RESEARCH

 LINEAR PROGRAMMING METHOD FOR GAME PROBLEM As remarked in graphical method for 2 x n or m x 2 games, the characteristic of linear relations can be used for solving the games by simplex method of linear programming. This method is applicable for more general m x n games between two players. It also comes handy when oddments of rows are not equal to oddments of columns. The game problem can be solved by simplex algorithm and the value of the game obtained for new matrix will be reduced by the constant added to get the value of the game for original matrix. Frequency values of strategies in both matrices remain same.

PRODUCTION ENGINEERING DEPT.

43

OPERATIONS RESEARCH

EXPERIMENT.NO: 8

INVENTORY MANAGEMENT  INTRODUCTION Inventory is material in stock and idles at a given point of time that will be used to satisfy some further demand of that material. Inventory decreases as demand process operates and increases as replenishment process operates. Demand may be random function and perhaps normally not under control of decision-maker, while replenishment in monitored by the decision-maker. The replenishment is the input process to the inventory system and gives the rate at which material is added to the inventory system. The source of replenishment may be either production or purchase of the material. The rate at which material is withdrawn from the inventory is the output process of the inventory. The output is always in response to demand. The output rate equals to demand rate unless the policy decision provides otherwise or in event of inventory level decreasing to zero level, when the situation is described as stock out or out-of-stock condition. The mathematical models of inventory system under different operating conditions involve mainly two-decision variable i.e. how much to order and when to order, when source of replenishment is purchase of how much to produce and when to produce, when production is the source or replenishment. With the associated cost of material and its storing, inventory system operating cost. It is therefore necessary to appreciate what benefits are derived from having inventory and then derive the concept of optimum inventory. The following benefits of inventory control, which resemble with its function, are selfexplanatory: 1. Inventory enables in decoupling production system from demand fluctuation. If demand increases inventory of finished and semi-finished goods take care of it. It demands decreases the inventory of finished and semi-finished goods could be built up. 2. Inventory enables to derive advantages of planning optimum lot size in production as a trade-off against setting time. 3. Inventory enables the sequencing of different components for optimum machine loading and set-up costs. 4. Inventory enables to have uniform labor force resulting labor force resulting in good labors relation. In production of the product with seasonal demand. 5. Inventory enables to sustain customer goodwill, as it is possible to honors the orders by committed dates. 6. In the absence of adequate, inventory a situation my come where “rush-order” has to be made for which, in general, very high price as to be paid.

PRODUCTION ENGINEERING DEPT.

44

OPERATIONS RESEARCH

All these advantages justify the policy of having large inventory. However, there are considerations, which warrant such a policy. These considerations are as under: 1. 2. 3. 4.

Inventory means locked up capital, which could be used for alternative purposed. Locked up capital involves interest. Inventory being physical goods in likely to deteriorate on storage. It involves the risk of fire ad theft. Alternatively, if involves insurance cost. This suggests that although inventory, because it has to be only adequate. Thus, excess inventories are undesirable. This calls for controlling the inventories in most profitable way.

 INVENTORY MODELS By inventory model, we mean to represent the inventory state, operating condition and costs involved through mathematical relationships, so as to fine Economic Order Quantity when source of procurement is purchase or to fine Economic Batch Quantity when source of procurement is manufacturing.

 Model 1: The model is Deterministic. Single item model i.e. it ignores all uncertainties and deals only with one item. It is characterized by: (1) demand is constant, at uniform rate and known with certainty (2) lead time and other system parameters such as costs are constant, independent of replenishment quantity and are known with certainty (3) replenishment is infinite and (4) shortage of stock is not permitted. A production system needs R units of a purchased material over a schedule period of time T. the rate of usage is uniform i.e. R/T. if all R units are purchased at the beginning of the schedule period T, the inventory position is as shown in fig, which is the graphical presentation of inventory level v/s time.

PRODUCTION ENGINEERING DEPT.

45

Ouantity in stock

OPERATIONS RESEARCH

T Time, t As shortage is not permitted, the replenishment has to commence at b. As replenishment is instantaneous, it is shown by the vertical line and the next cycle commences.

PRODUCTION ENGINEERING DEPT.

46

OPERATIONS RESEARCH

Thus, for the schedule period T there is average inventory of R/2 units, which involves holding cost. There is one order cost. Therefore, total associated cost for order R units: TCR (R) = C1 (R/2) T + C2

…..(1)

Ouantity in stock

Instead, if q units are ordered at the beginning and the order of the same quantity is repeated R/q times, the position will be shown in following figure.

tc

tc

tc Time, t

The total associated cost in schedule period T will then be R/q times cost associated with each order. TAC (q) = [C1 * (q/2) * tc] R/q TAC (q) = C1 * (R/2) * tc + C2 (R/q)…………(2) Comparing equations (1) and (2), it can be seen that by not ordering the full quantity in the beginning the cost-component due to holding decreases, as t c < T, and cost-component due to re-ordering increases R/q times. So, there has to be certain value of q at which TAC(q) is min. This value of q is optimum order-size of Economic Ordering Quantity designated as qo. Number of purchase-cycle in schedule time T = R/q = T/ t c. Therefore equation (2) can be rewritten as: TAC (q) = C1 * (R/2) * (Tq/R) + C2 (R/q) TAC (q) = C1 * (T/2) * q + C2 (R/q)…………..(3) From above equation TAC(q) depends only on q. Two individuals cost component (C1T/2)*q and C2R/q, as well as TAC(q) are shown in the following figure. To determine qo we differentiate TAC(q) in equation (3) with respect to q, for maximum and minimum TAC(q). Thus, d(TAC)/d(q) = C1T/2 – C2R/q2 = 0 So, qo = 2C2R / (C1/T) PRODUCTION ENGINEERING DEPT.

47

OPERATIONS RESEARCH

TAC (q) C2 R/q

Cost

C1Tq/2

q Second differentiation of TAC is Positive. Hence, the value of q is for minimum TAC, and corresponding value of q is optimum. So, qo = 2C2R / (C1/T).…………(4) This is called optimum lot size, also known as economic lot size. R/T is the rate of demand, in units per unit time. Designating it as r = R/T equation (4) becomes, qo = 2C2r/C1 If i is the interest rate on capital per unit time T and if holding cost essentially consists of purchases-investment. Then C1 = i * P where P is price per unit quantity. So, qo = 2C2R / (iPT) By substituting the value of qo of equation (4) in equation (3) we get minimum total associated cost during scheduled period T TAC (qo) = [C1C2RT/2] + [C1C2RT/2] = 2C1C2RT Minimum total associated cost per unit time TAC (q) = 2C1C2r This shows that for optimum value of qo when TAC minimum the cost-component due to holding of inventory is equal to the cost component due to re-ordering. Thus in for point P lies on the ordinate from the point of intersection of the graphs of individual costcomponents. Now, tcc optimum cycle times is given by, Ttcc = Tqo/R = T/R * [2C2R/C1T] = 2C2T/(C1R) = 2C2/(C1r)

PRODUCTION ENGINEERING DEPT.

48

OPERATIONS RESEARCH

 MODEL 4 Having considered deterministic demand models earlier, we may now consider the cases where demand is probabilistic, which is quite realistic in every day world. CHARACTERISTIC:

 

Demand is in discrete quantities; demand is probabilistic and is met instantaneously. Set-up cost is zero. Therefore, relevant cost elements are holding cost and shortage cost.

Let r l C1 C3

= = = =

number of discrete units required with probability, pr, stock level in discrete units, holding cost per unit quantity per unit time, shortage cost per unit quantity per unit time,

When l > r the inventory cost is due to holding. When r > l the inventory cost is due to shortage. 1. As demand is probabilistic the probable units in inventory is (l - r) pr and its cost is C1 (l - r) pr. The total inventory cost due to holding is, r=1

 C1 (l - r)pr r=0 As the demand exceeds and becomes l + 1 and above the cost is due to shortage. The probable units in shortage is (r - l) pr and its cost is C3(r - l) pr. Thus, if the demand is to vary from zero to infinity, r=1 TAC (l) =

∞

 C1(l - r)pr

+

r=0

 C3(r - l)pr

.....(5)

r=l+1

Now, optimum stock level lo can be considered as one in which one more unit well as one less unit will increase the cost. That is at lo. TAC (lo + 1) > TAC (lo) and TAC (lo - 1) > TAC (lo) We may re-write the equation (5) for l+1 stock level l+2 TAC (l + 1) =

∞

 C1(l + 1 - r)pr 0

l+1

+

 C3(r - l - 1)pr

.....(6)

l+2 1

PRODUCTION ENGINEERING DEPT.

49

OPERATIONS RESEARCH

Now

 C1(l + 1 - r)pr

 C1(l + 1 - r)pr

=

0

+ C1(l + 1 - l - 1)pl+1

0 1

 C1 (l + 1 - r)pr

=

0 l+1 So,

1

 C1(l + 1 - r)pr

=

0

1

 C1(l - r)pr

 C1(l - r)pr

+

0

.....(7)

0

∞ Similarly for

 C3(r - l - 1) pr l+2 ∞

=

 C3(r - l - 1) pr - C3(l + 1 - l - 1) pl+1 r=l+1 ∞

=

 C3(r - l – 1 )pr l+1

∞ So,



∞ C3 (r - l - 1)pr =

l+2

∞

 C3 (r - l)pr -  C3pr l+1

.....(8)

l+1

Substituting equations (7) and (8) in equation (6), l TAC (l + 1) =

l

 C1(l - r)pr

+

∞

 C1pr

0

0

l

∞

+

∞

 C3(r - l)pr -  C3pr l+1

l+1

So, TAC (l + 1) =

 C1(l - r)pr

+

0

l

 C3(r - l)pr

+

l+1

 C1(l - r)pr 0

∞ -

 C3pr

.....(9)

l+1

First two terms in equation (9) make TAC (lo) as in equation (5), therefore, 1 TAC (l + 1) = TAC (l) +

∞

 C1pr 0

∞

l

-

 C3pr l+1

∞

PRODUCTION ENGINEERING DEPT.

50

OPERATIONS RESEARCH

Now,  pr = 1 = 0

 pr

+

0

 pr l+1 l

l

Therefore, TAC (l + 1) = TAC (l) +  C1pr - C3 [1 -  pr] 0 0 l So, TAC (l + 1) = TAC (l) + (C1 + C3) pr - C3 0 For l to be optimum, TAC (lo + 1) > TAC (lo) lo

i.e., (C1 + C3)  Pr - C3 > 0 0 lo

So,  Pr > 0

C3 C1 + C3

So, P (r / lo) >

C3 C1 + C3

.....(10)

P (r / lo) means summation of P (r) for the value of r from zero to lo. If stock level is l - 1, l-1 TAC (l - 1) =

∞

 C1 (l - 1 - r) pr

+

0

 C3 (r - l + 1) pr

.....(11)

l

l-1 The first term

 C1 (l - 1 - r) pr

can be rewritten as

0 l

 C1 (l - 1 - r) pr



+ C1pr

0



l

l

 C1 (l - r) pr -  C1 pr 0

+ C1pr

.....(12)

0 ∞

The second term

 C3 (r - l + 1) pr can be rewritten as l

∞

∞

PRODUCTION ENGINEERING DEPT.

51

OPERATIONS RESEARCH

 C3 (r - l + 1) pr

=

l

 C3 (r - l + 1) pr

+ C3pl

l+1 ∞

∞

=  C3 (r - l) pr +  C3pr + C3pl l+1 l+1 ∞

l

=  C3 (r - l) pr + C3 (1 -  pr) + C3pl l+1 0

.....(13)

Substituting equation (12) and (13) in equation (11), l TAC (l - 1) =

TAC (l - 1) =

l

∞

l

 C1 (l - r) pr -  C1pr +  C3 (r - l)pr 0

0

l

∞

l+1

l

 C1 (l - r) pr +  C3 (r - l)pr 0

+ C3 (1 -  pr) + C3pl 0

l+1

(C1 + C3)

 pr +

C3 + C1pl + C3pl

0

So, l-1 TAC (l - 1) = TAC(l) - (C1 + C3)  pr + C3 0 For l to be optimum, TAC (lo - 1) > TAC(lo) l-1 So, - (C1 + C3)

 pr + C3 > 0 0 l-1

So, So,

 pr

C3 C1 + C3

>

C3 C1 + C3

> p(r / lo - 1)

0 .....(14)

Combining equations (10) and (14), for minimum TAC (lo) so the optimum stock level should be such that, p (r / lo - 1) <

C3 < p (r / lo) C1 + C3

PRODUCTION ENGINEERING DEPT.

52

OPERATIONS RESEARCH

p (r / lo - 1) means summation of p (r) for the value of r from zero to (lo - 1).

PRODUCTION ENGINEERING DEPT.

53

OPERATIONS RESEARCH

EXPERIMENT.NO: 9

QUEUING THEORY  INTRODUTION Most of the basic work on queues or waiting line theory was carried out by A. K. Erlang in early nineteenth century. He experienced congestion of telephone traffic during his work at Copenhagen Telephone Company and came out with most of the work for the mathematical models in queuing theory. Service-seekers and serves make a system, which needs consideration. Service may be anything that occupies a man, facility or location for some period of time so that potential service-seekers known as arrivals at any time and require the use of server. If at any time, in a queue may drive out a potential customer. On the other hand, if more serves are provided that reasonably necessary so that no queue or very short queue is formed, it costs more money. Therefore, a trade-off becomes necessary in designing service facility system. This needs an insight into the growth of queue in a given system.

 INPUT PROCESS:In order to describe the input processes, a random variable such as time between successive arrival events is designated. It is assumed that random variable is independent and identically distributed. Thus knowing the probability distribution, the input process can be described. Often the arrival of customers is completely random in nature and it is assumed that the number of customers arriving in any time interval „t‟ follows through Poisson distribution, with parameter t. Here,  is the average number of arrivals per unit time. There are some situations where customers arrive at fairly regular time intervals.

PRODUCTION ENGINEERING DEPT.

54

OPERATIONS RESEARCH

One variation of input process is the effect of status of queue on arrival. If a queue is specified to be finite, a customer arriving at the queue after this is not permitted to join the queue. Further, even if queue is not finite, a customer, seeing a long queue ahead of him might not join the queue. This is called balking. It may also happen that customer having joined the queue earlier might leave it with or without any intention of returning. This is called reneging. It is pertinent to queue discipline. So, probability of one arrival = 1 - (1-T) = T Let us note that if the density of inter arrival is exponential, the density g(y) of the total arrival time y for ant n consecutive arrivals is given by, g(y) = (y)n-1 e-ny / (n-1)!; y  0 and probability of n arrivals in time interval, T = (T)n e - T/n! Thus, assumption of exponential distribution of inter arrival times is equivalent to assuming Poisson distribution for probability distribution of n arrivals in interval T. Expectation, E (n/T) = T Variance, 2 (n/T) = T Instead of exponential distribution of inter arrival time, Erlang distribution of order n can be used. This is, f(t) = (n) (nt) (n-1) e - nt/(n-1)!; t  0 Expectation, E(t) = 1 /  Variance, 2(t) = 1/n2 (Erlang)

 SERVICE TIMES Assuming that one customer is served by one server at a time, and service time for one customer is independent of that for other. Let g(t) = probability density function of time t required to serve one customer. Then mean time of service = 0∞ e-t g(t) dt = 1 /  where  is mean service rate or number of customers served per unit time. Let us assume exponential (negative) distribution fro service time. Then, g (t) =  e-t; t  0 probability that service is not completed in time interval T = e-t for small values of T, it is approximately.

PRODUCTION ENGINEERING DEPT.

55

OPERATIONS RESEARCH

Probability of the event that service is complete in time interval T = 1 - T and the probability of the event that service is completed in time interval T = T

 QUENUE DISCIPLINE Queue discipline describes the policy of serving the service-seekers of a queue. Normally first-in-first-out popularly known ad FIFO (first-come-first-served) is a common queue discipline. It is generally followed in practice. Some manufacturing concerns consider the problem of machine breakdowns and repairs as a queuing model. In a group of machines, breakdown takes place at random time.

 ITERARRIVAL TIMES:It is necessary to specify the probability distribution of inter arrival times. Considering f(t) as the density function for the time interval t between any two consecutive arrivals, when t  0. Meantime between two consecutive arrivals = 0∞ f(t) t dt So, 1/ = 0∞ f(t) t dt It arrival is assumed completely random; the density function of inter arrival time can be described by negative exponential distribution. i.e., f(t) = e-/t, t0. Now, let A be the event that there is no arrival in the interval (O, T). The probability that there is no arrival in the interval (O, T) and no arrival in (O, T+T) is given by P(AB) =

∞ T+T

 e-/t dt = e-(T+T)

Now, P(B/A) = P(AB)/P(A) = e-(T+T)/ e-/t = e -t Probability of no arrival in interval T = e -t This depends only on T. Expanding e -t by Taylor‟s series; Probability of no arrival in interval T = 1 + (-T)/1! + (-T)2/2! + (-T)3! = 1-(T) + 2(T)2/2 - 3 (T)3/6

PRODUCTION ENGINEERING DEPT.

56

OPERATIONS RESEARCH

Neglecting higher terms of (T) for very small values of T, approximately probability of no arrival T = 1T. In any small interval of time T, as it is presumed to be sufficiently small to permit only one arrival at the most, only two mutually exclusive and collectively exhaustive events can occur i.e. either there is one arrival or there is no arrival. P [no arrival in any interval T ] + P [only one arrival in interval T] =1

 KENDALL‟S NOTATIONS Kendall‟s notations are to specify queuing models in standardized symbols, which mainly relate to inter arrival time and service time distribution and number of serves in the system as Nature of input Process

Nature of service time distribution

Number of servers

For symbols, M designates Exponential distribution En designates Erlang distribution of order n. D designates Deterministic distribution Thus, the queue model M/M/2 symbolizes Poisson input, exponential service time and two servers. It is believed that in order to specify a queuing model correctly one must specify the queue discipline above. To cover this additional variations Kendall‟s rotations were extended by three more terms in 1971 in a conference on Standardization of Notation in Queuing Theory. Now it reads : Input Service Process process

Number of servers

Limit of number in system

Number in the source

Queue discipline

Last three terms are omitted is they are (///∞/∞/ FIFO)

 QUEUE M/M/1: BALANCE EQUATION METHOD Let us consider a service system where there is only one server, input is Poisson and se5vice time distribution is exponential. We want to obtain operating characteristics of the queue. These characteristics will answer some of the following questions: Will a queue be formed? PRODUCTION ENGINEERING DEPT.

57

OPERATIONS RESEARCH

If so, will it be what is its probability of having n customers? What will be the mean number of customers in the system? What will be the queue length? What will be the waiting time for a customer? Let inter arrival time density function be  e -t and service time density function be e-t. Let at any time n be the number of customers in the system, including those waiting and those being served. Let Pn(T) be the probability that there are n customers in system at time T. In that case, the probability of having n customer in the system at time T+T is the union of four mutually exclusion and exhaustive events as:

  

One arrival and no departure in time interval T, T+T with n-1 customers at time T.



One arrival and one departure during time interval T, T+T with n u

Neither arrival nor departure during time interval T, T+T with n customers at time T. One departure and no arrival during time interval T, T+T with n+1 customers at time T.

Therefore, the balance equation can be set out as under: Pn(T+T) = (Probability of 1 Arrive in T)(Probability to no departure inT)Pn-1(T) + (Probability of no arrival in T) (Probability of no departure in T) Pn(T) + (Probability of no arrival in T)(Probability to one departure in T)Pn+1(T) + (Probability of 1 Arrive in T)(Probability to one departure in T) Pn(T) Making use of relations, Pn(T+T) = (T)(1-T) Pn-1(T) + (1-T)(1-T) Pn (T) + (1-T) T Pn+1(T)

PRODUCTION ENGINEERING DEPT.

58

OPERATIONS RESEARCH

Simplifying the terms on the right hand side, [Pn(T+T) - Pn (T)] / T = Pn-1(T) - TPn-1(T) - Pn(T) - Pn(T) + 2T Pn(T) + Pn+1(T) - T Pn+1(T)  dPn / dT = T

lim

0 {Pn(T+T) - Pn (T)} / T

 dPn / dT = Pn-1(T) – (+)Pn(T) + Pn+1(T) This expression is valid for n>0 For n=0, n-1 is meaningless, and departure has no significance. Therefore P0(T) is also meaningless. Let this limiting value of probability distribution be n for equilibrium dP n / dT must be zero, Pn becomes independent of T. Then equation becomes: Pn-1(T) - (+)Pn + Pn+1 = 0, for n = 1,2,3…….. subscript (T) is dropped for brevity and in equation , - P0 +  P1 = 0,

for n = 0

 P1 = {/}P0 Let / = . If >1, means rate of arrival is more than mean rate of service. As a consequence, the queue continues to build up indefinitely and for this the stationary probabilities do not exist. Only if 1, there exist stationary probabilities Pn. Equation can be re-written as Pn+1 = {(+)Pn – Pn-1} /  Putting n=1, P2 = (+)P1 /  Putting  = /, P0 = P0, P2 = 2 P0 Likewise P3 = 3P0 and it can be shown that Pn = n P0 ∞

Now,

 Pn

= 1

n=0  P0 + P1 + P2 + P3 +…+ Pn = 1  P0 + P0 + 2P0 + 3P0 + … + n P0 = 1.  P0 [1 +  + 2 +3 + … +n] = 1.  P0 = 1 / [1 +  + 2 +3 + … +n] = (1-). And Pn = (1-)n, for n = 0,1,2,…etc. P1 / P0 = P2 / P1 = P3 / P2 =…= Pn+1 / Pn =  Hence, Pn is in geometric progression for n = 0,1,2, …

PRODUCTION ENGINEERING DEPT.

59

OPERATIONS RESEARCH

The mean number of customer in the system, ň, is the summation of products of probabilities with corresponding values of n, n = 0, 1, 2, 3, … n=∞ ň =

 n Pn

= P1 + 2P2 + 3P3 +… = P0 + 22P0 +…

n=0  ň = P0 (1 + 2 +32 + ...) = P0 / (1-)2 Putting Po = (1-);  ň =  / (1-) =

 / (-)

P0 is the probability of having no customer in the system. Two events that the server is busy and that he is not busy are collectively exhaustive events. P0 [server is not busy] + P [server is busy] = 1. P0 [server is busy] = 1- P0. Thus, the traffic intensity is also the probability of server being busy. The queue length of mean number of customer in the waiting line nq will be given by, the summation of the product, pos probabilities and (n - 1) for n = 1 to infinite as one customer is being served. n=∞ nq =

n=∞

 (n-1)Pn = n=1 n=∞

nq =

 nPn

n=1

 nPn

n=∞ -

n=1

 Pn n=1

n=∞ -

 Pn - P0

n=1

 nq = ň - [1 - P0] But, ň =  / (1 - ) and P0 = 1 -   nq = { / (1-)} -  = 2  nq =  /  (-) For a customer joining a queue two matters are important. Firstly, how long he will have to be in the system? Secondly, how long he will to wait till server becomes available to serve him? In steady state queue, a customer who joins at average n customer in the system and after moving along the queue eventually gets served leaves behind the same average n customer. This means that his duration stay in the system Ts is such that provides for n arrivals at the mean rate of . Therefore ň = Ts and it is called Little”s formula.

PRODUCTION ENGINEERING DEPT.

60

OPERATIONS RESEARCH

Here, Ts = Expected number of customer in the system / Mean rate of arrival = ň /  =  / (1-) = 1 / (-) Similarly, Tq = Expected waiting time in the system - mean service time = Ts – (1/) = {1/(-)} – {1/} =  / (-).

PRODUCTION ENGINEERING DEPT.

61

OPERATIONS RESEARCH

EXPERIMENT.NO: 10

REPLACEMENT THEORY  INTRODUCTION Any engineering equipment has to give production service. While doing that, it essentially needs operation cost. Its operational economy is rated through amount of production or service per unit cost. With usage and years, equipment undergoes wear and tear, needs progressively more maintenance, goes down in production or service and requires frequent repairs. This involves additional cost, which in general increases with years. Therefore, at some stage one intuitively feels, the existing equipment has to be replaced by new similar or technologically better equipment. This is “Replacement Problem” and it seeks to answer „when to replace‟ and „with what?‟ The answers to these questions can be had with “Replacement Theory”.

 COST OF “KEEPING IT ON” AND “REPLACING” If we do not replace the existing equipment, we incur „operation, maintenance and repairs cost‟ which increases every year. Let Cm(n) = annual cost „operation maintenance and repairs‟ in nth year C = capital investment on the equipment which once incurred is charged as 88permanent cost If existing equipment is replaced it is discarded either as scrap of as still productively usable in some application fetching some price on desired either as scrap or as still productively usable in some application fetching some price on disposal. This is called salvage value. The salvage value of the equipment naturally decreases with year the decrease being very slow in initial years and then very steep, as it tends to be a scrap. Let Sn = salvage value of the equipment at the end of nth year Let us presume for simplicity that money value does not change with year. That is interest and inflation is insignificant. The cumulative total cost of „keeping it on‟ upto nth years = Capital investment value at the end on nth year + cumulative cost of 88operation, maintenance and repairs for nth year n TCK(n) = C + Cm 0

PRODUCTION ENGINEERING DEPT.

62

OPERATIONS RESEARCH

If replacement is considered at the end of the nth year, CCR(n) = cumulative cost if replacement at the end of nth year = TCK(n) - Sn Average annual cost if replaced at the end of nth years CCR(n) = [(C – Sn) + Cm] / n Obviously when average annual cost begins to rise, the replacement is due. This is the year of replacement n is given by when, CCR(n – 1) > CCR(n) and CCR(n + 1) > CCR(n) Implicit in the above is an assumption that level of performance of the equipment as been maintained the same over the years.

 REPLACEMENT BY ALTERNATIVE EQUIPMENT In the previous article, we decided the due age of replacement on the basis of average annual related cost of keeping the equipment. It may happen that while existing equipment is being used, similar but improved version of equipment with different investment cost, operation cost pattern and resale value pattern is available in the market. In such a situation, decision is to be made whether the existing equipment needs to be replaced by new version and if so when such a replacement should be made. Let A be the existing equipment. Its own minimum average annual cost of keeping is given by, n (CCR)A = [(Ca-San) + Cma] / n 0 where, Ca = capital investment of A San = resale value of A at the end of nth year Cma = operation maintenance cost of A from year to yea n = number of years after which the replacement of A is due. Let B be the new equipment. Its own minimum average annual cost of keeping is given by, (CCR)B = [(Cb-Sbn1) + Cmb] / n1 where, Cb = capital investment of B Sbn1 = resale value of B at the end of nth year Cmb = operation maintenance cost of B from year to yea n1 = number of years after which the replacement of B is due. Obviously, if (CCR)B < (CCR)A replacement of A by B is apparently advisable. Next question is when this replacement should be made? It is often suggested that in the year K when, PRODUCTION ENGINEERING DEPT.

63

OPERATIONS RESEARCH

[Ca – Sa(k+1) + SCma] [Ca + Sa(k) + SCma] > (CCR)B when incremental cost of A next year over previous year is more than minimum of annual average of B the replacement should be made. This is not correct because when equipment B replaces equipment A there is (C – S) of A carried over as also cumulative cost of maintenance of A till that year thus in composite arrangement of A replacing B other cumulative costs of A till that year and that of B thereafter should be worked, and on that basis the average annular cost be worked out, reckoning from the year of installation of A.

 CAPACITY CORRECTION IN ALTERNATIVE EQUIPMENT When exiting equipment is replaced by new equipment the latter may not have in general the same capacity specification. For example, existing lathe may have the capacity for producing 10 units per hour, whereas new equipment may have capacity for producing 12 units per hour. In such a situation comparison of costs has to be on the basis of the same performance and the correction factor should be applied by an appropriate multiplier.

 MONEY VALUE CHANGING WITH TIME REPLACEMENT The decisions regarding replacement of equipment are taking into account the money values of related costs new purchase, salvage value, operation cost, maintenance cost, repair cost from the year. So we have to work out the discounted value of money the present worth of money against the future cost figures, and find out the numbers of years, n at the end of which the equipment should be replaced. If i is the net incremental rate per annum, after one year it becomes (1+i), after two years (1+i)2, and after n years (1+i)n. thus, the present valve of 1 Rupee of nth year is 1 / (1+i)n. If we define r = 1 / (1+i) as discount range, present worth of 1 Rupee of nth year is rn. If C is the capital investment of today, m1, m2,… are the maintained repair cost in 1, 2, 3,… year respectively. Equipment is used to provide service or give production. It is presumed that repairs and maintenance cost are carried out from year to year to retain the same level of service or production.

 SALVAGE VALUE CONSIDERED Previously change of worth of money was considered without salvage value of the equipment to be replaced. If Si is the salvage value of the equipment, its discounted worth at present is Si / (1 + k)i = Siri as the salvage value is reckoned at the end of the concerned year.

PRODUCTION ENGINEERING DEPT.

64

OPERATIONS RESEARCH

Thus equation is modified as Pn = C + (m1 + rm2 + r2m3 + … + rn-1 mn) - Snrn Its weighted annual average can be shown as n

n

 = (C +  miri-1 – Snrn) /  ri i=1

i=1

The replacement is due for that value of n for which  is minimum.

 GROUP OF REPLACEMENT POLICY:It may appear advantageous to replace and item as and when it fails, particularly that item which does not deteriorate in its performance with lapse of time. However, the inherent risk in this policy of replacement is that replacement, when needed may take some time may be for producing item, putting a man to replace the item and time for replacing the item. This will entail down time or non-working period of the system. If it is a production system, this means loss of production. This implies cost. Hence, it is worth considering replacing an item before it has failed. The concept is similar to „preventive maintenance‟ or „inventory system‟ in which cost of shortage is very high. Let us consider a system having N number of identical items. This constitutes a group. If all items of group are replaced simultaneously at one time, the cost per item is C g. Having installed all N items as a group, the policy is to replace individual items as and when they are in group. The cost of individual replacement on failure is C i. Obviously Ci > Cg. The decision variable is period „t‟. The information needed is failure data over a period of time. This provides probability of failure. Let us consider following situation. A large hospital complex has several operation theatres. Each operation table has special light bulge attachments. The bulge is prone to failure. There are 200 bulbs installed in all. Considering 500 hours as „period‟ the failure of similar bulb has been as under, Out of 100 bulbs 9 20 33 51 77 90 100

failed by the end of first period, failed by the end of second period, failed by the end of third period, failed by the end of fourth period, failed by the end of fifth period, failed by the end of sixth period, and failed by the end of seventh period.

PRODUCTION ENGINEERING DEPT.

65

OPERATIONS RESEARCH

The management considers to make it a practice to replace all in a group at one time, then replace individual bulb as and when it fails, and after „fixed interval‟ of time. It is given that each bulb, when replaced in a group, costs Rs. 5, but when replaced individually on failure costs Rs. 20. Obviously, the criterion for optimization if the cost of the period. The period at the end of which minimum „average cost per period‟ is obtained, that will be „the fixed interval‟ or time for group management. Age-wise failure Probability is as under: 0-1 period 0.09 1-2 period 0.20 – 0.09 = 0.11 2-3 period 0.33 – 0.20 = 0.13 3-4 period 0.51 – 0.33 = 0.18 4-5 period 0.77 – 0.51 = 0.26 5-6 period 0.90 – 0.77 = 0.13 6-7 period 1.00 – 0.90 = 0.10 Let nk be the number of replacement at the end of kth period.

PRODUCTION ENGINEERING DEPT.

66

OPERATIONS RESEARCH

 PROBLEM Two functionally identical machine tools P and Q are available in the market. There is no market for machines even one-year old and when eventually disposed off as scrap it fetches insignificant amount. Price of machine tool P is Rs. 12,000. Its operation, maintenance and repair cost is Rs. 400 in the first year, progressively increasing by Rs. 100 in next two years, then by Rs. 200 in next two years and finally by Rs. 300, 400, 600, 800 in subsequent years. Price of machine tool Q is Rs. 12,000. Its operation, maintenance and repair cost is Rs. 200, 350, 550, 750, 1000, 1300, 1800, 2400, 3000 from year to year. (a) If worth of money remains constant, which is a better choice, P or Q? And in that case, what should be the replacement policy? (b) If worth of money increases by 10% every year, which is a better choice, P or Q? And in that case, what should be the replacement policy? (c) If Q is offered for purchase, through interest-subsidized scheme by State Finance Corporation, to the extent of 5%, what should be the replacement policy? State the assumptions you make.

 SOLUTION It is assumed that running costs – operation, maintenance and repairs including downtime costs – are increased at the beginning of each concerned year.

Table – 1 Machine Tool – P C = 12000, K = 0, r = 1 / (1+K) = 1 Year i

mi

ri-1

miri-1

 miri-1

ri-1

1 2 3 4 5 6 7 8 9

400 500 600 800 1000 1300 1700 2300 3100

1 1 1 1 1 1 1 1 1

400 500 600 800 1000 1300 1700 2300 3100

400 900 1500 2300 3300 4600 6300 8600 11700

1 2 3 4 5 6 7 8 9

PRODUCTION ENGINEERING DEPT.

C+ miri-1  ri-1 12400 6450 4500 3575 3060 2767 2615 2575 2634

67

OPERATIONS RESEARCH

(a) Table – 1 gives the weighted average of annual cost i C +  miri-1 = i=1 i  ri-1 i=1 It can be seen with m8 = 2300, m9 = 3100, 8 = 2575 i.e., m8 < 8 < m9 Therefore, the minimum present worth of annual value for P is Rs. 2575 Corresponding value for Machine Tool Q, as given in Table – 2 is Rs. 2669. Thus, machine tool P is a better choice and with this, the replacement policy is to affect the replacement at the end of 8th year.

Table – 2 Machine Tool – Q C = 13000, K = 0, r= 1 / (1+K) = 1 Year i

mi

ri-1

miri-1

 miri-1

ri-1

1 2 3 4 5 6 7 8 9

200 350 550 750 1000 1300 1800 2400 3000

1 1 1 1 1 1 1 1 1

200 350 550 750 1000 1300 1800 2400 3000

200 550 1100 1850 2850 4150 5950 8350 11350

1 2 3 4 5 6 7 8 9

PRODUCTION ENGINEERING DEPT.

C+ miri-1  ri-1 13200 6775 4700 3713 3170 2859 2708 2669 2706

68

OPERATIONS RESEARCH

(b) When change in money worth is taken into account, r = 1 / (1.10). The weighted average of annual cost,  is tabulated in Table – 3 for machine tool P, and in Table – 4 for machine tool Q.

Table – 3 Machine Tool – P C = 12000, K = 0.10, r= 1 / 1.10 Year i

mi

ri-1

miri-1

 miri-1

ri-1

1 2 3 4 5 6 7 8 9

400 500 600 800 1000 1300 1700 2300 3100

1.000 0.909 0.826 0.751 0.683 0.621 0.565 0.513 0.466

400 455 496 601 683 807 961 1180 1445

400 855 1351 1925 2635 3442 4403 5583 7028

1.000 1.909 2.735 3.486 4.169 4.79 5.355 5.868 6.334

C+ miri-1  ri-1 13200 7081 5109 4168 3650 3568 3172 3104 3096

Table – 4 Machine Tool – Q C = 13000, K = 0.10, r= 1 / (1.10) Year i

mi

ri-1

miri-1

 miri-1

ri-1

1 2 3 4 5 6 7 8 9

200 350 550 750 1000 1300 1800 2400 3000

1.000 0.909 0.826 0.751 0.683 0.621 0.565 0.513 0.466

200 318 454 63 683 807 961 1231 1398

200 518 972 1535 2218 3025 3986 5217 6615

1.000 1.909 2.735 3.486 4.169 4.790 5.355 5.868 6.664

PRODUCTION ENGINEERING DEPT.

C+ miri-1  ri-1 13200 7081 5109 4168 3650 3568 3172 3104 3096

69

OPERATIONS RESEARCH

For machine too P, least value of  is Rs. 2996, whereas for machine tool Q this value does not appear in the range of data given. However, the least value for Q as available is Rs. 3096. Therefore, P is better choice with replacement at the end of 8th year. (c) When interest for machine tool Q is subsidized, r = 1 / (1 + 0.05) and the value of  are tabulated in Table – 5. Comparing the least value of Rs. 2873 with the least value of D for P in Table – 3 i.e. Rs. 296, it can be concluded that the machine tool Q is better choice, with replacement at the end of 8th year.

Table – 5 Machine Tool – Q C = 13000, K = 0.05, r= 1 / (1.05) Year i

mi

ri-1

miri-1

 miri-1

ri-1

1 2 3 4 5 6 7 8 9

200 350 550 750 1000 1300 1800 2400 3000

1.000 0.952 0.907 0.864 0.823 0.784 0.746 0.711 0.677

200 333 499 648 823 1019 1268 1706 2031

200 533 1032 1680 2503 3522 4790 6496 8527

1.000 1.925 2.859 3.723 4.546 5.330 6.076 6.787 7.464

PRODUCTION ENGINEERING DEPT.

C+ miri-1  ri-1 13200 6933 4911 3945 3411 3101 2929 2873 2884

70

OPERATIONS RESEARCH

EXPERIMENT.NO: 11

STUDY ABOUT SEQUENCING PROBLEM.  HEUSTERIC PROBLEM SOLVING. Problem solving methods discuss earlier posses well defined models. Analytical techniques and algorithms to obtain optimum solution. As was stated in model formulation phases in chapter of real life problems. In general defi. Clear cut crystallization and trimming problem can be brought within the relation of models. The techniques to the tool kit of O.R. will take care of the solution. However in many cases this may not be possible. In such cases heustric approach in problem solving comes hardly. It is now obvious that the ill-structured problems are those problems which are not amenable to solution by analytical or algorithms solution techniques. The concept of illstructured problems is understood in contrast to well structured problem ( WSP), the character being characterized by : 1. formulable as an acceptable model. 2. capable of attaining feasible solution. 3. defined criteria for feasibility and optimum solution. 4. availability of techniques for solving models. 

SEQUENCING PROBLEM :The problem of sequencing falls within the realm of heuristic methods. Sequencing problems encompasses those scheduling problems in which objective function or sequence for processing set of jobs or activity to be undertaken on given facility in a defined technological order. Sequence is a very important function in production planning and control. This chapter will concentrate machine to perform operation on the job which have unique design futures and have resulted from a specific customer order. In order to describe a specific case of job shop scheduling problem we want to study for 4 factors which are 1. the job arrival . if „n‟ jobs arrive at a time in a shop where „m‟ facilities on which they are to be processed are idle and available . the problem is called as static problem. The problem will be known as dynamic problem if jobs arrive at random with some stock tic process. 2. number of machines „m‟ that are in the job shops. 3. the flow process for „n‟ jobs through „m, machines. 4. the measure of performance to be optimized which plays a decisive roll in job shop schedule problem. Gantt chart is a most simple and widely expected representation of scheduling are shown along vertical axes and operations time along horizontal axis. Each operation on various resources (facility over machines) is represented by a horizontal bar. Since the chart breaks down resources allocation by time. It gives a display of max span. Job waiting chart breaks down resources allocation by time it gives a display

PRODUCTION ENGINEERING DEPT.

71

OPERATIONS RESEARCH

of observation of this chart. And improvement to the schedule depend on analyst critical observation. The general problem of sequencing is „n‟ jobs are to be performed on 1,2,or several or all machine. Each job having its own technological order on machine. The sequence be so determine as to minimize total elapsed time for „n‟ jobs to be completed. Rules of heuristic methods in sequencing problems have so far been establish for a few specific cases viz. 1. n jobs on 1 machine. 2. n jobs on 2 machine x & y in the same order. 3. n jobs on 3 machine x,y & z and subject to special restriction of data. 4. 2 jobs on m machines each jobs may have its technological order and 5. n jobs on m machines having in the same technological order. 

„N‟ JOBS AND „1‟ MACHINE :The simplest case of scheduling is to decide sequence of n jobs on a single resource or machine. In a basic single machine problem n jobs are available for processing at time „0‟ (static problem). Their facility setup times are independent on their sequence and can be added to their individual processing time for the power of scheduling . this aggregate of setup times and processing times for each job is constant. And known with certainty . the facility or machine is continuously available without interruption for processing the jobs and will not be idle. So long a job is waiting . once processing of jobs started will be completed without any break . the total number of distinct schedules will be n! . since all the schedules will results in the same next pan different performance are used to evaluate the schedules.

 „N‟ JOBS AND „2‟ MACHINES:For further detail description let us consider the illustrative problem –1 given in tutorial.

 „N‟ JOBS AND „3‟ MACHINES :let us consider n jobs on 3 machines . F1,F2 & F3 is same technological order. There is no general optimum or satisfying solution obtain so far. If a problem satisfied for n jobs and 2 machines as desired in art. The condition is minimum time element on F1max. time element on F2 . and minimum time element on F3  max. time element on F2. In that case , 3 columns (. F1,F2 & F3) time elements are redesigneted for 2 machines A & B elements as , Ai = ( F1) I + ( F2)I and Bi = ( F2) I + ( F3)I

 „2‟ JOBS AND „M‟ MACHINES :jobs J1 & J2 are to be made on machine F1, F2, F3, ….. Fm not necessarily in the same technological order. Graphical methods provides a very, simple for obtaining solution.

PRODUCTION ENGINEERING DEPT.

72

OPERATIONS RESEARCH

ASSIGNMENTS LP FORMULATION – ASSIGNMENT 1.

2.

A small manufacturer employs five skilled men and ten semi skilled men for making a product in two qualities: a deluxe model and an ordinary model. The production of a deluxe model requires 2-hours work by a skilled man and a 2-hour work by a semi skilled man. The ordinary model requires 1-hour work by a skilled man and a 3-hours work by a semi skilled man. According to worker union‟s rules, no man can work more than 8-hours per day. The profit of the deluxe model is Rs.1000 per unit and that of the ordinary model is Rs.800 per unit. Formulate a linear programming model for this manufacturing situation to determine the production volume of each model such that the total profit is maximized. A firm manufactures three products A, B & C. Their profits per unit are Rs.300, Rs.200 and Rs.400, respectively. The firm has two machines and the required processing time in minutes on each machine for each product is given in the following table: Product A B C Machine 1 4 3 5 Machine 2 2 2 4 Machines 1 and 2 have 2000 and 2500 machine minute, respectively. The upper limits for the production volumes of the product A, B & C are 100 units, 200 units and 50 units, respectively. But, the firm must produce a minimum of 50 units of the product A. Develop a LP model for this manufacturing situation to determine the production volume of each product such that the total profit is maximized.

3.

The manager of an oil refinery has to decide on the optimal mix of two possible blending processes. The inputs and the outputs per production run of the blending process are as follows:

Process 1 2

Input Crude A Crude B 5 4

3 5

Output Gasoline G1 Gasoline G2 5 4

8 4

The maximum amounts of availability of crude A and crude B are 200 units and 150 units, respectively. Market requirements show that at least 100 units of Gasoline G1 and 80 units of Gasoline G2 must be produced. The profits per production run from process 1 and process 2 are Rs.3 lacs and Rs. 4 lacs respectively. Formulate this problem as a LP model to determine the number of production runs of each process such that the total profit is maximized.

PRODUCTION ENGINEERING DEPT.

73

OPERATIONS RESEARCH

SOLVE EXAMPLES USING SIMPLEX METHOD 1. Minimize Z=2x+9y-4z Subject to 2x+3y+4z  16 x+6y-4z16 x,y, z >0 [S1=8, y=8/3,Z=24] 2. Maximize z=4x+5y Subject to 2x+3y8 3x+y4 x,y0 Use big M method. [S2=8, x=4, z=16] 3. Maximize Z=6x+10y+8z Subject to 2x+3y8 2y+5z10 3x+2y+4z15 x,y,z0 [y=750/41, z=930/41, x=89/41, Z=212.78] 4. Maximize Z=40x+30y Subject to 3x+2y300 x+y80 2x+y200 3x+4y300 x60 y60 x,y0 [S1=80, y=20, S3=60, S4=40, x=60, S6=40, Z=3000] 5. Minimize Z=20x1+10x2 Subject to x1+2x240 3x1+x2=30 4x1+3x260 x1,x 20 Use (i) Big „M‟ Method. (ii) Two – Phase Method [x1=6, x2=12, S1=10, Z=240] 6. Solve the following problem: Maximize Z= -x1-4x2-3x3 Subject to 2x1+x2+3x34 x1+2x2+2x33SS x1, x2 0 and x3 is unrestricted in sign. [Problem is infeasible]

PRODUCTION ENGINEERING DEPT.

74

OPERATIONS RESEARCH

FORMULATE PROBLEM AND SOLVE USING SIMPLEX METHOD 1. Shri Rajendra Desai has booked orders for product A and product B at the sales price of Rs. 6 and Rs. 8 per unit respectively, for M/S supreme Engineers with the condition that materials cost will be borne by the company i.e. M/S Supreme Engineers. Shri Desai negotiates the terms with the Kartik Engineering, a job order shop, which can offer machines of type x for 60 hours per week and machines of type y for 100 hours per week at hourly rates. Each machine can produce product A and B in any combination. Machine-hours of type x are available with the operators of the Kartik Engineering only and the rates are Rs. 4 per machine-cum-operator-hour. Machines of type y are available with two alternative offers viz. Desai can either hire the machines alone at the rate of Rs. 1/machine hour as well as operator at the rate of Rs. 3 per hour or Desai can hire his own operator for machines y at the rate of Rs. 3 per hour. The production rates are given in the Exhibit A. Production rate, units per hour Product

Exhibit – A

Machines, Type x

Machines, Type y With operator of With Desai‟s Kartik Engg. operator A 10 6 8 B 20 12 18 Formulate L.P.P. to maximize profit of Shri Desai. [ Maximize Z = (6- 4/10) X1 + (8-4/20) X2 + (6-4/6) X3 + (8-4/12)X4 +(6-4/8)X5 + (8-4/18)X6 Subject to X1 /10 + X2 /20  60 X3 /6 + X4 /12 + X5 /8 + X6 /18  10 X1, X2, X3, X4, X5, X6,  0] 2. The State Industries Finance Corporation is to decide its investment of Rupees 20 lacs on two proposals of Private sector Industries X and Y> X undertakes to guarantee annual return of 10 per cent, and Y of 15 per cent. As X is in the line of basic consumer products and that too co-operative venture, the Government has laid down that at least Rs.5 lacs should be invested in X. The corporation would like to have investments so made as to procure the minimum of 12 per cent annual return. For the reason best known to one of the Directors, following his rigid attitude in this regard SIFC has decided not to have investment in Y and X more than in the ratio 1.6: 1. Formulate this L.P. problem for maximum annual return. Solve it be either (1) Graphical method or (2) Simplex method. [maximize Z = 0.1 X1 + 0.15 X2 Subject to X1 + X2 = 20 0.1 X1 + 0.15 X2  0.12 (X1 + X2 ) X1 5 PRODUCTION ENGINEERING DEPT.

75

OPERATIONS RESEARCH

X2 / X1  1.6 / 1 X1, X2  0 X1 = 765/91, X2 = 1055/91, S2 = 107/260, Z = 2.5797] 3. The following data is available for two products. Product

Production Alternatives

1

1 2 2 1 Production hrs. available/week Production cost Rs./hr.

Production Rate in units/hr. Centre 1 Centre 2 0.4 ------------------0.5 0.5 1.0 500 400 6 8

Material cost is same for both the products and is Rs. 5 per unit. Selling price Rs. Per unit for product one is 25 and that of product two is 31. Solve the problem for optimal product mix. [X1 = 1250, X2 = 800, X3 =0, Z = 9450] 4. A plant can produce three products, A, B and C, Product A needs 4 hours of department 2 and one hour of department 3. Product B needs two hours of department 1 and two hours of department 2, while product C needs two hours of department 1 and two hours of department 3. Their respective profit coefficients in Rs. Per unit are 50, 40, and 55. Hours available per month with department 1, 2, and 3 are 1000, 1000, and 800 respectively. A purchased part is used in assembly of product A and C. Only 4000 parts are available for the month. Two such parts are used in each piece of product A and three parts in each piece of product C. There is a sales commitment of 200 units of product A. Find the optimal product mix.

DUALITY & SENSITIVITY ANALYSIS Problem 1: Construct the dual of the problem: Maximize Z = 3x+5y Subject to X- 2y  3 X + 3y 9 X–y5 X  0, is unrestricted in sign Solve the dual. [DUAL IS MAXIMIZE Z = -3A-9B+5C SUBJECT TO –A-B+C 3 -2A+3B+C -5 A,B,C 0. C=11,A=8,S3=0,Z=31] PRODUCTION ENGINEERING DEPT.

76

OPERATIONS RESEARCH

Problem: 2 Use dual simplex method to solve the following Minimize Z = 2x + 3y Subject to 3x + 4y  5 4x + 5y  7 x + 2y  4 x,y0 [S1 = ¼, X= 7/4, S3 =9/4, Z = 7/2] Problem: 3 The following tableau gives an optional solution to a standard linear programme: Maximize Z = CX. Subject to AX = B, X 0 Tableau 7

x2

0 s2 (zj – cj)

5 X1 x3 ¾ ½ 7/2

¼ ¼

7 X2 1

-4 X3 -1/4

0 S1 ¼

0 S2 0

0 0

-3/4 9/4

-5/4 7/4

1 0

S1 and S2 are the slack variables. (a) How much can c1 be increased before the current basis is no longer optimal? (b) How much can c2 be varied sp that the given basis ( x2 , S2) is still optimal? (c) What are the shadow prices of two resources? [(a) c1=21/4, x1=2/3, S2=1/3,Z=4 (b) 20/3 c216 (c) 7/4 and 0]

PRODUCTION ENGINEERING DEPT.

77

OPERATIONS RESEARCH

QUEING THEORY 1. Customer arrivals at a teller counter in a Commercial Bank are considered to be following Poisson probability distribution with an average time of 10 minutes between one arrival and the next. The time length of service that is rendered is assumed to be distributed exponentially with mean three minutes i) What is the probability that a person arriving at the teller will have to wait? ii) What is the average length of queue that forms from time to time? iii) The Commercial Bank will install a second teller man when convince that the arrival rate increase in order to justify the second booth. When does this happen? 2. There is congestion on the platform of Ahmed Railway station. The trains arrive at the rate of 30 trains per day. The waiting time for any train to flag-off is exponentially distributed with an average of 36 minutes. Calculate the following: i) The mean queue size. ii) The probability that the queue size exceeds 10.

PRODUCTION ENGINEERING DEPT.

78

OPERATIONS RESEARCH

INVENTORY CONTROL ASSIGNMENT 1. The Bombay Shoe Company has found that it purchases a large amount of industrial tapes for production of its shoes. Currently, it purchases Rs.10,00,000 a year of the various sized tapes from the local manufactures. A proposal was made by its supplier, was offer consist of 1.25% discount if BSC places an order quarterly BSC has calculated the cost to purchase at Rs.22.5 per order. Rs.20 per tape & inventory carrying costs at 18%. Should BSC accept discount offer from its supplier? If not, what alternate offer should be made in term of a discount? 2. The Himavan manufacturing company wishes to determine the most economy quantity for one of its products. Manufacturing cost amount to Rs.15 per unit. The production is 5000 units per annum. Each lot now requires a set-up cost of Rs.25 and the inventory cost of 25% of the average inventory value. What is the most economic lot size to manufacturers? What is the corresponding total yearly cost? 3. Demand for a certain part order by Shah brothers tends to be constant at the monthly rate of 1000 units. The per unit carrying cost of this item is Rs.25 per year, & cost of placing an order is Rs.75. i) What is the optimal order size? How often should an order be placed? ii) Show that the annual holding cost & ordering cost are equal when an optimal order size is used. What is the total relevant cost? iii) If the company wants to order only one every other week, by what percentage would this increase the total relevant cost? 4. The Calcutta Tool Company can manufacture a certain type of tool at the rate of 1480 per run, the demand for this tool is quite steady at annual rate of 9000 units. Unit cost of the tool is Rs.30, an set up cost per production run is Rs.500. The annual cost per unit sort is Rs.20. The company has determined the optimal production lot size to be 3000 units. i) What is the annual inventory holding cost, expressed as percentage of unit cost? ii) What is the total relevant cost & the max. inventory level? 5. Let C1=50(Rs.), Cs=20C1, & the demand distribution is as under: r 0 1 2 3 4 5 6 P(r) 0.9 0.05 0.02 0.01 0.01 0.01 0 What is the optimum quantity to be ordered? 5. Assume that demand during a certain time interval T is random with P( r ) being the probability that the total demand is r during interval T. The demand rate is constant during the interval T. C1=10(Rs.), C2=20C1 and the demand distribution is as under: r 0 1 2 3 4 5 6 P(r) 0.1 0.2 0.2 0.3 0.1 0.1 0 What should be the initial inventory level?

PRODUCTION ENGINEERING DEPT.

79

OPERATIONS RESEARCH

PROBLEMS ON GAMES THEORY 1. Linear programming method: (i) B

A

1 2 3

1 1 6 6

2 7 2 1

(ii) B 3 2 7 6

(iii) A

A

1 5 4

2 7 8

3 9 11

1 2 3

1 4 11 5

B 2 7 6 6

3 9 10 9

1 2 3

1 3 -2 2

2 -1 3 -2

1 1 2 3

(iv) 1 2

1 -1 5

B 2 6 -3

3 4 -6

A

6 (v)

A

1 2

(vi) 1 2 3

1 -5 5 5

B 2 10 -10 -20

B 3 20 -10 -20

(vii)

A

3 1 2 -1

4 2 3 1

2

3

4

-1 -3

-3 4

5 -3

4 -2

-3

-2

4

3

(viii) B

A

B

1

2

3

4

1 2

4 15

10 5

11 13

14 18

3 4 5 6

4 17 14 11

9 12 18 14

6 10 17 15

10 7 8 9

PRODUCTION ENGINEERING DEPT.

A

80

OPERATIONS RESEARCH

TRANSPORTATION Problem: Find the initial basic feasible solution of the following transportation problem by Vogel‟s approximation method: Warehouses W1 W2 W3 W4 Capacity F1 F2 F3

10 70 40

Requirement 5

30 30 8

50 40 70

10 60 20

7 9 18

8

7

14

34

Problem: A company has received a contract to supply gravel for three new construction projects located in towns A, B and C. Construction engineers have estimated the required amounts of gravel which will be needed at these construction projects as shown below: Project location

Weekly requirement (Truck loads)

A B C

72 102 41

The company has three gravel plants X, Y and Z located in three different towns. The gravel required by the construction projects can be supplied by these three plants. The amount of gravel which can be supplied by each plant is as follows: Plant

Amount available/week (Truck loads)

X Y Z

76 62 77

The company has computed the delivery cost from each plant to each project site. These costs (in rupees) are shown in the following table: Cost per load A B C X Plant Y Z

4 16 8

8 24 16

PRODUCTION ENGINEERING DEPT.

8 16 35

81

OPERATIONS RESEARCH

(a) Schedule the shipment from each plant to each project in such a manner so as to minimize the total transportation cost within the constraints imposed by plant capacities and project requirements. (b) Find the minimum cost. (c) Is the solution unique? If it is not, find alternative schedule with the same minimum cost.

ASSIGNMENT Problem: Solve the following assignment problem using Hungerian method. The matrix entries are processing times in hours. Operator 1 2 3 4 5

Job

1 2 3 4 5

20 4 23 17 16

22 26 14 15 19

35 24 17 16 21

22 24 19 18 19

18 7 19 15 25

Problem: Consider the problem of assigning four sales persons to four different sales regions as shown below such that the total sales is maximized.

1 2 Salesman 3 4

1

Sales region 2 3

4

5 5 7 6

11 7 8 8

9 7 9 12

8 9 9 11

The cell entries represent annual sales figures in crores of rupees. Find the optimal allocation of the sales persons to different regions. Problem: The flight timings between two cities, X and Y are as given in the following two tables. The minimum layover time of any crew in either of the cities is 3 hours. Determine the base city for each crew so that the sum of the layover times of all the crews in non-base cities is minimized. Timing of Flights form City X to City Y Flight number

Departure time (from City X)

PRODUCTION ENGINEERING DEPT.

Arrival time (to City Y) 82

OPERATIONS RESEARCH

101 102 103 104

6 a.m. 10 a.m. 3 p.m. 8 p.m.

8.00 a.m. 12.00 noon 5.00 p.m. 10.00 p.m.

Timing of Flights from City Y to City X Flight number 201 202 203 204

Departure time (from City Y)

Arrival time (to City X)

5.30 a.m. 9.00 a.m. 4.00 p.m. 10.00 p.m.

7.00 a.m. 10.30 a.m. 5.30 p.m. 11.30 p.m.

PRODUCTION ENGINEERING DEPT.

83

OPERATIONS RESEARCH

NETWORK PROBLEMS: Problem: Consider the details of a distance network as shown below: Arc

Distance

Arc

Distance

1-2 1-3 1-4 1-5 2-3 2-6 2-7 3-4

8 5 7 16 15 3 4 5

3-6 4-5 4-6 5-8 6-8 6-9 7-9 8-9

6 8 12 7 9 15 12 6

(a) Construct the distance network. (b) Find the shortest path from Node 1 to Node 9 using the systematic method. (c) Find the shortest path from Node 1 to Node 9 using Dijkstra‟s algorithm. Problem: Consider the details of a distance network as shown below: Arc

Distance

1-2 1-3 1-4 2-3 2-4 3-4 3-5 3-6

3 8 10 4 7 2 8 6

(a) Construct the detail network. (b) Apply Floyd‟s algorithm and obtain the final matrices, D 5 and P5. (c) Find the shortest path and the corresponding distance for each of the following: (i) from Node 1 to Node 5 (ii) from Node 2 to Node 5.

PRODUCTION ENGINEERING DEPT.

84

OPERATIONS RESEARCH

Problem: For the network shown in the Figure activity, resource requirements are given in the table. Solve the problem for resource allocation. There are two cranes and 8 welders available for the project.

3 B A

C E

D

1

2

4

F

6

A

5 Figure

Table Activity

A

B

C

D

E

F

Duration Days

10

10

8

14

3

9

Resources Required

-

2 Cranes

8 Welders

6 Welders

-

1 Crane

PRODUCTION ENGINEERING DEPT.

85

OPERATIONS RESEARCH

Problem: The critical path network analysis is given in Figure. The activity times are also given for each activity. Determine the critical path and critical path time. Also determine the floats for each activity.

3

Figure

9

12 4 3

8

8

12

1

2 7

6

5

4 10 2

5

PRODUCTION ENGINEERING DEPT.

A

7

86