大学精品课件:运筹学(五).ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《大学精品课件:运筹学(五).ppt》由用户(罗嗣辉)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大学 精品 课件 运筹学
- 资源描述:
-
1、第五章第五章整整 数数 规规 划划主要内容:主要内容:第一节第一节 整数规划的数学模型及解的特点整数规划的数学模型及解的特点第二节第二节 解纯整数规划的割平面法解纯整数规划的割平面法第三节第三节 分支定界法分支定界法第四节第四节 0-10-1型整数规划型整数规划第五节第五节 指派问题指派问题第一节第一节整数规划的数学模型及解的特点整数规划的数学模型及解的特点一、整数规划问题举例一、整数规划问题举例 例例1 1(纯整数规划)(纯整数规划):某个中型百货商场对售货人员(周工某个中型百货商场对售货人员(周工资资200200元)的需求经统计如下表:元)的需求经统计如下表:为了保证销售人员充分休息,销售
2、人员每周工作为了保证销售人员充分休息,销售人员每周工作5 5天,休息天,休息2 2天天(这两天是连续的)。问应如何安排销售人员的工作时间,使(这两天是连续的)。问应如何安排销售人员的工作时间,使得所配售货人员的总费用最小?得所配售货人员的总费用最小?星期星期一一二二三三四四五五六六七七人数人数12151214161819 解解:设:设x xj j为在星期为在星期j j开始上班的销售人员数目,开始上班的销售人员数目,则该问题的数学模型为:则该问题的数学模型为:71200minjjxz 例例2 2(0-10-1整数规划)整数规划):某公司有:某公司有5 5个投资项目被列入投资计划,个投资项目被列入
3、投资计划,各项目需要的投资额和期望的收益见下表:各项目需要的投资额和期望的收益见下表:已知该公司只有已知该公司只有600600万元资金可用于投资,由于技术上的原因,投资万元资金可用于投资,由于技术上的原因,投资受到以下约束:受到以下约束:(1 1)项目)项目1 1、项目、项目2 2和项目和项目3 3至少应有一项选择;至少应有一项选择;(2 2)项目)项目3 3和项目和项目4 4最多只能选一项;最多只能选一项;(3 3)项目)项目5 5选中的前提是项目选中的前提是项目1 1必须选中。必须选中。问如何选择一个最好的投资方案使得总的投资收益最大。问如何选择一个最好的投资方案使得总的投资收益最大。项目
4、项目投资额投资额/万元万元期望收益期望收益/万元万元121015023002103100604130805260180 解解:每一个投资项目都有被选择和不被选择两:每一个投资项目都有被选择和不被选择两种可能,因此令:种可能,因此令:则该问题的数学模型为:则该问题的数学模型为:543211808060210150maxxxxxxz 5,4,3,2,11011600260130100300210.154332154321jxxxxxxxxxxxxxstj,或或 不投资)不投资)(对项目(对项目投资)投资)对项目对项目j 0j(1jx5,4,3,2,1 j 例例3 3(混合整数规划)(混合整数规划)
5、:工厂:工厂A1A1和和A2A2生产两种物资。由于该种物资供不生产两种物资。由于该种物资供不应求,需要再建立一家年生产能力为应求,需要再建立一家年生产能力为200kt200kt的工厂,相应的建厂方案有的工厂,相应的建厂方案有A3A3和和A4A4两个。这种物资的需求地有两个。这种物资的需求地有B1,B2,B3,B4B1,B2,B3,B4四个。各工程年生产能力、四个。各工程年生产能力、各地需求量、各厂至各需求地的单位物资运费见下表:各地需求量、各厂至各需求地的单位物资运费见下表:工厂工厂A3A3或或A4A4开工后,每年的生产费用估计分别为开工后,每年的生产费用估计分别为12001200万元或万元或
6、15001500万元。万元。现要决定建设工厂现要决定建设工厂A3A3还是还是A4,A4,才能使今后每年的总费用最少。才能使今后每年的总费用最少。B1B2B3B4A12934400A28357600A37612200A44525200350400300150 解解:设:设x xijij表示从表示从A Ai i厂运往厂运往B Bj j地的物资数量,再设:地的物资数量,再设:则该问题的数学模型为:则该问题的数学模型为:厂)厂)(建(建)建建4 03(1AAy厂 4141)1(15001200minijijijyyxcz 104,3,2,1;4,3,2,1,0)1(200200600400150300
7、400350.4443424134333231242322211413121144342414433323134232221241312111或或yjixyxxxxyxxxxxxxxxxxxxxxxxxxxxxxxxxxxstij二、整数规划问题的数学模型二、整数规划问题的数学模型 njjjxcz1min)max(或或 整数整数个变量中部分或全部为个变量中部分或全部为),或或n),1(0),1(.1njxmibxastjnjijij规划变量规划整数变量整数变量整数或全部为个混合整数不全部为个纯整数规划全部为个10 10n n n三、整数规划问题的解的特点三、整数规划问题的解的特点 整数整数个变
8、量中部分或全部为个变量中部分或全部为),或或n),1(0),1(.1njxmibxastjnjijij njjjxcz1min)max(或或 ),1(0),1(.1njxmibxastjnjijij),或或整数规划问题整数规划问题整数规划问题的松弛问题整数规划问题的松弛问题1、整数规划问题的可行解一定是其松弛问题的可行解;、整数规划问题的可行解一定是其松弛问题的可行解;2、若目标函数求极大(、若目标函数求极大(小小),整数规划问题的最优解对),整数规划问题的最优解对应的目标函数值一定小(应的目标函数值一定小(大大)于等于其松弛问题最优解对)于等于其松弛问题最优解对应的目标函数值。应的目标函数值
9、。njjjxcz1min)max(或或3、不能把其松弛问题的最优解取整作为该整数规划问题、不能把其松弛问题的最优解取整作为该整数规划问题的最优解。的最优解。214maxxxz 且取整数且取整数0,82332.212121xxxxxxst第二节第二节求解纯整数规划的割平面法求解纯整数规划的割平面法一、割平面法的思路一、割平面法的思路1、求出整数规划问题的、求出整数规划问题的松弛问题的最优解。松弛问题的最优解。2、若得到最优解满足整数要求,则该最优解就、若得到最优解满足整数要求,则该最优解就是整数规划问题的最优解;是整数规划问题的最优解;若最优解不满足整数要求,则若最优解不满足整数要求,则增加一个
10、约增加一个约束条件(建立割平面方程)束条件(建立割平面方程),使得最优解不,使得最优解不满足该约束条件,而所有的整数规划的可行满足该约束条件,而所有的整数规划的可行解仍满足该约束条件。解仍满足该约束条件。3、重新求解增加约束条件后的最优解,回到、重新求解增加约束条件后的最优解,回到2。二、割平面法计算步骤二、割平面法计算步骤例:用割平面法求解纯整数规划例:用割平面法求解纯整数规划213maxxxz 为整数为整数2121212121,0,521045323.xxxxxxxxxxst213maxxxz 0,521045323.21212121xxxxxxxxst松弛松弛问题问题-3/70-5/70
11、022/71-3/70031/703/70-2/7109/7-12/701/70113/73000-13jjzc jcBCBxb2x2x3x4x5x1x1x4x解:解:(1 1)求解其松弛问题的最优解求解其松弛问题的最优解。用单纯形法。用单纯形法进行求解,得到最优单纯形表如下(进行求解,得到最优单纯形表如下(x3,x4,x5x3,x4,x5为松为松弛变量):弛变量):该最优解不满足整数要求,因此需要建立割平面方程。该最优解不满足整数要求,因此需要建立割平面方程。(2 2)建立割平面方程)建立割平面方程:最终单纯形表第一行:最终单纯形表第一行:5317271713xxx 5317271761xx
12、x 1727176153 xxx072717653 xx因为因为x x1 1为整数,故为整数,故x x1 1-1-1也为整数,因此等号左边的也为整数,因此等号左边的式子也为整数。又因为式子也为整数。又因为6/76/7小于小于1 1,x x3 3和和x x5 5都大于等都大于等于于0 0,故该整数一定小于等于零。,故该整数一定小于等于零。即:即:(割平面约束)(割平面约束)引入松弛变量引入松弛变量x6,x6,建立割平面方程:建立割平面方程:767271653 xxx76727153 xx3-10000313/7101/702/70-19/701-2/703/70031/700-3/7122/70
13、0-6/700-1/70-2/7100-5/70-3/70jjzc jcBCBxb1x3x4x5x6x1x2x2x6x4x用对偶单纯形法继续求解,得到新的最优解用对偶单纯形法继续求解,得到新的最优解:(3 3)把割平面方程加入到上个最终单纯形表中,得到)把割平面方程加入到上个最终单纯形表中,得到:3-1000031100001-15/4010-1/40-5/405/2001-1/20-11/207/40001/41-3/4000-1/40-17/4jjzc jcBCBxb1x3x4x5x5x1x2x2x6x3x该最优解仍不满足整数要求,因此还需要建立割平面方程。该最优解仍不满足整数要求,因此还
14、需要建立割平面方程。最终单纯形表第四行:最终单纯形表第四行:654434147xxx 66454141431xxxx 14141436564 xxxx041414364 xx43414164 xx(割平面约束)(割平面约束)引入松弛变量引入松弛变量x7,x7,建立割平面方程:建立割平面方程:434141764 xxx(4 4)建立割平面方程)建立割平面方程:3-100000311000010-15/4010-1/40-5/4005/2001-1/20-11/2007/40001/41-3/400-3/4000-1/40-1/41000-1/40-17/40jjzc jcBCBxb1x3x4x5
15、x5x1x2x2x6x3x7x311000010-1201000-1-10400100-5-20100001-1103000101-400000-4-11x5x2x3x4xjjzc 7x(5 5)将割平面方程带入上个最优单纯形表中,用对偶单纯形法求解)将割平面方程带入上个最优单纯形表中,用对偶单纯形法求解:该最优解满足整数要求,即为整数规划的最优解。该最优解满足整数要求,即为整数规划的最优解。76727153 xx43414164 xx 521045323521421321xxxxxxxxx 215214213251045233xxxxxxxxx76)25(72)233(712121 xxxx
16、6)25(2)233(2121 xxxx11x767271653 xxx76)25(72)233(7162121 xxxxx161xx 43)1(41)1045(41121 xxx311045121 xxx321 xx(第(第1 1个割平面方程个割平面方程)(第(第2 2个割平面方程个割平面方程)考察割平面方程的几何意义:考察割平面方程的几何意义:BACD11xEFABCDE(1,5/4)AGHF321 xxGHD(13/7,9/7)ABEFH(1,2)三、注意三、注意 整数规划模型的约束条件中,若约束条件中整数规划模型的约束条件中,若约束条件中变量的系数或右端常数取值不为整数时,首变量的系数
17、或右端常数取值不为整数时,首先要把它们变为整数)先要把它们变为整数)保证松弛变量或剩余变量保证松弛变量或剩余变量的取值也为整数。的取值也为整数。第三节第三节分分 支支 定定 界界 法法一、分支定界法的思路一、分支定界法的思路 分支分支:若整数规划的松弛问题的最优解不符合整数要若整数规划的松弛问题的最优解不符合整数要求,假设求,假设 不符合整数要求,不符合整数要求,是不超过是不超过 的最的最大整数,则构造两个约束条件:大整数,则构造两个约束条件:和和 ,分别将其并入松弛问题中,从而形成两个后继问,分别将其并入松弛问题中,从而形成两个后继问题,即两个分支。题,即两个分支。iibx ibib iib
18、x 1iibx为整数规划的最优解的为整数规划的最优解的出现创造了条件出现创造了条件(不是整数)松弛问题最优解中iibx x1x2X1=2.5X1=2X1=3定界定界:在分支过程中,若某个后继问题恰巧获得整数规:在分支过程中,若某个后继问题恰巧获得整数规划问题的一个可行解,那么,它的目标函数值就是一个划问题的一个可行解,那么,它的目标函数值就是一个“界限界限”,可以作为衡量处理其它分支的一个依据(当,可以作为衡量处理其它分支的一个依据(当某个分支的最优解的目标函数值比该界限差,则这个分某个分支的最优解的目标函数值比该界限差,则这个分支可以剔除不计)。当出现更优的支可以剔除不计)。当出现更优的“界
19、限界限”,则用新界,则用新界限代替原来的界限。限代替原来的界限。提高了最优解的搜索效率提高了最优解的搜索效率二、分支定界法的步骤二、分支定界法的步骤例:用分支定界法求解整数规划例:用分支定界法求解整数规划21maxxxz 为整数为整数21212121,0,3121451149.xxxxxxxxst松弛松弛问题问题21maxxxz 0,3121451149.212121xxxxxxst解解:(:(1)求解其松弛问题。)求解其松弛问题。得到最优解得到最优解 (3/2,10/3),不满足整数要求。,不满足整数要求。x1x2A(3/2,10/3)S (2)分支。)分支。选择选择x1=3/2进行分支进行
20、分支。构造两个约束条件:构造两个约束条件:x111和和x1x12进行分支进行分支。x1x2(1,7/3)BC(2,23/9)S1S2 得到两个后继问题:得到两个后继问题:LP1LP1和和LP2LP2。(3)继续分支。)继续分支。因为因为LP1和和LP2所得到的最优解都不满足整数所得到的最优解都不满足整数要求,需要继续分支要求,需要继续分支。考虑到。考虑到LP2的最优解对应的的最优解对应的目标函数值较大些,因此,选择目标函数值较大些,因此,选择LP2进行分支。进行分支。LP2最优解中最优解中x2=23/9不满足整数要求,需要不满足整数要求,需要进行分支。构造两个约束条件:进行分支。构造两个约束条
21、件:x22和和x23 x1x2(1,7/3)BD(33/14,2)S1S21 得到两个后继问题:得到两个后继问题:LP21LP21和和LP22LP22。(4)继续分支。)继续分支。LP22无可行解;无可行解;LP21所得到的最优解所得到的最优解(33/14,2)不满足整数要求,需要继续分支)不满足整数要求,需要继续分支。考虑到考虑到LP21的最优解对应的目标函数值较大些,的最优解对应的目标函数值较大些,因此,选择因此,选择LP21的的x1进行分支。进行分支。构造两个约束条件:构造两个约束条件:x12和和x13.x1x2(1,7/3)BF(2,2)S1S212S211E(3,1)得到两个后继问题
22、:得到两个后继问题:LP211LP211和和LP212LP212。(5)定界)定界 LP211和和LP212所得到的最优解(所得到的最优解(2,2)和(和(3,1)都满足整数要求,且对应的目标值相)都满足整数要求,且对应的目标值相同,都为同,都为4,因此可以给目标函数定下界,因此可以给目标函数定下界4。考虑考虑LP1,其最优解对应的目标函数为,其最优解对应的目标函数为10/3,小于下界小于下界4,因此不用对其进行分支,因此不用对其进行分支。所以,该整数规划问题的最优解为(所以,该整数规划问题的最优解为(2,2)和)和(3,1)。6/293/10,2/321zxxA S3/103/7,121zx
23、xC S19/419/23,221zxxB S214/612,14/3321zxxD S21 无可行解S22)442,221Z(zxxFS21141,321zxxE S21211x 21x 21x 31x 22x 32x 上述求解过程可以总结如下图:上述求解过程可以总结如下图:第四节第四节0-1 0-1 整整 数数 规规 划划一、一、0-10-1规划的举例规划的举例1 1、选址问题(布点问题)、选址问题(布点问题)要选取投资场所,已知要选取投资场所,已知:区名区名Ai可供选择的点可供选择的点投资投资(元)(元)年利润年利润(元)(元)总资金总资金(元)(元)东区东区 A1b1c1B A2(最多
展开阅读全文