“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.
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.
1 comments:
Nice explanation.
Indeed appreciable.
cheers,
lacks
Post a Comment