Free Assignments via E-mail

Enter your email address:

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

Sunday, April 18, 2010

This is the most probable assignment question of Operation Research for MB0032 SMU MBA. The question is “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.” You already have taken many solved assignments from SMU MBA MB002 such as - classification of Operations Research models, Matrix Minimum Method and Penalty Cost Method or Big-M Method for Solving LPP.

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.

Sunday, April 11, 2010

This question comes from Operation Research assignment of MB0032 for SMU MBA. The question is “Describe the Matrix Minimum method of finding the initial basic feasible solution in the transportation problem.” From the SMU MBA MB002 assignment I already have shared about classification of Operations Research models and Penalty Cost Method or Big-M Method for Solving LPP.

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.

Sunday, April 4, 2010

Write the question from Operation Research assignment of MB0032 for SMU MBA. The question is “Describe the Penalty Cost method (Big M Method) for solving L.P.P.” From the SMU MBA MB002 assignment you already have gotten classification of Operations Research models.

Consider a L.P.P. when at least one of the constraints is of the type ≥ or =. While expressing in the standard form, add a non negative variable to each of such constraints. These variables are called artificial variables. Their addition causes violation of the corresponding constraints, since they are added to only one side of an equation, the new system is equivalent to the old system of constraints if and only if the artificial variables are zero. To guarantee such assignments in the optimal solution, artificial variables are incorporated into the objective function with large positive coefficients in a minimization program or very large negative coefficients in a maximization program. These coefficients are denoted by ± M.

Whenever artificial variables are part of the initial solution Xo, the last row of simplex table will contain the penalty cost M. The following modifications are made in the simplex method to minimize the error of incorporating the penalty cost in the object function. This method is called Big M-method to penalty cost method.

1. The last row of the simplex table is decomposed into two rows, the first of which involves those terms not containing M, while the second involves those containing M.

2. The step 1 of the simplex method is applied to the last row created in the above modification and followed by steps 2,3 and 4 until this row contains no negative elements. Then step 1 of simplex algorithm is applied to those elements next to the last row that are positioned over zero in the last row.

3. Whenever an artificial variable ceases to be basic, it is removed from the first column of the table as a result of step 4, it is also deleted from the top row of the table as is the entire column under it.

4. The last row is removed from the table whenever it contains all zones.

5. If non-zero artificial variables are present in the final basic set, then the program has no solution. In contrast, zero valued artificial variables in the final solution may exist when one or more of the original constraints equations are redundant.

New MBA Assignments

Opinions on MBA Assignments