MB0048
Q1 / Describe the framework of Operations Research.1 / / The goal of operations research is to provide a framework for constructing models of decision-making problems, finding the best solutions with respect to a given measure of merit, and implementing the solutions in an attempt to solve the problems. Given that O.R. represents an integrated framework to help make decisions, it is important to have a clear understanding of this framework so that it can be applied to a generic problem.
The OR approach comprises the following seven sequential steps:
(1) Orientation
(2) Problem Definition
(3) Data Collection
(4) Model Formulation
(5) Solution
(6) Model Validation and Output Analysis
(7) Implementation and Monitoring.
Tying each of these steps together is a mechanism for continuous feedback; Figure 1 shows this schematically.
- Orientation: The first step in the O.R. approach is referred to as problem orientation. The primary objective of this step is to constitute the team that will address the problem at hand and ensure that all its members have a clear picture of the relevant issues. Typically, the team will have a leader and be constituted of members from various functional areas or departments that will be affected by or have an effect upon the problem at hand. In the orientation phase, the team typically meets several times to discuss all of the issues involved and to arrive at a focus on the critical ones. This phase also involves a study of documents and literature relevant to the problem in order to determine if others have encountered the same (or similar) problem in the past, and if so, to determine and evaluate what was done to address the problem. The aim of the orientation phase is to obtain a clear understanding of the problem and its relationship to different operational aspects of the system, and to arrive at a consensus on what should be the primary focus of the project. In addition, the team should also have an appreciation for what has been done elsewhere to solve the problem.
- Problem Definition: This is the second, and in a significant number of cases, the most difficult step of the O.R. process. The objective here is to further refine the deliberations from the orientation phase to the point where there is a clear definition of the problem in terms of its scope and the results desired. A clear definition of the problem has three broad components to it.
- The first is the statement of an unambiguous objective. Along with a specification of the objective it is also important to define its scope, i.e., to establish limits for the analysis to follow.
- The second component of problem definition is a specification of factors that will affect the objective. These must further be classified into alternative courses of action that are under the control of the decision maker and uncontrollable factors over which he or she has no control.
- The third and final component of problem definition is a specification of the constraints on the courses of action, i.e., of setting boundaries for the specific actions that the decision-maker may take.
- Data Collection: In the third phase of the O.R. process data is collected with the objective of translating the problem defined in the second phase into a model that can then be objectively analyzed. Data typically comes from two sources – observation and standards. The first corresponds to the case where data is actually collected by observing the system in operation and typically, this data tends to derive from the technology of the system. Other data are obtained by using standards; a lot of cost related information tends to fall into this category. For instance, most companies have standard values for cost items such as hourly wage rates, inventory holding charges, selling prices, etc.; these standards must then be consolidated appropriately to compute costs of various activities. On occasion, data may also be solicited expressly for the problem at hand through the use of surveys, questionnaires or other psychometric instruments.
- Model Formation: Greater simplification is still necessary before a analysis can be performed. This is achieved by constructing a model. A mathematical model is a collection of functional relationships by which allowable actions are delimited and evaluated. Although the analyst would hope to study the broad implications of the problem using a systems approach, a model cannot include every aspect of a situation. A model is always an abstraction that is, by necessity, simpler than the reality. Elements that are irrelevant or unimportant to the problem are to be ignored, leaving sufficient detail so that the solution obtained with the model has value with regard to the original problem. The statements of the abstractions introduced in the construction of the model are called the assumptions The appropriateness of the assumptions can be determined only by subsequent testing of the model’s validity. Models must be both tractable -- capable of being solved, and valid -- representative of the true situation. These dual goals are often contradictory and are not always attainable. We have intentionally represented the model with well-defined boundaries to indicate its relative simplicity.
- Model Solution: The next step in the process is to solve the model to obtain a solution to the problem. Tools available to the analyst are used to obtain a solution to the mathematical model. Some methods can prescribe optimal solutions while other only evaluate candidates, thus requiring a trial and error approach to finding an acceptable course of action. To carry out this task the analyst must have a broad knowledge of available solution methodologies. It may be necessary to develop new techniques specifically tailored to the problem at hand. Generally there are three techniques viz, feasibility analysis, optimality analysis and sensitivity analysis.
- Validation and Analysis: Once a solution has been obtained two things need to be done before one even considers developing a final policy or course of action for implementation. The first is to verify that the solution itself makes sense. The process of ensuring that the model is an accurate representation of the system is called validation. A typical error that might be discovered at this stage is that some important constraint was ignored in the model formulation - this will lead to a solution that is clearly recognized as being infeasible and the analyst must then go back and modify the model and re-solve it. This cycle continues until one is sure that the results are sensible and come from a valid system representation.The second part of this step in the O.R. process is referred to as "what-if" analysis in order to provide not just a recommended course of action, but also details on its range of applicability and its sensitivity to model parameters.
- Implementation and Monitoring: The last step in the O.R. process is to implement the final recommendation and establish control over it. Implementation entails the constitution of a team whose leadership will consist of some of the members on the original O.R. team. This team is typically responsible for the development of operating procedures or manuals and a time-table for putting the plan into effect. Once implementation is complete, responsibility for monitoring the system is usually turned over to an operating team. From an O.R. perspective, the primary responsibility of the latter is to recognize that the implemented results are valid only as long as the operating environment is unchanged and the assumptions made by the study remain valid. Thus when there are radical departures from the bases used to develop the plan, one must reconsider one's strategy.
Q2 / a. Explain the graphical method of solving Linear Programming Problem.
b. A paper mill produces two grades of paper viz., X and Y. Because of raw material
restrictions, it cannot produce more than 400 tons of grade X paper and 300 tons of grade Y
paper in a week. There are 160 production hours in a week. It requires 0.20 and 0.40 hours toproduce a ton of grade X and Y papers. The mill earns a profit of Rs. 200 and Rs. 500 per tonof grade X and Y paper respectively. Formulate this as a Linear Programming Problem.
2a. / Linear programming is a widely used model type that can solve decision problems with many thousands of variables. Generally, the feasible values of the decisions are delimited by a set of constraints that are described by mathematical functions of the decision variables. The feasible decisions are compared using an objective function that depends on the decision variables. For a linear program the objective function and constraints are required to be linearly related to the variables of the problem.
Decision variables describe the quantities that the decision makers would like to determine. They are the unknowns of a mathematical programming model. Typically we will determine their optimum values with an optimization method. In a general model, decision variables are given algebraic designations such as xi.
The objective function evaluates some quantitative criterion of immediate importance such as cost, profit, utility, or yield. The general linear objective function can be written as
Here cjis the coefficient of the jth decision variable. The criterion selected can be either maximized or minimized.
A constraint is an inequality or equality defining limitations on decisions. Constraints arise from a variety of sources such as limited resources, contractual obligations, or physical laws. In general, an LP is said to have m linear constraints that can be stated as
In most practical problems the variables are required to be nonnegative;
This special kind of constraint is called a nonnegativity restriction
Combining the aforementioned components into a single statement gives:
The constraints, including nonnegativity and simple upper bounds, define the feasible region of a problem
Graphical Method of Solution of a Linear Programming Problem
The graphical method is applicable to solve the LPP involving two decision variables x1, and x2, we usually take these decision variables as x, y instead of x1, x2. To solve an LP, the graphical method includes two major steps.
a) The determination of the solution space that defines the feasible solution. The set of values of the variable x1, x2, x3,....xn which satisfy all the constraints and also the non-negative conditions is called the feasible solution of the LP.
b) The determination of the optimal solution from the feasible region.
a) To determine the feasible solution of an LP, we have the following steps.
Step 1: Since the two decision variable x and y are non-negative, consider only the first quadrant of xy-coordinate plane.
Step 2: Each constraint is of the form ax+by<=c or ax+by>=c
Draw the line ax + by = c (1)
For each constraint, draw the line. Each line divides the first quadrant in to two regions say R1 and R2, suppose (x1, 0) is a point in R1. If this point satisfies the in equation ax + by<=c or (>= c), then shade the region R1. If (x1, 0) does not satisfy the inequality, shade the region R2.
Step 3: Corresponding to each constant, we obtain a shaded region. The intersection of all these shaded regions is the feasible region or feasible solution of the LP.
The optimal solution to a LPP, if it exists, occurs at the corners of the feasible region.
b) The determination of the optimal solution from the feasible region.
Step 1: Find the feasible region of the LLP.
Step 2: Find the co-ordinates of each vertex of the feasible region.
These co-ordinates can be obtained from the graph or by solving the equation of the lines.
Step 3: At each vertex (corner point) compute the value of the objective function.
Step 4: Identify the corner point at which the value of the objective function is maximum (or minimum depending on the LP)
The co-ordinates of this vertex is the optimal solution and the value of Z is the optimal value.
2b. / A paper mill produces two grades of paper viz., X and Y. Because of raw material
restrictions, it cannot produce more than 400 tons of grade X paper and 300 tons of grade Y
paper in a week. There are 160 production hours in a week. It requires 0.20 and 0.40 hours to
produce a ton of grade X and Y papers. The mill earns a profit of Rs. 200 and Rs. 500 per ton
of grade X and Y paper respectively. Formulate this as a Linear Programming Problem.
Paper Grade / X / Y
Maximum Produce / 400 tons / 300 tons
Production Hours / 0.20 hrs / 0.40hrs / 160 hrs
Profit per unit / Rs 200 / Rs 500
Let us assume that mill produces x tons of grade X paper and y tons of grade Y paper in order to maximize profit represented as Z.
Total Production of grade X paper can be atmost 400 tons, hence x<= 400
Total Production of grade Y paper can be atmost 300 tons, hence y<= 300
Productions hrs for grade X paper = 0.20x hrs
Productions hrs for grade Y paper = 0.40x hrs
Total production hours = 0.20x+0.40y which could atmost be 160 hrs
Hence 0.20x+0.40y <= 160
Firm’s objective is to maximize profit, hence objective function would be
Maximize Z = 200x + 500 y.
Thus, LPP representation of the given problem would be
Maximize Z = 200x + 500 y
Under the constraints
x<= 400 (Maximum Produce of X)
y<= 300 (Maximum Produce of Y)
0.20x+0.40y <= 160 (Production Hours)
x,y >= 0
Q3 / a. Explain some of the important terms of the transportation problem.
b. Explain the steps of MODI (Modified Distribution) method.
3a / There is a type of linear programming problem that may be solved using a simplified version of the simplex technique called transportation method. Because of its major application in solving problems involving several product sources and several destinations of products, this type of problem is frequently called the transportation problem. It gets its name from its application to problems involving transporting products from several sources to several destinations. Although the formation can be used to represent more general assignment and scheduling problems as well as transportation and distribution problems. The two common objectives of such problems are either (1) minimize the cost of shipping m units to n destinations or (2) maximize the profit of shipping m units to n destinations.
Thus, the transportation model is concerned with distributing a commodity from a group of supply centers, called sources to a group of receiving centers, called destinations to minimize total transportation cost.
Let us assume there are m sources supplying n destinations. Source capacities, destinations requirements and costs of material shipping from each source to each destination are given constantly.
LP formulation
Suppose a company has m warehouses and n retail outlets. A single product is to be shipped from the warehouses to the outlets. Each warehouse has a given level of supply, and each outlet has a given level of demand. We are also given the transportation costs between every pair of warehouse and outlet, and these costs are assumed to be linear. More explicitly, the assumptions are:
•The total supply of the product from warehouse i is ai, where I = 1, 2,. . . ,m.
•The total demand for the product at outlet j is bj, where j = 1, 2,. . .,n.
•The cost of sending one unit of the product from warehouse I to outlet j is equal to cij, where i = 1, 2,. . .,m and j= 1, 2,. . .,n. The total cost of a shipment is linear in the size of the shipment. The problem of interest is to determine an optimal transportation scheme between the warehouses and the outlets, subject to the specified supply and demand constraints.
Decision Variables: A transportation scheme is a complete specification of how many units of the product should be shipped from each warehouse to each outlet. Therefore, the decision variables are: xij= the size of the shipment from warehouse i to outlet. This is a set of m × n variables.
Objective Function: For any i and any j, the transportation cost per unit is cij; and the size of the shipment is xij. Since we assume that the cost function is linear, the total cost of this shipment is given by cij xij. Summing over all i and all j now yields the overall transportation cost for all combinations. Thus objective function is Minimize ∑i∑jcijxij.
The transportation problem has following properties:
Feasibility: Generally it is assumed that the total supply equals the total demand. As long as the supply equals demand, there exists a feasible solution to the problem. If this is not true for a particular problem, dummy sources or destinations can be added to make it true. The text refers to such a problem as a balanced transportation problem. These dummy centers may have zero distribution costs, or costs may be assigned to represent unmet supply or demand.
Integrality: If the supplies and demands are integer, every basic solution including optimal one, have integer values. Therefore, it is not necessary to resort to integer programming to find integer solutions. Linear programming suffices. In general, a basic solution to the transportation model will have a number of basic variables equal to the number of sources(m) plus the number of destinations(n) minus one i.e. (m + n - 1).
Degeneracy exists in a transportation problem when the number of filled cells is less than the number of rows plus the number of columns minus one (m + n - 1). Degeneracy may be observed either during the initial allocation when the first entry in a row or column satisfies both the row and column requirements or during the Stepping stone method application, when the added and subtracted values are equal. Degeneracy requires some adjustment in the matrix to evaluate the solution achieved. The form of this adjustment involves inserting some value in an empty cell so a closed path can be developed to evaluate other empty cells. This value may be thought of as an infinitely small amount, having no direct bearing on the cost of the solution.
3b / Modi Distribution method
It is a method for computing optimum solution of a transportation problem which allows to compute improvement indices quickly for each unused square without drawing all of the closed paths. Because of this, it can often provideconsiderable time savings over other methods for solving transportation problems.MODI provides a new means of finding the unused route with the largest negative improvementindex. Once the largest index is identified, we are required to trace only one closed path. This pathhelps determine the maximum number of units that can be shipped via the best unused route.