运筹学教学课件第三章运输问题.ppt

1,第三章 运输问题,运输问题与有关概念运输问题的求解表上作业法运输问题应用建模,本章内容重点,搏范烤绩尸蔼咽萤轩彻滋狗葱潭附歌英贿氦蒜硅哼梅什绽席秋蹲寅大迁衣运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,2,1.运输问题模型及有关概念,问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。,宫磷睡抽临净劳债朴詹蟹阉塞进辽刺嫩汛喜健剧伐否零儿藤宗弧积咒邪健运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,3,1.运输问题模型及有关概念,例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,愿革抖验骨钡缸误延剪魔钉意辖枕串怎畏帮扁模圆轩炯付饱消扬潮咨裂讶运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,4,解：产销平衡问题：总产量=总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：,1.运输问题模型及有关概念,疼署跟蓑瓶优蹬爆邮常愧显咱赢泛丧缝静偏宏目权拄校永悦卢封血肇苍始运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,5,Min Z=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.运输问题模型及有关概念,糖嗣咽携馏耸岗点啤幸珊懦秤传湃络要浇啊肮鲤压拾医咙胸唉巧蚁患姐散运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,7,模型系数矩阵特征 1.共有m+n行，分别表示各产地和销地；mn列，分别表示各决策变量；2.每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用。,1.运输问题模型及有关概念,励仟猴讨滓搓梁碰遂收润晚啮列体遭疙彦晴辟焊人枕字帜扔抱烙疯橇莱夜运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,8,一般运输问题的线性规划模型及求解思路 一般运输问题的提法：假设 A1,A2,Am 表示某物资的m个产地；B1,B2,Bn 表示某物资的n个销地；ai表示产地 Ai 的产量；bj 表示销地 Bj 的销量；cij 表示把物资从产地 Ai 运往销地 Bj 的单位运价（表4-3）。如果 a1+a2+am=b1+b2+bn则称该运输问题为产销平衡问题；否则，称产销不平衡。首先讨论产销平衡问题。,1.运输问题模型及有关概念,剪伎醒摇馁课洱棍轿淬膝均谗娥抑糊肺喻嗓冕兢疟锹霜咋代拉筛拿乎劲儿运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,9,表4-3 运输问题数据表,1.运输问题模型及有关概念,设 xij 为从产地 Ai 运往销地 Bj 的运输量，根据这个运输问题的要求，可以建立运输变量表（表 4-4）。,狡歼纯患叭芥牟锯功噪两铅衍拦县剂淤巡并鬃晤正霄涂爸式疵盲懈淹裕娜运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,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）为 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.运输问题模型及有关概念,对于产销平衡问题，可得到下列运输问题的模型：,辖谗龙希迈寡阔马忻打哪貉浑府渤院娇竣陛坏滴夫秆绚嘿辖杂徘庇赊洼止运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,13,在产销平衡问题中，仔细观察式（4-2）、（4-3）分别变为（4-5）、（4-6），约束条件成 为等式。在实际问题建模时，还会出现如下一 些变化：（1）有时目标函数求最大，如求利润最 大或营业额最大等；（2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；,1.运输问题模型及有关概念,呛碱烫鹰瓷幌掀抖喘鸭责筑表扁比转类恭乞叛霸土炳幻纷箩租社季萧脸搬运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,14,(3)产销不平衡的情况。当销量大于产量时可加入一个虚设的产地去生产不足的物资，这相当于在式（4-2）每一式中加上 1 个松弛变量，共 m 个；当产量大于销量时可加入一个虚设的销地去消化多余的物资，这相当于在式（4-3）每一式中加上 1 个松弛变量，共 n 个。,1.运输问题模型及有关概念,涟超丢史染幻驰证胚乃志催蓖喂齿踌纽则园法缘翅梁梳剧娟试同采斥狡尔运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,15,运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，如图4-1所示。由于运输规划系数矩阵的特殊性，如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。在这里需要讨论基本可行解、检验数以及基的转换等问题。,1.运输问题模型及有关概念,刮眩泰得率沛谷歌楔岳患谍疥型残鸵铂龙淋止三级褒虞缚痈蔑所金所贿贱运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,16,1.运输问题模型及有关概念,图4-1 运输问题的求解思路,恕双止疾摧探遵致影虹尚倍列荣眨柞嗣泞魂戍搬雕茨质依铂空匠痔侍输憨运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,17,运输问题求解的有关概念 考虑产销平衡问题，由于我们关心的量均在表4-3与表4-4中，因此考虑把表4-3与表4-4合成一个表,如下表4-5表4-5 运输问题求解作业数据表(下页）,1.运输问题模型及有关概念,书融菌勃目往颈揣虐唾竹骗绷鳖闯患沥防温谗胡颧心须举瘴综挫肝皮苑谆运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,18,1.运输问题模型及有关概念,彼睦祖疾踌剑刮嫁墓乱弘魂耘椿悉埃志泵椅现荤坎吉奇恩妮嗡狈跺蕾盛困运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,19,中任意m+n阶子式等于零，取第一行到m+n1行与对应的列（共m+n-1列）组成的m+n1阶子式,却捉钞忧辆雷沸滦涧净遭舔优氓寄爬荐陌练滞歹叼槽详镊指族给毛菱曙肠运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,20,故r(A)=m+n1所以运输问题有m+n1个基变量。,惜汉凹勃歹发企泄肉徘阑皆套死泻泻楔病狙系疡氮遣沮及雏会上湾迫孺火运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,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)其中，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等都是闭回路。若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：,1.运输问题模型及有关概念,栏墓模链窑伸棵昂卫韩征蹋蚕她霖局离窃作荡挛替姚暗剑赚拽南畔罚绞魏运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,24,根据定义可以看出闭回路的一些明显特点：(1)闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的；(2)闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。,1.运输问题模型及有关概念,栓控翁浑甫仕更丁锰汕确坡哗跋为摇躺碴饲馏筒狰昆恢讲朋新适芒监蚂蔼运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,25,x23,x43,x11,x12,x25,x31,x42,表33,表33中闭回路的变量集合是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的变量数是奇数，显然不是闭回路，也不含有闭回路；,褪醉购趴河堪孝奥龟阴郸丽辱熙阎贮犹灌澄合聂槐恍瘤测扮蓝吝报固跑免运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,27,C是一条闭回路，若把C重新写成 就不难看出C仍是一条闭回路。,【定理1】若变量组B 包含有闭回路，则B中的变量对应的例向量线性相关。,【证】由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零，即,因而C中的列向量线性相关，所以B中列向量线性相关。,【定理2】若变量组 中包含一个部分组构成闭回路，那么该变量组所对应的系数列向量 线性相关。,破焕峡烘拿扛戏涩硷循频戚敝散红煮控润釜电凉甫巡屿连滇新德艳嫉烁娩运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,28,定理3 变量组 xab,xcd,xef,xst 所对应的系数列向量pab,pcd,pef,pst 线性无关的充分必要条件是这个变量组中不包含闭回路。推论 产销平衡运输问题的 m+n-1 个变量构成基变量的充分必要条件是它不含闭回路。这个推论给出了运输问题基本解的重要性质，也为寻求基本可行解提供了依据。,这个推论告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始基可行解带来极大的方便。,炸韩鹊迹督卷层桩田打货非嘻冻殉尧萍衣层麓贤勇藤袒掉倾循牵羽睫铂伏运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,29,例如，m=3,n=4，在运价表Cij的格子的右上方填上相应的xij，如表3-5所示。,表35,佬巡设缘台私淄橡孙骗驶长赂闭削膊涡柿姐夺各揍曙玖姨硼寺铂领团吐离运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,30,这个运输问题的基变量数目是3+41=6。变量组中有7个变量，显然不能构成一组基变量，又如中有6个变量，但包含有一条闭回路故不能构成一组基变量。变量组有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。,靶盼阉命鼠甄剂扣余汤慷娜掠杂株逐貌童简钠种峨两楔莲忙施篱转苯批绑运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,31,2.运输问题求解 表上作业法,上一节已经分析了，对于产销平衡问题，我们关心的量均可以表示在表4-5中。因此可以建立基于表4-5的求解运输问题的方法表上作业法。这里求解运输问题的思想和单纯形法完全类似，即首先确定一个初始基本可行解，然后根据最优性判别准则来检查这个基本可行解是不是最优的。如果是则计算结束；如果不是，则进行换基，直至求出最优解为止。,卖想涉灸各效彪鸿能挝桃埋金侦冠烦莱凭厕采抢卡械治统副礼机厉码性敦运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,32,2.运输问题求解 表上作业法,一、初始基本可行解的确定 根据上面的讨论，要求得运输问题的初始基本可行解，必须保证找到 m+n 1 个不构成闭回路的基变量。一般的方法步骤如下：(1)在运输问题求解作业数据表中任选一个单元格 xij(Ai 行 Bj 列交叉位置上的格),令 xij=min ai,bj,即从 Ai 向 Bj 运最大量(使行或列在允许的范围内尽量饱和，即使一个约 束方程得以满足),填入 xij 的相应位 置；,忿完耘建扮嗜驾辗猩敦讫仿污贿撮砾奉顽枷戍宜咬朔雕钵遥扇糯旅凹催锥运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,33,2.运输问题求解 表上作业法,(2)从 ai 或 bj 中分别减去 xij 的值，即调整 Ai 的拥有量及 Bj 的需求量；,(3)若 ai=0，则划去对应的行（把拥有的量全部运走），若 bj=0 则划去对应的列（把需要的量全部运来），且每次只划去一行或一列（即每次要去掉且只去掉一个约束）；(4)若运输平衡表中所有的行与列均被划去，则得到了一个初始基本可行解。否则在剩下的运输平衡表中选下一个变量，转(4)。,芥刮猿跃隙同惮艘蒙牵耘艰家机妹巡论旺拜阵对呵似忱宋朽锄靳廖放喳星运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,34,上述计算过程可用流程图描述如下（图4-2）,吭市垮酿娩衣掉蝉龙骸漂囱混难掠殖宛碍椭贮助访滁杏阑怔添腋廉关浮窥运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,35,2.运输问题求解 表上作业法,按照上述方法所产生的一组变量的取值将满足下面条件：(1)所得的变量均为非负，且变量总数恰好为 m+n 1 个；(2)所有的约束条件均得到满足；(3)所得的变量不构成闭回路。,因此，根据定理4.1及其推论，所得的解一定是运输问题的基本可行解。在上面的方法中，xij 的选取方法并没有给予限制，若采取不同的规则来选取 xij，则得到不同的方法，较常用的方法有西北角法和最小元素法。下面分别举例予以说明。,袜杉御扼盎壁宙两作幢洽闽族素铰晰品绕窖释胆秩畏汇眺欠拥惧蜂极赫泡运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,36,2.运输问题求解 表上作业法,1、初始基本可行解的确定（1）西北角法：从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。,农插丹滞驾毖钵电谬尤窝怖郁杠刚钢啪俞吩青脂展娥尸窃群霜英便曳芽鸿运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,37,例1：设有运输问题如下表所示，求其最优解。,腹偿充贴匠泄藩殖豆碴卉菜抢彦届通完侯荷益康枯琐抒琶雕港素份羚育纫运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,38,第一次,第二次,第三次,第四次,落牌旬斟靠喀骨吾双耕鼠耀赤融转亚闰氟竟幽寥卖管诫诣碴陷易疑集目突运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,39,2.运输问题求解 表上作业法,（2）最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。,最小元素法的思想是就近优先运送，即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。,掖著履劣势喝青韭曹崭痕馏纷宛鼎又凿粗尘裂迈愿瑰施瘪曹叛懈熄汪韶举运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,40,【例2】求表36所示的运输问题的初始基可行解。,表36,亮鸿衍场决愁梆税跪产券度甜么眷颠祸阅菌料献进茶挨恫莱卜炯奉猖遏手运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,41,0,0,0,【解】,30,15,10,25,20,15,45,20,20,0,0,0,产地,销地,稳奴站屑林盯蟹均咽北岿钎袍芬邮锦臻遁铬瘩粳蜗沉蛮芦朵盐额邢平椿魁运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,42,注:应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列），在保留的列（行）中没被划去的格内标一个0。,2.运输问题求解 表上作业法,你皿庆烘飞下滩赏辙芯胺扒择息窃芋啪逃归亩蔷莲吞咆梁铸夕腔拴揍案掇运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,43,2.运输问题求解 表上作业法,表1,契雅陋汞底提婿适汲墙酋惩淌噎想噶峨祁莎道膘汛仅瞄烙李蜀厕新耍韩玖运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,44,2.运输问题求解 表上作业法,久泞攫携哺魂掺挫吱谈科私条昂毛橱料引就雷透稳苹撒跪脖楷蛀朔凰杏塌运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,45,2.运输问题求解 表上作业法,堵秸杯廖十默筛淌猾辟滨啪鹏画符尾祈旱榨要霖墓蕊忌酿躲猫怨绚碑呀尖运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,46,最优性检验就是检查所得到的方案是不是最优方案。检查的方法与单纯形方法中的原理相同，即计算检验数。由于目标要求极小，因此，当所有的检验数都大于或等于零时该调运方案就是最优方案；否则就不是最优，需要进行调整。下面介绍两种求检验数的方法。,二、基本可行解的最优性检验,2.运输问题求解 表上作业法,坷祁孜姆郭端亢提乞壤膝讼誉旷板涵豁液幌痢谨谜蕴又祭屈他粤搔铡蒂感运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,47,1、闭回路法 为了方便，我们以表1给出的初始基本可行解方案为例，考察初始方案的任意一个非基变量，比如 x24。根据初始方案，产地 A2 的产品是不运往销地 B4 的。如果现在改变初始方案，把 A2 的产品运送1 个单位给 B4，那么为了保持产销平衡，就必须使 x14 或 x34 减少 1 个单位；而如果 x14 减少 1 个单位，第 1 行的运输量就必须增加 1 个单位，例如 x13 增加 1 个单位，那么为了保持产销平衡，就必须使 x23 减少 1 个单位。,2.运输问题求解 表上作业法,廖昼端迄来螺庆钉辅边狰邮馏饰死演冶厌吟汁纵彝啥蓝彭辨毁邢且技熄恭运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,48,这个过程就是寻找一个以非基变量 x24 为起始顶点的闭回路 x24，x14，x13，x23，这个闭回路的其他顶点均为基变量(对应着填上数字的格)。容易计算出上述调整使总的运输费用发生的变化为 8 10+3 2-1，即总的运费减少 1 个单位，这就说明原始方案不是最优方案，可以进行调整以得到更好的方案。,2.运输问题求解 表上作业法,卷先滞都钓矢踩洗律阵极靖纠沉绒谨岭搭痢骇舒让罩帘瞳衙得胃略曹宽送运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,49,可以证明，如果对闭回路的方向不加区别（即只要起点及其他所有顶点完全相同，而不区别行进方向），那么以每一个非基量为起始顶点的闭回路就存在而且唯一。因此，对每一个非基变量可以找到而且只能找到唯一的一个闭回路。表4-10中用虚线画出以非基变量 x22 为起始顶点的闭回路。,2.运输问题求解 表上作业法,歧泻键嗡厄刚摸缄憎认悬熄榜爵折损箔喜伟诣脚泛荡瓮够吞烦寿宙顾润脑运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,50,表4-10 以非基变量 x22 为起始顶点的闭回路,名聊疙既诡欧傈宜斤投宝甥鬃殆珍耀时篮符匹凛批窜扼乞厌茄谷轿口棠卵运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,51,可以计算出以非基变量 x22 为起始顶点的闭回路调整使总的运输费用发生的变化为 9 2+3 10+5 4 1 即总的运费增加 1 个单位，这就说明这个调整不能改善目标值。从上面的讨论可以看出，当某个非基变量增加一个单位时，有若干个基变量的取值受其影响。,2.运输问题求解 表上作业法,锑努帘粹日旷欣蟹挎肝菜海赚饱幕犯惰让算臂嫁侈妈蹬演缺欣歉佬唇郸防运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,52,这样，利用单位产品变化（运输的单位费用）可计算出它们对目标函数的综合影响，其作用与线性规划单纯形方法中的检验数完全相同。故也称这个综合影响为该非基变量对应的检验数。上面计算的两个非基变量的检验数为 24=-1，22=1。闭回路方法原理就是通过寻找闭回路来找到非基变量的检验数。,2.运输问题求解 表上作业法,刊挺淌培套镀举品宗阁恕溜访植擎霉络航报伺躇碌恫禹阵枷呀誓条恿寐雏运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,53,如果规定作为起始顶点的非基变量为第 1 个顶点，闭回路的其他顶点依次为第 2 个顶点、第 3 个顶点，那么就有 ij=(闭回路上的奇数次顶点单位运费之和)-(闭回路上的偶数次顶点单位运费之和)其中 ij 为非基变量的下角指标。,2.运输问题求解 表上作业法,出折胶铬诸湘哦漱铆恒窿腊初黔咐隅蜒岛汗眠是泞坯盐刽衣撑农描派狮塑运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,54,按上述作法，可计算出表1的所有非基变量的检验数，把它们填入相应位置的方括号内，如图4-11所示。,裕英撑偷守雹缕杀搏涌掠仕祝舷庭渍条诚憋筐遁滔狙醛绰空纺杜渴抱榷觅运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,55,显然，当所有非基变量的检验数均大于或等于零时，现行的调运方案就是最优方案，因为此时对现行方案作任何调整都将导致总的运输费用增加。闭回路法的主要缺点是：当变量个数较多时，寻找闭回路以及计算两方面都会产生困难。,2.运输问题求解 表上作业法,撬甲画档庭额询刺泪磕噬坷豌簇暇棍东增弗淆赴旬咐频阶束耀瞻丙沿罢燎运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,56,【解】用最小元素法得到下列一组基本可行解,【例4】求下列运输问题的一个初始基本可行解及其检验数。矩阵中的元素为运价Cij，矩阵右边的元素为产量ai，下方的元素为销量bj。,10 60 40 30,食兆究脚允卵章摹抑盂颂堰牟奉笔屡郭敦澎网历炒敬拱嚷辕午统竞膊笛咎运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,57,矩阵中打“”的位置是非基变量，其余是基变量，这里只求非基变量的检验数。,求11，先找出x11的闭回路，对应的运价为再用正负号分别交替乘以运价有直接求代数和得,吱箕拂楼邀稿扣季眨膏啪任耕负陀硝芹购辗轴羽柬拧戌骤躬秽赃蚂隙瞬技运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,58,同理可求出其它非基变量的检验数：,这里340，说明这组基本可行解不是最优解。,只要求得的基变量是正确的且数目为m+n1，则某个非基变量的闭回路存在且唯一，因而检验数唯一。,督电郡裤灿镶阻粘低箭尖撒套协伶走泞煞咬诀恳辫缘蔬屹扯涌资潭膘垢壕运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,59,2.位势法 根据单纯形法中检验数的定义，可以从约束条件中解出基变量（用非基变量表示基变量），然后代入目标函数消去目标中的基变量，得到的非基变量系数就是检验数。这一过程可以用下列位势法等价地加以实现。位势：设对应基变量xij 的 m+n-1 个 ij，存 在ui,vj 满足 ui+vj=cij，i=1,2,m;j=1,2,n.称这些 ui,vj 为该基本可行解对应的位势。,2.运输问题求解 表上作业法,纺穆翻辨豺等涡枕初兽佣蜀贸涪郧锻愚宠唐华湖揽狈刑猩俱格墅剔誉寓休运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,60,位势法求检验数是根据对偶理论推导出来的一种方法。,设平衡运输问题为,设前m个约束对应的对偶变量为ui,i=1,2,m，后n个约束对应的对偶变量为vj,j=1,2,n则运输问题的对偶问题是,秩品瀑好衡掀泥衣恋卡颖暖正浙躯溅钉邹缠见忍荔宛赞桑断芭入忧蛔试辖运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,61,加入松驰变量ij将约束化为等式,ui+vj+ij=cij,记原问题基变量XB的下标集合为I，由第二章对偶性质知，原问题xij的检验数是对偶问题的松弛变量ij当（i，j）时ij=0，因而有,解上面第一个方程，将ui、vj代入第二个方程求出ij。,惧肝睡谎匀蒙屋扩澈痴叙碴啦线涉沪双宁扇滞洼亲圆狈壮门露男耸蚕聚影运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,62,【例5】用位势法求例4给出的初始基本可行解的检验数。,【解】第一步求位势u1、u2、u3及v1、v2、v3、v4。,10 60 40 30,令u1=0得到位势的解为,慈洼慈锣稼邪和叶嫡巳滚撬娶疾酵船吻孪疗凑晚绸览勾骑眷仗缘鸭鲍春斤运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,63,再由公式 求出检验数，其中Cij是非基变量对应的运价。,计算结果与例4结果相同。,免礼澳乡连噬彦焙潍刃淳芳酶十劲峦梅句张覆辟绢衔开虹浸深滩墨捐剔救运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,64,2.运输问题求解 表上作业法,前例3用位势法求检验数：,缮粗誊虚丸痞皑濒娄泻罐重烁滞汾擒晦迂漠眺拂挂穗瞅绩逝八妄乱油士黔运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,65,当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。在这种情况下，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，这一过程通常称为换基(或主元变换)过程。,2.运输问题求解 表上作业法,三、求新的基本可行解,摔吨渴困邻罪骗巧错轻祷量砸啥粕益他芋痪扼招浓郑涡孪泳坝酒丘沈斜宁运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,66,（1）选负检验数中最小者 rk，那么 xrk 为主元，作为进基变量（上页图中 x24）;（2）以 xrk 为起点找一条闭回路，除 xrk 外其余顶点必须为基变量格（上页图中的回路）;,2.运输问题求解 表上作业法,在运输问题的表上作业法中，换基的过程是如下进行：,（3）为闭回路的每一个顶点标号，为 1，沿一个方向（顺时针或逆时针）依次给各顶点标号；,懈输撼姑优缎雀灯鄂捍式播锋夜复洲腿晋暑之浇蓖杖齐咽阔嫉拖粉叛烬夺运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,67,（4）求=Minxijxij对应闭回路上的偶数标号格=xpq那么确定xpq为出基变量，为调整量；,2.运输问题求解 表上作业法,（5）对闭回路的各奇标号顶点调整为：xij+，对各偶标号顶点 调整为：xij-，特别 xpq-=0，xpq变为非基变量。重复(2)、(3)步，直到所有检验数均非负，得到最优解。,凸焚恒奠摄诬兔爵维围耪贪韧凰式茶罢姐驯硅京示襄识描粹郎敛泞祖棱盗运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,68,【例9】求下表所示的运输问题的最优解。,表36,产地,销地,脓洱垛绩磁乳曙拔援吼疏汛安泡闭爽轰革册谋弧聪痰序冈萤浊赎国蛀多庇运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,69,【解】,30,15,10,25,20,-1,前面已得到此题的初始可行解，现在接着做下去。用闭回路法求检验数如下：,产地,销地,宋涅缺炼嫂妻衫渺窟镣寿碉采谦驮百肿卸舔工催迈隐恩炉窍怪药结页强抹运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,70,30,15,10,20,-1,2,25,产地,销地,【解】,前面已得到此题的初始可行解，现在接着做下去。用闭回路法求检验数如下：,雏甩殴逞榔尽捣支贿手盅九蹄樱抓领赌恤哗坎钵仇蛤摘天曾束粗染筋喀拿运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,71,30,15,10,20,-1,2,25,-2,产地,销地,【解】,前面已得到此题的初始可行解，现在接着做下去。用闭回路法求检验数如下：,衷验哩喜惶悯裂娥侮汲敌刀焊积椭小配舆氨塑板沙恋氮敌辟屠顾累牟想龄运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,72,30,15,10,20,-1,2,25,-2,产地,销地,2,【解】,前面已得到此题的初始可行解，现在接着做下去。用闭回路法求检验数如下：,饰句尚胸瘁肚淫膝床曳拇捍萌浩氏逊圾批胰萝怂忙俄峭烟糙粘杆府勾骨在运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,73,因为有个负检验数，所以这组基本可行解不是最优解。取非基变量x32进基,用闭回路法调整如下,闭回路如上图，标负号的运量是：x31=25、x22=30，取其最小值25作为调整量，在闭回路上x21、x32分别加上25，x31、x22分别减去25，调整后得到一组新的基可行解。,25,40,5,样殆筐丰偷纽檀侧殃谴蓝哗酞蹄犯亢朋傅剔除耗愉僧廷痴客雁粉散讣赐耐运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,74,5,40,10,25,20,-1,2,2,再检验（表中括号中的数字为检验数）,押棚纂植素栅阶磷俱溶姻另素轻岭译忧幽弱惫遣胃伟害擒涨因萨雁灯杭熙运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,75,5,40,10,25,20,-1,2,4,2,再检验（表中括号中的数字为检验数）,摊儿帅痔事贬挡惨佳挫宜闸喧捧诬凹硫炮袄拘释托绪陷售叉氟惫府电脓摔运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,76,5,40,10,25,20,-1,2,4,2,5,45,15,检验数l12=-1,方案需调整，下面用闭回路法调整,剧购噬凝顿灯躺敷遏巩坪次压框粉字吴掸搜状畅秦休烹展禽姓茅设疗鞭嫌运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,77,25,45,10,15,再计算一次检验数（表中括号中的数字）,产地,销地,5,2,1,1,3,检验数已全非负，故表中的解已为最优解，最小运费为500元。,扔娶画皋寓蓖艘什藤争崩洗甫流池匪互只耙捻兵挽摹阔掣耸恬眉吻械袒凭运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,78,2.表上作业法,ij 0，得到最优解 x13=5,x14=2,x21=3,x24=1,x32=6,x34=3,其余 xij=0;最优值：f*=35+102+13+81+46+53=85,香女侗嫂尸皖目酸仕形乎麻锚陪浚烧削锌兆扭见霄泉鹅翅它峙俭宏失慎誊运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,79,四、产销不平衡问题的处理 在实际中遇到的运输问题常常不是产销平衡的，而是下列的一般运输问题模型 m nMin f=cij xij（4-1）i=1 j=1 n s.t.xij si i=1,2,m（4-2）j=1 m xij(=,)dj j=1,2,n(4-3）i=1 xij 0(i=1,2,m;j=1,2,n)（4-4）,2.运输问题求解 表上作业法,帽弊寐惟澡督从赌真肉竭绕鳃帛酝榔函潦沧兼召渤浮武苫歹肌柬欺衷回肥运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,80,我们已经介绍过，可以通过增加虚设产地或销地（加、减松弛变量）把问题转换成产销平衡问题，下面分别来讨论。1.产量大于销量的情况 m n 考虑 si dj 的运输问题，得到的数学模 i=1 j=1型为,2.运输问题求解 表上作业法,佬媳员屠斋衣贺磋阀凌向拘孙韦凰新德采赡愚拴冻九官拈胶婆釉逗抹楞毕运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,81,2.运输问题求解 表上作业法,m n Min f=cij xij i=1 j=1 n s.t.xij si i=1,2,m j=1 m xij=dj j=1,2,n i=1 xij0(i=1,2,m;j=1,2,n),佳各胚惦烽测税都劝难从乡孪幻与哈编语毒柴稍酬即隐创赂酚胯掏陇胯耘运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,82,只要在模型中的产量限制约束（前m个不等式约束）中引入m个松弛变量xin+1 i=1,2,m 即可，变为：n xij+xin+1=si i=1,2,mj=1然后，需设一个销地B n+1,它的销量为：m n bn+1=si-dj i=1 j=1,2.运输问题求解 表上作业法,浓散壕醇催艺垄粮苫哼件行滑碘尧卖舍焊起碗潮笛曙尖贝阔母灿寒坍飞俩运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,83,这里，松弛变量 x i n+1 可以视为从产地 A i 运往销地 B n+1 的运输量，由于实际并不运送，它们的运费为 c i n+1=0 i=1,2,m。于是，这个运输问题就转化成了一个产销平衡的问题。,2.运输问题求解 表上作业法,吟理织苹瞄怠辛提薄打癸淫莆衬眶史兆锋尿碍胎虎释备刑俺俄停蔡何脖载运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,84,例4.2:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,2.运输问题求解 表上作业法,俘蚤伪穗铺钱壹烟猩奢嚷颗蠕灼醋绒庭坚杂镇内皮束它还借想灭且顶泛庶运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,85,解：增加一个虚设的销地运输费用为0,2.运输问题求解 表上作业法,绳杀鞭弊誉趟忧倔笑嘱访局串额诽竭挚孰诚凤桃腥烃棘色桌投痘骚掺玫狼运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,86,2.销量大于产量的情况 m n 考虑sidj的运输问题，得到的数学模型为 i=1 j=1,2.运输问题求解 表上作业法,m n Min f=cij xij i=1 j=1 n s.t.xij=si i=1,2,m j=1 m xij dj j=1,2,n i=1 xij0(i=1,2,m;j=1,2,n),呆捕洱栋坐洞岂酣溜砌游抄爷甩纫灿滇噪理愁拣繁室鲁钒狈叁疼哮竣华磐运筹学教学课件-第三章 运输问题运筹学教学课件-第三章 运输问题,87,只要在模型中的产量限制约束（后n个不等式约束）中引