求解整数规划算法

《求解整数规划算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求解整数规划算法——分枝定界法原理步骤：将要求解的整数规划问题称为IL，与它相应的线性规划问题称为问题L。①解问题L，可能得到以下情况之一：（a）L没有可行解，这时IL也没有可行解（b）L有最优解，且解变量都是整数，因而它也是IL的最优解，则停止；（c）L有最优解，但不符合IL中的整数条件，记它的目标函数值为，若记为IL的最优目标函数值，则必有②迭代：第一步：分枝：在L的最优解中任选一个不符合整数条件的变量，设其值为，构造两个约束条件：和。将这两个条件分别加入问题L，将L分成两个后继问题L1和L2。求解L1和L2。定界：以每个子问

2、题的求解结果，与其它问题的解的结果一道，找出最优目标函数值最小者作为新的下界，替换，从已符合整数条件的各分枝中，找出目标数值为最小者作为新的上界，即有。第二步——比较与剪枝：各分枝的最优目标函数中若有大于者，则剪掉这一枝；若小于，且不符合整数条件，则重复第一步骤，一直到最后得到最优目标函数值为止，从而得最优整数解。割平面算法求解整数规划模型这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量是整数的条件，但增加线性约束条件使得由原可行域中切割掉一部分，这部分只包含非整数解，但没切割掉任何整数可行解。这个方法就是指

3、怎样找到适当的割平面，使切割后最终得到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。0-1型整数规划一、解决的主要问题背包问题P35,售货员问题P34,投资组合问题P33,投资决策问题P33,飞机排队P31，（资料）集合覆盖和布点问题P212《运筹学基础》，与生产方式有关的固定成本问题P213《运筹学基础》1如果决策i为是或有0如果决策i为否或无二、模型建立：假设现有m种资源对可供选择的n个项目进行投资的数学模型为：求一组决策变量使其中，表示投资第项获得的期望收益。表示第种资源投于第项目数量，表示第种资源的限量。