[工学]运筹学整数规划

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

1、第五章整数规划IntegerProgramming第五章整数规划第1节整数规划的数学模型及解的特点第2节分支定界法第3节0-1型整数规划第4节指派问题第1节整数规划的数学模型及解的特点一、整数规划的含义要求一部分或全部决策变量必须取整数值的规划问题。第1节整数规划的数学模型及解的特点整数规划的松弛问题不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。若松弛问题是一个线性规划，则称该整数规划为整数线性规划。第1节整数规划的数学模型及解的特点整数线性规划的数学模型第1节整数规划的数学模型及解的特点整数线性规划问题的类型（1）纯（全）整数线性

2、规划：全部决策变量都必须取整数值的整数线性规划（2）混合整数线性规划：决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划（3）0-1型整数线性规划：决策变量只能取值0或1的整数线性规划第1节整数规划的数学模型及解的特点例1：某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定，服务员连续工作8h（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。时段12345678服务员最少数目10891113853第1节整数规划的数学模型及解的特点例1：解：设在第j时段开始时上班的服务员人数为xj。第1节

3、整数规划的数学模型及解的特点二、整数规划的解的特点整数规划问题的可行域是它的松弛问题可行域的子集整数规划问题的可行解是它的松弛问题的可行解整数规划问题最优解的目标函数值不优于它的松弛问题最优解的目标函数值第1节整数规划的数学模型及解的特点三、整数规划的解法例2：某宝石加工厂最近新到6粒大小、质量等级相似的钻石毛料，管理层有两种选择，一是切磨成一般的皇冠形，每粒可获利2.5千元；一是切磨成虽然较难切磨但当前市场较流行的心形，每粒可获利4千元。若切磨成皇冠形则每粒需要5个工作日，若切磨成心形则每粒需要9个工作日，由于工厂切工师傅较忙，最多只有45个

4、工作日来做这批工作。另外，由于毛料自身形状的关系，其中只有4粒毛料可以切磨成皇冠形，而6粒毛料中任何一粒都可以切磨成心形。那么，管理层应如何决策才能使这批钻石获利最大？第1节整数规划的数学模型及解的特点例2：解：设x1，x2分别为切磨成皇冠形和切磨成心形的钻石粒数maxz=2.5x1+4x2x1+x2≤65x1+9x2≤45x1≤4x1，x2≥0x1，x2整数第1节整数规划的数学模型及解的特点完全枚举法对于可行域有界的整数规划问题，整数规划的可行解是一个有限集，将这个集内的每一个点对应的目标函数值都一一计算出来，然后从中找出最优者，则为整数规划

5、的最优解。第1节整数规划的数学模型及解的特点例3：用完全枚举法求解下述整数规划问题。maxz=x1+4x2-2x1+3x2≤3x1+2x2≤8x1，x2≥0x1，x2整数第1节整数规划的数学模型及解的特点小结（1）对整数规划问题的松弛问题的最优解中不符合整数要求的分量进行简单地取整，所得到的整数解可能不一定是整数规划问题的最优解，甚至也不一定是整数规划问题的可行解（2）对于复杂的模型，完全枚举法费时，甚至不可能实现第2节分支定界法一、分支定界法的思路分支定界法是先求解整数规划的松弛问题，如果其最优解不符合整数条件，则用增加约束的办法求出整数规划

6、问题的上下界，并把松弛问题的可行域分成互不重叠的子区域，再求解这些子区域的松弛问题，不断缩小整数规划问题上下界的差距，最后取得整数规划问题的最优解。第2节分支定界法二、分支定界法的含义分支定界法是一种部分枚举法，通过不断地分割松弛问题的可行域并进行比较，最终求得整数规划问题的最优解。第2节分支定界法三、分支定界法的步骤第一步：求解松弛问题。（1）松弛问题无可行解，则整数规划问题无可行解，计算停止；（2）松弛问题有最优解，并且符合整数规划问题的整数条件，则松弛问题的最优解就是整数规划问题的最优解，计算停止；（3）松弛问题有最优解，但是不符合整数规

7、划问题的整数条件，则松弛问题的最优值是整数规划问题最优值的上界值（求极大时）或下界值（求极小时），下界值（求极大时）可暂定为-∞或上界值（求极小时）可暂定为+∞。第2节分支定界法第二步：分支。在松弛问题的最优解中任选一个不符合整数条件的变量xi，其值为bi，用[bi]表示小于bi的最大整数，构造以下两个约束条件：将这两个约束条件分别加入整数规划问题，形成两个子问题，再求解这两个子问题的松弛问题。第2节分支定界法第三步：定界。以每个子问题的松弛问题为一分支标明求解的结果，与其他问题的解的结果相比较：（1）若解满足子问题的整数条件，则找到了一个整数

8、规划问题的可行解，为新的下界值（求极大时）或上界值（求极小时）；（若计算中同时出现两个及以上整数规划问题可行解，则选取其中最大（求极大时）或最小（求极