求解整数规划算法

《求解整数规划算法》由会员分享，可在线阅读，更多相关《求解整数规划算法（2页珍藏版）》请在金锄头文库上搜索。

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

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

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