《运筹学课件--第四章 整数规划》由会员分享，可在线阅读，更多相关《运筹学课件--第四章 整数规划（44页珍藏版）》请在金锄头文库上搜索。
1、管理运筹学-管理科学方法李军桂林电子科技大学商学院Sub titleOR:SM第4 章 整数规划内容提要第一节 整数规划问题 纯整数规划 0-1规划混合整数规划 第二节 整数规划求解 分枝定界法 第三节 整数规划应用2OR:SM 一般 步骤求解的ILP 求解 特点分析整数 规划OR:SM33本章框架本章要点： 1.整数规划的特点； 2.整数线性规划求解原理； 3.0-1规划和指派问题的处理思路问题背景与数学描述分枝定界法 原理割平面法进一步讨论 建模0-1规划 特殊的ILP 指派问题2011-3-25OR:SMOR:SM第一节 整数规划问题 线性规划的决策变量取值可以是任意非负实数，但许多 实
2、际问题中，只有当决策变量的取值为整数时才有意义 例如，产品的件数、机器的台数、装货的车数、完成工作的人 数等，分数或小数解显然是不合理的。 要求全部或部分决策变量的取值为整数的线性规划问 题，称为整数规划(Integer Programming)。 全部决策变量的取值都为整数，则称为全整数规划(All IP) 仅要求部分决策变量的取值为整数，则称为混合整数规划 (Mixed IP) 要求决策变量只取0或1值，则称0-1规划(0-1 Programming)4OR:SMOR:SM第一节 整数规划问题一、纯整数规划例4.1：某企业利用材料和设备生产甲乙产品，其工艺消耗 系数和单台产品的获利能力如下
3、表所示：资源AB产品甲25乙17现有量935单台利润65问如何安排甲、乙两产品的产量，使利润为最大。 解：设x1为甲产品的台数，x2为乙产品的台数。 maxZ= 6x1 +5 x2 2x1 + x2 9 5x1 +7 x2 35 x1, x2 0 x1, x2 取整数 5OR:SMOR:SM第一节 整数规划问题二、0-1规划序号物品重量重要性系数1食品 5202氧气 5153冰镐 2184绳索 6145帐篷 1286相机 247设备 410登山队员可携带最大重量为25公斤。问都带哪些物品的重要性最大。解：对于每一种物品无非有两种状态，带或者不带，不妨设 0 x j 1不带此种物品带此种物品0-
4、1规划的模型： max Z 20 x1 15 x 2 18 x3 14 x 4 8x5 4 x6 10 x7 5 x1 5x 2 2 x3 6 x 4 12 x5 2 x6 4 x7 25 x j 0或1 ( j 1,2, 7)6OR:SMFi nOR:SM第一节 整数规划问题三、混合整数规划例：某产品有n个区域市场，各区域市场的需求量为 bj吨/月；现拟 在m个地点中选址建生产厂，一个地方最多只能建一家工厂；若选 i 地建厂，生产能力为 ai吨/月，其运营固定费用为F元/月；已知址i至j 区域市场的运价为cij元/吨。如何选址和安排调运，可使总费用最小？解：选址建厂与否是个0-1型决策变量，
5、7假设 yi =1，选择第 i 址建厂， yi=0，不选择第 i 址建厂； 计划从 i 址至区域市场 j 的运输运量xij为实数型决策变量。m m in Z y i F i i 1 x ij y i a i j 1 m s .t . x i j b j i 1 x ij 0 y i 0 ,1m n c ij x ij i 1 j 1i 1, 2 , ., mj 1, 2 , ., nOR:SMOR:SM第二节 整数规划求解一、舍入化整法 为了满足整数解的要求，自然想到“舍入”或“截尾”处理，以得到 与最优解相近的整数解。 这样做除少数情况外，一般不可行，因为化整后的解有可能超出 了可行域，成为
6、非可行解；或者虽是可行解，却不是最优解。不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题 对于例1的数学模型，不考虑整数约束的最优解：x1 *=28/9， x2 * =25/9，Z * =293/9舍入化整x1 =3， x2 =3，Z =33，不满足约束条件5x1 +7 x2 35，非可行解；x1 =3， x2 =2，Z =28，满足约束条件，是可行解，但不是最优解； x1 =4， x2 =1，Z =29，满足约束条件，才是最优解。8OR:SM5OR:SM第二节 整数规划求解二、穷举整数法x22x1 + x2 =943 (3,3)21 1 2 3( 31 947, 2 )9 5x1 +
7、7 x2 =35x1对于决策变量少，可行的整数解又较少时，这种穷举法有时是 可行的，并且也是有效的。但对于大型的整数规划问题，可行的整数解数量很多，用穷举 法求解是不可能的。例如，指派问题 。9OR:SMOR:SM第二节 整数规划求解三、分支定界法 不考虑整数限制，先求出相应线性规划 的最优解， 若求得的最优解符合整数要求，则是原IP的最优解； 若不满足整数条件，则任选一个不满足整数条件的变量来 构造新的约束，在原可行域中剔除部分非整数解。 依次在缩小的可行域中求解新构造的线性规划的最优 解，直到获得原整数规划的最优解。 定界的含义： IP是在相应的LP基础上增加整数约束 IP的最优解不会优于
8、相应LP的最优解 对MaxZ，相应LP的Z*是原IP的上界10OR:SMOR:SM第二节 整数规划求解【例3.5 】用分枝定界法求解例3.1max Z 4 x 1 3 x 2 1 . 2 x 1 0 . 8 x 2 10 2 x 1 2 . 5 x 2 25 x 1 , x 2 0 , 且均取整数【解】先求对应的松弛问题（记为LP0）：max Z 4 x1 3x21.2 x1 0.8x2 10LP0 : 2 x1 2.5x2 25 x1 , x2 0 用图解法得到最优解X（3.57,7.14）,Z0=35.7,如下图所示。11OR:SMx2OR:SM第二节 整数规划求解1.2x1 0.8x2
9、1010AB松弛问题LP0的最优解 X=(3.57,7.14),Z0=35.72x1 2.5x2 2512oC 8.3310x1 OR:SMx21.2x1 0.8x2 10LP2LP1OR:SM增加约束x1 3及x1 4得到两个线性规划max Z 4x1 3x2 10ABLP1:X=(3,7.6),Z1=34.81.2x1 0.8x2 10 2x1 2.5x2 25LP1: x1 3 x1 , x2 0max Z 4x1 3x2 LP2:X=(4,6.5),Z2=35.5 2x1 2.5x2 25 LP2 : x1 4 x1 , x2 0C13o3410x1 OR:SMx2A6OR:SM选择目
10、标值最大的分枝LP2进行分枝，增加约束x2 6及x2 7，显然x2 7不可行，得到线性规划10LP1:X=(3,7.6),Z1=34.8x2 7不可行Bmax Z 4x1 3x21.2x1 0.8x2 10 2x1 2.5x2 25LP3 : x1 4，x2 6 x1 , x2 0LP3:X=(4.33,6),Z3=35.33LP1 LP3C14o3410x1 OR:SM 1.2x1 0.8x2 106OR:SMx2 10A由于 Z 3 Z 1，选择 LP 3 进行分枝，增加约束x 1 4 及 x 1 5，到线性规划 LP 4 及 LP 5： max Z 4x1 3x2 LP1:X=(3,7.
11、6),Z1=34.82x1 2.5x2 25 LP4 : LP4:X=(4,6),Z4=34 x1 4，x2 6，x1 4 x1 , x2 0 即x1 4, 可行域是一条线段max Z 4x1 3x2LP1LP3LP5:X=(5,5),Z5=35 1.2x1 0.8x2 10 2x1 2.5x2 25LP5 : x1 5，x2 6 LP5 C x1 , x2 015o34 510x1OR:SMOR:SM尽管LP1的解中x1不为整数，但Z5Z因此LP5的最优解 就是原整数规划的最优解。上述分枝过程可用下图表示LP0:X=(3.57,7.14),Z0=35.7x13LP1:X=(3,7.6) Z1
12、=34.8x26x14LP2:X=(4,6.5) Z2=35.5 x2716LP3:X=(4.33,6) Z3=35.33x14LP4:X=(4,6) Z4=34无可行解x15LP5:X=(5,5) Z5=35OR:SM1 7 959526 27254 54544 7676OR:SM52 52第二节 整数规划求解三、分支定界法LP 0 ：x 1 3 , x 2 2 , Z 3 2 9 9上界： 32下界： 0MaxZ 6 x1 5x2 2 x1 x2 9 5x 7 x 35 s.t. 1 x1 , x2 0 x1 , x2取整数x13L P 1 ：x 1 3 , x 2 2 , Z 3 2 7
13、 7x1 4LP 2 ：x 1 4 , x 2 1, Z 2 9上界： 32下界： 29x22x2 3L P 3： x 1 3 , x 2 2 , Z 2 8x 1 2x12L P 4 ：, x 2 3, Z 3 1x1 3上界： 31下界： 29x 1L P 5 ： 2, x 2 37, Z 29L P 6 ： 无 可 行 解上界：下界：2929x23x2 4L P 7 ：L P 8 ：上界：2917x 1 2, x 2 3, Z 2 7x 1 1, x 2 4, Z 28下界： 29OR:SMOR:SM18分枝定界法小结非整数解A 增加约束整数解B1增加约束非整数解B2, 比B1好增加约束非整数解B4, 比B1,B3好增加约束整数B3 ， 增加约束1 若分枝后得到整数解，则这枝不必再分枝。2 若分枝后得到非整数解, 如果比整数解更好，则这枝继续分枝3 若分枝后得到非整数解, 如果比整数解更差，则这枝不必再分枝这里解的好坏是指对应目标函数值的大小182011-3-25OR:SMOR:SM第三节 整数规划应用一、生产基地规划例：某公司拟建设A、B两种类型的生产基地若干个，两种类型的生产基地 每个占地面积，所需经费，建成后生产能力及现有资源情况如下表所示。问A、 B类型基地各建设多少个，可使总生产能力最大？AB资源限制占
