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.
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.
0 comments:
Post a Comment