Archive for the ‘MB0048-Operations Research Assignments’ Category
MB0048 : Compare and contrast CPM and PERT. Under what conditions would you recommend scheduling by PERT? Justify your answer with reasons.
Posted October 20, 2011
on:MB0048 : Compare and contrast CPM and PERT. Under what conditions would you recommend scheduling by PERT? Justify your answer with reasons.
Answer :- Project management has evolved as a new field with the development of two analytic techniques for planning, scheduling and controlling projects. These are the Critical Path Method (CPM) and the Project Evaluation and Review Technique (PERT). PERT and CPM are basically time-oriented methods in the sense that they both lead to the determination of a time schedule.
Basic Difference between PERT and CPM
Though there are no essential differences between PERT and CPM as both of them share in common the determination of a critical path. Both are based on the network representation of activities and their scheduling that determines the most critical activities to be controlled so as to meet the completion date of the project.
PERT
Some key points about PERT are as follows:
- PERT was developed in connection with an R&D work. Therefore, it had to cope with the uncertainties that are associated with R&D activities. In PERT, the total project duration is regarded as a random variable. Therefore, associated probabilities are calculated so as to characterise it.
- It is an event-oriented network because in the analysis of a network, emphasis is given on the important stages of completion of a task rather than the activities required to be performed to reach a particular event or task.
- PERT is normally used for projects involving activities of non-repetitive nature in which time estimates are uncertain.
- It helps in pinpointing critical areas in a project so that necessary adjustment can be made to meet the scheduled completion date of the project.
CPM
- CPM was developed in connection with a construction project, which consisted of routine tasks whose resource requirements and duration were known with certainty. Therefore, it is basically deterministic.
- CPM is suitable for establishing a trade-off for optimum balancing between schedule time and cost of the project.
- CPM is used for projects involving activities of repetitive nature.
PROJECT SCHEDULING BY PERT-CPM
It consists of three basic phases: planning, scheduling and controlling.
Phases of PERT-CPM
1. Project Planning: In the project planning phase, you need to perform the following activities:
- Identify various tasks or work elements to be performed in the project.
- Determine requirement of resources, such as men, materials, and machines, for carrying out activities listed above.
- Estimate costs and time for various activities.
- Specify the inter-relationship among various activities.
- Develop a network diagram showing the sequential inter-relationships between the various activities.
2. Project Scheduling: Once the planning phase is over, scheduling of the project is when each of the activities required to be performed, is taken up. The various steps involved during this phase are listed below:
- Estimate the durations of activities. Take into account the resources required for these execution in the most economic manner.
- Based on the above time estimates, prepare a time chart showing the start and finish times for each activity. Use the time chart for the following exercises.
ü To calculate the total project duration by applying network analysis techniques, such as forward (backward) pass and floats calculation
ü To identify the critical path
ü To carry out resource smoothing (or levelling) exercises for critical or scarce resources including re-costing of the schedule taking into account resource constraints
3. Project Control: Project control refers to comparing the actual progress against the estimated schedule. If significant differences are observed then you need to re-schedule the project to update or revise the uncompleted part of the project.
MB0048 : State and discuss the methods for solving an assignment problem. How is Hungarian method better than other methods for solving an assignment problem?
Posted October 20, 2011
on:MB0048 :State and discuss the methods for solving an assignment problem. How is Hungarian method better than other methods for solving an assignment problem?
Answer : Assignment becomes a problem because each job requires different skills and the capacity or efficiency of each person with respect to these jobs can be different. This gives rise to cost differences. If each person is able to do all jobs with same efficiency then all costs will be the same and each job can be assigned to any person. When assignment is a problem it becomes a typical optimisation problem. Therefore, you can compare an assignment problem to a transportation problem.
Solution Methods
The assignment problem can be solved by the following four methods :
- Enumeration method
- Simplex method
- Transportation method
- Hungarian method
Enumeration method:
In this method, a list of all possible assignments among the given resources and activities is prepared. Then an assignment involving the minimum cost, time or distance or maximum profits is selected. If two or more assignments have the same minimum cost, time or distance, the problem has multiple optimal solutions. This method can be used only if the number of assignments is less. It becomes unsuitable for manual calculations if number of assignments is large
Simplex method:
The simplex method focuses on solving LPP of any enormity involving two or more decision variables.
The simplex algorithm is an iterative procedure for finding the optimal solution to a linear programming problem. The objective function controls the development and evaluation of each feasible solution to the problem. If a feasible solution exists, it is located at a corner point of the feasible region determined by the constraints of the system.
The simplex method simply selects the optimal solution amongst the set of feasible solutions of the problem. The efficiency of this algorithm is because it considers only those feasible solutions which are provided by the corner points, and that too not all of them. You can consider obtaining an optimal solution based on a minimum number of feasible solutions.
Transportation method
Transportation model is an important class of linear programs. For a given supply at each source and a given demand at each destination, the model studies the minimisation of the cost of transporting a commodity from a number of sources to several destinations.
As assignment is a special case of transportation problem it can also be solved using transportation model. But the degeneracy problem of solution makes the transportation method computationally inefficient for solving the assignment problem.
Hungarian method
There are various ways to solve assignment problems. Certainly it can be formulated as a linear program (as we saw above), and the simplex method can be used to solve it. In addition, since it can be formulated as a network problem, the network simplex method may solve it quickly.
However, sometimes the simplex method is inefficient for assignment problems (particularly problems with a high degree of degeneracy). The Hungarian Algorithm developed by Kuhn has been used with a good deal of success on these problems and is summarized as follows.
Step 1. Determine the cost table from the given problem.
- If the no. of sources is equal to no. of destinations, go to step 3.
- If the no. of sources is not equal to the no. of destination, go to step2.
Step 2. Add a dummy source or dummy destination, so that the cost table becomes a square matrix. The cost entries of the dummy source/destinations are always zero.
Step 3. Locate the smallest element in each row of the given cost matrix and then subtract the same from each element of the row.
Step 4. In the reduced matrix obtained in the step 3, locate the smallest element of each column and then subtract the same from each element of that column. Each column and row now have at least one zero.
Step 5. In the modified matrix obtained in the step 4, search for the optimal assignment as follows:
(a) Examine the rows successively until a row with a single zero is found. Enrectangle this row ()and cross off (X) all other zeros in its column. Continue in this manner until all the rows have been taken care of.
(b) Repeat the procedure for each column of the reduced matrix.
(c) If a row and/or column has two or more zeros and one cannot be chosen by inspection then assign arbitrary any one of these zeros and cross off all other zeros of that row / column.
(d) Repeat (a) through (c) above successively until the chain of assigning () or cross (X) ends.
Step 6. If the number of assignment () is equal to n (the order of the cost matrix), an optimum solution is reached.
If the number of assignment is less than n(the order of the matrix), go to the next step.
Step7. Draw the minimum number of horizontal and/or vertical lines to cover all the zeros of the reduced matrix.
Step 8. Develop the new revised cost matrix as follows:
(a)Find the smallest element of the reduced matrix not covered by any of the lines.
(b)Subtract this element from all uncovered elements and add the same to all the elements laying at the intersection of any two lines.
Step 9. Go to step 6 and repeat the procedure until an optimum solution is attained.
MB0048 : Given a general linear programming problem, explain how you would test whether a basic feasible solution is an optimal solution or not. How would you proceed to change the basic feasible solution in case it is not optimal?
Posted October 20, 2011
on:MB0048 : Given a general linear programming problem, explain how you would test whether a basic feasible solution is an optimal solution or not. How would you proceed to change the basic feasible solution in case it is not optimal?
Answer :- Initial basic feasible solution of a LPP
Consider a system of m equations in n unknowns x1, x_{2} – – a_{n},
a_{11} x_{1} + a_{12} x_{2} + – – + a_{1n} x_{n} = b_{1}
a_{21} x_{1} + a_{22} x_{2} + – – + a_{2n} x_{n} = b_{2}
_{………………………………………………………}
a_{m1} x_{1} + a_{m2} x_{2} + – – + a_{mn} x_{n} = b_{n}
Where mn
To solve this system of equations, you must first assign any of n – m variables with value zero. The variables assigned the value zero are called non-basic variables, while the remaining variables are called basic variables. Then, solve the equation to obtain the values of the basic variables. If one or more values of the basic variables are valued at zero, then solution is said to degenerate, whereas if all basic variable have non-zero values, then the solution is called a non-degenerate solution. A basic solution satisfying all constraints is said to be feasible.
Following are the steps to test whether a basic feasible solution is an optimal solution or not as follows:
- Introduce stack variables (S_{i}’s) for “” type of constraint.
- Introduce surplus variables (S_{i}’s) and artificial variables (A_{i}) for “” type of constraint.
- Introduce only Artificial variable for “=” type of constraint.
- Cost (C_{j}) of slack and surplus variables will be zero and that of artificial variable will be “M”
- Find Z_{j} – C_{j} for each variable.
- Slack and artificial variables will form basic variable for the first simplex table. Surplus variable will never become basic variable for the first simplex table.
- Z_{j} = sum of [cost of variable x its coefficients in the constraints – Profit or cost coefficient of the variable].
- Select the most negative value of Z_{j} – C_{j}. That column is called key column. The variable corresponding to the column will become basic variable for the next table.
- Divide the quantities by the corresponding values of the key column to get ratios; select the minimum ratio. This becomes the key row. The basic variable corresponding to this row will be replaced by the variable found in step 6.
- The element that lies both on key column and key row is called Pivotal element.
- Ratios with negative andvalue are not considered for determining key row.
- Once an artificial variable is removed as basic variable, its column will be deleted from next iteration.
- For maximisation problems, decision variables coefficient will be same as in the objective function. For minimisation problems, decision variables coefficients will have opposite signs as compared to objective function.
- Values of artificial variables will always is – M for both maximisation and minimisation problems.
- The process is continued till all Z_{j} – C_{j}0.
To test for optimality of the current basic feasible solution of the LPP, use the following algorithm called simplex algorithm. Let’s also assume that there are no artificial variables existing in the program.
Perform the following steps to solve the simplex algorithm to change the basic feasible solution in case it is not optimal
1) Locate the negative number in the last row of the simplex table. Do not include the last column. The column that has negative number is called the work column.
2) Next, form ratios by dividing each positive number in the work column, excluding the last row into the element in the same row and last column. Assign that element to the work column to yield the smallest ratio as the pivot element. If more than one element yields the same smallest ratio, choose the elements randomly. The program has no solution, if none of the element in the work column is non-negative.
3) To convert the pivot element to unity (1) and then reduce all other elements in the work column to zero, use elementary row operations.
4) Replace the x -variable in the pivot row and first column by x-variable in the first row pivot column. The variable to be replaced is called the outgoing variable and the variable that replaces it is called the incoming variable. This new first column is the current set of basic variables.
5) Repeat steps 1 through 4 until all the negative numbers in the last row excluding the last column are exhausted.
6) You can obtain the optimal solution by assigning the value to each variable in the first column corresponding to the row and last column. All other variables are considered as non-basic and have assigned value zero. The associated optimal value of the objective function is the number in the last row and last column for a maximisation program, but the negative of this number for a minimisation problem.
MB0048 : A furniture manufacturer makes two products: chairs and tables. Processing of these products is done on two machines A and B. A chair requires 2 hours on machine A and 6 hours on machine B. A table requires 5 hours on machine A and no time on machine B. There are 16 hours per day available on machine A and 30 hours on machine B. Profit gained by the manufacturer from a chair and a table is Rs 2 and Rs 10, respectively. What should be the daily production of each of the two products?
Posted October 20, 2011
on:MB0048 : A furniture manufacturer makes two products: chairs and tables. Processing of these products is done on two machines A and B. A chair requires 2 hours on machine A and 6 hours on machine B. A table requires 5 hours on machine A and no time on machine B. There are 16 hours per day available on machine A and 30 hours on machine B. Profit gained by the manufacturer from a chair and a table is Rs 2 and Rs 10, respectively. What should be the daily production of each of the two products?
Solution
Let x_{1 }= no of hours on machine A & x_{2 }=no of hours on machine B
Then the problem can be formulated as a P model as follows:-
Objective function, Maximise Z = 2x_{1} + 10x_{2}
Constraint equations: –
2x_{1} + 6x_{2} < 16
5x_{1 }< 30_{ }
x_{1}, x_{2} > 0
Step I
Treating all the constraints as equality, the first constraint is
2x_{1} + 6x_{2} < 16
Put x1 = 0 ⇒ = x_{2} = 2.7 ∴ The point is (0, 2.7)
Put x_{2} = 0 ⇒ = x_{1} = 8 ∴ The point is (8, 0) 2.7
Step II
Treating all the constraints as equality, the first constraint is
5x_{1 }< 30_{ }0_{ }6A_{ }8c
_{X1} = 6 ∴ The point is (6, 0)
Step III
The intersection of the above graphic denotes (A, B, C) the feasible region for the given problem.
Step IV
At corner points (O, A, B, C), find the profit value from the objective function. That point which maximize the profit is the optimal point.
Corner points |
W-Ordinates |
Objective Function Z = 2x_{1} + 10x_{2} |
Value |
A | (6, 0) | Z = 2(6) +0 | 12 |
B | (6, 2/3) | Z = 2(6) + 10 (2/3) | 19 |
C | (8, 0) | Z = 2(8) + 0 | 16 |
Result
The optimal solution is:
No of hours on machine A = 6
No of hours on machine B =2/3
Total profit, = 19 which is the maximum.
MB0048 : Operation Research is an aid for the executive in making his decisions by providing him the needed quantitative information, based on scientific method analysis. Discuss.
Posted October 20, 2011
on:MB0048 : Operation Research is an aid for the executive in making his decisions by providing him the needed quantitative information, based on scientific method analysis. Discuss.
Answer:- The Operations Research may be regarded as a tool which is utilized to increase the effectiveness of management decisions. In fact, OR is the objective feeling of the administrator (decision-maker). Scientific method of OR is used to understand and describe the phenomena of operating system.
OR models explain these phenomena as to what changes take place under altered conditions, and control these predictions against new observations. For example, OR may suggest the best locations for factories, warehouses as well as the most economical means of transportation. In marketing, OR may help in indicating the most profitable type, use and size of advertising campaigns subject to the final limitations.
The advantages of OR study approach in business and management decision making may be classified as follows:
1. Better Control. The management of big concerns finds it much costly to provide continuous executive supervisions over routine decisions. An OR approach directs the executives to devote their attention to more pressing matters. For example, OR approach deals with production scheduling and inventory control.
2. Better Co-ordination. Some times OR has been very useful in maintaining the law and order situation out of chaos. For example, an OR based planning model becomes a vehicle for coordinating marketing decisions with the limitation imposed on manufacturing capabilities.
3. Better System. OR study is also initiated to analyses a particular problem of decision making such as establishing a new warehouse. Later, OR approach can be further developed into a system to be employed repeatedly. Consequently, the cost of undertaking the first application may improve the profits.
4. Better Decisions. OR models frequently yield actions that do improve an intuitive decision making. Sometimes, a situation may be so complicated that the human mind can never hope to assimilate all the important factors without the help of OR and computer analysis.
QUANTITATIVE TECHNIQUES OF OR:
A brief account of some of the important OR models providing needed quantitative information base on scientific method analysis are given below:
1. Distribution (Allocation) Models: Distribution models are concerned with the allotment of available resources so as to minimize cost or maximize profit subject to prescribed restrictions. Methods for solving such type of problems are known as mathematical programming techniques. We distinguish between liner and non-liner programming problems on the basis of linearity and non-linearity of the objective function and/or constraints respectively. In linear programming problems, the objective function is linear and constraints are also linear inequalities/equations. Transportation and Assignment models can be viewed as special cases of linear programming. These can be solved by specially devised procedures called Transportation and Assignment Techniques.
In case the decision variables in a linear programming problem are restricted to either integer or zero-one value, it is known as Integer and Zero-One programming problems, respectively. The problems having multiple, conflicting and incommensurable objective functions (goals) subject to linear constraints are called linear goal programming problems. If the decision variables in a linear programming problem depend on chance, then such problems are called stochastic linear programming problems.
2. Production/Inventory Models: Inventory/Production Models are concerned with the determination of the optimal (economic) order quantity and ordering (production) intervals considering the factors such as—demand per unit time, cost of placing orders, costs associated with goods held up in the inventory and the cast due to shortage of goods, etc. Such models are also useful in dealing with quantity discounts and multiple products.
3. Waiting Line (or Queuing) Models: In queuing models an attempt is made to predict:
(i) How much average time will be spent by the customer in a queue?
(ii) What will be an average length of waiting linear or queue?
(iii) What will be the traffic intensity of a queuing system? etc.
The study of waiting line problems provides us methods to minimize the sum of cost of providing services and cost obtaining service which are primarily associated with the value of time spent by the customer in a queue.
4. Markovian Models: These models are applicable in such situation where the state of the system can be defined by some descriptive measure of numerical value and where the system moves from one state to another on probability basis. Brand-switching problems considered in marketing studies are an example of such models.
5. Competetive Strategy Models (Games Theory): These models are used to determine the behavior of decision-making under completion or conflict. Methods for solving such models have not been found suitable for industrial applications, mainly because they are referred to an idealistic world neglecting many essential features of reality.
6. Net work Models: These models are applicable in large projects involving complexities and inter-dependencies of activities. Project Evaluation and Review Techniques (PERT) And critical Method (CPM) are used for planning, scheduling and controlling complex project which can be characterized net-work.
7. Job Sequencing Models: These Models involve the selection of such a sequence of performing a series of jobs to be done on service facilities (machines) that optimize the efficiency measure of performance of the system. In other words, sequencing is conserved with such a problem in which efficiency measure depends upon the order or sequences of performing a series of jobs.
8. Replacement Models: The models deal with the determination of optimum replacement policy in situations that arise when some items or machinery need replacement by a new one. Individual and group replacement polices can be used in the case of such equipments that fail completely and instantaneously.
9. Simulation Models: Simulation is a very powerful technique for solving much complex models which cannot be solved otherwise and thus it is being extensively applied to solve to solve a variety of problems. This technique is more useful when following two types of difficulties may arise:
(i) The number of variables and constraint relationships may be so large that it is not computationally feasible to pursue such analysis.
(ii) Secondly, the model may be much away from the reality that no confidence can be placed on the computational results.
In fact, such models are solved by simulation techniques where no other method is available for its solution.
MB0048 : Outline the broad features of the Judgement phase and Research phase of the scientific method in OR. Discuss in detail any of these phases.
Posted October 20, 2011
on:MB0048 : Outline the broad features of the Judgement phase and Research phase of the scientific method in OR. Discuss in detail any of these phases.
Answer : – About forty years ago, it would have been difficult to get a single operations-researcher to describe a procedure for conducting OR project. The procedure for an OR study generally involves the following major phases:
Phase1: Formulating the problem: Before proceeding to find the solution of a problem, first of all one must be able to formulate the problem in the form of an appropriate model. To do so, the following information will be required.
- Who has to take the decision?
- What are the objectives?
- What are the ranges of controlled variables?
- What are the uncontrolled variables that may affect the possible solutions?
- What are the restrictions or constraints on the variables?
Since wrong formulation cannot yield a right decision (solution), one must be considerably careful while execution this Phase.
Phase II: Constructing a mathematical model: The second phase of the investigations is concerned with the reformulation of the problem in an appropriate from which is convenient for analysis. The most suitable form for this purpose is to construct a mathematical model representing the system under study. It requires the identification of both static and dynamic structural elements. A mathematical model should include the following three important basic factors:
(i) Decision variables and parameters,
(ii) Constraints or Restrictions,
(iii) Objective function.
Phase III: Deriving the solutions from the model: This phase is devoted to the computation of those values of decision variables that maximize (or minimize) the objective function. Such solution is called an optimal solution which is always in the best interest of the problem under consideration.
Phase IV: Testing the model and its solution (updating the model): After completing the model, it is once again tested as a whole for the errors if any. A model said to be valid if it can provide a reliable prediction of the system’s performance. A good practitioner of Operations Research realize that his model be applicable for a longer time and those he updates the model time to time by talking into account the past, present and future specifications of the problem.
Phase V: Controlling the solution: This Phase establishes controls over the solution with any degree of satisfaction. The model requires immediate modification as soon as the controlled variables (one or more) change significantly, otherwise the model goes out of control. As the conditions are constantly changing in the world, the model and solution may not remain valid for a long time.
Phase VI: Implementing the solution: Finally, the tested results of the model are implemented to work. This Phase is primarily executed with the cooperation of Operation Research experts and those who are responsible for managing and operating the systems.
Scientific Method in Operation Research: The scientific method in OR study generally involves the three Phases:
(i) the judgment Phase,
(ii) the research Phase, and
(iii) the action Phase.
The judgment Phase includes:
(i) A determination of the operation.
(ii) The establishment of the objectives and values related to the operation.
(iii) The determination of the suitable measures of effectiveness.
(iv) Lastly, the formulation of the problems relative to the objectives.
The research Phase utilizes:
(i) Observations and data collection for a better understanding of what the problem is.
(ii) Formulation of hypothesis and models.
(iii) Observation and experimentation to test the hypothesis on the basis of additional data.
(iv) Analysis of the available information and verification of the hypothesis using pre-established measures of effectiveness.
(v) Predictions of various results from the hypothesis, generalization of the result and consideration of alternative methods.
The action Phase:
OR consists of making recommendations for decision process by those who first posed the problem for consideration, or by anyone in a position to make a decision influencing the operation in which the problem occurred.
MB0048 : State two major reasons for using simulation. Explain the basic steps of Monte-Carlo simulation. Briefly describe the application in finance & Accounting.
Posted October 5, 2011
on:MB0048 : State two major reasons for using simulation. Explain the basic steps of Monte-Carlo simulation. Briefly describe the application in finance & Accounting.
Answer: – major reasons for using simulation
Simulation is also called experimentation in the management laboratory. While dealing with business problems, simulation is often referred to as ‘Monte Carlo Analysis’. Two American mathematicians, Von Neumann and Ulan, in the late 1940s found a problem in the field of nuclear physics too complex for analytical solution and too dangerous for actual experimentation. They arrived at an approximate solution by sampling. The method they used had resemblance to the gambler’s betting systems on the roulette table; hence the name ‘Monte Carlo’ has stuck.
Imagine a betting game where the stakes are based on correct prediction of the number of heads, which occur when five coins are tossed. If it were only a question of one coin; most people know that there is an equal likelihood of a head or a tail occurring, that is the probability of a head is ½. However, without the application of probability theory, it would be difficult to predict the chances of getting various numbers of heads, when five coins are tossed. In this kind of situation simulation plays an important role.
MONTE CARLO SIMULATION
Monte Carlo simulation is useful when same elements of a system, such as arrival of parts to a machine, etc., exhibit a chance factor in their behavior. Experimentation on probability distribution for these elements is done through random sampling. Following five steps are followed in the Monte Carlo simulation:
Procedure of Monte Carlo Simulation:
- Decide the probability distribution of important variables for the stochastic process.
- Calculate the cumulative probability distributing for each variable in Step 1
- Decide an interval of random numbers for each variable.
- Generate random numbers.
- Simulate a series of trials and determine simulated value of the actual random variables.
Application of Simulation in finance & Accounting.
The range of application of simulation in business is extremely wide. Unlike other mathematical models, simulation can be easily understood by the users and thereby facilitates their active involvement. This makes the results more reliable and also ensures easy acceptance for implementation. The degree to which a simulation model can be made close to reality is dependent upon the ingenuity of the OR team who identifies the relevant variables as well as their behavior.
You have already seen by means of an example how simulation could be used in a queuing system. It can also be employed for a wide variety of problems encountered in production systems – the policy for optimal maintenance in terms of frequency of replacement of spares or preventive maintenance, number of maintenance crews, number of equipment for handling materials, job shop scheduling, routing problems, stock control and so forth. The other areas of application include dock facilities, facilities at airports to minimize congestion, hospital appointment systems and even management games.
In case of other OR models, simulation helps the manager to strike a balance between opposing costs of providing facilities (usually meaning long term commitment of funds) and the opportunity and costs of not providing them.