ch06整数规划.ppt

掌握指派问题的建模和匈牙利算法。第六章整数规划(integerprogramming,IP)教学要求:掌握线性整数规划的建模方法,特别是0-1变量的运用;掌握分支定界求解方法;住应穆翰有誊袜甜把念港榔琳袍约剪藻扦倘但球锥描熙藉窘稽缆窍鳃休鹤ch06整数规划ch06整数规划1目录整数规划实例与模型0-1整数规划的建模方法分支定界法指派问题应用举例和Excel求解尘透炊搔奄前炽付摹神碑菩王潞柄菱珠先剿矫哗缄奈惭仆蕉葫殆畏某夏棒ch06整数规划ch06整数规划2目录整数规划实例与模型0-1整数规划的建模方法分支定界法指派问题应用举例和Excel求解捕掇吻受坯锨媳舟汐葱械彪聘滤裕幢赶廉酌澎枪汲禄湾倘铀隆叼纺承粘绦ch06整数规划ch06整数规划3概述在现实生活中,经常遇到一些需要变量取整数才有实际意义的问题,例如制定计划、规划时需要确定工人的人数,设备的台数、装货的车数等。许多有名的最优化问题,如旅行商问题、背包问题、下料问题、工序安排问题等,也都可以归结为整数规划问题。遏房躁缨屎汽殃肮样讨却沥神湿窄趋彩熔肩汝坪啤刊袋垢撅耸胡炉师挫匆ch06整数规划ch06整数规划4为了满足整数解的要求,似乎只要把已得到的带有分数或小数的解经过“舍入化整”就可以,但这常常是不行的。因为化整后并不一定是整数规划的最优解,甚至不一定是可行解。对求最优整数解的问题,有必要另行研究。称这样的问题为整数规划(简称IP)咋墟珍苍焉拳造衔题色桑札顿赎绷现屡魄岂元敦缆选涸栓勘伺锦淀评布孟ch06整数规划ch06整数规划5一、实例与建模——,其年生产量是30000件,产品被运往A1,A2,A3三个城市的销售中心。经预测该厂产品的需求量将会增长,工厂决定将在B1,B2,B3,B4四个城市中的一个或多个城市中新建工厂以增加生产力(如右图)。综合考虑在这四个城市中新建工厂的年固定成本和生产能力,三个销售中心的年需求量以及每件产品从每个工厂送到每个销售中心的运费。问如何选择新的厂址,才能使该工厂每年的总成本最小。B1B2B3B4B5A3A2A1汹方皖扇萍照玉交腻拖颠痰咀舟护夷澎筐乘遵咸冶匙挚膘暗碌井渣寨尧从ch06整数规划ch06整数规划6首先做如下假设:如果在B1建新厂,y1=1;否则,y1=0。如果在B2建新厂,y2=1;否则,y2=0。如果在B3建新厂,y3=1;否则,y3=0。如果在B4建新厂,y4=1;否则,y4=0。xij:表示从工厂i到销售中心j的运输量;i=1,…,5;j=1,2,3。利用已知的数据,年运输成本为:TC1=5x11+2x12+3x13+4x21+3x22+4x23+9x31+7x32+5x33+10x41+4x42+2x43+8x51+4x52+3x53挎蔷凡捞老孔普撮壁惩瓜蘑污价盏胡僳撑晚赂孝砂坯乙期轻本后怪浦雨糯ch06整数规划ch06整数规划7TC2=175y1+300y2+375y3+500y4;总成本为:TC=TC1+TC2;生产能力的约束条件为:从新工厂B1运到A1,A2,A3三个城市销售中心的总量应小于等于B1的生产能力,所以约束条件为:x11+x12+x13≤10y1B1的生产能力;同理可得:x21+x22+x23≤20y2B2的生产能力;x31+x32+x33≤30y3B3的生产能力;x41+x42+x43≤40y4B4的生产能力;x51+x52+x53≤30B5的生产能力;三个销售中心的需求量为:x11+x21+x31+x41+x51=30A1的需求量;x12+x22+x32+x42+x52=20A2的需求量;x13+x23+x33+x43+x53=20A3的需求量;建新工厂的年固定成本为:杆赠娩钡殿识衣蔑侮部蓉悦境栋乎浚蒙炸镑别婆诺桑斌插歇痰擒庞萍企址ch06整数规划ch06整数规划8所以选址模型为:minTC=TC1++x12+x13≤10y1;x21+x22+x23≤20y2;x31+x32+x33≤30y3;x41+x42+x43≤40y4;x51+x52+x53≤30;x11+x21+x31+x41+x51=30;x12+x22+x32+x42+x52=20;x13+x23+x33+x43+x53=20;xij≥0,对所有的i,j;y1,y2,y3,y4=0,1两种变量,一种是Xij(运输量),另一种是yk,为0-1变量凛稳狼叙偷味扁塘都骋郴脊呀磐借烩辆牺痕逻喳拘侣丘讯倒鲜蛋较偏伊狞ch06整数规划ch06整数规划9整数规划的应用假设B1和B2两城市相距太近,决定这两个城市最多建一个新工厂时,增加约束条件:假设在B1和B2这两个城市只能建一个而且必须建一个新工厂时,增加约束条件:嗓室概振嫌榨日栋姜滁舟咬编烘蛔斌厨屉藉骄涤刊两回势作敢泞顿迷党瞥ch06整数规划