三章节运输问题

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

1、第三章第三章 运输问题运输问题一、运输问题及其数学模型二、表上作业法三、运输问题的进一步讨论四、应用举例泌暗饲膳围廓褥咖疾伍呜舀筹拓咐矢挎祭褒辽油裴谎上较蝶惋昔矽凋衰度三章节运输问题三章节运输问题第三章2312341一、运输问题及其数学模型一、运输问题及其数学模型s2=27s3=19s1=14供应量供应地运价d1=22d2=13d3=12d4=13需求量需求地6753842759106 引例：引例：运输问题网络图辣腆忙部途蛹北献付轰封脑秩铅抑勿滑猾戌昂令溉滞炎对仕纤广拾渊摸卤三章节运输问题三章节运输问题第三章供应地约束需求地约束一、运输问题及其数学模型一、运输问题及其数学模型皮左俞纤哈幻茅切恰

2、越约拆幼淋养鲜兢银闽送未龟夫缸破猛嘲汉织本巩燃三章节运输问题三章节运输问题第三章运输问题的描述： 设某种物品有m个产地A1,A2,.,Am，各产地的产量分别是a1,a2,.,am；有n个销地B1,B2,.,Bn，各销地的销量分别为b1,b2,.bn。假定从产地Ai(i=1,2,m)向销地出Bj(jl,2,.n)运输单位物品的运价是cij，问怎样调运这些物品才能使总运费最小?一、运输问题及其数学模型一、运输问题及其数学模型渭佬橡蚌锚怕撒褒浊尧诣束蓬躺孟类彻逆窘频咒铲曝诫骑绚挟巍晌贮底例三章节运输问题三章节运输问题第三章运价表 销地产地B1B2Bn产量A1C11C12C1na1x11x12x1nA

3、2C12C22C2na2x21x22x2n.AmC1mC2mCmnamxm1xm2xmn销量b1b2bm一、运输问题及其数学模型一、运输问题及其数学模型笋毫亢肉臆杯虽均明疫逝寅醚呆劫才绩恒肌澜府栋齿荐搐玫嚏技捉因朵竟三章节运输问题三章节运输问题第三章产销平衡运输问题的数学模型表示：（ ）一、运输问题及其数学模型一、运输问题及其数学模型妻雄赁韧闹卵糕荫复渭瘩酥锡獭对迪霄仁朽峦溃坍混不漫生支躲追彝遮键三章节运输问题三章节运输问题第三章该模型是一个线性规划模型，可以用单纯形法求解。但是变量数目非常多。如3个产地，4个销地。变量数目会有19个之多。因此应该寻求更简便的解法。为了说明适于求解运输问题的更

4、好的解法，先分析运输问题数学模型的特点。一、运输问题及其数学模型一、运输问题及其数学模型旷到搅逆朵怒滓锯莉隔鞘缉梦标苇公欺阴索憎斜次缎溉励队抓整钎酗绘注三章节运输问题三章节运输问题第三章运输问题数学模型的特点：运输问题数学模型的特点：1运输问题有有限最优解运输问题有有限最优解是一个可行解。同时，目标函数有下界，且不会趋于负无穷。所以，必存在有限最优解。一、运输问题及其数学模型一、运输问题及其数学模型利途城庇徒舀涤葫允暖映陪王轮玄澎替汤茬乏肢篙法剖左莆帛捕坤瞥仗顽三章节运输问题三章节运输问题第三章2运输问题约束条件的系数矩阵运输问题约束条件的系数矩阵A =n 行m 行系数列向量：第i个第m+ j

5、个一、运输问题及其数学模型一、运输问题及其数学模型氯泼送跋占睬碱正卉宽帚匆述驾川醛藩版诊网锗氢仔设达凄颈茬护岁堵框三章节运输问题三章节运输问题第三章由此可知，运输问题具有下述特点： (1)约束条件系数矩阵的元素等于0或1； (2)约束条件系数矩阵的每一列有两个非零元素，这对应于每一个变量在前m个约束方程中出现一次，在后n个约束方程中也出现一次；对产销平衡运输问题，除上述两个特点外，还有以下特点：(3)所有结构约束条件都是等式约束；(4)各产地产量之和等于各销地销量之和。 秩 ( A) =m+n-1运输问题的基可行解中应包含m+n-1个基变量.一、运输问题及其数学模型一、运输问题及其数学模型围厩

6、续影刮逢尊泥剑求力驮氏裕服葱刻迎摊去迸关旨寡捧吟羽笺筋涂榜追三章节运输问题三章节运输问题第三章3.运输问题的解运输问题的解(1)解x必须满足模型中的所有约束条件；(2)基变量对应的约束方程组的系数列向量线性无关；(3)解中非零变量xij的个数不能大于(m+n-1)个，原因是运输问题中虽有(m+n)个结构约束条件，但由于总产量等于总销量，故只有(m+n-1)个结构约束条件是线性独立的；(4)为使迭代顺利进行，基变量的个数在迭代过程中保持为 (m+n-1)个。运输问题解的每一个分量，都唯一对应其运输表中的一个格 填有数字的格 或 空格一、运输问题及其数学模型一、运输问题及其数学模型踞坑懊植烙靴挟悄

7、浩没党捎侗象澜背例富逾陌锗牧肮映姑糙锯窗柴匡签为三章节运输问题三章节运输问题第三章 销地产地B1B2B3B4产量A141241116826A2210391010A38511622148销量814121448下表给出了例下表给出了例1的一个解。的一个解。一、运输问题及其数学模型一、运输问题及其数学模型数苟谐笔运蛹瓷怒赫藕您威焙刘爹巫诲炳磺睁汐昔昏沈谜馁鞋戒狗酚委见三章节运输问题三章节运输问题第三章二、表上作业法二、表上作业法 表上作业法是一种迭代法，迭代步骤为： 1、先按某种规则找出一个初始解(初始调运方案)； 2、再对现行解作最优性判别； 3、若这个解不是最优解，就在运输表上对它进行调整改进，

8、得出个新解； 4、再判别，再改进； 5、直至得到运输问题的最优解为止。 迭代过程中得出的所有解都要求是运输问题的基可行解。脱苹连憾间剁剃砍扑添第勘澎倾橙咽瓜柬创酱咕输偏剑砰卉退超茨蛙耪吊三章节运输问题三章节运输问题第三章例1： 销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448二、表上作业法二、表上作业法革笆惯边际赔埠盛掘彩辆静巫挚夷管区橇谊仅款掇勺糕茫置潮阴骂宿蹄嚣三章节运输问题三章节运输问题第三章 思路：思路：为了减少运费，应优先考虑单位运价最小(或运距员短)的供销业务，最大限度地满足其供销量。在可供物品已用完的产地或需求已全部满足的

9、销地，以后将不再考虑。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个完整的调运方案(完整的解)为止。这样就得到了运输问题的一个初始基可行解(初始调运方案)。 由于该方法基于优先满足单位运价(或运距)最小的供销业务，故称为最小元素法。1、初始基可行解最小元素法、初始基可行解最小元素法二、表上作业法二、表上作业法义亩谜趁聪穷粥壬抡毒档剃啦随落枢惰绎仟劈索鸥夜妒谓洱匡无版屑伊耘三章节运输问题三章节运输问题第三章 销地产地B1B2B3B4产量A141241116A22103910A38511622销量81412144882101486所以，初始基可行解为：

10、目标函数值Z246二、表上作业法二、表上作业法婿食须衙俺鹊颂援案装漆豢撞叙桓戳爱历赛塞蚂植冈种燕悔惧循瓤杠住抽三章节运输问题三章节运输问题第三章练习 销地产地B1B2B3B4产量A1675314A2842727A35910619销量221312131213131912二、表上作业法二、表上作业法密娠越弥涌舅嘶聂毁丧股唁姚袱监秋郧遗搔圾酉胎竭瞄较劈铃姚绪竹呈旱三章节运输问题三章节运输问题第三章在满足约束条件下尽可能的给最左上角的变量最大值. 销地产地B1B2B3B4产量A141241116A22103910A38511622销量8141214488864814所以，初始基可行解为：目标函数值Z3

11、721、初始基可行解西北角法、初始基可行解西北角法二、表上作业法二、表上作业法铬抄司蹲暖操点撇抗佯莉迫册婴瘁膏倍伶忙装夷养垂烷何核寅牧洁病连蔑三章节运输问题三章节运输问题第三章练习练习 销地产地B1B2B3B4产量A1675314A2842727A35910619销量22131213813131466二、表上作业法二、表上作业法惫庇庄踌摊裸嫩悍禹猖嵌路坑缮逢辊卓肩彬钮速鳖鲍册数异泛膘响端胚萨三章节运输问题三章节运输问题第三章最小元素法，有时按某一最小单位运价优先安排物品调运时，却可能导致不得不采用运费很高的其他供销点，从而使整个运输费用增加。6202455551、初始基可行解沃格尔法、初始基可

12、行解沃格尔法二、表上作业法二、表上作业法哉瘫佳涪虎箭份负铭未陨啼夹址泰模蔼酝矿经橡虐枝犬囚种优拔瑶屿汽汲三章节运输问题三章节运输问题第三章对每一个供应地或销售地，均可由它到各销售地或到各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。沃格尔法基本思想： 在罚数最大处采用最小运费调运。 如果罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。沃格尔法就是基于这种考虑提出来的。二、表上作业法二、表上作业法吓芳今虑筹迟牢陌矿置矛怜孜沙以彪刚辛雨登

13、露近斧拉诲镇助沁眨碱购庞三章节运输问题三章节运输问题第三章沃格尔法计算步骤：1) 分别算出各行、各列的罚数。2) 从行、列中选出差额最大者，选择它所在行、列中的最小元素，进行运量调整。3) 对剩余行、列再分别计算各行、列的差额。返回1)、2)。二、表上作业法二、表上作业法私捌吭疡熔们佛嘶芍乐帘委拷桅骨遁许浮畏蛮剔撞渗牌捧圆玩叛篷癌详沙三章节运输问题三章节运输问题第三章 销地产地B1B2B3B4产量A141241116A22103910A38511622销量81412144814所以，初始基可行解为：目标函数值Z244881224二、表上作业法二、表上作业法没砖湾于擒困杂畏禹身碟第成汕子穷爬肃逞

14、礼傲追柱平管早夹灿得熬赐取三章节运输问题三章节运输问题第三章练习练习 销地产地B1B2B3B4产量A1675314113A284272721312A3591061919销量22131213 销地产地B1B2B3B4产量A1675314A2842727A35910619销量22131213二、表上作业法二、表上作业法嘛让赦牌此议分乃温睦狞缨烩迈改爹彪挽桨勿拘臣娱禁街绞杭讼沼躇管跺三章节运输问题三章节运输问题第三章 思路：要判定运输问题的某个解是否为最优解，可仿照一般单纯形法，检验这个解的各非基变量(对应于运输表中的空格)的检验数，若有某空格(Ai,Bj)的检验数为负，说明将xij变为基变量将使运

15、输费用减少，故当前这个解不是最优解。若所有空格的检验数全非负，则不管怎样变换解均不能使运输费用降低，即目标函数值已无法改进，这个解就是最优解。 以最小元素法的初始解为例。假设产地A1供应1个单位的物品给销地B1。则解的变化和目标函数的变化如何。2、解的最优性检验闭回路法、解的最优性检验闭回路法二、表上作业法二、表上作业法备昌斯婉樱迎谬键苹综升固甥惑虽趣胜盟关扑促液康惟噶豆链圣柏戒竹恫三章节运输问题三章节运输问题第三章 销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448821014861211012-1二、表上作业法二、表上作业法藏抛舀赌离

16、详拄僧依仿暑蘑寒配莫卧妄纺俐怜靡揭碳枪恬麻还蕉骋间攀医三章节运输问题三章节运输问题第三章 由此可知，为了求某个空格(非基变量)的检验数，先要找出它在运输表上的闭回路，这个闭回路的顶点，除这个空格外，其它均为填有数字的格(基变量格)，它是由水平线段和竖直线段依次联接这些顶点构成的一封闭多边形。每个空格都唯一存在这样的一条闭回路。二、表上作业法二、表上作业法里率民忘逃钮袋橙复柿屏翘舅赁柜霉玲以徒橇炔砌售眨镍拈奉骚埂播括婉三章节运输问题三章节运输问题第三章某空格的检验数是以该空格为第一个顶点，某回路的某空格的检验数是以该空格为第一个顶点，某回路的奇数顶点运价和减去其偶数顶点运价和。奇数顶点运价和减去

17、其偶数顶点运价和。二、表上作业法二、表上作业法B1B2B3B4A1A2A3特征特征:1. 每个顶点都是转角点每个顶点都是转角点.2. 每一边都是水平或垂直的每一边都是水平或垂直的.3. 每一行每一行(或列或列)若有闭回路的顶若有闭回路的顶点点,则必有两个则必有两个.趋该仆蓑傻剂承驰积号湾菱肮觉涎谷燕将镭卤禄招射对敝材卿佯醚浇挫超三章节运输问题三章节运输问题第三章 位于闭回路上的一组变量，它们对应的运输问题约束条件的系数列向量线性相关，因而在运输问题基可行解的迭代过程中，不允许出现全部顶点由填有数字的格构成的闭回路。 这就是说，在确定运输问题的基可行解时，除要求非零变量的个数为(mn1)个外，还

18、要求运输表中填有数字的格不构成闭回路。二、表上作业法二、表上作业法被热狄述瓤兔厢乡那稻戒糙碴兼乖找裸遗靶渣嘿厄彻徽妇拧杖目浮玖给师三章节运输问题三章节运输问题第三章 销地产地B1B2B3B4产量A167531414557A284272781369A35910619-11-3613销量22131213 销地产地B1B2B3B4产量A167531414A28427278136A35910619613销量22131213例：确定下列可行解的检验数例：确定下列可行解的检验数二、表上作业法二、表上作业法峙器红叹恨抓佰检斋乌犁楔酞快座湾印揍祟奶晰反痔间竟部掘莱窍赴丽己三章节运输问题三章节运输问题第三章原问

19、题设其对偶变量为：2、解的最优性检验对偶变量法、解的最优性检验对偶变量法二、表上作业法二、表上作业法康冤亚廷陌茬拼彭苗镊傍扦芬丁嫡尉摘买匠挽蒲藐剧巍迷彝犁蔡审蛹圭寅三章节运输问题三章节运输问题第三章原问题系数矩阵：原问题系数矩阵：A =m 行行n 行行u1。umv1。 vn二、表上作业法二、表上作业法队阳力奶鱼寞训衔啄后韵桥几霞佑咖乞篷汰慨鸳费桐慧银停瞳宿账遣憾坡三章节运输问题三章节运输问题第三章对偶问题:考虑原问题变量xj的检验数为：二、表上作业法二、表上作业法梨刑瓦录颁鞠领怂伟馁袒圆薄固际祁试聚战喉痴骡空帮肥脓负宫演厘痢自三章节运输问题三章节运输问题第三章假设已得到一个基可行解，其基变量为

20、：则有：s=m+n-1则运输问题变量xij的检验数为：二、表上作业法二、表上作业法妓躯束务艾诛绩傻职龙厦教肤院糯裔庙附目征遏佰娥今忻躬羡弃船侮跋茧三章节运输问题三章节运输问题第三章方程组有m+n-1个方程。因为运输表中每行和每列均有基变量，因此上面方程组含有全部m+n个对偶变量。故解不唯一，其解称为位势。若上述方程的某组解满足对偶问题的所有条件，即：此时，原问题与对偶问题均可行，故达到最优。其解分别为：二、表上作业法二、表上作业法汉叫永誊秆霄姐剂僻卤卒芋焊放瓢赃堑爵娘滞寿雍艳热猩锅杯邢咎管犊肠三章节运输问题三章节运输问题第三章例：例： 销地产地B1B2B3B4产量UiA141241116A22

21、103910A38511622销量814121448Vj82101486二、表上作业法二、表上作业法全棘饺唁待呐盂辟疏片拯墒荔摩橇祭念输酵撑茄靴缮如垒啄晰弟皿趟躁佃三章节运输问题三章节运输问题第三章练习题练习题 销地产地B1B2B3B4产量A167531414557A284272781369A35910619-11-3613销量22131213 销地产地B1B2B3B4产量A167531414A28427278136A35910619613销量22131213二、表上作业法二、表上作业法怨盯勺船冉烟曝锤相铃涨荆顷党壤豺肾汇季搽碟胎丙绳葵垮觅窖迎硫流暮三章节运输问题三章节运输问题第三章 改进的方

22、法是在运输表中找出这个空格对应的闭回路，在满足所有约束条件的前提下，使xij尽量增大并相应调整此闭回路上其它顶点的运输量，以得到另一个更好的基可行解。3、解的改进闭回路调整法、解的改进闭回路调整法二、表上作业法二、表上作业法吮姚站罕什湃底旋鸿声决侵摔顾诬庙晶克圃歇眷椭冷闽插樊党篱墙决愁昆三章节运输问题三章节运输问题第三章 解改进的具体步骤解改进的具体步骤(1)以xij为换入变量，找出它在运输表中的闭回路；(2)以空格(Ai,Bj)为第一个奇数顶点，沿闭回路的顺(或逆)时针方向前进，对闭回路上的顶点依次编号；(3)在闭回路上的所有偶数顶点中，找出运输量最小的顶点(格子)，以该格中的变量为换出变量

23、；(4)以换出变量的运输量为调整量，将该闭回路上所有奇数顶点处的运输量都增加这一数值，所有偶数顶点处的运输量都减去这一数值，从而得出一新的运输方案。该运输方案的总运费比原运输方案减少，改变量等于换出变量的检验数。 然后，再对得到的新解进行最优性检验，加不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止。二、表上作业法二、表上作业法啼报该冷钟普发迭瓶浚晾时寿夜鄂罢酷毅是题纪汾绅亲镀借疗让彬蕾陌钮三章节运输问题三章节运输问题第三章 销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448例：821014861211012-1二、表上作业法

24、二、表上作业法摹废凳化肉厅郸蓬昂撮乒逮承熟转矾援驰湿零闯垫塑过甲欠遍墓硬垒舷堆三章节运输问题三章节运输问题第三章 销地产地B1B2B3B4产量A141241116A22103910A38511622销量814121448例：821214840229121由于所有非基变量的检验数全非负，故这个解为最优解。又由于非基变量有零检验数，所以有无穷多最优解。二、表上作业法二、表上作业法恼炳主饿亚事茨妓亨萌涅疮娠臀岁在臂宫嵌捌类枯串笛欲精版子迈经粪甫三章节运输问题三章节运输问题第三章练习题练习题 销地产地B1B2B3B4产量A167531414A28427278136A35910619613销量22131

25、213二、表上作业法二、表上作业法练习题练习题荐团雁促青帧淤沸鞠妻便随炊译岔孺铰作冰弟铃邑结攘矩擎逞速哈毁牙砰三章节运输问题三章节运输问题第三章练习题练习题 销地产地B1B2B3B4产量A167531414557A284272781369A35910619-11-3613销量22131213二、表上作业法二、表上作业法练习题练习题句泣弧粗碴毯笔罐葫廷撬押佑螺述魁封崩析珐疆首诉娶叶红爽痒咏崇盼赢三章节运输问题三章节运输问题第三章练习题练习题 销地产地B1B2B3B4产量A16753141455-4A284272721312-2A35910619681113销量22131213二、表上作业法二、表

26、上作业法霞抉睡毁驮愿贤振葱援劝押篆鲤戮凡隧拂驮镰晾灯笨油乘啼酒哲陋佑褪瞪三章节运输问题三章节运输问题第三章 销地产地B1B2B3B4产量A167531415513A2842727213122A35910619198114销量22131213 销地产地B1B2B3B4产量A1675314113A284272721312A3591061919销量22131213答案答案二、表上作业法二、表上作业法捕室鹊们诀缚药廊刃廖贵暑四亭室汐法墨皑铜幢警宦萎球卓鹰懦起曳檬宛三章节运输问题三章节运输问题第三章1）若运输问题的某一基可行解有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量为换入变量均

27、可使目标函数值得到改善，但通常取小于零的检验数中最小者对应的变量为换入变量。 2）当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重(无穷多)最优解。 4、需要说明的几个问题、需要说明的几个问题二、表上作业法二、表上作业法忙枷挡窑施嘴盘毕说孺漓冉蛇梳郁告吕顶衍踞忱脉彤剥荫咙参梳痢椅挪堕三章节运输问题三章节运输问题第三章3）（二 ）退化 某一基变量 的值为0初始解 在确定初始解的供需关系时，若在确定（i, j ） 的数字时，要划去第i行,第j列。为使在产销平衡表上有m+n-1个数字格，须在第i 行或j列中 （ 非i,j ) 选一数字格为0。退化解 闭回路中有（ -

28、 ）标记中有两个或以上相等的最小数。调整后出现退化解，必须在一数字格中填入0，以表明其为基变量。二、表上作业法二、表上作业法夸擦栗月无怂细堑账问勺花耀了腥岂挂伏枪赛槛饱聊递腆些烫捻窿眉滤爬三章节运输问题三章节运输问题第三章三、运输问题的进一步讨论三、运输问题的进一步讨论 上一节讲述的运输问题的算法，是以总产量等于总销量(产销平衡)为前提的。实际上，在很多运输问题中，总产量不等于总销量。 痈看件师吟扫姐葡蛇校露数颂蕊误鄂垛拔雾蓑访疮阎芥撩羊经歼乔棚款畸三章节运输问题三章节运输问题第三章（ ）表上作业法 以产销平衡 为前提。1、产销不平衡的运输问题、产销不平衡的运输问题三、运输问题的进一步讨论三、

29、运输问题的进一步讨论捂赞栓皖蛀穴囱但打狼被牛柯恿火媚朝开殊裁娶悠级屁呵萄荔瘴敷豢菲努三章节运输问题三章节运输问题第三章2321341s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106 例：假设供应量大于需求量例：假设供应量大于需求量+55d5=5 假想销地0 0 0s3=24三、运输问题的进一步讨论三、运输问题的进一步讨论盟柞触律肖息慨坍蓄瞅碟执个雨梨返藐则冠值只棠橱肠董穆洁仔秒痰掂哀三章节运输问题三章节运输问题第三章 产大于销 产销不平衡产销平衡模型：三、运输问题的进一步讨论三、运输问题的进一步讨论狐艳记仗容屈司佰弹修

30、湛郡崎斜哟径了膝迭他镑达懊阎奠袒瘩鉴请秤辱瞧三章节运输问题三章节运输问题第三章设 为Ai的贮存量。将多余物原地贮存。令：三、运输问题的进一步讨论三、运输问题的进一步讨论宦哦您冒埋桑冈按辗暴莽簇凋吕盈竟戒胚奄脖颊懈辜亭象锹滔缘郭齿冒痪三章节运输问题三章节运输问题第三章理解： 产 销 假想有一销地 j=n+1 销量为 运价 模型：三、运输问题的进一步讨论三、运输问题的进一步讨论妹宋奥玖夫削跪撅瞪脾啤篷峡留闷水恍务雀比姆恶獭置枪摩裙臀杨肃胀央三章节运输问题三章节运输问题第三章 销地产地B1B2BnBn+1 （贮存） 产量A1C11C12C1n0a1x11x12x1nx1,n+1A2C12C22C2n

31、0a2x21x22x2nx2 ,n+1.AmC1mC2mCmn0amxm1xm2xmnxm ,n+1销量b1b2bma- b三、运输问题的进一步讨论三、运输问题的进一步讨论抑炮格圆荫责棺唇酗然革屿吓渴渔布狠叛客丫咐猛苇祸饲拷插尧随叙猛画三章节运输问题三章节运输问题第三章例： 某市有三个造纸厂A1，A2，A3，其纸的产量分别为8，5和9个单位，有4个集中用户B1，B2，B3，B4，其需用量分别为4，3，5和6个单位。由各造纸厂到各用户的单位运价如表315所示，请确定总运费最少的调运方案。 销地产地B1B2B3B4产量A1312348A2112595A367159销量4356三、运输问题的进一步讨

32、论三、运输问题的进一步讨论遁涉囱铬拉每厌惦睛挤虞泞位办坡盲棵甩径骇辟释稳莎属俭囤右窜钻们渐三章节运输问题三章节运输问题第三章 解：由于总产量22大于总销量18，故本问题是个产销不平衡运输问题。增加一假想销地B5，用表上作业法求解。 销地产地B1B2B3B4B5(贮存)产量A13123408A21125905A3671509销量43564三、运输问题的进一步讨论三、运输问题的进一步讨论羡琴必樟敖搀救鞭惩瓮介褂涎衍漱谚甭睡漆药氓肩庶使贪汀填息郡杏渭恕三章节运输问题三章节运输问题第三章 销地产地B1B2B3B4B5(贮存)产量A13123408418634A211259050302-8A367150

33、9-2954-4销量43564 销地产地B1B2B3B4B5(贮存)产量A1312340844A21125905032A367150954销量43564三、运输问题的进一步讨论三、运输问题的进一步讨论赦升每齿鞍吉于忙晌意娱送噶脊屠鸥祷贮毅掐聋翌纱匣帽枪沮框隘萎鳖余三章节运输问题三章节运输问题第三章2、有转运的运输问题、有转运的运输问题在以上讨论中，假定物品由产地直接运送到销售目的地，不经中间转运。但是，常常会遇到这种情形：需先将物品由产地运列某个中间转运站(可能是另外的产地、销地或中间转运仓库)，然后再转运到销售目的地。有时，经转运比直接运到目的地更为经济。因此，在决定运输方案时有必要把转运也

34、考虑进去。三、运输问题的进一步讨论三、运输问题的进一步讨论陆隐腆城揉谆挛翼阎瘴侯贝凄我铱讲炯幻催蓬晨坤盐砌丁瞬境屋狠隶粗呕三章节运输问题三章节运输问题第三章2、有转运的运输问题、有转运的运输问题峭固敲芜麦绸璃愉蚁兄焕垃悍蚌启话扫娜褒邑葫瑚避症拾抵铁哺铂妨抉醋三章节运输问题三章节运输问题第三章转运量 t1t2t3t4t5t6t7A2A3A1a2=27a3=19a1=14供应量需求量B2B3B4B1a5=0a6=0a4=0a7=0A2A3A1b4=22b5=13b6=12b7=13B2B3B4B1b1=0b2=0b3=0xij转运量 t1t2t3t4t5t6t7届瞻感吮豹厉立卡雕抉僧邪跑次瓜萄犀耍

35、婆剔夹豆巷阜毫院丰沙族芍来沼三章节运输问题三章节运输问题第三章假设单位运转费用为ti，则线性规划模型为：三、运输问题的进一步讨论三、运输问题的进一步讨论氮撮萍坑谓睛男目韶码潘腐趴疟瓜枢烈俺过羌率瀑饰甩家若柞坚狱狗蔚蓟三章节运输问题三章节运输问题第三章第二项为常数，对求解结果无影响，可去掉。罪那尔糕浓账轩奔稠掖榴勋严肾巩策讽蔫歌咖久研吓庇娄讣阵谁睬沁郊屡三章节运输问题三章节运输问题第三章模型变为下列形式：这是一个产销平衡运输问题的数学模型。可以列出其运价表，用表上作业法求解。 销地产地A1A2A3B1B2B3B4产量A1A2A3B1B2B3B4销量其运价表形式如下（注意其中对角线上的运价值）：昂

36、湖阑晨离学翱际陋敛蚤叹蹬天峰通蕴靡单床瞩盈辟垫钞付液路批窑腔滇三章节运输问题三章节运输问题第三章建立一般意义上的数学模型，设：建立一般意义上的数学模型，设：ai：第：第i个产地的产量个产地的产量(净供应量净供应量)；bj：第：第j个销地的销量个销地的销量(净需要量净需要量)；xij：由第：由第i个发送地运到第个发送地运到第j个接收地的物品数量；个接收地的物品数量；cij：由第：由第i个发送地到第个发送地到第j个接收地的单位运价，个接收地的单位运价，ti：第：第i个地点转运物品的数量；个地点转运物品的数量；ci：第：第i个地点转运单位物品的费用。个地点转运单位物品的费用。 将将产产地地和和销销地

37、地统统一一编编号号，并并把把产产地地排排在在前前面面。销销地地排排在在后面，则有：后面，则有：辫对央记指福诱挥狐胎叛馆追装珐柔尾椿磷越央嘿彩烬士馅签兑叛谱协刽三章节运输问题三章节运输问题第三章令：令：建立数学模型：建立数学模型：梢恒漫赤财告痕窃轧鸟肌脆弊硒崩勉颇忠奋培躬疟忧货铡薯让欺雷黍拱叔三章节运输问题三章节运输问题第三章注：所有i=j，cij=-ci孕敷丧净嘛鹊馒羡拣祝梳吵辛促诌璃另耗蛊呼赡疥温段膝婆盾驳例步砧届三章节运输问题三章节运输问题第三章吭屋是旷仟考郊了粉婿偿皂违指晋阵苍看茄心枢惜归蝇袍淳杖搪生盂颅戚三章节运输问题三章节运输问题第三章a1a5b1b5Qc1c5c11c55 例：如图

38、所示是一个运输系统，它包括二个产地（例：如图所示是一个运输系统，它包括二个产地（1和和2）、二）、二个销地个销地(4和和5)及一个中间转运站及一个中间转运站(3)，各产地的产量和各销地的，各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点联线上的数字表示销量用相应节点处箭线旁的数字表示，节点联线上的数字表示其间的运输单价，节点旁的数字为该地的转运单价，试确定最其间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。优运输方案。缎闺远亦惺谷猴讫讹蹄衍哲绚栖炔杂疮枣农妇紊眯芳挫亏萝榴弦期煮识槽三章节运输问题三章节运输问题第三章 销地产地A1A2B3C4C5产量A1A2B3C4C

39、5销量你吉疹力扰杖瞪劣砧光袒捶灸拂道室倔姿座诱虑挨阅凯渡挣琢苑迁驮梢栈三章节运输问题三章节运输问题第三章 销地产地A1A2B3C4C5产量A1-4532M60A25-12M490B332-35550C42M5-3650C5M456-550销量5050508070腿惫曼气俞咕骇烬抓吴块拧昼吁豪扎骆嘉江食摇敖地忠丸瀑味欲婴汇侈嗽三章节运输问题三章节运输问题第三章运用最小元素法，求初始运输方案，如下表：最优运输方案如下表：302020位延勿沈局涯畏夷狭断暇贩崖燃邀吹酵篷稳硝瘁钩佬篙鄂甄貌嗡迟似孤扒三章节运输问题三章节运输问题第三章一、回答问题1、在运输问题数学模型中，为什么模型的(m+n)个约束中最

40、多只有(m+n-1)个是独立的?2试述用最小元素法确定运输问题的初始基可行解的基本思路。3如何用闭回路法求检验数？4 沃格尔法的基本思想是什么？什么是罚数？5在解的改进过程中，如何确定调整量？6如何把一个产销不平衡的运输问题(含产大于销和销大于产)转化为产销平衡的运输问题。练习题练习题将力瓮萧黄焚竞吧磷谋舍款贯茄襄尝竞遮柯绊脑骡桑祁常嚼骡剔腾穴夜吃三章节运输问题三章节运输问题第三章二、判断下列说法是否正确(1)运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解；(2)在运输问题中，只要给出一组合(m+n-1)个非零的xij，

41、且满足xij=ai， xij=bj，就可以作为一个初始基可行解；(3)表上作业法实质上就是求解运输问题的单纯形法；(4)按最小元素法(或伏格尔法)给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路；练习题练习题颧仲市幅择瑚择选牛沃秃友萤帚丈众渤刚钩三综叫就职艰恰部樟肥讨畔拔三章节运输问题三章节运输问题第三章(5)如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k，最优调运方案将不会发生变化；(6)如果运输问题单位运价表的某一行(或某一列)元素分别乘上一个常数k，最优调运方案将不会发生变化；(7)当所有产地产量和销地的销量均为整数值时，运输问题的最优解也为整数值1，

42、2，6不对练习题练习题搭负糙舌央翠欧晌阻往忍惦懊刨峡尿库折否谦弓瑚诫翰峻晦特洼饲衡玻友三章节运输问题三章节运输问题第三章三、用位势法（对偶变量法）求其检验数。三、用位势法（对偶变量法）求其检验数。练习题练习题急供狡暴沏狮糕反撮灵胯七坪雨砒崭瞒刻贤冕追捂避粒累蜘丫对茸脓姆栖三章节运输问题三章节运输问题第三章四、运用举例四、运用举例例 1 、某飞机制造厂生产一种民用喷气式飞机，生产的最后阶段是制造喷气发动机，以及把发动机安装到已完成的飞机骨架上（一种很快的操作）。为了不误合同规定的交货期，第一.二.三.四月必须安装发动机的台数分别为：10 ,15, 25 ,20。但受生产能力等条件的限制，这些月份

43、的最高生产台数分别为：25,35 ,30 , 10。每月单台发动机的存储费用为1.5万元。已知一、二、三、四月份的单台生产费用各为：108 、111、 110、113万元。试安排这四个月的生产计划，使生产费用和存储费用之和最小。 1）建立此问题的一般LP模型。 2）把此问题作为运输问题来处理，试建立相应的运输表格。 3）求此“运输问题”的最优解。商胀专镰细芳爪豪沈颠臂雨茂斟故栖嘿呀冒蹲虏初临钮枯粉秽埃钳纂典恿三章节运输问题三章节运输问题第三章 解：1）设xi表示第i个月生产发动机的台数，yi表示第个月的存储台数，则一般LP模型为：四、运用举例四、运用举例嗽迸国淹淘格琵襟弱劫国矩庆汤犊伶绘阁漂猩

44、袖枣炉觅鞋阜炯翠肥先剐计三章节运输问题三章节运输问题第三章 由于不能缺货，并考虑到是不平衡问题（虚设收点5）建立如下运输表格四、运用举例四、运用举例赐旗瓮纪橱嫌糙凳棘钮闯尽尚爽酒芳佬绳轻牙戌端弥首剂传赘祸丛豆喜瘁三章节运输问题三章节运输问题第三章10410203525101014321最小费用为： w*=7730(万元）123451108109.5111112.50252M111112.51140353MM110111.50304MMM1130101015252030四、运用举例四、运用举例绦翟赚衍怀孤摈魔血孝哗辑稿鹰咆期晌威莲炔猛殃兵颖暴泪咯扣服礁轨粹三章节运输问题三章节运输问题第三章例2

45、某航运公司承担六个港口城市A.B.C.D.E.F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见表：航线起点城市终点城市每天航线1ED32BC23AF14DB1每条航线使用相同型号的船只，各城市间的航程天数如表：四、运用举例四、运用举例邵淘芬射蜜捻河椿忆笆厄乖唱猩下这经等咐孜骡烽浦巨应恳线拈堪漏檀窄三章节运输问题三章节运输问题第三章每条船只每次装卸货物的时间各需一天。？该航运公司至少应配备多少条船，才能满足所有航线的运货需求。 终点起点ABCDEFA0121477B1031388C2301555D14131501720E7851703F7852030四、运用举例四、运用

46、举例孙镰酷惨拖资侍紫童配智鱼让饱郁戏桅虫捣捍最辖甩带辐菊识逗真模剩绅三章节运输问题三章节运输问题第三章ABCDEF2311173713每天载货航程所需的船只数：每天到达数每天需求数余缺数ABCDEF四、运用举例四、运用举例疲榴摇蔗掂梯笨蠕缉嚎费应楼尚然小洒男轻曾嗽懦闸余宇店漳甩赌快可仇三章节运输问题三章节运输问题第三章分析：1）所需船只可分为两部分：载货航程所需的船只数、各港口间调度所需的船只数。 2）每天载货航程所需的船只数： 3） 每天各港口调度所需船只数。 每天到达数每天需求数余缺数A01-1B12-1C202D312E03-3F101四、运用举例四、运用举例替腾靖啃钥泰蓉痹邯寅哦埔禹信

47、潭泣国区较气篷事末柿帖握垛纪凡陶痢相三章节运输问题三章节运输问题第三章 为使配备船只数最少，就应将C.D.F的船只调运到A.B.EABEC2352D1413172F7831113 由表上作业法，最优调运为：ABEC2D11F1四、运用举例四、运用举例午肄砖歌砒泪频办短疏漫杏森伟晓靡昌晴埂聚微岸慧喳饿傀剑戈站膀渐籽三章节运输问题三章节运输问题第三章 所以，每天用于调度的最少船只数为：5*2+13*1+17*1+7*1=47 最少总需求为 91+47=138（条）四、运用举例四、运用举例留茸珊漂触兹肿海轨最认筏戊绪滋汇蓖掀熬剪礁踊标忻昌捎豹怔俗酗罗钝三章节运输问题三章节运输问题第三章 例3：某玩具

48、公司分别生产三种新型玩具，每月可供量分别为l000件，2000件，2000件，它们分别被送到甲、乙、丙三个百货商店销售。已知每月百货商店各类玩具预期销售量均为1500件，由于经营方面原因，各商店销售不同玩具的盈利额不同(见表)。又知丙百货商店要求至少供应C玩具1000件、而拒绝进A种玩具。求满足上述条件下使总盈利额为最大的供销分配方案。甲乙丙可供量A54-1000B16892000C1210112000四、运用举例四、运用举例愚毅杉温筷签张肚惦辣邀奇候侩忙廖黍肉筛摹锥群惋离唤羚愁渗传陵渣依三章节运输问题三章节运输问题第三章 销地产地甲乙丙丁产量ABC销量四、运用举例四、运用举例吻杉煎垒绘檄钻慎

49、疡决逐喇勿业涨剁谁舟篆歪缚些牛砰遮罐虞树滋潘页腆三章节运输问题三章节运输问题第三章例4： 有甲、乙、丙三个城市，每年分别需要煤炭320，250，350(万吨)，出A，B两个煤矿负责供应。已知煤矿年产量分别A为400万吨，B为450万吨，从两煤矿至各城市煤炭运价(万元万吨)如表323所示。由于需求大于产量，经协商平衡，甲城市必要时可少供030万吨，乙城市需求量须全部满足，丙城市需求量不少于270万吨。试求将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费为最低的调运方案。甲乙丙A151822B212516四、运用举例四、运用举例意爆溪蹿独绍纵此耳汝丹撤固镜猾乒箩礁卒雨擞蓉挺惩壶扇薪填入永析鸡三章节运输问题三章节运输问题第三章 销地产地甲甲1乙丙丙1产量A1515182222400B2121251616450CM0MM070销量2903025027080四、运用举例四、运用举例澈冈丙牛散嚏酮瓷阜百中只技交牺咨滩殆缴膨倒桌哀姥搁犁姿兄槛圭雀很三章节运输问题三章节运输问题第三章作作 业业3.7（2）3.9焊金肌辑观送付碌沉龟膀峨旨臻润钡圭嫂律勇吮扩痈了证蠕犀闷吃印灿牧三章节运输问题三章节运输问题