## Free Assignments via E-mail

Subscribe the blog by your Email ID for the SMU MBA assignments updates.

## Branch and Bound Technique to solve an I.P.P. Problem for MB0032 SMU MBA Assignment

Thursday, May 27, 2010

“Describe the Branch and Bound Technique to solve an I.P.P. problem.” This is MB0032 SMU MBA question assignment. It is solved assignment of Operation Research chapter of Sikkim Manipal University. I already have shared North-West Corner rule, Matrix Minimum Method and Integer Programming Problem assignments also of SMU MBA MB0032.

Sometimes a few or all the variables of an IPP are constrained by their upper or lower bounds or by both. The most general technique for the solution of such constrained optimization problems is the branch and bound technique.

To explain how this partitioning helps, let us assume that there were no integer restrictions, and suppose that this then yields an optimal solution to LPP.

Then the solution having the larger value for z is clearly optimum for the given IPP. However, it usually happens that one of these problems has no optimal solution satisfying and thus some more computations are necessary. We now discuss step wise the algorithm that specifies how to apply the partitioning and in a systematic manner to finally arrive at an optimum solution.

We start an initial lower bound for z, say z at the first iteration which I less than or equal to the optimal value z, this lower bound may be taken as the starting Lj for some Xj.

In addition to the lower bound z, we also have a list of LPP’s differing only in the bounds. To start with the master list contains a single LPP consisting of 1, 2, 3, 4 and 5. We now discuss below, the step by step procedure that specifies how the partitioning 6 and 7 can be applied systematically to eventually get an optimum integer – valued solution.

Now, on terming we find that only two feasible integer solution namely 5 and 6 have been recorded. The best of these gives the optimum solution to the given IPP. Hence the optimum integer solution to the given IPP is:

Z0 = 55, X1 = 4, X2 = 3.

## North West Corner Rule for Finding the Initial Basic Feasible Solution in the Transportation Problem from MB0032 Assignment

Sunday, May 16, 2010

“Describe the North-West Corner rule for finding the initial basic feasible solution in the transportation problem.” The question has been taken from MB0032 MBA assignment of SMU. This question has been taken from Operation Research chapter of Sikkim Manipal University. We already have discussed about MODI method, Matrix Minimum Method and Integer Programming Problem in this series.

North West Corner Rule:

Step 1: The first assignment is made in the cell occupying the upper left hand (North West) corner of the transportation table. The maximum feasible amount is allocated there, that is X11 = min (a1, b1).

So that either the capacity of origin O1 is used up or the requirement at destination D1 is satisfied or both. This value of X11 is entered in the upper left hand corner (Small Square) of cell (1, 1) in the transportation table.

Step 2: If b1 > a1 the capacity of origin O, is exhausted but the requirement at destination D1 is still not satisfied, so that at least one more other variable in the first column will have to take on a positive value. Move down vertically to the second row and make the second allocation of magnitude X21 = min (a2, b1 – x21) in the cell (2, 1). This either exhausts the capacity of origin O2 or satisfies the remaining demand at destination D1.

If a1 > b1 the requirement at destination D1 is satisfied but the capacity of origin O1 is not completely exhausted. Move to the right horizontally to the second column and make the second allocation of magnitude X12 = min (a1 – x11, b2) in the cell (1, 2). This either exhausts the remaining capacity of origin O1 or satisfies the demand at destination D2.

If b1 = a1, the origin capacity of O1 is completely exhausted as well as the requirement at destination is completely satisfied. There is a tie for second allocation; an arbitrary tie breaking choice is made. Make the second allocation of magnitude X12 = min (a1 – a1, b2) = 0 in the cell (1, 2) or X21 = min (a2, b1 – b2) = 0 in the cell (2, 1).

Step 3: Start from the new north west corner of the transportation table satisfying destination requirements and exhausting the origin capacities one at a time, move down towards the lower right corner of the transportation table until all the rim requirements are satisfied.

## Transportation Problem and MODI Method of Solving Transportation Problem From MB0032 Assignment

Sunday, May 2, 2010

The question is – “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.” It has been taken from MB0032 assignment of SMU MBA. It is the question of Operation Research book of Sikkim Manipal University. I am back with this question after the - Matrix Minimum Method, Integer Programming Problem and Penalty Cost Method or Big-M Method for Solving LPP.

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.