运筹学教学课件第三章运输问题.ppt
《运筹学教学课件第三章运输问题.ppt》由会员分享,可在线阅读,更多相关《运筹学教学课件第三章运输问题.ppt(111页珍藏版)》请在课桌文档上搜索。
1、1,第三章 运输问题,运输问题与有关概念运输问题的求解表上作业法运输问题应用建模,本章内容重点,搏范烤绩尸蔼咽萤轩彻滋狗葱潭附歌英贿氦蒜硅哼梅什绽席秋蹲寅大迁衣运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,2,1.运输问题模型及有关概念,问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地,在每个产地的供应量与每个销地的需求量已知,并知道各地之间的运输单价的前提下,如何确定一个使得总的运输费用最小的方案。,宫磷睡抽临净劳债朴詹蟹阉塞进辽刺嫩汛喜健剧伐否零儿藤宗弧积咒邪健运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,3,1.运输问题模
2、型及有关概念,例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?,愿革抖验骨钡缸误延剪魔钉意辖枕串怎畏帮扁模圆轩炯付饱消扬潮咨裂讶运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,4,解:产销平衡问题:总产量=总销量 设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表:,1.运输问题模型及有关概念,疼署跟蓑瓶优蹬爆邮常愧显咱赢泛丧缝静偏宏目权拄校永悦卢封血肇苍始运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,5,Min Z=
3、6x11+4x12+6x13+6x21+5x22+5x23,s.t.x11+x12+x13=200 x21+x22+x23=300 x11+x21=150 x12+x22=150 x13+x23=200 xij0(i=1,2;j=1,2,3),1.运输问题模型及有关概念,损咐瘪崎督浓楞洽序候竟钎绒咎多铁士楷送埃苇钒谦滑镊喜混允喊兔茅刃运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,6,1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1,系数矩阵,1.运输问题模型及有关概念,糖嗣咽携馏耸岗点啤幸珊懦秤传湃络要浇
4、啊肮鲤压拾医咙胸唉巧蚁患姐散运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,7,模型系数矩阵特征 1.共有m+n行,分别表示各产地和销地;mn列,分别表示各决策变量;2.每列只有两个 1,其余为 0,分别表示只有一个产地和一个销地被使用。,1.运输问题模型及有关概念,励仟猴讨滓搓梁碰遂收润晚啮列体遭疙彦晴辟焊人枕字帜扔抱烙疯橇莱夜运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,8,一般运输问题的线性规划模型及求解思路 一般运输问题的提法:假设 A1,A2,Am 表示某物资的m个产地;B1,B2,Bn 表示某物资的n个销地;ai表示产地 Ai 的产量;bj 表
5、示销地 Bj 的销量;cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价(表4-3)。如果 a1+a2+am=b1+b2+bn则称该运输问题为产销平衡问题;否则,称产销不平衡。首先讨论产销平衡问题。,1.运输问题模型及有关概念,剪伎醒摇馁课洱棍轿淬膝均谗娥抑糊肺喻嗓冕兢疟锹霜咋代拉筛拿乎劲儿运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,9,表4-3 运输问题数据表,1.运输问题模型及有关概念,设 xij 为从产地 Ai 运往销地 Bj 的运输量,根据这个运输问题的要求,可以建立运输变量表(表 4-4)。,狡歼纯患叭芥牟锯功噪两铅衍拦县剂淤巡并鬃晤正霄涂爸式疵盲懈淹裕
6、娜运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,10,表4-4 运输问题变量表,1.运输问题模型及有关概念,楚姻静傻布佰矩壶缨捍眨寡措卷费随家与憋诸丈诡襟硕尊丘暇猫瘟姓蓄闭运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,11,m nMin Z=cij xij(4-1)i=1 j=1 n s.t.xij ai i=1,2,m(4-2)j=1 m xij(=,)bj j=1,2,n(4-3)i=1 xij 0(i=1,2,m;j=1,2,n)(4-4),1.运输问题模型及有关概念,于是得到下列一般运输问题的模型:,在模型(4-1)(4-4)中,式(4-2)为
7、m 个产地的产量约束;式(4-3)为 n 个销地的销量约束。,亲哩剿嚼曳扯睬滦径展右署砾已诬裴赔洽舜夕扑渐题狂潭肮盗去宰四穷嵌运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,12,m n Min Z=cij xij i=1 j=1 n s.t.xij=ai i=1,2,m(4-5)j=1 m xij=bj j=1,2,n(4-6)i=1 xij0(i=1,2,m;j=1,2,n),1.运输问题模型及有关概念,对于产销平衡问题,可得到下列运输问题的模型:,辖谗龙希迈寡阔马忻打哪貉浑府渤院娇竣陛坏滴夫秆绚嘿辖杂徘庇赊洼止运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输
8、问题,13,在产销平衡问题中,仔细观察式(4-2)、(4-3)分别变为(4-5)、(4-6),约束条件成 为等式。在实际问题建模时,还会出现如下一 些变化:(1)有时目标函数求最大,如求利润最 大或营业额最大等;(2)当某些运输线路上的能力有限制时,模型中可直接加入(等式或不等式)约束;,1.运输问题模型及有关概念,呛碱烫鹰瓷幌掀抖喘鸭责筑表扁比转类恭乞叛霸土炳幻纷箩租社季萧脸搬运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,14,(3)产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资,这相当于在式(4-2)每一式中加上 1 个松弛变量,共 m 个;当产
9、量大于销量时可加入一个虚设的销地去消化多余的物资,这相当于在式(4-3)每一式中加上 1 个松弛变量,共 n 个。,1.运输问题模型及有关概念,涟超丢史染幻驰证胚乃志催蓖喂齿踌纽则园法缘翅梁梳剧娟试同采斥狡尔运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,15,运输问题是一种特殊的线性规划问题,在求解时依然可以采用单纯形法的思路,如图4-1所示。由于运输规划系数矩阵的特殊性,如果直接使用线性规划单纯形法求解计算,则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。在这里需要讨论基本可行解、检验数以及基的转换等问题。,1.运输问题模型及
10、有关概念,刮眩泰得率沛谷歌楔岳患谍疥型残鸵铂龙淋止三级褒虞缚痈蔑所金所贿贱运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,16,1.运输问题模型及有关概念,图4-1 运输问题的求解思路,恕双止疾摧探遵致影虹尚倍列荣眨柞嗣泞魂戍搬雕茨质依铂空匠痔侍输憨运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,17,运输问题求解的有关概念 考虑产销平衡问题,由于我们关心的量均在表4-3与表4-4中,因此考虑把表4-3与表4-4合成一个表,如下表4-5表4-5 运输问题求解作业数据表(下页),1.运输问题模型及有关概念,书融菌勃目往颈揣虐唾竹骗绷鳖闯患沥防温谗胡颧心须举瘴综
11、挫肝皮苑谆运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,18,1.运输问题模型及有关概念,彼睦祖疾踌剑刮嫁墓乱弘魂耘椿悉埃志泵椅现荤坎吉奇恩妮嗡狈跺蕾盛困运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,19,中任意m+n阶子式等于零,取第一行到m+n1行与对应的列(共m+n-1列)组成的m+n1阶子式,却捉钞忧辆雷沸滦涧净遭舔优氓寄爬荐陌练滞歹叼槽详镊指族给毛菱曙肠运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,20,故r(A)=m+n1所以运输问题有m+n1个基变量。,惜汉凹勃歹发企泄肉徘阑皆套死泻泻楔病狙系疡氮遣沮及雏会上湾迫孺火运筹
12、学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,21,运输问题的基变量共有 m+n-1 个,A的秩为 m+n-1。运输问题的 m+n-1 个变量构成基变量的充分必要条件是不含闭回路。重要概念:闭回路、闭回路的顶点,特点,运输问题基变量的,1.运输问题模型及有关概念,扇欺另鉴围宦患俞燥爬茨石谰蓬夺法苛行耗动册宵膝乎遇磷裳蹈吻斧合围运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,22,定义4.1 在表4-5的决策变量格中,凡是能够排列成下列形式的 xab,xac,xdc,xde,xst,xsb(4-7)或 xab,xcb,xcd,xed,xst,xat(4-8)其中
13、,a,d,s 各不相同;b,c,t 各不相同,我们称之为变量集合的一个闭回路,并将式(4-7)、式(4-8)中的变量称为这个闭回路的顶点。,为了说明这个特征,我们不加证明的给出一些概念和结论。下面的讨论建立在表4-5中决策变量格的基础上。,1.运输问题模型及有关概念,柞定淌伪蝉亭菲婚直姨磊卷淆孜踪梦镊雍界碱掩埂闲馆贵苏舷遗锹煎鹿肥运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,23,例如,x13,x16,x36,x34,x24,x23;x23,x53,x55,x45,x41,x21;x11,x14,x34,x31等都是闭回路。若把闭回路的各变量格看作节点,在表中可以画出如下形
14、式的闭回路:,1.运输问题模型及有关概念,栏墓模链窑伸棵昂卫韩征蹋蚕她霖局离窃作荡挛替姚暗剑赚拽南畔罚绞魏运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,24,根据定义可以看出闭回路的一些明显特点:(1)闭回路均为一封闭折线,它的每一条边,或为水平的,或为垂直的;(2)闭回路的每一条边(水平的或垂直的)均有且仅有两个闭回路的顶点(变量格)。,1.运输问题模型及有关概念,栓控翁浑甫仕更丁锰汕确坡哗跋为摇躺碴饲馏筒狰昆恢讲朋新适芒监蚂蔼运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,25,x23,x43,x11,x12,x25,x31,x42,表33,表33中闭
15、回路的变量集合是x11,x12,x42,x 43,x 23,x 25,x 35,x 31共有8个顶点,这8个顶点间用水平或垂直线段连接起来,组成一条封闭的回路。,出肝徐渊钥普捣盅抚避佛赚磷很致全萍班罪邢骸丙胆轿违冈剔矢炸卜呕抵运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,26,表34,一条回路中的顶点数一定是偶数,回路遇到顶点必须转90度与另一顶点连接,表33中的变量x 32及x33不是回闭路的顶点,只是连线的交点。,表34中闭回路是,例如变量组,A不能组成一条闭回路,但A中包含有闭回路,B的变量数是奇数,显然不是闭回路,也不含有闭回路;,褪醉购趴河堪孝奥龟阴郸丽辱熙阎贮犹
16、灌澄合聂槐恍瘤测扮蓝吝报固跑免运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,27,C是一条闭回路,若把C重新写成 就不难看出C仍是一条闭回路。,【定理1】若变量组B 包含有闭回路,则B中的变量对应的例向量线性相关。,【证】由线性代数知,向量组中部分向量组线性相关则该向量组线性相关,显然,将C中列向量分别乘以正负号线性组合后等于零,即,因而C中的列向量线性相关,所以B中列向量线性相关。,【定理2】若变量组 中包含一个部分组构成闭回路,那么该变量组所对应的系数列向量 线性相关。,破焕峡烘拿扛戏涩硷循频戚敝散红煮控润釜电凉甫巡屿连滇新德艳嫉烁娩运筹学教学课件-第三章 运输问题运筹
17、学教学课件-第三章 运输问题,28,定理3 变量组 xab,xcd,xef,xst 所对应的系数列向量pab,pcd,pef,pst 线性无关的充分必要条件是这个变量组中不包含闭回路。推论 产销平衡运输问题的 m+n-1 个变量构成基变量的充分必要条件是它不含闭回路。这个推论给出了运输问题基本解的重要性质,也为寻求基本可行解提供了依据。,这个推论告诉了一个求基变量的简单方法,同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的,不需要在系数矩阵A中去寻找,从而给运输问题求初始基可行解带来极大的方便。,炸韩鹊迹督卷层桩田打货非嘻冻殉尧萍衣层麓贤勇藤袒掉倾循牵羽睫
18、铂伏运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,29,例如,m=3,n=4,在运价表Cij的格子的右上方填上相应的xij,如表3-5所示。,表35,佬巡设缘台私淄橡孙骗驶长赂闭削膊涡柿姐夺各揍曙玖姨硼寺铂领团吐离运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,30,这个运输问题的基变量数目是3+41=6。变量组中有7个变量,显然不能构成一组基变量,又如中有6个变量,但包含有一条闭回路故不能构成一组基变量。变量组有6个变量且不含有任何闭回路,故可以构成此问题的一组基变量。,靶盼阉命鼠甄剂扣余汤慷娜掠杂株逐貌童简钠种峨两楔莲忙施篱转苯批绑运筹学教学课件-第三
19、章 运输问题运筹学教学课件-第三章 运输问题,31,2.运输问题求解 表上作业法,上一节已经分析了,对于产销平衡问题,我们关心的量均可以表示在表4-5中。因此可以建立基于表4-5的求解运输问题的方法表上作业法。这里求解运输问题的思想和单纯形法完全类似,即首先确定一个初始基本可行解,然后根据最优性判别准则来检查这个基本可行解是不是最优的。如果是则计算结束;如果不是,则进行换基,直至求出最优解为止。,卖想涉灸各效彪鸿能挝桃埋金侦冠烦莱凭厕采抢卡械治统副礼机厉码性敦运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,32,2.运输问题求解 表上作业法,一、初始基本可行解的确定 根据上面
20、的讨论,要求得运输问题的初始基本可行解,必须保证找到 m+n 1 个不构成闭回路的基变量。一般的方法步骤如下:(1)在运输问题求解作业数据表中任选一个单元格 xij(Ai 行 Bj 列交叉位置上的格),令 xij=min ai,bj,即从 Ai 向 Bj 运最大量(使行或列在允许的范围内尽量饱和,即使一个约 束方程得以满足),填入 xij 的相应位 置;,忿完耘建扮嗜驾辗猩敦讫仿污贿撮砾奉顽枷戍宜咬朔雕钵遥扇糯旅凹催锥运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,33,2.运输问题求解 表上作业法,(2)从 ai 或 bj 中分别减去 xij 的值,即调整 Ai 的拥有量及
21、 Bj 的需求量;,(3)若 ai=0,则划去对应的行(把拥有的量全部运走),若 bj=0 则划去对应的列(把需要的量全部运来),且每次只划去一行或一列(即每次要去掉且只去掉一个约束);(4)若运输平衡表中所有的行与列均被划去,则得到了一个初始基本可行解。否则在剩下的运输平衡表中选下一个变量,转(4)。,芥刮猿跃隙同惮艘蒙牵耘艰家机妹巡论旺拜阵对呵似忱宋朽锄靳廖放喳星运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,34,上述计算过程可用流程图描述如下(图4-2),吭市垮酿娩衣掉蝉龙骸漂囱混难掠殖宛碍椭贮助访滁杏阑怔添腋廉关浮窥运筹学教学课件-第三章 运输问题运筹学教学课件-第
22、三章 运输问题,35,2.运输问题求解 表上作业法,按照上述方法所产生的一组变量的取值将满足下面条件:(1)所得的变量均为非负,且变量总数恰好为 m+n 1 个;(2)所有的约束条件均得到满足;(3)所得的变量不构成闭回路。,因此,根据定理4.1及其推论,所得的解一定是运输问题的基本可行解。在上面的方法中,xij 的选取方法并没有给予限制,若采取不同的规则来选取 xij,则得到不同的方法,较常用的方法有西北角法和最小元素法。下面分别举例予以说明。,袜杉御扼盎壁宙两作幢洽闽族素铰晰品绕窖释胆秩畏汇眺欠拥惧蜂极赫泡运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,36,2.运输问题
23、求解 表上作业法,1、初始基本可行解的确定(1)西北角法:从西北角(左上角)格开始,在格内的右下角标上允许取得的最大数。然后按行(列)标下一格的数。若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去。如此进行下去,直至得到一个基本可行解。,农插丹滞驾毖钵电谬尤窝怖郁杠刚钢啪俞吩青脂展娥尸窃群霜英便曳芽鸿运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,37,例1:设有运输问题如下表所示,求其最优解。,腹偿充贴匠泄藩殖豆碴卉菜抢彦届通完侯荷益康枯琐抒琶雕港素份羚育纫运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,38,第一次,第二次,第三次,第四次,落
24、牌旬斟靠喀骨吾双耕鼠耀赤融转亚闰氟竟幽寥卖管诫诣碴陷易疑集目突运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,39,2.运输问题求解 表上作业法,(2)最小元素法:从运价最小的格开始,在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去。如此进行下去,直至得到一个基本可行解。,最小元素法的思想是就近优先运送,即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束,依次下去,直到最后一个初始基可行解。,掖著履劣势喝青韭曹崭痕馏纷宛鼎又凿粗尘裂迈愿瑰施瘪曹叛懈熄汪韶举运
25、筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,40,【例2】求表36所示的运输问题的初始基可行解。,表36,亮鸿衍场决愁梆税跪产券度甜么眷颠祸阅菌料献进茶挨恫莱卜炯奉猖遏手运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,41,0,0,0,【解】,30,15,10,25,20,15,45,20,20,0,0,0,产地,销地,稳奴站屑林盯蟹均咽北岿钎袍芬邮锦臻遁铬瘩粳蜗沉蛮芦朵盐额邢平椿魁运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,42,注:应用西北角法和最小元素法,每次填完数,都只划去一行或一列,只有最后一个元例外(同时划去一行和一列)。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 教学 课件 第三 运输 问题
链接地址:https://www.desk33.com/p-615237.html