第五章 整数规划.ppt

《第五章 整数规划.ppt》由会员分享，可在线阅读，更多相关《第五章 整数规划.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章 整数规划整数规划2例例2、某昼夜服务的公交线路每天各时间区段内某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下：所需司机和乘务人员数如下：班次班次 时间时间 所需人数所需人数1 6：00 10：00 602 10：0014：00 703 14：0018：00 604 18：0022：00 205 22：002：00 206 2：00 6：00 307 设司乘人员在各时间段一开始时上班，并连设司乘人员在各时间段一开始时上班，并连8续工作续工作8小时，小时，问问该公司线路至少应配备多少司该公司线路至少应配备多少司9乘人员。乘人员。3解：解：设设x1，x2 ，x3，x6为各

2、班新上班为各班新上班人数。人数。目标函数：目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：约束条件：4一、整数规划问题一、整数规划问题1 1、整数规划模型的一般形式：、整数规划模型的一般形式：、整数规划模型的一般形式：、整数规划模型的一般形式：整数规划分为整数规划分为：l（1）纯整数规划；）纯整数规划；l（2）混合整数规划；）混合整数规划；l（3）0-1整数规划整数规划。5、解的特点、解的特点结论：结论：PIP的最优解的最优解“不优于不优于”其松弛问题的最优解。其松弛问题的最优解。6l l二、分枝定界法二、分枝定界法l可解：可解：纯整数规划、混合整数规划问题纯整数规划、混合整数

3、规划问题l基本思路：基本思路：l 先求松弛问题的最优解，若不是整数解，则添加先求松弛问题的最优解，若不是整数解，则添加两个约束条件，舍弃一部分非整数的可行解，并将原两个约束条件，舍弃一部分非整数的可行解，并将原松弛问题分解为两个子问题。分枝后，某些整数点就松弛问题分解为两个子问题。分枝后，某些整数点就有可能处于可行域的边界上，有机会找到最优解。有可能处于可行域的边界上，有机会找到最优解。7l例例1、用分枝定界法求解整数规划问题：用分枝定界法求解整数规划问题：解解：（1）求解松弛问题）求解松弛问题L：最优解：最优解：8（2）分枝：）分枝：对对L分别增加约束：分别增加约束：将将 L 分解为两个子问

4、题分解为两个子问题 L1，L2 原可行域原可行域 D 变为变为 D1，D29（3）继续对）继续对L1分解：分解：添加约束：添加约束：将将 L1 分解为两个子问题分解为两个子问题 L3，L410（4）继续对）继续对L2分解：分解：添加约束：添加约束：将将 L2 分解为两个子问题分解为两个子问题 L5，L611 问题（0）x1=4.81，x2=1.82 Z0=356 问题（6）无可行解 问题（1）x1=4，x2=2.1 Z1=349 问题（2）x1=5，x2=1.57 Z2=341 问题（3）x1=4，x2=2 Z1=340 问题（5）x1=5.44，x2=1 Z1=308 问题（4）x1=1.4

5、2，x2=2 Z1=32712优点：优点：可解纯整数规划、混合整数规划问题。可解纯整数规划、混合整数规划问题。优于穷举优于穷举 法，仅在一部分可行的法，仅在一部分可行的N解中寻找最优解。解中寻找最优解。缺点：缺点：若变量数目很大，计算工作量很大，可结合割平面若变量数目很大，计算工作量很大，可结合割平面 法使用。法使用。13l l三、三、01整数规划整数规划l一般表示式：一般表示式：14l（1）矛盾约束的处理）矛盾约束的处理l 例例1、约束条件：约束条件：l 解：解：15l例例2、约束条件约束条件l解、解、16（2）m个约束中个约束中k个起作用个起作用例例3、设线性规划模型中有设线性规划模型中有

6、m个约束条件：个约束条件：希望其中希望其中k个起作用。个起作用。解：解：17（3）满足一定逻辑关系的决策问题）满足一定逻辑关系的决策问题例例4、若第一个因素确定，则第二个因素必须确定，反若第一个因素确定，则第二个因素必须确定，反之不一定。之不一定。解：解：18l例例5、（投资选择问题）、（投资选择问题）l某公司有某公司有n个拟选择的投资项目，其中项目个拟选择的投资项目，其中项目j所需所需投资额为投资额为aj，期望收益为，期望收益为cj，j=1,2,n。项目之间有下述联系。项目之间有下述联系：l（）项目，和至少选两项；（）项目，和至少选两项；l（）选项目，则必选项目，反之不一定；（）选项目，则必

7、选项目，反之不一定；l（）项目与项目要么同时选中，要么同时不被选中。（）项目与项目要么同时选中，要么同时不被选中。l该公司总共筹集资金为万元，问怎样选择项目，才使收该公司总共筹集资金为万元，问怎样选择项目，才使收益最大？益最大？l解：解：19l例例6、（工件排序问题）、（工件排序问题）l用四台机床加工三种产品。用四台机床加工三种产品。l加工产品加工产品2的总时间不得超过的总时间不得超过d。现要求确定产品在各机。现要求确定产品在各机床上的加工顺序，使完成全部产品的加工时间结束最早。床上的加工顺序，使完成全部产品的加工时间结束最早。产品产品1机床机床1a11机床机床3a13机床机床4a14产品产品

8、2机床机床1a21机床机床2a22机床机床4a24产品产品3机床机床2a32机床机床3a3320l解：解：设设xij表示产品表示产品i在机床在机床j上开始加工的时间。上开始加工的时间。l（）同一种产品的加工顺序约束（）同一种产品的加工顺序约束产品产品1134产品产品2124产品产品32321l（2）每台机床加工顺序的约束）每台机床加工顺序的约束产品产品1134产品产品2124产品产品32322产品产品1134产品产品2124产品产品32323l（3）产品）产品2的加工总时间约束的加工总时间约束产品产品1134产品产品2124产品产品32324l（4）目标函数）目标函数l 设全部产品加工完毕的时

9、间为设全部产品加工完毕的时间为w。产品产品1134产品产品2124产品产品32325l01整数规划的解法整数规划的解法：（只介绍小规模的）（只介绍小规模的）l1、穷举法：、穷举法：l n个变量，个变量，2n个组合。个组合。l2、隐枚举法：、隐枚举法：l 不全检查，只检查一部分。不全检查，只检查一部分。26l例例2、求解、求解01整数规划：整数规划：27 (x2,x1,x3)Z值值 （0 0 0）（0 0 1）（0 1 0）（0 1 1）（1 0 0）（1 0 1）（1 1 0）（1 1 1）最优解：最优解：x2=0，x1=1，x3=1（0 0 0）（0 0 1）（0 1 0）（0 1 1）（1

10、 0 0）（1 0 1）（1 1 0）（1 1 1）0 5 8 28l l四、指派问题四、指派问题l 指派指派n个人去完成个人去完成n项不同的任务，如何给项不同的任务，如何给每个人分配任务，使总效率最高。每个人分配任务，使总效率最高。29l例例1、今欲指派甲乙丙丁四人加工今欲指派甲乙丙丁四人加工ABCD四种不同的零件，四种不同的零件，l每人加工四种零件所需要的时间如下表所示，问应该派谁加每人加工四种零件所需要的时间如下表所示，问应该派谁加l工何种零件，可使总的花费时间最少。工何种零件，可使总的花费时间最少。零件零件 人人 甲甲 乙乙 丙丙丁丁 4 6 5 8 6 10 7 8 7 8 11 9 9 3 8 4 30313233