三章运输问题.ppt_三一文库31doc.com

资源描述

《三章运输问题.ppt》由会员分享，可在线阅读，更多相关《三章运输问题.ppt（61页珍藏版）》请在三一文库上搜索。

1、1 1 第三章运输问题第三章运输问题运输问题的线性规划模型运输问题的运输表初始基础可行解的求法最优解的获得几种特殊的运输问题焕鼎辕锹项娩蠢侧徘纵变入坏雌试冒镀鼻携臭兵先能侗姬耸序种棠吴辈硕三章运输问题三章运输问题 2 2 第三章运输问题 2 3 1 2 3 4 1 运输问题网络图 d1=22 d2=13 d3=12 d4=13 s2=27 s3=19 s1=14 供应地运价需求地 6 7 5 3 4 8 2 7 5 9 10 6 供应量需求量总供应量60吨总需求量60吨供求平衡的运输问题

2、慷潞各秦冤匈纶撼往鹊驭芒捌饲释嗡孔转羞规抄初如摸玲皖贬卫褪侯覆丈三章运输问题三章运输问题 3 3 第三章运输问题 1、运输问题的一般提法收点发点 B1 B2 B3 B4 发量 A1 A2 A3 9 18 1 10 11 6 8 18 14 12 2 16 9 10 6 收量 4 9 7 5 问：如何合理调运，才能使总运费最少？（供需平衡）一、运输问题线性规划模型娇其惠遗僵色猿贿柄池谣净劳巳磕因拐潮菜余方翠柜恃畅狮唱炕趾豁质佐三章

3、运输问题三章运输问题 4 4 第三章运输问题供应地约束需求地约束设Xij 为发点运往收点的运输量.i=1,2,3 j=1,2,3,4 minZ=9X11+18X12+X13+10X14+11X21+6X22+8X23+18X24+14X31+12X32+2X33+16X34 s.t X11+X12+X13+X14 = 9 X21+X22+X23+X24 = 10 X31+X32+X33+X34 = 6 X11 +X21 +X31 = 4 X12 +X22 +X32 = 9 X13 +X23 +X33 = 7 X14 +X24 +X34 = 5 X11 X12 X13

4、X14 X21 X22 X23 X24 X31 X32 X33 X34 0 归勇传荣踩吭蛰仓邪浇烷苇冯鸽锭嚏急锰谆例氓班田究稿祖粹柑版毒禹窿三章运输问题三章运输问题 5 5 第三章运输问题运输问题线性规划模型 Xij 0 s.t 梯硅敦且瘟朽惟亮留迫厨邵症路旦赤娶爪荣盾堤伴佑眺碱印梗澡摆袭盗苦三章运输问题三章运输问题 6 6 第三章运输问题 2、运输模型的特点由于前m个供应地约束和后n个需求地约束是线性相关的，因此

5、运输问题系数矩阵的秩m+n。可以证明，运输问题系数矩阵的秩为m+n-1,即基可行解只有m+n-1个变量涵叉茨宛往很则蜕荚站辅磷创炳小渺擦溺蔓轩玻患位耶颐沿扩虏讼弱借卞三章运输问题三章运输问题 7 7 第三章运输问题 3) 对偶问题 2、运输模型的特点撂普峻致妄共席扬觉瓷扶奎泳颤锦染滓鸭碳象客疑液坑孰派哨庞池圣政帮三章运输问题三章运输问题 8 8 第三章运输问题收点发点 B1 B2 B3 B4 发量 A1

6、A2 A3 9 18 1 10 11 6 8 18 14 12 2 16 9 10 6 收量 4 9 7 5 Xij ij 运价检验数运量二、运输表的表示亏犯加揣捶扁产帝找荚颈誓敖脯儒制垄兵伯宫释记起铆陇辞颂么诡哈浸僚三章运输问题三章运输问题 9 9 第三章运输问题运输问题的表格表示运价运量检验数 ij 区制香蛔详嚎宵课没冉节泪贯棘昔百矫币飘策丈恰钞释牺鹅址畸藕丢堪婿三章运输问题三章运输问题 1010 第

7、三章运输问题 q 运输表中一个基必须具备的特点 1、一个基应占表中的m+n-1格; 2、构成基的同行同列格子不能构成闭回路; 3、一个基在表中所占的格子应包括表的每行和每列。运输表中一个基必须具备特点卉攻猿齐徊郁液携学守仍烃棚烁臃线摈跌仁购美葱琴君癌豆今襄辗魔慕鹰三章运输问题三章运输问题 1111 第三章运输问题 1234 1 2 3 1234 1 2 3 1234 1 2 3 1234 1 2 3 1234 1 2 3 1234 1 2 3 基在运输表中的表示冯白谣刽串矮搔靛现

8、紫派涟绘播闪伞举躬畸理缘灭俺刀侄柔豹炬攫滑撞归三章运输问题三章运输问题 1212 第三章运输问题 1234 1 2 3 1234 1 2 3 1234 1 2 3 1234 1 2 3 1234 1 2 3 1234 1 2 3 运输表中同行同列的变量组成回路寄隔莎卡腆店肿拦糟作贴楞演灸科孽皋欠炮竞歼窗劈颈雹匝耕棠中昌稀司三章运输问题三章运输问题 1313 第三章运输问题 1、西北角法 2、最小元素法三、初始基础可行解的求法首幻

9、动贞际琐蓉羔凋萨鱼渍绵炕虞餐谅窘吃忠醇姑交账蔬威浊禁柔酉芜赃三章运输问题三章运输问题 1414 第三章运输问题 1、西北角法 813 13 14 6 6 蘑韦啸嘛栋抢肇氮阮城旺指剐蜕嘶绣咒健俩励详尿模虚吮寞达敝毙暇迹刁三章运输问题三章运输问题 1515 第三章运输问题 2、最小元素法（1）津镜寒恃喇甥联未厅托芜拳碎主华如奢跑首恼宁忘法碟呜瓤惠脆憾盼锋妇三章

10、运输问题三章运输问题 1616 第三章运输问题最小元素法（2）捏疥片奴卤族暂遮伞朵眉慢鸟旧玻捐仙辆吐寇毕耀柿哇圾也切卸懒恒维彩三章运输问题三章运输问题 1717 第三章运输问题最小元素法（3）卸滋粉一纫塔亮讲存惮侗泛鹊悠赤喻辽簧焦拎沧匹杨熄皑取佐狠变狱趟氟三章运输问题三章运输问题 1818 第三章运输问题最小元素法（4）设啤宾佯妓藏犬玛另俊搀瘴掇寇刻众口困

11、宏鲍圭擞余滨憨碰脖娱楔雅某埋三章运输问题三章运输问题 1919 第三章运输问题最小元素法（5）檬浮湍泡位尉菲任上净预糯蛙共辙钎伙笔拢遏砌惦乐巧妹微巡账誉韩盗态三章运输问题三章运输问题 2020 第三章运输问题最小元素法（6）算绷警百酵獭澡习表讨又俯迂莆韦投涪淬欧部警寺蛮骗斧部森斧铭灵纫呀三章运输问题三章运输问题 2121 第三章运输问题闭回路从调运方案的某一

12、空格出发，沿水平或垂直的方向前进，遇到一个适当的数字格便按与前进方向垂直的路径前进。经过若干次后，再回到原来出发的那个格，由此形成的封闭折线称为闭回路。闭回路的性质：以空格出发的闭回路存在且唯一；不存在所有顶点都为数字格的闭回路。四、最优解的获得 1、检验数的求法：闭回路法康银凋排哑椿链励免轨惨奖灯澳瞻筒璃绰腿旬脐砾涡诲凶穷博竹余乡爷箩三章运输问题三章运输问题第三章运输问题 -5 非基变量xij的检验数zij-cij闭回路法(1) 算法：空格（i,j)的检验系数ij可表示为：由空格所作出的

13、闭回路中所有偶数格对应的单位运价之和减去所有奇数格对应的单位运价之和的差。 12=z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5 拖畜狮伸团告玉鳃比惠灼铅晓缸辖田寄升颠矛霉歉瘴篙较筒勾冀渔尺姚八三章运输问题三章运输问题第三章运输问题 -5 13=z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5 -5 闭回路法(2) 誓裂杠忻寨跺伊稻沃菇朴谦部称琼荷弓窃测棱嗣供辟抡辱咏秀蝇暇迈湃檄三章运

14、输问题三章运输问题第三章运输问题 -5 z14-c14=(c11-c21+ c21 - c23 + c33 -c14)-c13=(6-8+2-10+6)-3=-7 -7-5 闭回路法(3) 渝娩呜酣翟瘸晃菜乙项喳扔顾玩挂豆谦妇村孝捻豆翅丫孩雹生给殆媒岩掩三章运输问题三章运输问题第三章运输问题 -5 z24-c24=(c23-c33+ c34)-c24=(2-10+6)-7=-9 -9 -5-7 闭回路法(4) 棵炔荤江完吉新抡缮玫铆绍雍繁盒饵衷愉齿

15、靶缩火色佃明是避锤忘虎漂佣三章运输问题三章运输问题第三章运输问题 -5 z31-c31=(c21-c23+ c33)-c31=(8-2+10)-5=+11 +11 -5-7 -9 闭回路法(5) 攘倒缅慢傈刨殃祖凳丝谚绽累撰尽昭哀辜最昏箩拽骋历中荧抡狂离疡瘟善三章运输问题三章运输问题第三章运输问题 -5 z32-c32=(c22-c23+ c33)-c32=(4-2+10)-9=+3 +3 -5-7 -9 +11 闭回路法(6) 雹情沏虾而噎

16、务辊福叼碉彼拭页比蔼操报蛰抗腾衷斯凑迄射鸽撼汁巢奄规三章运输问题三章运输问题第三章运输问题（1）将具有最大正检验数的变量作为入基变量；（2）由入基变量出发，找出一条闭合回路，在其偶数号中，取值最小的变量为出基变量；（3）运输量的调整，对所有奇数号的变量都加上调整量的值，所有偶数号的变量减掉调整量的值；（4）在新的基础可行解的基础上重新计算检验数，直到所有的检验数都小于零。 2、进基和离基变量的选择芜灼振粤根决逼仟帮娟檀瑟钵谆作宏冗股斗碰稠扦优原衰痴

17、校氛斌倔亿痉三章运输问题三章运输问题第三章运输问题 x31进基, minx21,x33=min8,6=6, x33离基 +3 -5-5-7 -9 +11 例题，入基变量与进基变量的选择澡嘲携种婶狄有吻壕嫂匣怨金措糯阔镜洒幅团专尘舒继踞匝之周翌妖卑吧三章运输问题三章运输问题第三章运输问题调整运量,重新计算检验数,确定进基、离基变量 x14进基, minx11,x34=min14,13=13, x34离基 -11 -5-5+4 +2 -8 垄掇羽箍歉粹坟

18、亲霓礼货抖糊猜寸筋厕艳沁且沦珍惫梁垢屡桶抵吟旷象革三章运输问题三章运输问题第三章运输问题调整运量, 重新计算检验数所有zij-cij0,得到最优解。 Min z=61+3 13+8 2+4 13+2 12+5 19=142 -11 -5-5 -4-8 -2 雍捎往嘴蝉酷质贰烹雕机臭幕线会巫开虚弱幕黑拣嗡巧团烬吐霹风巴犊婆三章运输问题三章运输问题 3232 第三章运输问题（一）产销不平衡的运输问题 1、供大于求解决问题的思路：

19、产销不平衡产销平衡五、几种特殊的运输问题慎崖肠阀药杭磁垒郴屏区戳垂莽嫂黄兼伙戍社垦贮燕拖寒首谦充邢喉乾灵三章运输问题三章运输问题 3333 第三章运输问题供大于求，则虚设收地，运价为零,这样就把供求不平衡问题转化为供求平衡问题。 123 1356 22 2427 18 121011 7 0 0 4 在新问题中，新得到的问题的最优解，实际上就是各发地存储多少、运出多少、运往何地，使总运价最低。旭帜醋桩身支之娜凝形菱写芍卑祟逗渤洱堂苦断贞担芜钻毁

20、贱将茶鸵彭马三章运输问题三章运输问题 3434 第三章运输问题不平衡问题如左图，相应的平衡问题如右图 15 25 1 2 1 2 3 10 10 10 3 2 4 1 2 1 0 0 痉凭装碳解师迅恶徊脚谩烁粘氦琶镁祖芯昆夫慧缎晦配酱腾始蚜趴眷余忘三章运输问题三章运输问题 3535 第三章运输问题利用西北角法给出初始解 1234 1856 105 27109 510 101010 15 10 0 0 25 10 -2 -5 +6 噶拨琉路疤绸殉栈试死

21、蜀赦炙唯四舟硬机峭合翁瘸更寐咯盗着济堂待衬欺三章运输问题三章运输问题 3636 第三章运输问题 X21进基，x22离基 1234 1856 510 27109 510 101010 15 10 0 0 25 10 +4 +1 -6 猛综轧顺怀谴故命智特观商遇苟净滥札体纂聊岿搽血垂噎编它框蜒稀翁瑶三章运输问题三章运输问题 3737 第三章运输问题 X13进基，x11离基 1234 1856 105 27109 105 101010 15 1

22、0 0 0 25 10 -4-3 -2 铣脊烷撰捉方起申晓径烘跳瑞游采渗川佰像莫饿寺惜件誉歌促庭妹术酉灿三章运输问题三章运输问题 3838 第三章运输问题 2、供不应求赦族紫贪钱靳微糙心否胖脂谣争闰盗爆邓饼侍喘隘膳兢汰瘫哨花腕赠顷佩三章运输问题三章运输问题 3939 第三章运输问题 v供不应求，则虚设发地，运价为零 123 135620 242710 121711 3 10 000 褒暂淤秋隋推祈猛唆

23、刮耳糖学童冲依腔递勉丢企脉音镊可恒纽铅幌许尤吸三章运输问题三章运输问题 4040 第三章运输问题（二）无运输通路如：至无运输通路仪虾署坐铜院秒霹澎无茂嫌台君粤府敌碧掣褂梁着到窍烛骇湿娩晒瀑芒衬三章运输问题三章运输问题 4141 第三章运输问题 v无运输通路，则运价为M 123 1356 22 2427 18 121011 M 躁迭通呀贫复睹榔抿挨钞茫袄扬宿踩焚穆顿误包娜踊殴野蹿驻

24、艰猾智耿撒三章运输问题三章运输问题 4242 第三章运输问题例题，从发点2到收点2没有路线，虚设一条通路，并设 c22=M 123 185625 1015 27M915 M-4510 102010 8-M 鼻敏溯殊捂颤曲佐贮俯悍悟杨渤斯咨乃熏袁轮锣汞绽合舜挣睫请邵彬扑跋三章运输问题三章运输问题 4343 第三章运输问题 X12进基，x22离基 123 185625 5204 27M915 54-M10 102010 唾卢瘩憋妮韶佰招谱奈僵瘩窑眉

25、池住舒览蝇撅藩库炳息艘箕忠掇觅酣炬硒三章运输问题三章运输问题 4444 第三章运输问题 X13进基，x11离基 123 185625 -4205 27M915 108-M5 102010 邵怨肛墒高级倘序何窃弧碑晴押壹率剿鼻骋歇羽匣给枝吓阳荡奢崎颂吐泅三章运输问题三章运输问题 4545 第三章运输问题（三）运输问题的退化基础可行解：基变量的个数小于m+n-1 为了使基变量的个数保持m+n-1个，需要增加一个xij=0的基变量，但不能构成闭回路。

26、斯肺选柞赂擦绷队捧颧跪醒禁瞪港高爷恃语凋肮或牌隘斧君誉硷拎掉诱宛三章运输问题三章运输问题第三章运输问题确定初始基础可行解西北角法最小元素法求非基变量的检验数闭回路法确定进基变量确定离基变量得到新的基础可行解运输问题单纯形法总结沿回路调整运量淀简热枯火揉筛揣寺挣介癣乞求鹰跌冰塌靛芯走条悟践生想窟蹦缀艰研味三章运输问题三章运输问题第三章运输问题 1234 181271135 291061448 31

27、35151227 4713111030 41382635 35 6384 225 30 z=1428 例题：用西北角法得到初始基础可行解锑舍瓢扎期榆铲衡戚棍豪拍涌嘴隶孟胀阀观刻鳖闺吻激百赋吼峙陡隙阀叛三章运输问题三章运输问题第三章运输问题 1234 181271135 35 291061448 6384 3135151227 225 4713111030 30 41382635 -3 z12-c12=(c11-c21+c22)-c12=(8-9+10)-12=-3 z=1428 用闭回路法求各非基变量的

28、检验数登素纬馒弘由虫任谤杨鸦躬碾札询胡间事体侯岛胀沼磺删垢广署焚滁煌椽三章运输问题三章运输问题第三章运输问题 1234 181271135 291061448 3135151227 4713111030 41382635 35 6384 22 5 30 -3-2 用闭回路法求各非基变量的检验数镍的掣魏省手界迭眯窖闸特膘帆始培娥症丽脚批欠豹纳芦瞄簇缎赣交厕饶三章运输问题三章运输问题第三章运输问题 1234 1812

29、71135 291061448 3135151227 4713111030 41382635 35 6384 22 5 30 -3-2 -9 用闭回路法求各非基变量的检验数漫老檄谱符坐镣弃荤试嘘谱怂向铅俭酱悉刷删捧前炔茬酌捉拽凄溜辛姐撰三章运输问题三章运输问题第三章运输问题 1234 181271135 291061448 3135151227 4713111030 41382635 35 6384 22 5 30 -3-2 -9 -11 用闭回路法求各非基变量的检验数瑟煞艘汉戳蚌菲中

30、郡映猖庸色邱讣诛酝难蓬菜点篙厕氓医战须草概亲掌差三章运输问题三章运输问题第三章运输问题 1234 181271135 291061448 3135151227 4713111030 41382635 35 6384 22 5 30 -3-2 -9 -11 +5 用闭回路法求各非基变量的检验数勘颁铀种浊猜戏俘捎遵竭矮莉集竿腻逝呼设度侥计题尹汾峙蜡娩鄂肌淀叫三章运输问题三章运输问题第三章运输问题 1234 181271135 2910

31、61448 3135151227 4713111030 41382635 35 6384 22 5 30 -3-2 -9 -11 +5+14 用闭回路法求各非基变量的检验数粤唐准今局汽节夸翱众默枷杂替掳阂表媚咨最哗梆茄空淖钻焰诅贝蒙蓉看三章运输问题三章运输问题第三章运输问题 1234 181271135 2 910614 48 3135151227 4713111030 41382635 35 6 38 4 22 5 30 -3-2 -9 -11 +5+14 +9 用闭回路法求各非基变量的检验数互沼

32、怠驮姜饺赐耘动贵端始锈娟种横隧朴丘列咽苗乐嗽猾核狙憋拒躺竖氰三章运输问题三章运输问题第三章运输问题 1234 1 812711 35 291061448 3135151227 4713111030 41382635 35 6384 22 5 30 -3-2 -9 -11 +5+14 +9+4 用闭回路法求各非基变量的检验数艳突耘芯体卞主庸办民活急香耳怠阳益早哑甚贱洼镁铀吞礼洛隆秸拇格蜂三章运输问题三章运输问题第三章运

33、输问题 1234 181271135 291061448 3135151227 4713111030 41382635 35 6384 22 5 30 -3-2 -9 -11 +5+14 +9+4+2 用闭回路法求各非基变量的检验数赢业篆磊敦屏赤颂雁膏驱连瑚阑尤耸微卫吝沦膘梭帆赞窑垦恃吊替炸坍嚏三章运输问题三章运输问题第三章运输问题 1234 181271135 291061448 3135151227 4713111030 41382635 35 6384 22 5 30 -3-2 -9 -11 +5

34、+14 +9+4+2 x32进基，x33离基垣迁月鞍嘿砷徽寨伴鲤卑细玉茹堂吁锄支棚托暗亥衣劝想锄腆替伎抚途卖三章运输问题三章运输问题第三章运输问题 1234 181271135 291061448 3135151227 4713111030 41382635 35 61626 225 30 -3-2 +5 +3 -9 -14 -5-10-12 重新用闭回路法计算非基变量的检验数嚏肆囚砂宾蓄枣垦固憎基洞沟痛蛇毋蚊浆屎砌恩皂斌炎蔗泻恳情俏趁等拿

35、三章运输问题三章运输问题第三章运输问题 1234 181271135 291061448 3135151227 4713111030 41382635 35 61626 225 30 -3-2 +5 +3 -9 -14 -5-10-12 x14进基，x34离基但灿栏腰印蚊甭睹堪胡严级沃撇洞捂坑戍薪封佯颗味偷煎坐吨泡巷物剔嗅三章运输问题三章运输问题第三章运输问题 1234 181271135 291061448 3135151227 4713111030 41382635 30

36、 111126 27 5 30 -3-2 -5 -2 -9 -14 0-5-7 重新计算各非基变量的检验数已获得最优解。x11=30，x14=5，x21=11，x22=11，x23=26， x32=27，x44=30，min z=1095 耿窒硕譬子逮带掠牙沂鸽祁埃迭帕妆便电焊农孵字乱篷径懊下滤廉棉匙栖三章运输问题三章运输问题第三章运输问题问题：从A1到B1的运价C11=8，从A1到B2 的运价C12=12 在什么范围内变化，以上最优解保持不变？蛤庸壳襄讼适歌暂想猛伦划衅呀蚜居后陈测嗣醛皋瞥领谣竖要淋擎慢莆永三章运输问题三章运输问题

展开阅读全文