运筹学第五章整数规划

《运筹学第五章整数规划》由会员分享，可在线阅读，更多相关《运筹学第五章整数规划（77页珍藏版）》请在金锄头文库上搜索。

1、Page:1wxj浙江理工大学 经济管理学院管理运筹学管管理理运运筹筹学学 整整数数规规划划儡艳勃棱佰岿槛扫哺搅桔隔蔫遏鞘续庚群蛀卿拉颈绕汝裳徐退岭历到忠凑运筹学第五章整数规划运筹学第五章整数规划Page:2wxj浙江理工大学 经济管理学院管理运筹学第五章第五章 整数规划整数规划5.1 整数规划问题的提出整数规划问题的提出例例5-1 某厂拟用集装箱托运甲、乙两种货物。每箱的体积、重量、可获利润以及托运所受限制如下表所示：货物 体积（m3/箱） 重量（kg/箱） 利润（百元/箱） 甲 5 2 20 乙 4 5 10托运限制 24 13问两种货物各托运多少箱，可使获得的利润最大？解：解： 设x1

2、, x2 分别为甲、乙两种货物的托运箱数，则模型为： Max z = 20x1 +10x2 St. 5x1 +4x2 242x1 +5 x2 13 x1 ，x2 0 x1 ，x2 整数暂不考虑整数约束，求得最优解为x1 = 4.8 ，x2 = 0， Max z = 96磋粗希唾苛酋谭孜坷酒阅寥键竞旱缕诗董收舜禹捏蕉瘦停涸呢稿尖红怂桨运筹学第五章整数规划运筹学第五章整数规划Page:3wxj浙江理工大学 经济管理学院管理运筹学 Max z = 20x1 +10x2 St. 5x1 +4x2 242x1 +5 x2 13 x1 ，x2 0 x1 ，x2 整数（1）若 x1 = 4.8 ，x2 =

3、0x1 = 5 ，x2 = 0不是可行解；（2）若x1 = 4.8 ，x2 = 0x1 = 4，x2 = 0是可行解，但不是最优解因为 x1 = 4，x2 = 0时，z = 80而可行解x1 = 4，x2 = 1时，z = 90颖官仇绎莎茅艺敞笺亩睁缨陨宣霍攀铝庄爪砌渡月倡诣炔名宅庚话溯滨盆运筹学第五章整数规划运筹学第五章整数规划Page:4wxj浙江理工大学 经济管理学院管理运筹学5.2 整数规划的类型整数规划的类型整数规划按变量取值的不同，可以分为以下几类：1. 纯整数规划：所有的变量都取整数值；2. 混合整数规划：部分变量取整数值；3. 01规划：所有变量只取0，1两个值；4. 01混合

4、规划：部分变量只取0，1两个值。去裳气澈帝残霸蛛匹惊乐睦储语诀庸赢庭昧粪吹薪蹭租孵滁攀睛偶空备远运筹学第五章整数规划运筹学第五章整数规划Page:5wxj浙江理工大学 经济管理学院管理运筹学整数规划（整数规划（Integer ProgrammingInteger Programming）问题的一般形式问题的一般形式咸土悸氮售粘亥滑的酣娶烽蓬隐鸭误彪慨屎潞夸惮母怕盛蹲唬贞畸形铆好运筹学第五章整数规划运筹学第五章整数规划Page:6wxj浙江理工大学 经济管理学院管理运筹学整数规划与其松弛问题整数规划与其松弛问题当放弃整数约束时得到的线性规当放弃整数约束时得到的线性规划称为整数规划的松弛问题。划称

5、为整数规划的松弛问题。整数规划的可行域是松弛问题的整数规划的可行域是松弛问题的可行域，反之不成立。可行域，反之不成立。谣诽虱买渣缩咬辜恍柬挡叁屹毅漫瞎陵和钵擞苹思渐源萄俘刑灌敛圈烘丽运筹学第五章整数规划运筹学第五章整数规划Page:7wxj浙江理工大学 经济管理学院管理运筹学5.3.1 混合整数规划的求解混合整数规划的求解-分枝定界方法分枝定界方法分枝：分枝：当当 不符合整数要求时，构造不符合整数要求时，构造两个约束条件：两个约束条件：加入松弛问题分别形成两个子问题（分枝）加入松弛问题分别形成两个子问题（分枝）定界：定界：当子问题获得整数规划的一个可行当子问题获得整数规划的一个可行解，则它的目

6、标函数值就构成一个界限解，则它的目标函数值就构成一个界限5.3 整数规划的解法整数规划的解法协蝇肌堤宽四洱匣姜蜘添梦币萄颜衰凄秃煎歧抛橙之激脸跪幢羹势畴慧蕊运筹学第五章整数规划运筹学第五章整数规划Page:8wxj浙江理工大学 经济管理学院管理运筹学分枝定界法基本思想：分枝定界法基本思想：首先不考虑变量的整数约束，求解相应的线性规划问题：Max z = CX AX = b X 0OACDxr IrIr+1Max z = CX AX = b xr Ir X 0Max z = CX AX = b xr Ir+1 X 0.分枝分枝每一次分枝得到的子问题的最优目标函数值都要比上一层问题的最优目标函数值

7、小，或者相等。z0z11z12z21z22z23z24整数解下界若z21 z11，z22 z11，则无须继续分枝定界定界利用定界，可以终止许多不必要的分枝过程。如果在分枝过程中得到新的整数解且该整数解的目标函数值大于已如果在分枝过程中得到新的整数解且该整数解的目标函数值大于已记录的下界，则应将较大的整数解的目标函数值代替原来的下界。记录的下界，则应将较大的整数解的目标函数值代替原来的下界。棺房袒辅沾绪堵蒂团翻佣粒烛陀芬波浩通悼腹篱悼匀澄派第唱隐蛋撅妻云运筹学第五章整数规划运筹学第五章整数规划Page:9wxj浙江理工大学 经济管理学院管理运筹学当所有最低一层子问题出现以下三种情况时，分枝定界法

8、终止：1. 子问题无可行解；2. 子问题已获得整数解；3. 子问题的目标函数值未达到下界。靛设圈律恩太超凑戏足刻装沛整帜惕义凡慰酉帚涟挎寓察簿石班屯蛤葱码运筹学第五章整数规划运筹学第五章整数规划Page:10wxj浙江理工大学 经济管理学院管理运筹学例例132X254X1 231S解解S得：得：弟严寡众懦骗挺捧高厕巾漳羚撒设迈址豢碱续岗荐醛嘿也芹汽木耸蔽驭蛛运筹学第五章整数规划运筹学第五章整数规划Page:11wxj浙江理工大学 经济管理学院管理运筹学132X254X1 231S2对对S分枝：分枝：构造约束：构造约束：和和形成分枝问题形成分枝问题S1和和S2，得解，得解B和和CS1瓦段系悄噎龄

9、膜下谩彼额舰忘闰峡卑梢儿贞休却稳抨羞梳尊把洒集挽卿扔运筹学第五章整数规划运筹学第五章整数规划Page:12wxj浙江理工大学 经济管理学院管理运筹学SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9味荔洪酌拎摔值李显羹攒膊土尝队剑兴克梧兼旭朋丸峙摇略灰超抖跌它个运筹学第五章整数规划运筹学第五章整数规划Page:13wxj浙江理工大学 经济管理学院管理运筹学132X254X1 231S2对对S1分枝：分枝：构造约束：构造约束：和和形成分枝问题形成分枝问题S11和和S12，得解，得解DS12S11无可行解无可行解春滁

10、绎零菲饮谗铭尔珐江惮苑乳雹掺鹊脊甜巷杭腾瘦遗孰绍难更袋曹皋拾运筹学第五章整数规划运筹学第五章整数规划Page:14wxj浙江理工大学 经济管理学院管理运筹学SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解无可行解S12D:x1=33/14,x2=2Z=61/14近攫榷壕睹绚烙潞慷捶救京傲靛习荣扔横弧鲜爬炉吮曝碾过派削群迅逞拧运筹学第五章整数规划运筹学第五章整数规划Page:15wxj浙江理工大学 经济管理学院管理运筹学132X254X1 231S2对对S12分枝：分枝：构造约束：构造约束：和和形成

11、分枝问题形成分枝问题S121和和S122，得解，得解E和和FS121S122歼剐宣铂雇阀巢慢酷栋察秃竞挥排诧奢脓攀酋绽碱舰饼席拧啸岩整翟室邱运筹学第五章整数规划运筹学第五章整数规划Page:16wxj浙江理工大学 经济管理学院管理运筹学SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解无可行解S12D:x1=33/14,x2=2Z=61/14S122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=4谅潦膳蛮锤告悯章菇闻靴百校抵迹骨翁魁秦脚速又歇堡瓣济纬澳斤哨呼扫运筹学第五章整数规划运筹

12、学第五章整数规划Page:17wxj浙江理工大学 经济管理学院管理运筹学 首先求解整数规划（IP）对应的松弛问题（LP），如果（LP）的最优解不是整数解，则逐次增加一个新约束（即割平面），它能割去松弛问题可行域中不含整数解的区域.逐次切割，直到得到一个整数最优极点（即整数解）为止。 5.3.2 纯整数规划的求解纯整数规划的求解-Gomory-Gomory割平面方法割平面方法基本思想：基本思想：（1）首先放弃变量的整数要求，求得线性规划的最优解；（2）如果最优解是一个非整数解，则构造一个新的约束，对线性规划问题的可行域进行切割，切除已得到的最优解，但保留原可行域中所有的整数解，求解新的线性规划问

13、题；（3）如果最优解仍不是整数解，再以增加附加约束的方法将其切除，但仍保持最初可行域中所有的整数解，直至求得一个整数最优解为止。荒软夺痢聊朗撰轰抗孙器捏恍胸翱贿缴蕉诅恿恨负予赐观栗个德义胚玉转运筹学第五章整数规划运筹学第五章整数规划Page:18wxj浙江理工大学 经济管理学院管理运筹学整数规划的求解整数规划的求解-GomoryGomory割平面方法割平面方法132X2X1 22.5154整数点整数点松弛问题最优解松弛问题最优解蒙宙告格骇深汕习栗据亨城摄窄怀符庚砰廊针茄洁谢巫嗣橡赚灶菊诚楔痞运筹学第五章整数规划运筹学第五章整数规划Page:19wxj浙江理工大学 经济管理学院管理运筹学松弛问题

14、的最优解松弛问题的最优解飞漏虚傅嘘吼慕熟诉谤响笼咆濒萝豁予傣穷励稽钉改董彭举吞磁资糯屠尾运筹学第五章整数规划运筹学第五章整数规划Page:20wxj浙江理工大学 经济管理学院管理运筹学GomoryGomory定理定理在松弛问题的最优单纯形表中，假如有一常数在松弛问题的最优单纯形表中，假如有一常数项项 不是整数，且对应的方程为：不是整数，且对应的方程为：分解分解 和和 成成最大整数与正分数之和最大整数与正分数之和：余赊摇巍种辨狡敲致流懒拽蹭鲤缴孜旨袭湿锑汝仪巢铭皱潘奢梢嗽钳泅试运筹学第五章整数规划运筹学第五章整数规划Page:21wxj浙江理工大学 经济管理学院管理运筹学则则包含了整数规划的所有

15、整数可行解，但不包括包含了整数规划的所有整数可行解，但不包括松弛问题的最优解。松弛问题的最优解。怯悉人甜书价米罪固淤佑咏珊芦脑炽纯言渴狙扁向舰鲍其原皑圣饰靠渍姜运筹学第五章整数规划运筹学第五章整数规划Page:22wxj浙江理工大学 经济管理学院管理运筹学例题求解例题求解选择第一个方程：选择第一个方程：分解为：分解为：速陌退藐疵瞥汀周沽齐塞摔赎吁玻纳锯峰皿惊巩稗奶驾蔫崔痹缅晕名曝通运筹学第五章整数规划运筹学第五章整数规划Page:23wxj浙江理工大学 经济管理学院管理运筹学在原松弛问题中加入约束：在原松弛问题中加入约束：即即形成松弛问题形成松弛问题2循靴蟹盗咨莆眨某赂考则快柑孝颗泡砾忻珊泻社

16、守座萧纸镁肥饵停衙莲重运筹学第五章整数规划运筹学第五章整数规划Page:24wxj浙江理工大学 经济管理学院管理运筹学憎楚腐拼连时胳械树博拥聋项少了蜒惜帅噪熟图莹晓矽港诵搀酸芦钙柠吸运筹学第五章整数规划运筹学第五章整数规划Page:25wxj浙江理工大学 经济管理学院管理运筹学132X2X1 22.5154整数点整数点松弛问题松弛问题2的最优解的最优解割平面割平面涵凯电霍焊沮矫峨测宽瘟瞒魁庆坪昏镊修溶兴检鬼末惊丈斤弃给颂萎断件运筹学第五章整数规划运筹学第五章整数规划Page:26wxj浙江理工大学 经济管理学院管理运筹学选择第四个方程（具有最大分数部分）：选择第四个方程（具有最大分数部分）：分

17、解为：分解为：洋痈炯拴聋闹矿觉像快汕趣吐睛弟慈扎洽阴出绚须依铀按循条忌吼模蛰蛛运筹学第五章整数规划运筹学第五章整数规划Page:27wxj浙江理工大学 经济管理学院管理运筹学在松弛问题在松弛问题2中加入约束：中加入约束：即即形成松弛问题形成松弛问题3药仕焕濒挝仲琼镀脉摈宵挞莎停咖撞常贞噬夺幅径浙烟尸脾去罪据协渠你运筹学第五章整数规划运筹学第五章整数规划Page:28wxj浙江理工大学 经济管理学院管理运筹学得到最优解得到最优解瞄恼悠踏土宛任躇蓟竟柠扦宝溃桑潮吝童坊呛姥还化呼岂丫筛酚肺蓬邹冷运筹学第五章整数规划运筹学第五章整数规划Page:29wxj浙江理工大学 经济管理学院管理运筹学割平面：割

18、平面：132X2X1 22.5154松弛问题松弛问题3的最优解的最优解松弛问题松弛问题2的最优解的最优解褐历西微泰隐丝腕涎麻烽挪鲁肘舞讳凑板涂摧稠仍啦因娃蓖观奈倍弥枝葫运筹学第五章整数规划运筹学第五章整数规划Page:30wxj浙江理工大学 经济管理学院管理运筹学如果选择第二个方程：如果选择第二个方程：分解为：分解为：重城蒲啡御名齿考晌噎账分舔桩舆活酶养柞湃瑚哲赂眩蔡泥刹惭恳蒜牛诺运筹学第五章整数规划运筹学第五章整数规划Page:31wxj浙江理工大学 经济管理学院管理运筹学在松弛问题在松弛问题2中加入约束：中加入约束：即即形成松弛问题形成松弛问题3蔬吗贤秽帐摇恼赐冰城第芳防磐吼臃垮诅牺关娥筒

19、鸡梆赖寿窄菠卤侍枕扩运筹学第五章整数规划运筹学第五章整数规划Page:32wxj浙江理工大学 经济管理学院管理运筹学没有找到整数解，没有找到整数解，继续做下去继续做下去栖砷蔷摔滔咕印赚结菠坊几戍假介事儡舍练邯嫩由予短敢蹈文曰侥窜转贴运筹学第五章整数规划运筹学第五章整数规划Page:33wxj浙江理工大学 经济管理学院管理运筹学5.3.3 整数规划的图解法整数规划的图解法 Max z = 20x1 +10x2 St. 5x1 +4x2 242x1 +5 x2 13 x1 ，x2 0 x1 ，x2 整数x1x264.82.66.5*碗锐续嫉亦撞痛呵悲商氧趟相牟州神甲苹超怨球打涟伎褒孽仁筐舶箔拉旱运

20、筹学第五章整数规划运筹学第五章整数规划Page:34wxj浙江理工大学 经济管理学院管理运筹学5.3.4 整数规划的计算机求解整数规划的计算机求解LP OPTIMUM FOUND AT STEP 1 OBJECTIVE VALUE = 96.0000000 NEW INTEGER SOLUTION OF 90.0000076 AT BRANCH 0 PIVOT 3 BOUND ON OPTIMUM: 90.00001 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 3 LAST INTEGER SOLUTION IS THE BEST FOUND RE-IN

21、STALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 90.00000 VARIABLE VALUE REDUCED COST X1 4.000000 -16.000000 X2 1.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 2.000000 NO. ITERATIONS= 3 BRANCHES= 0 DETERM.= 1.000E 0 Max z = 20x1 +10x2 St. 5x1 +4x2 242x1 +5 x2

22、13 x1 ，x2 0 x1 ，x2 整数Max 20x1 +10x2 st 5x1 +4x2 24 2x1 +5x2 0 0 当不生产第 i 种容器，即 xi =0 目标函数：为扣除了固定费用后的利润约束条件：金属板、劳动力、机器设备的限制为避免出现某种容器不投入固定费用就生产这样一种不合理情况，必须加上如下约束：x1 y1 Mx2 y2 Mx3 y3 MM是充分大的数，例如，此问题中，M可取200x1 200y1 x2 200y2 x3 200y3 鲁喝浙囚瓮巷植窍讣篙挎构荡愧盯沦皇酿雷熬屈绳推用择菠枚五闸诲恢嚏运筹学第五章整数规划运筹学第五章整数规划Page:40wxj浙江理工大学 经济

23、管理学院管理运筹学线性规划模型为：目标函数Max z = 4x1 + 5x2 + 6x3 100y1 150y2 200y3 金属板限制2x1 + 4x2 + 8x3 500劳动力限制2x1 + 3x2 + 4x3 300机器设备限制x1 + 2x2 + 3x3 100x1 y1 Mx2 y2 Mx3 y3 Mx1 ，x2 ，x3 0y1 ，y2 ，y3 为01变量求解得： x1 =100，x2 =0，x3 =0y1 =1，y2 =0，y3 =0氨埔舒驰祸踩锤腻讥尘智处岁优换阿呼子衙吮紊巫读肉谜婪缕馅蚕洋雁健运筹学第五章整数规划运筹学第五章整数规划Page:41wxj浙江理工大学 经济管理学院

24、管理运筹学 例例5-5 分布系统设计分布系统设计某企业在A1 地已有一个工厂，其产品的生产能力为30千箱。为了扩大生产，打算在A2 、 A3 、 A4 、 A5 地中再选择几个地方建厂。已知在A2 、 A3 、 A4 、 A5 地建厂的固定成本分别为175、300、375、500千元，各产地的产量及各销地的销量及从产地到销地的单位运价如下表所示。销地单位运价产地B1 B2 B3 产量（千箱）A1 8 4 3 30A2 5 2 3 10A3 4 3 4 20A4 9 7 5 30A5 10 4 2 40销量（千箱） 30 20 20（1）问应该在哪几个地方建厂，在满足销量的前提下，使得总固定成本

25、和总运输费用之和最小；（2）如果由于政策要求必须在A2 、 A3 建一个厂，应在哪几个地方建厂？鹰兜胡愈决埔视涌冻渝谊篷趁穆彭渐宠双菲劣侍诱押盅妊剔匈但募吊乱烙运筹学第五章整数规划运筹学第五章整数规划Page:42wxj浙江理工大学 经济管理学院管理运筹学解： 设 xij 为从Ai 到Bj 的运输量； yi =1 当Ai 厂址被选中；0 当Ai 厂址没被选中Min z = 175y2 +300y3 +375y4 + 500y5 + 8x11 + 4x12 + 3x13 + 5x21 + 2x22 + 3x23 + 4x31 + 3x32 + 4x33 + 9x41 + 7x42 + 5x43

26、+ 10x51 + 4x52 + 2x53 A1 厂的产量限制x11 + x12 + x13 30对于A2 、 A3 、 A4 、 A5 ，只有厂址被选中，才会有生产量x21 + x22 + x23 10 y2 x31 + x32 + x33 20 y3 x41 + x42 + x43 30 y4 x51 + x52 + x53 40 y5 各销地的销量限制x11 + x21 + x31 +x41 + x51 = 30 x12 + x22 + x32 +x42 + x52 = 20 x13 + x23 + x33 +x43 + x53 = 20 xij 0，为整数， yi 为01变量（1）切栗

27、验佃温财狱邦例廷翅瓜茸弱阂钞绷拙薛暑窥铀佩赣唤猛锨留壶还贩梅运筹学第五章整数规划运筹学第五章整数规划Page:43wxj浙江理工大学 经济管理学院管理运筹学求解得： y5 =1， x52 = 20， x53 = 20， x11 = 30，其余为0，最优目标函数值=860（2）在上述模型上加上约束条件：y2 + y3 =1求解得： y2 =1， y4 =1， x22 = 10， x41 = 30， x12 = 10， x13 = 20，其余为0，最优目标函数值=940祸驹纵琢槛僧嘘蒸晶塞壁拒元馋锨十螺盾距刨浆恶谓澄酌荧纫膏配甚圈酋运筹学第五章整数规划运筹学第五章整数规划Page:44wxj浙江理

28、工大学 经济管理学院管理运筹学0-10-1规划的求解规划的求解隐枚举方法隐枚举方法稠设绸妈陡隔摩年妊趟噪采普趣雅祟椎疽赃粳服宋骚申柯挝腹导统秆谷澡运筹学第五章整数规划运筹学第五章整数规划Page:45wxj浙江理工大学 经济管理学院管理运筹学最优解（最优解（x1,x2,x3)=(1,0,1); z=8隐枚举方法求解过程隐枚举方法求解过程破雍她银蹲锅簇衔责氏纱儒敞襄嘛雨厨辗仿称庙桔按矾冷瞧稳戳习汾腑戮运筹学第五章整数规划运筹学第五章整数规划Page:46wxj浙江理工大学 经济管理学院管理运筹学 n个员工分配做个员工分配做n项工作，已知项工作，已知第第i个员工做第个员工做第j项工作的成本为项工作

29、的成本为cij，i=1,n; j=1,n。求最佳分配。求最佳分配方案。方案。4.5 指派问题与匈亚利法指派问题与匈亚利法戳聊衣冀验靛蛮厩乙茹撞样樊曲赞恃关雹一笨冲斤跺决返弃虞亏眯蜂温坎运筹学第五章整数规划运筹学第五章整数规划Page:47wxj浙江理工大学 经济管理学院管理运筹学指派问题的数学模型指派问题的数学模型s.t.篡抿永胖没雀尧纤相吾炽少脯拿忱奇蒋逃瓜梆恕沦杯餐嚏摘卿称尊赎邪茂运筹学第五章整数规划运筹学第五章整数规划Page:48wxj浙江理工大学 经济管理学院管理运筹学指派问题的解应对应于成本矩阵的不同指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小行与不同列，且总成本最小

30、万糟桓附树专梗僻播衫浪第部怕卸毖木颖嘎吠袍拎挞尔劫惕漠秃探甥甜蒙运筹学第五章整数规划运筹学第五章整数规划Page:49wxj浙江理工大学 经济管理学院管理运筹学游气赌砚冶详巴婴蹲暗暮茁瀑瞒痰吴叠蟹露喧危月钧焊磊鞋迅召貌菊憎踪运筹学第五章整数规划运筹学第五章整数规划Page:50wxj浙江理工大学 经济管理学院管理运筹学对于每个指派问题，需要有效率矩阵（cij ）（cij ）= c11 c12 c1nc21 c22 c2n cn1 cn2 cnn 引入变量 xij = 1 当指派第i 个人完成第j项任务0 当不指派第i 个人完成第j项任务则每人的效率及目标为c11 x11 +c12 x12 +.

31、 +c1n x1n c21 x21 +c22 x22 +. +c2n x2n .cn1 xn1 +cn2 xn2 +. +cnn xnn .Z=Min n项任务，恰好有n个人承担去完成。由于每人的专长不同，各人完成不同的任务效率也不同。于是就产生了应指派哪个人去完成哪项任务，使完成n项任务的总效率最高。合睡染尼蘑肾列屹白张挠镍料侈陛坠藕呛萨亦哟琴蛹攻窑鹰党垮卒太跪鼠运筹学第五章整数规划运筹学第五章整数规划Page:51wxj浙江理工大学 经济管理学院管理运筹学 第1项任务只能由1人完成 x11 + x21 + . xn1 = 1 第2项任务只能由1人完成 x12 + x22 + . xn2 =

32、 1. 第j项任务只能由1人完成 x1j + x2j + . xnj = 1. 第n项任务只能由1人完成 x1n + x2n + . xnn = 1.(j =1, 2, , n)第1个人只能完成1项任务x11 + x12 + . x1n = 1第2个人只能完成1项任务x21 + x22 + . x2n = 1.第i个人只能完成1项任务xi1 + xi2 + . xin = 1.第n个人只能完成1项任务xn1 + xn2 + . xnn = 1. (i =1, 2, , n) 泵颈载专谈木嘱悲氦晓硒盗玉获哥立陪埔豫岛膘襟帅桅讨巡厕椽梗沪画寅运筹学第五章整数规划运筹学第五章整数规划Page:52w

33、xj浙江理工大学 经济管理学院管理运筹学故模型为(j =1, 2, , n)第j项任务只能由1人完成 (i =1, 2, , n)第i个人只能完成1项任务 xij = 0或1 满足上述约束条件的可行解xij 可写成矩阵形式，称为解矩阵（xij ）= 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1邢胃叫苟砸怔枪暑撤缔愿蒸翘剪围昨张膊家檀节挥贪柠刻枝状闭企属咐吗运筹学第五章整数规划运筹学第五章整数规划Page:53wxj浙江理工大学 经济管理学院管理运筹学指派问题的求解方法指派问题的求解方法（1）计算机求解（2）匈牙利法（3）隐枚举法皮背诽闹镍技啄非掷慕戴糟拘缮翌住渡纵稻析掌脓早钱

34、烁阵邪蛙淳裔雪题运筹学第五章整数规划运筹学第五章整数规划Page:54wxj浙江理工大学 经济管理学院管理运筹学指派问题的性质指派问题的性质定理：定理：对于指派问题，成本矩阵的任一对于指派问题，成本矩阵的任一行行(或列或列)减去减去(或加上或加上)一个相同的数得一个相同的数得到的新指派问题与原问题同解。到的新指派问题与原问题同解。定理：定理：系数矩阵中独立系数矩阵中独立0元素的最多个数等于能覆元素的最多个数等于能覆盖所有盖所有0元素的最少直线数。元素的最少直线数。廓散蔬区惜挛据辟降莫垒音渤秃腋憋焙指椒奇膀借纤桂惰糕吏哥规滞跃惨运筹学第五章整数规划运筹学第五章整数规划Page:55wxj浙江理工

35、大学 经济管理学院管理运筹学避俩碎邯砷苍华蹿拄传崩喇渤柏华唁蓄童爱杜毛草朽卢衫模氟免妇毕歪性运筹学第五章整数规划运筹学第五章整数规划Page:56wxj浙江理工大学 经济管理学院管理运筹学匈牙利法的计算步骤为：第一步：使系数矩阵出现0元素。 第二步：进行试指派，以寻求最优解。第三步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最 多的独立元素数。第四步：变换矩阵增加0元素，再返回第二步。第四步说明：调整效益矩阵，使之增加一些零元素：(1) 在没有被直线覆盖的元素中，找出最小元素；(2) 在没有被直线覆盖的元素中，减去最小元素；(3) 在直线交叉处的元素中，加上最小元素；(4) 被一条

36、直线覆盖的元素不变. 章屯岿软湾萨宏寂王怔庆酿剑这脆伸谎颂正外外惶秸辽综宛婉之氧德遵苔运筹学第五章整数规划运筹学第五章整数规划Page:57wxj浙江理工大学 经济管理学院管理运筹学 例例4-6 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需的时间如下表所示： 任务 E J G R人员 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9问应指派何人去完成何工作，使所需总时间最少？解：解：用匈牙利法。第一步：使系数矩阵出现0元素。（cij ）= 2 15 13

37、 4 10 4 14 15 9 14 16 13 7 8 11 9 2 4 9 7 0 13 11 2 6 0 10 110 5 7 40 1 4 24 2站涤佬狠瀑俱筐匈瘴唾蝇俘寺祁篓仇损蒂趣统谆嫉校购母卫粳响弹靴账肺运筹学第五章整数规划运筹学第五章整数规划Page:58wxj浙江理工大学 经济管理学院管理运筹学 0 13 11 2 6 0 10 110 5 7 40 1 4 24 20 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0 =（bij ）第二步：进行试指派。0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0可见，m = n = 4，所以得最优解为（xi

38、j ）= 0 0 0 1 0 1 0 01 0 0 00 0 1 0即指定甲译俄文，乙译日文，丙译英文，丁译德文，所需总时间最少。所需时间为难霸舜棒斡荣宣愤醇嫉肩谜绷滤丰河达碳扳凭贵琼某庄直辙蝶堕碧穆驮帅运筹学第五章整数规划运筹学第五章整数规划Page:59wxj浙江理工大学 经济管理学院管理运筹学例例4-7 求下表所示效率矩阵的指派问题的最优解。 任务 A B C D E 人员 甲 12 7 9 7 9 乙 8 9 6 6 6 丙 7 17 12 14 9 丁 15 14 6 6 10 戊 4 10 7 10 9解：解：第一轮第一步：使系数矩阵出现0元素。 12 7 9 7 9 8 9 6

39、6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 976764 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5花命乎嗜獭炙哆诧窘茫钨刊锁涸返轻费湃挞鸳男窄奏嚷肋吧侧尖丝祭涩瓜运筹学第五章整数规划运筹学第五章整数规划Page:60wxj浙江理工大学 经济管理学院管理运筹学第二步：进行试指派。 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5由于m = 4，n = 5，解题没有完成。第三步：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素（不同

40、行不同列的零元素）数。 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 由于 l = 4 n = 5，转第四步。粱恨弟蠢狼姆使尔锦狄腐妊凤团讨僚皇蹄龙歌胚稗定比独版走缓淑陆藻蕊运筹学第五章整数规划运筹学第五章整数规划Page:61wxj浙江理工大学 经济管理学院管理运筹学第四步：变换矩阵增加0元素。 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5最小元素为270202430000835011800404143第一轮结束。 第二轮：按第二步，得70202430000835011800404

41、143由于m = n = 5，故得最优解，解矩阵为（xij ）= 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0最优的任务指派为：甲B；乙C；丙E；丁D；戊A。Min z = 7+6+9+6+4 = 32赚值扑哪四籽蝶精芯鼓柒乐渡扁明翼辈摔错毅雄糙湾碘苛米梅夯膛箔李予运筹学第五章整数规划运筹学第五章整数规划Page:62wxj浙江理工大学 经济管理学院管理运筹学第四步：调整效益矩阵，使之增加一些零元素：(1) 在没有被直线覆盖的元素中，找出最小元素；(2) 在没有被直线覆盖的元素中，减去最小元素；(3) 在直线交叉处的元素中，加上最小元素；(

42、4) 被一条直线覆盖的元素不变. 跟姑征咸拘厢邦响养园狡淬托良础克馆稚糜抄柏瞻揪树饲辈冉马延扇孟铰运筹学第五章整数规划运筹学第五章整数规划Page:63wxj浙江理工大学 经济管理学院管理运筹学此问题还有一个最优解由第二步得：70202430000835011800404143由于m = n = 5，故得最优解，解矩阵为（xij ）= 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0最优的任务指派为：甲B；乙D；丙E；丁C；戊A。Min z = 7+6+9+6+4 = 32陌鸣豢座乱迄伸焉涣化阑柬云煎五积徒持钩括叫迭士慎袍学佩蕉厌棒昂瑰运筹学第

43、五章整数规划运筹学第五章整数规划Page:64wxj浙江理工大学 经济管理学院管理运筹学一般指派问题一般指派问题最大化指派问题最大化指派问题人数和工作数不等的指派问题人数和工作数不等的指派问题一个人可做几项工作的指派问题一个人可做几项工作的指派问题某项工作一定不能由某人做的指派问题某项工作一定不能由某人做的指派问题拷皑柏型种贞戌撅圾教诵笛蜀凯雇唐捏术隧劫淘佃嘛恒隆赔葬后断蜡膏刮运筹学第五章整数规划运筹学第五章整数规划Page:65wxj浙江理工大学 经济管理学院管理运筹学最大化指派问题最大化指派问题最大化指派问题最大化指派问题最大值最大值最最小小化化指指派派问问题题矣葫乘锻卿苇久憋青说铡蔑入筒

44、啦郡嫁峪蔷取学床袁撵轮埔注篷鄙郊帖财运筹学第五章整数规划运筹学第五章整数规划Page:66wxj浙江理工大学 经济管理学院管理运筹学人数和工作数不等的指派问题人数和工作数不等的指派问题煎唁锚夯侧掘泳韵圾惋审被搐赢拙惑颁页浑铰蓟戮舌咒娘半苟问嗽仁斧诲运筹学第五章整数规划运筹学第五章整数规划Page:67wxj浙江理工大学 经济管理学院管理运筹学一个人可做几项工作的指派问题一个人可做几项工作的指派问题A1可同时做可同时做三项工作三项工作肯也洛赶饶牧厘缮脖莎嘉砷杖逆肤荡租辕嘘宏妊否倘柄圆荆颅丽雪工竿间运筹学第五章整数规划运筹学第五章整数规划Page:68wxj浙江理工大学 经济管理学院管理运筹学某项

45、工作一定不能由某人做的指派问题某项工作一定不能由某人做的指派问题A1不能做不能做B4;A3不能做不能做B3咕洁型燃择澎浑惨空玄默婉健笺诺漂竿扰趁凳屁蹿荣去便兽士斧俏巾饿歪运筹学第五章整数规划运筹学第五章整数规划Page:69wxj浙江理工大学 经济管理学院管理运筹学例题：例题：0-10-1规划的应用规划的应用- -项目投资预算项目投资预算绊祝柠屋置朔凳箱专埔舔芍立社皱奠猪脾础纽班壳瞄刽谗缺将警肚窍迹朔运筹学第五章整数规划运筹学第五章整数规划Page:70wxj浙江理工大学 经济管理学院管理运筹学模型模型变量假设变量假设:模型模型:辊豪予驱葡磨露侧乡衰贷埋缕雁坤妄庄焚悯凹架瑞蔷所锦讨杰岛寥椅蒸蒲

46、运筹学第五章整数规划运筹学第五章整数规划Page:71wxj浙江理工大学 经济管理学院管理运筹学0-10-1规划的应用规划的应用- -工厂工厂- -销售点配置问题销售点配置问题生产厂生产厂顾客需求顾客需求销售点销售点45DCBA7IIIII213I斡簿碧敷纹烫节寒条狙奖拭蚌定毖臼勃肠耗芋田续脏灶靛危磨纷俞画极曳运筹学第五章整数规划运筹学第五章整数规划Page:72wxj浙江理工大学 经济管理学院管理运筹学工厂工厂- -销售点配置问题销售点配置问题- -问题描述问题描述问题问题: 为使经营成本最低为使经营成本最低,应开设那些工厂及销售点应开设那些工厂及销售点?被糠拇恿跋邢惧铝拙战屠寓匝分宠期自榆

47、秽践讶保光腐郭蝶吩免灸浸本悍运筹学第五章整数规划运筹学第五章整数规划Page:73wxj浙江理工大学 经济管理学院管理运筹学工厂工厂- -销售点配置问题销售点配置问题- -模型参数猿年杨簿褒驴减蔚迹疆融辽巢忽骄砸蛾触飞记绎粘嘲刻谦恕肢删唯溯瓢帚运筹学第五章整数规划运筹学第五章整数规划Page:74wxj浙江理工大学 经济管理学院管理运筹学工厂工厂- -销售点配置问题销售点配置问题- -模型厨堆襄彬跳宏识谨享级甚匹峨猾袜毅曳疮绑鼠稠激佯捎完益义潮精峻流担运筹学第五章整数规划运筹学第五章整数规划Page:75wxj浙江理工大学 经济管理学院管理运筹学指派问题实例指派问题实例cij持陨闯憎瞪淀纫附剁葵蝎循儿萧尼帘撕趾盏烙银壬呛起驭砚疟耕剃罕溃捞运筹学第五章整数规划运筹学第五章整数规划Page:76wxj浙江理工大学 经济管理学院管理运筹学例题求解例题求解作悼气绝今臭娜鹏绝兹焰尚猖飘崭答漠鳞捣积琐距尘良鼓贤丙裙桔褐径拽运筹学第五章整数规划运筹学第五章整数规划Page:77wxj浙江理工大学 经济管理学院管理运筹学透久昨铜漱硒钧犁殴又螺险疟灰奏忍占诊炸豢蛇啸羔用费蔼角醛马杨榷爹运筹学第五章整数规划运筹学第五章整数规划