用分枝定界法求解整数规划(最小化)问题的步骤

步骤用文字表示的那些

例如求整数规划(最大化)问题的步骤

第一步是:解线性规划松弛问题.然后设原整数规划问题为A,所对应的松弛问题为B,(1)若问题B没有可行解,这时问题A也没有可行解,终止.(2)问题B有最优解,并符合问题A的整数约束,则问题B的最优解即为问题A的最优解,则停止.(3)问题B有最优解,但不符合问题A的整数条件,记它的目标函数值为Z￣.

第二步是分枝与定界.用观察法找问题A的一个整数可行解,一般可取Xj=0,j=1,...,n,试求其目标函数值,并记做Z_.以Z*表示问题A的最优目标函数值；这时有Z_≤Z*≤Zˉ进行迭代.

......