管理运筹学 第4章 整数规划

《管理运筹学 第4章 整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、管理运筹学主讲教师：马越峰第四章整数规划4.1.整数规划数学模型及解的特点4.2.整数规划问题的解法4.3.0-1整数规划4.4.指派问题4.1整数规划数学模型及解的特点目标函数：S.T整数规划数学模型的一形式：整数线性规划的类型纯整数线性规划（pureintegerlinearprogramming)混合整数线性规划（mixedintegerlinearprogramming)0-1整数线性规划(zero-oneintegerlinearprogramming)整数线性规划例1.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。问两种

2、货物各托运多少件，可使获得利润最大。货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙384356托运限制4024解：设x1、x2分别为甲、乙两种货物托运的件数建立模型:目标函数：Maxz=5x1+6x2约束条件：3x1+8x2≤404x1+3x2≤24x1，x2≥0且为整数整数规划解的特点松弛问题：不考虑整数，由余下的目标函数和约束条件构成的规划问题。整数规划问题的可行解集合是它的松弛问题可行解集合的一个子集，任意两个可行解的凸组合不一定满足整数约束条件，因而不一定仍为可行解。由于整数规划问题的可行解一定也是它的松弛问题的可行解，所以前者最优解的目标函数值不会优于后者最

3、优解的目标函数值。对松弛问题的最优解中不符合整数要求的部分取整，得到的解是否为整数规划问题的最优解？4.2整数规划问题的解法分支定界法割平面法匈牙利法（指派问题）枚举法整数规划问题解法整数规划的分枝定界法分枝定界法是求解整数规划的一种常用的有效的方法，它既能解决纯整数规划的问题，又能解决混合整数规划的问题。大多数求解整数规划的商用软件就是基于分枝定界法而编制成的。分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的

4、距离，最后得整数规划的最优解。任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。性质：解:(一)先求出以下线性规划的解：Z=29/6(二)将一个线性规划问题分为两枝，并求解。可由x1≤1或x1≥2中取值。将线性规划1分解为两支，如下：线性规划3：Max2x1+3x2s.t.195x1+273x2≤13654x1+40x2≤140x1≥2x1,x2≥0解得z3=41/9,x1=2,x2=23/9线性规划2：Maxx1+x2s.t.

5、x1+9/14x2≤51/14-2x1+x2≤1/3x1≤1x1,x2≥0解得z2=10/3,x1=1,x2=7/3(三)优选S1进行分支（41/9>10/3)线性规划4：本规划无可行解线性规划5：（四)对线性规划5进行分支：线性规划6：线性规划7：用下图表示例的求解过程与求解结果用下图表示例的求解过程与求解结果从以上解题过程可得用分枝定界法求解目标函数值最大的整数规划的步骤，我们将求解的整数规划问题称为A，将与其相对应的松弛问题称为B，以zb表示问题A的目标函数。求解问题B，可得以下情况之一：1.B没有可行解，则A也没有可行解，求解过程停止。2.B有最优解，且符合问题A的整数条件，

6、则B的最优解即为A的最优解，求解过程停止。3.B有最优解，但不符合A的整数条件，转第二步。第一步：在B的最优解中选一个最远离整数要求的变量，不妨设此变量为xj，以[bj]表示小于bj的最大整数，构造以下两个约束条件，xj≤[bj]和xj≥[bj]+1并加入问题B，得到B的两个后继问题。解这两个后继问题。转步骤3第二步：考查所有后继问题，若其中有几个存在最优解，且最优解满足问题A的整数要求，则以它们中的最优目标函数值和界zb作比较。若比界zb更优，则以其取代原来的zb,并称后继问题为C。否则原来的界zb不变。转步骤4第三步：不属于C的后继问题中，称存在最优解且其目标函数值比界zb更优的

7、后继问题为待查的后继问题。若不存在待查的后继问题，当问题C存在时，问题C的最优解就是A的最优解；当问题C不存在时，和界zb对应的可行解就是问题A的最优解。Zb即为问题A的最优目标函数值。若存在待查的后继问题，则选择其中目标函数最优值最优的一个后继问题，改称其为问题B，转步骤2.第四步：4.30-1整数规划及其应用Maxz=CXS.T.0-1变量的选取与用途（1）n个取一个（2）n个取k个若多个至少取K个？（3）选甲必须选乙，选乙不一定选甲（4）n个约束条件