M.B.A-FINANCE Sem-1 OPERATION MANAGEMENT(Sikkim Manipal University-2007)

Some important topic

Matrix Minimum Method, Integer Programming Problem and Penalty Cost Method or Big-M Method for Solving LPP.

Ques 1 What do you understand by the transportation problem? What is the basic assumption behind the transportation problem? Describe the MODI method of solving transportation problem

Ans Transportation Problem:

Here we study an important class of linear programs called the transportation model. This model studies the minimization of the cost of transporting a commodity from a number of sources to several destinations. The supply at each source and the demand at each destination are known.

The objective is to develop an integral transportation schedule that meets all demands from the inventory at a minimum total transportation cost.

Basic Assumption behind Transportation Problem:

Let us consider a T.P involving m-origins and n-destinations. Since the sum of origin capacities equals the sum of destination requirements, a feasible solution always exists. Any feasible solution satisfying m+n-1 of the m + n constraints is a redundant one and hence can be deleted. This also means that a feasible solution to a T.P can have at the most only m + n – 1 strictly positive components, otherwise the solution will degenerate.

It is always possible to assign an initial feasible solution to a T. P. in such a manner that the rim requirements are satisfied. This can be achieved either by inspection or by following some simple rules. We begin by imagining that the transportation table is blank i.e. initially all Xij = 0. The simplest procedures for initial allocation discussed in the following section.

MODI Method of Solving Transportation Problem:

The first approximation to (2) is always integral and therefore always a feasible solution. Rather than determining a first approximation by a direct application of the simplex method it is more efficient to work with the table given below called the transportation table. The transportation algorithm is the simplex specialized to the format of table it involves:

a) Finding an integral basic feasible solution
b) Testing the solution for optimality
c) Improving the solution, when it is not optimal
d) Repeating steps (1) and (2) until the optimal solution is obtained

The solution of T.P. is obtained in two stages. In the first stage we find basic feasible solution by any one of the following methods a) North-west corner rale b) Matrix Minima method or least cost method c) Vogel’s approximation method. In the second stage we test the B.Fs for its optimality either by MODI metod or by stepping stone method.

Ques 2 “What do you understand by the Integer Programming Problem? Describe the Gomory’s All-I.P.P. method for solving the I.P.P. problem?

Ans An integer programming problem can be described as follows:

Determine the value of unknowns X1, X2, …, Xn

So as to optimize z = C1X1 + C2X2 + … CnXn

Subject to the constraints

ai1 X1 + ai2 X2 + … + ain Xn = bi, i = 1,2, …, m

and xj ≥ 0 j = 1, 2, …, n

where xj being an integral value for j = 1, 2, …, k ≤ n.

If all the variables are constrained to take only integral value i.e. k = n, it is called an all (or pure) integer programming problem. In case only some of the variables are restricted to take integral value of rest (n – k) variables are free to take any one negative values, then the problem is known as mixed integer programming problem.

Gomory’s All – IPP Method:

An optimum solution to an I. P. P. is first obtained by using simplex method ignoring the restriction of integral values. In the optimum solution if all the variables have integer values, the current solution will be the desired optimum integer solution. Otherwise the given IPP is modified by inserting a new constraint called Gomory’s or secondary constraint which represents necessary condition for integrability and eliminates some non integer solution without losing any integral solution.

After adding the secondary constraint, the problem is then solved by dual simplex method to get an optimum integral solution. If all the values of the variables in this solution are integers, an optimum inter-solution is obtained, otherwise another new constrained is added to the modified L P P and the procedure is repeated.

An optimum integer solution will be reached eventually after introducing enough new constraints to eliminate all the superior non integer solutions. The construction of additional constraints, called secondary or Gomory’s constraints is so very important that it needs special attention.

Ques 3 Describe the Matrix Minimum method of finding the initial basic feasible solution in the transportation problem?

Ans  Matrix Minimum Method:

Step 1: Determine the smallest cost in the cost matrix of the transportation table. Let it be Cij, Allocate Xij = min (aj, bj) in the cell (i, j).

Step 2: If Xij = aj cross off the ith row of the transportation table and decrease bj by ai go to step 3.

If xij = bj cross off the ith column of the transportation table and decrease ai by bj go to step 3.

If Xij = ai = bj crosss off either the ith row or the ith column but not both.

Step 3: Repeat steps 1 and 2 for the resulting reduced transportation table until all the rim requirements are satisfied whenever the minimum cost is not unique make an arbitrary choice among the minima.

The Initial Basic Feasible Solution:

Let us consider a T.P involving m-origins and n-destinations. Since the sum of origin capacities equals the sum of destination requirements, a feasible solution always exists. Any feasible solution satisfying m+n -1 of the m+n constraints is a redundant one and hence can be deleted. This also means that a feasible solution to a T.P can have at the most only m + n -1 strictly positive component, otherwise the solution will degenerate.

It is always possible to assign an initial feasible solution to a T.P. in such a manner that the rim requirements are satisfied. This can be achieved either by inspection or by following some simple rules. We begin by imagining that the transportation table is blank i.e. initially all Xij = o. The simplest procedures for initial allocation discussed in the following section.

Ques 4 “Describe the broad classification of Operations Research models in details. Name the different steps needed in OR approach of problem solving?”

Ans A model is a representation of the reality. It is an idealized representation or abstraction of a real life system. A model is helpful in decision making as it provides a simplified description of complexities and uncertainties of a problem in logical structure.

A) Physical Model: It includes all form of diagrams, graphs and charts. They are designed to deal with specific problems. They bring out significant factors and inter-relationship in pictorial firm so as to facilitate analysis.

B) Mathematical Model: It is known as symbolic models also. It employs a set of mathematical symbols to represent the decision variable of the system.

C) By Nature of Environment: We have 1) Deterministic model in which every thing is defined and the results are certain. Eg: EOQ model 2) Probabilistic Models in which the input and output variables follow a probability distribution. Eg: Games Theory.

D) By the extent of Generality: The two models belonging to this class are 1) General models can be applied in general and does not pertain to one problem only. Eg: Linear programming 2) Specific model is applicable under specific condition only. Eg: Sales response curve or equation as a function of advertising is applicable in the marketing function alone.

Methodology of Operations Research:

The basic dominate characteristic feature of operations research is that it employs mathematical representations or model to analyze problems. This distinctive approach represents an adaptation of the scientific methodology used by the physical sciences. The scientific method translates a real given problem into a mathematical representation which is solved and transformed into the original context. The OR approach problem solving consists of the following steps:

Definition of the Problem

Construction of the Model

Solution of the Model

Validation of the Model

Implementation of the Final Result