Ch运输问题实用教案

《Ch运输问题实用教案》由会员分享，可在线阅读，更多相关《Ch运输问题实用教案（246页珍藏版）》请在金锄头文库上搜索。

1、一、运输(ynsh)问题的数学模型第1页/共245页第一页，共246页。 问题(wnt)的提出 在许多大型连锁超市的商品(shngpn)供应, 物流公司的物资供应都牵涉到众多货物的运输(ynsh)问题. 这些问题最终都面临一个如何降低货物运输成本的问题. 该问题可用下面的方式加以描述:第2页/共245页第二页，共246页。 问题(wnt) 设有某种物资, 该物资共有 个产地, 产地 的产量的需求量为 且产量和需求量为相等. 分析 一个合适的运输方案即是要确定从第 个产地为 该物资另有 个销售点, 销售点从产地 到销售点 的单位运输成本为 求一个运输方案(fng n), 使总运输费用为最小.到第

2、 个需求点 的物资供应量. 假设供应量为 则第3页/共245页第三页，共246页。问题(wnt)的约束条件为而相应(xingyng)的总运输成本为第4页/共245页第四页，共246页。从而(cng r)得到问题的数学模型第5页/共245页第五页，共246页。例1 试对下面的运输问题(wnt)建立相应的数学模型.20055655030需求量需求量60158610408104121002012614产量产量销地销地产地产地第6页/共245页第六页，共246页。解 由前面的讨论容易(rngy)得到相应的数学模型:第7页/共245页第七页，共246页。第8页/共245页第八页，共246页。注: 前面所

3、讨论的是产销平衡(pnghng)的运输问题. 若产销不平衡时, 相应的模型(mxng)将分为产大于销或销大于产的运输问题. 当产大于销时, 则问题(wnt)的模型为:第9页/共245页第九页，共246页。而当需求量大于供应量时, 相应(xingyng)的模型为第10页/共245页第十页，共246页。二、表上作业(zuy)法第11页/共245页第十一页，共246页。 在上面(shng min)的例中可以看到: 运输问题的数学模型最终归结为一个线性规划(xin xn u hu)的模型, 并可用相应的解法加以求解,但即使是一个简单的运输(ynsh)问题, 涉及到的变量也是比较多的, 因而求解也较为困

4、难. 这里将介绍一种新的解法:表上作业法.第12页/共245页第十二页，共246页。 表上作业(zuy)法的求解步骤: 求出一个(y )初始可行解; 判定(pndng)当前解是否为最优解; 解的调整.第13页/共245页第十三页，共246页。 求初始(ch sh)基可行解 1.西北角法 用西北角法求运输问题的初始(ch sh)解的要点是: 从西北角开始按最大可能进行(jnxng)分配, 直到完成所有分配.第14页/共245页第十四页，共246页。例2 用西北角法求下面(xi mian)运输问题的初始解.销地销地产地产地1234产量产量132765002752360031546300需求量需求量

5、600400200200第15页/共245页第十五页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200解 由西北角法, 首先分配 得500100第16页/共245页第十六页，共246页。再对第二列及第三列进行(jnxng)分配, 即有下表销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200500100400100第17页/共245页第十七页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量6004

6、00200200500100400100100200最后对第三行进行(jnxng)分配, 得下表,第18页/共245页第十八页，共246页。由此得初始(ch sh)解为此时(c sh)对应的运输成本为 第19页/共245页第十九页，共246页。注 1.用西北角法所得到问题的解与表中的单位(dnwi)运输成2.在表格中, 凡填入数据的单元 称为基变量, 否则称3.基变量的个数应 当等式不成立时, 则称该本无关, 因而(yn r)该解一般与最优解的距离较“远”;为非基变量(binling).解是退化的. 对退化问题, 需要虚拟基变量来补充基变量的个数, 其取值为0.第20页/共245页第二十页，共

7、246页。例3 用西北角法求下面(xi mian)问题的初始解销地销地产地产地1234产量产量131131072192843741059需求量需求量385420第21页/共245页第二十一页，共246页。解 由西北角法, 容易(rngy)得到问题的初始解销地销地产地产地1234产量产量131131072192843741059需求量需求量38542034454第22页/共245页第二十二页，共246页。即: 问题(wnt)的初始解为并注意(zh y)到该解是退化的. 此时可令来增加(zngji)基变 量的个数.第23页/共245页第二十三页，共246页。 2.最小元素(yun s)法 最小元素

8、法的基本想法是: 按最小成本(chngbn)进行分配.第24页/共245页第二十四页，共246页。例4 用最小元素(yun s)法求下面运输问题的初始解.销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200第25页/共245页第二十五页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200300解 由最小元素法, 最小成本为 故第26页/共245页第二十六页，共246页。剩下的最小成本分别为销地销地产地产地1234产量产量13276500275236003

9、1546300需求量需求量600400200200300400200第27页/共245页第二十七页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200300400200最后有100200200第28页/共245页第二十八页，共246页。由此得到问题(wnt)的初始解此时(c sh)对应的运输成本为第29页/共245页第二十九页，共246页。例5 用最小元素法求下面运输(ynsh)问题的初始解.销地销地产地产地1234产量产量131131072192843741059需求量需求量385420第30页/共245页第三十页

10、，共246页。解 由最小元素(yun s)法得:销地销地产地产地1234产量产量131131072192843741059需求量需求量385420314831第31页/共245页第三十一页，共246页。即: 初始(ch sh)解为第32页/共245页第三十二页，共246页。 最优解的判定(pndng) 为判断当前解是否(sh fu)为最优解, 需要建立相应的位势. 若 为基变量, 则有因基变量的个数为 故令 由此得到所有为此定义(dngy)位势 的位势.第33页/共245页第三十三页，共246页。例6 求下面(xi mian)运输问题的初始解所对应的位势.销地销地产地产地1234产量产量132

11、765001004002752360020020020031546300300需求量需求量600400200200第34页/共245页第三十四页，共246页。解 由位势的定义, 及 是基变量, 由此得到 同样有得 再由 及 得 同理即有下表:又可得其它(qt)位势:第35页/共245页第三十五页，共246页。销地销地产地产地1234产量产量132765001004002752360020020020031546300300需求量需求量600400200200第36页/共245页第三十六页，共246页。例7 求下面运输(ynsh)问题的初始解所对应的位势销地销地产地产地1234产量产量13113

12、1074321928431374105981需求量需求量385420第37页/共245页第三十七页，共246页。解 由位势的定义可分别(fnbi)得到第38页/共245页第三十八页，共246页。销地销地产地产地1234产量产量131131072192843741059需求量需求量385420314831第39页/共245页第三十九页，共246页。 下面的例子说明对退化问题的处理(chl)方式第40页/共245页第四十页，共246页。例8 求下面运输问题(wnt)的初始解所对应的位势销地销地产地产地1234产量产量13113107342192844374105954需求量需求量385420第41

13、页/共245页第四十一页，共246页。解 由位势(wi sh)的定义可分别得到第42页/共245页第四十二页，共246页。销地销地产地产地1234产量产量13113107342192844374105954需求量需求量385420第43页/共245页第四十三页，共246页。此时(c sh), 因基变量的个数计算下去. 为此(wi c), 虚拟基变量势:故位势无法(wf)再继续再进一步计算位第44页/共245页第四十四页，共246页。销地销地产地产地1234产量产量131131072192843741059需求量需求量38542034454第45页/共245页第四十五页，共246页。 由位势,

14、再定义影响系数 其定义关系为: 若 为非基变量(binling), 则第46页/共245页第四十六页，共246页。例9 对下面(xi mian)问题求相应的影响系数.第47页/共245页第四十七页，共246页。645132576723200200400600需求量需求量300360025001产量产量4321销地销地产地产地300400200100200200第48页/共245页第四十八页，共246页。解 因 为非基变量, 由影响系数的定义, 有第49页/共245页第四十九页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量6004002

15、00200300400200100200200第50页/共245页第五十页，共246页。 最优解判定(pndng)方法 当前解是最优解第51页/共245页第五十一页，共246页。 解的调整(tiozhng) 若当前(dngqin)解不是最优解, 则要进行适当的解的调整, 以 1.确定进基变量 : 2.对当前进基变量 构造一条闭回路:降低运输(ynsh)费用. 其具体步骤为第52页/共245页第五十二页，共246页。 闭回路(hul): 从当前非基变量出发, 以直线方式向前（后, 注意(zh y)到在闭回路上, 除出发顶点外, 其余顶点均为基左, 右）前进, 遇到(y do)某一个基变量变向,

16、直到回到起点.变量顶点.第53页/共245页第五十三页，共246页。常见(chn jin)的几种闭回路形式第54页/共245页第五十四页，共246页。 3.在闭回路上确定最大调整量 首先在闭回路上给各顶点以编号(bin ho): 出发顶点标号为0, 依次类推(litu). 例如在下面的回路中, 各个顶点的编号为:第55页/共245页第五十五页，共246页。 最大调整量 闭回路上编号为奇数顶点的最小运输 例如在下面(xi mian)问题中, 则最大调整量量.第56页/共245页第五十六页，共246页。 4.求出新解 在闭回路上进行解的调整: 偶数顶点+ 奇数顶点第57页/共245页第五十七页，共

17、246页。 由此得到求解运输(ynsh)问题的具体方法: 1.求出问题的初始解（一般(ybn)用最小元素法）; 2.求出位势及影响(yngxing)系数, 从而判定是否为最优解; 3.若不是最优解, 则进行解的调整; 4.重新进行判定.第58页/共245页第五十八页，共246页。例10 求下面运输(ynsh)问题的最小成本解销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200第59页/共245页第五十九页，共246页。解 由西北角法得到(d do)问题的初始解:销地销地产地产地1234产量产量1327650027523600315

18、46300需求量需求量600400200200500100400100100200第60页/共245页第六十页，共246页。再求出相应(xingyng)的位势及影响系数.第61页/共245页第六十一页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200500100400100100200第62页/共245页第六十二页，共246页。即有下表第63页/共245页第六十三页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量60040020020050010040010

19、0100200第64页/共245页第六十四页，共246页。由于 是最小的负数, 故以 为进基变量, 构即造闭回路(hul): 第65页/共245页第六十五页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200500100400100100200第66页/共245页第六十六页，共246页。由此得最大调整量 从而得到新解. 注意到该解是退化的, 因而需要虚拟基变量: 令并进一步计算位势(wi sh)和影响系数: 第67页/共245页第六十七页，共246页。销地销地产地产地1234产量产量13276500275236003

20、1546300需求量需求量600400200200500100400100100200第68页/共245页第六十八页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量6004002002005001004002002000第69页/共245页第六十九页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量6004002002005001004002002000第70页/共245页第七十页，共246页。最小影响(yngxing)系数为闭回路(hul)为:最大调整量 即有第71页/共245页

21、第七十一页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量6004002002005001004002002000第72页/共245页第七十二页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量6004002002005001004002002000第73页/共245页第七十三页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量6004002002005001004002002000第74页/共245页第七十四页，共246页。

22、最小影响(yngxing)系数为构造(guzo)闭回路:第75页/共245页第七十五页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量6004002002005001004002002000第76页/共245页第七十六页，共246页。最大调整量 由此得到新解:第77页/共245页第七十七页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量6004002002005001004002002000第78页/共245页第七十八页，共246页。销地销地产地产地1234产量产量1327650

23、03002002752360020020020031546300300需求量需求量600400200200第79页/共245页第七十九页，共246页。再一次计算位势和影响(yngxing)系数, 得第80页/共245页第八十页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200300300200200200200第81页/共245页第八十一页，共246页。由于 故当前解为最优解, 最优解值第82页/共245页第八十二页，共246页。注 由于在上题的解题中的初始解是通过(tnggu)西北角法得到的, 因而求解过程比较烦

24、琐(fn su). 下面我们用最小元素法求解该问题(wnt).第83页/共245页第八十三页，共246页。例11 求下面问题(wnt)的最小成本解销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200第84页/共245页第八十四页，共246页。解 由最小元素法得问题(wnt)的初始解销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200300400200100200200第85页/共245页第八十五页，共246页。进一步求出位势及影响(yngxing)系数:第86页/共2

25、45页第八十六页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200300400200100200200第87页/共245页第八十七页，共246页。最小影响系数为 闭回路为最大调整量 由此得到新解:第88页/共245页第八十八页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求量需求量600400200200300400200100200200第89页/共245页第八十九页，共246页。销地销地产地产地1234产量产量132765002752360031546300需求

26、量需求量600400200200300300200200200200第90页/共245页第九十页，共246页。注意到该解即为用西北角法求解过程(guchng)中所得到的最优解. 此例说明用最小元素法所得到(d do)的初始解一般情况下比用西北角法得到的初始解更为(n wi)优越.第91页/共245页第九十一页，共246页。例12 求下面运输(ynsh)问题的最小成本解.销地销地产地产地1234产量产量137641522432123438513需求量需求量111010940第92页/共245页第九十二页，共246页。销地销地产地产地1234产量产量137641522432123438513需求量

27、需求量111010940解 由最小元素法得到(d do)问题的初始解:11178103第93页/共245页第九十三页，共246页。对此初始解, 再求相应的位势和影响(yngxing)系数:第94页/共245页第九十四页，共246页。销地销地产地产地1234产量产量13764157822432121113438513103需求量需求量111010940第95页/共245页第九十五页，共246页。最小影响(yngxing)系数即有下表:闭回路(hul)为第96页/共245页第九十六页，共246页。销地销地产地产地1234产量产量13764157822432121113438513103需求量需求量

28、111010940第97页/共245页第九十七页，共246页。最大调整量为 由此得到新解销地销地产地产地1234产量产量13764157822432121113438513103需求量需求量111010940第98页/共245页第九十八页，共246页。10358344234825410673409101011需求量需求量133122151产量产量4321销地销地产地产地第99页/共245页第九十九页，共246页。计算相应的位势(wi sh)及影响系数:第100页/共245页第一百页，共246页。销地销地产地产地1234产量产量13764151052243212843438513310需求量需求

29、量111010940第101页/共245页第一百零一页，共246页。最小影响系数 取 为进基变量, 则闭回最大调整量为 由此得到新解:路为第102页/共245页第一百零二页，共246页。销地销地产地产地1234产量产量13764151052243212843438513310需求量需求量1110109404第103页/共245页第一百零三页，共246页。销地销地产地产地1234产量产量1376415692243212843438513310需求量需求量111010940第104页/共245页第一百零四页，共246页。再计算(j sun)位势及影响系数:第105页/共245页第一百零五页，共24

30、6页。销地销地产地产地1234产量产量1376415692243212843438513310需求量需求量111010940第106页/共245页第一百零六页，共246页。最小影响系数 取 为进基变量, 则闭回路为最大调整量为第107页/共245页第一百零七页，共246页。销地销地产地产地1234产量产量1376415692243212843438513310需求量需求量111010940第108页/共245页第一百零八页，共246页。销地销地产地产地1234产量产量13764156922432122103438513310需求量需求量111010940第109页/共245页第一百零九页，共2

31、46页。进一步计算位势和影响(yngxing)系数第110页/共245页第一百一十页，共246页。销地销地产地产地1234产量产量13764156922432122103438513310需求量需求量111010940第111页/共245页第一百一十一页，共246页。最小影响系数 回路最大调整量为 从而得到新解:第112页/共245页第一百一十二页，共246页。销地销地产地产地1234产量产量13764156922432122103438513310需求量需求量1110109402第113页/共245页第一百一十三页，共246页。销地销地产地产地1234产量产量1376415872243212

32、1023438513310需求量需求量111010940第114页/共245页第一百一十四页，共246页。计算(j sun)位势和影响系数, 得第115页/共245页第一百一十五页，共246页。销地销地产地产地1234产量产量13764158722432121023438513310需求量需求量111010940第116页/共245页第一百一十六页，共246页。因 故当前解为最优解, 且最小成本为 第117页/共245页第一百一十七页，共246页。例13 求解下面的运输(ynsh)问题:销地销地产地产地1234产量产量1347128251357395285需求量需求量549220第118页/共

33、245页第一百一十八页，共246页。解 由最小元素(yun s)法得初始解:销地销地产地产地1234产量产量1347128251357395285需求量需求量549220453512第119页/共245页第一百一十九页，共246页。计算(j sun)位势, 得销地销地产地产地1234产量产量1347128512251357433952855需求量需求量549220第120页/共245页第一百二十页，共246页。此时最小影响系数 回路为最大调整量 由此得到新解第121页/共245页第一百二十一页，共246页。销地销地产地产地1234产量产量1347128512251357433952855需求量

34、需求量549220第122页/共245页第一百二十二页，共246页。销地销地产地产地1234产量产量1347128512251357433952855需求量需求量5492202第123页/共245页第一百二十三页，共246页。销地销地产地产地1234产量产量1347128532513574123952855需求量需求量549220第124页/共245页第一百二十四页，共246页。再计算(j sun)位势和影响系数, 得第125页/共245页第一百二十五页，共246页。销地销地产地产地1234产量产量1347128532513574123952855需求量需求量549220第126页/共245页

35、第一百二十六页，共246页。此时最小影响系数 回路为最大调整量 由此得到新解第127页/共245页第一百二十七页，共246页。销地销地产地产地1234产量产量1347128532513574123952855需求量需求量549220第128页/共245页第一百二十八页，共246页。销地销地产地产地1234产量产量1347128532513574123952855需求量需求量5492203第129页/共245页第一百二十九页，共246页。销地销地产地产地1234产量产量1347128532513571423952855需求量需求量549220第130页/共245页第一百三十页，共246页。再计算

36、(j sun)位势和影响系数, 得第131页/共245页第一百三十一页，共246页。销地销地产地产地1234产量产量1347128532513571423952855需求量需求量549220第132页/共245页第一百三十二页，共246页。因 故当前解为最优解, 且最小成本为 第133页/共245页第一百三十三页，共246页。三、几类特殊的运输(ynsh)问题第134页/共245页第一百三十四页，共246页。 在前面所讨论的是产销平衡的运输问题, 实际(shj)工作中遇到(y do)的更多的是产销不平衡的运输问题. 由于在处理中是把产销不平衡的运输(ynsh)问题化为产销平衡的运输(ynsh)

37、问题加以解决, 故本段中我们将其归为特殊的运输问题来解决.第135页/共245页第一百三十五页，共246页。 1.产销不平衡(pnghng)的运输问题 产大于销的运输(ynsh)问题 设运输问题中, 产量(chnling)总和大于需求量的总和, 即有为此, 虚拟需求点 需求量为第136页/共245页第一百三十六页，共246页。运输成本均为 从而将问题转化为产销平衡的问题(wnt).第137页/共245页第一百三十七页，共246页。销地销地产地产地123产量产量1295352461015需求量需求量1510155040例14 求解(qi ji)运输问题第138页/共245页第一百三十八页，共24

38、6页。解 虚拟(xn)第四个需求点, 由此得下表销地销地产地产地1234产量产量129503524610015需求量需求量1510151050第139页/共245页第一百三十九页，共246页。由最小元素(yun s)法, 容易得到问题的初始解:销地销地产地产地1234产量产量129503524610015需求量需求量1510151050计算位势和影响(yngxing)系数得:101015105第140页/共245页第一百四十页，共246页。销地销地产地产地1234产量产量129503515101024610015105需求量需求量1510151050第141页/共245页第一百四十一页，共24

39、6页。最小影响系数 回路最大调整量 由此得到新解第142页/共245页第一百四十二页，共246页。销地销地产地产地1234产量产量129503515101024610015105需求量需求量15101510505第143页/共245页第一百四十三页，共246页。销地销地产地产地1234产量产量12950351515524610015105需求量需求量1510151050第144页/共245页第一百四十四页，共246页。相应的位势(wi sh)和影响系数为销地销地产地产地1234产量产量12950351515524610015105需求量需求量1510151050第145页/共245页第一百四十

40、五页，共246页。因 故当前解为最优解, 且最小成本为 第146页/共245页第一百四十六页，共246页。 销大于产的运输(ynsh)问题为此, 虚拟产地 产量为 设运输问题(wnt)中, 需求量总和大于产量的总和, 即有运输成本均为的问题(wnt).从而将问题转化为产销平衡第147页/共245页第一百四十七页，共246页。例15 求下面(xi mian)运输问题的最小费用解.销地销地产地产地123产量产量18561202151012803391080需求量需求量1407090 280300第148页/共245页第一百四十八页，共246页。解 由前面讨论, 虚拟产地 产量为则有下表:第149页

41、/共245页第一百四十九页，共246页。销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300第150页/共245页第一百五十页，共246页。由最小元素法得问题的初始(ch sh)解, 并计算位势和影响系数第151页/共245页第一百五十一页，共246页。销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300 208070504040第152页/共245页第一百五十二页，共246页。销地销地产地产地123产量产量185612021510128033910804MM

42、M20需求量需求量1407090300 208070504040第153页/共245页第一百五十三页，共246页。最小影响系数 回路最大调整量 由此得到新解第154页/共245页第一百五十四页，共246页。销地销地产地产地123产量产量1856120407010215101280803391080804MMM2020需求量需求量1407090300第155页/共245页第一百五十五页，共246页。销地销地产地产地123产量产量1856120407010215101280803391080804MMM2020需求量需求量1407090300第156页/共245页第一百五十六页，共246页。最小影

43、响系数 回路最大调整量 由此得到新解:第157页/共245页第一百五十七页，共246页。销地销地产地产地123产量产量1856120408021510128070103391080804MMM2020需求量需求量1407090300第158页/共245页第一百五十八页，共246页。销地销地产地产地123产量产量1856120408021510128070103391080804MMM2020需求量需求量1407090300第159页/共245页第一百五十九页，共246页。因 故当前解为最优解, 且最小成本为 第160页/共245页第一百六十页，共246页。 注: 在上题中, 若先分配(fnpi

44、)由此得到(d do)初始解:第161页/共245页第一百六十一页，共246页。销地销地产地产地123产量产量1856120507021510128060203391080804MMM2020需求量需求量1407090300第162页/共245页第一百六十二页，共246页。再计算(j sun)相应的位势, 有第163页/共245页第一百六十三页，共246页。销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300 208050702060第164页/共245页第一百六十四页，共246页。最小影响(yngxing)系数为闭回路(hu

45、l)为第165页/共245页第一百六十五页，共246页。销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300 208050702060第166页/共245页第一百六十六页，共246页。此时最大调整量为20, 继续迭代, 所得到(d do)的解即为前面解法(ji f)中的初始解.第167页/共245页第一百六十七页，共246页。销地销地产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300 208050702060第168页/共245页第一百六十八页，共246页。销地销地

46、产地产地123产量产量185612021510128033910804MMM20需求量需求量1407090300 208070504040第169页/共245页第一百六十九页，共246页。 2.存在无通行路的运输(ynsh)问题 所谓存在无通行路的运输(ynsh)问题是指在一个运输(ynsh)问题中, 分析: 对所给条件, 为使 不能成为基变量, 可使相产地 与需求点 之间不存在相应的运输线路. 在此种情况下, 求运输(ynsh)方案.应的运输成本为最大的. 为此可设 再由前面所提供的方法求出最优解.第170页/共245页第一百七十页，共246页。例16 求解(qi ji)下面的运输问题:销地

47、销地产地产地1234产量产量17654502973650387350需求量需求量20403060150第171页/共245页第一百七十一页，共246页。销地销地产地产地1234产量产量1765450297365038M7350需求量需求量20403060150解 由最小元素(yun s)法得初始解5010304020第172页/共245页第一百七十二页，共246页。注意(zh y)到该解是退化的, 故需虚拟基变量. 但基变量需在求位势(wi sh)的过程中加以解决. 先求位势(wi sh):第173页/共245页第一百七十三页，共246页。销地销地产地产地1234产量产量17654504010

48、2973650203038M735050需求量需求量20403060150第174页/共245页第一百七十四页，共246页。此时, 位势计算中断, 问题(wnt)在于初始解退化. 为此, 虚拟基变量, 令 则有第175页/共245页第一百七十五页，共246页。销地销地产地产地1234产量产量1765450401029736502003038M735050需求量需求量20403060150第176页/共245页第一百七十六页，共246页。此时最小影响系数 回路为最大调整量 由此得到新解第177页/共245页第一百七十七页，共246页。销地销地产地产地1234产量产量176545020201029

49、73650203038M735050需求量需求量20403060150第178页/共245页第一百七十八页，共246页。计算位势(wi sh)和影响系数后得:第179页/共245页第一百七十九页，共246页。销地销地产地产地1234产量产量17654502020102973650203038M735050需求量需求量20403060150第180页/共245页第一百八十页，共246页。因 故当前解为最优解, 且最小成本为 第181页/共245页第一百八十一页，共246页。例17 有三个化肥厂供应四个地区农用化肥. 假设(jish)等量的化肥在这些地区使用(shyng)效果相同. 各化肥厂的年产

50、量, 各地区的需要量和各厂到各地的单位运价(yn ji)如下表所示, 求总运费最省的调运方案.第182页/共245页第一百八十二页，共246页。不限不限307050最高需求最高需求1007030最低需求最低需求50_23201936015191314250172213161产量产量4321 地区地区化肥厂化肥厂第183页/共245页第一百八十三页，共246页。解 此为产销不平衡的运输(ynsh)问题. 总产量为160, 四个地区(dq)的最低需求量为110, 最高需求量可以设为210. 因而是需求量大于产量(chnling)的问题. 为此虚设工厂. 再注意到各地区的需求量分为两部分, 一部分是

51、必须满足的, 另一部分是可以不满足的. 由此产生表格.第184页/共245页第一百八十四页，共246页。0M0M0MMM23201919151519171722131613141416210501030702030504503602501443211第185页/共245页第一百八十五页，共246页。 注意(zh y)对表中第四行中单位成本的理解. 由最小元素法得到问题(wnt)的初始解:第186页/共245页第一百八十六页，共246页。11234411616132217175050214141319151560301020319192023MM501010304M0M0M05030203020

52、70301050210第187页/共245页第一百八十七页，共246页。11234411616132217175050214141319151560301020319192023MM501010304M0M0M0503020302070301050210第188页/共245页第一百八十八页，共246页。再计算(j sun)相应的影响系数:第189页/共245页第一百八十九页，共246页。此时 为进基变量, 由此得新解第190页/共245页第一百九十页，共246页。11234411616132217175050214141319151560301020319192023MM501030104M0

53、M0M3005020302070301050210第191页/共245页第一百九十一页，共246页。再一次计算(j sun)位势和影响系数有第192页/共245页第一百九十二页，共246页。11234411616132217175050214141319151560301020319192023MM501010304M0M0M0503020302070301050210第193页/共245页第一百九十三页，共246页。再计算相应的影响(yngxing)系数以 为进基变量, 则有新解第194页/共245页第一百九十四页，共246页。11234411616132217175050214141319

54、151560302010319192023MM5020304M0M0M0503020302070301050210第195页/共245页第一百九十五页，共246页。经过数次换基后得到(d do)问题的最优解:第196页/共245页第一百九十六页，共246页。 4.具有(jyu)中转站的运输问题 某类物资有 个产地, 产地 的产地为对该类物资有 个需求点, 第 个需求点的需求量为 从产地到达需求点都需经过 个中转站中的某个中转站. 启动第 个中转站将发生固定费用相应(xingyng)的单位费用(fi yong)分别为 求运输方案, 使总运费为最小.中转站的最大转运量为第197页/共245页第一百

55、九十七页，共246页。 引入 变量 表示启用第 个中转站,表示经过从 个产地到第 个中转站及从第 个中转站到第 个需求点的运输量, 则问题的目标函数为产量(chnling)限制:第198页/共245页第一百九十八页，共246页。 中转站能力(nngl)限制:需求量限制(xinzh)： 供需平衡限制(xinzh):第199页/共245页第一百九十九页，共246页。 由此得到(d do)该问题的数学模型:第200页/共245页第二百页，共246页。第201页/共245页第二百零一页，共246页。第202页/共245页第二百零二页，共246页。四、指派(zhpi)问题第203页/共245页第二百零三

56、页，共246页。 1.指派(zhpi)问题的数学模型 问题 设有 项工作, 交给 个人去完成. 每个人只能 如此的问题(wnt)即称为指派问题(wnt).完成(wn chng)其中的一项. 又每人完成(wn chng)其中任何一项工作的代价为已知, 求这样的任务分配方案, 使完成这些工作的总代价为最小.第204页/共245页第二百零四页，共246页。 以 表示第 人完成第 项工作所需的代价, 由此得 如此的矩阵称为(chn wi)指派问题中的代价矩阵.到矩阵(j zhn):第205页/共245页第二百零五页，共246页。 引入决策变量 :第 人完成第 项工作;第 项工作由其他人完成.由此得到矩

57、阵 注意到: 由于每项工作只能由一人(y rn)完成及每人只能完成一项工作, 故在矩阵中每行和每列只能(zh nn)有一个1, 其余均为0. 如此的矩阵(j zhn)称为指派问题中的指派矩阵(j zhn).第206页/共245页第二百零六页，共246页。例17 设指派问题中的代价(diji)矩阵为则下列(xili)矩阵 第207页/共245页第二百零七页，共246页。均为指派矩阵, 其代价分别为 而矩阵则不是(b shi)指派矩阵. 所谓求解指派(zhpi)问题的最小值解, 即为求解这样的矩阵, 使对应(duyng)的代价为最小.第208页/共245页第二百零八页，共246页。 分析(fnx)

58、 条件: 矩阵中每行每列的元素只有一个(y )是1, 其余均为行:列:零的数学(shxu)表达式为:第209页/共245页第二百零九页，共246页。由此得到(d do)问题的模型为:而相应(xingyng)的代价为第210页/共245页第二百一十页，共246页。第211页/共245页第二百一十一页，共246页。 2.指派问题(wnt)的求解方法 设代价矩阵为 我们用下面的方法求其最 每行减去该行的最小数; 每列减去该列的最小数;每行每列至少一个零. 判断是否有 个独立的零, 若有, 则在指派矩阵中, 小值解:相应元素(yun s)取1, 其余为0.第212页/共245页第二百一十二页，共246

59、页。 所谓有 个独立的零, 即指这些零应分布在不同的行判断(pndun)方法: 用最少的横线和竖线将所有的零划去, 若最列上.少的线数为 则一定有 个独立的零.第213页/共245页第二百一十三页，共246页。例18 求下面指派(zhpi)问题中的最小值解.解行列第214页/共245页第二百一十四页，共246页。注意到在最后(zuhu)表中, 每行每列都有零的存在. 在下面(xi mian)矩阵中, 选独立的零:则问题的最优解为 其余即相应(xingyng)的指派矩阵为第215页/共245页第二百一十五页，共246页。最小代价(diji)为第216页/共245页第二百一十六页，共246页。例1

60、9 求下面(xi mian)指派问题的最小值解:解行列第217页/共245页第二百一十七页，共246页。注意(zh y)到, 对表可以用3条线将所有(suyu)的零划去, 因而没有4个独立的零.对此我们有下面的迭代(di di)次序:第218页/共245页第二百一十八页，共246页。在所有(suyu)未划去的数中找最小数;未划去的数减去该数;交叉点加上该数, 其余(qy)不变;继续(jx)判定.在上例中:第219页/共245页第二百一十九页，共246页。最小数为2, 由此得:此时(c sh)有4个独立的零, 因而(yn r)最优解为 第220页/共245页第二百二十页，共246页。其余 最小代

61、价为注意(zh y)到该问题的最优解是不唯一的. 但最小值相同.第221页/共245页第二百二十一页，共246页。例20 求指派(zhpi)问题的最小值解:解行列第222页/共245页第二百二十二页，共246页。最小数为2, 继续(jx)迭代最优解为 其余 最小第223页/共245页第二百二十三页，共246页。代价(diji)为第224页/共245页第二百二十四页，共246页。 3.两类特殊的指派(zhpi)问题 的指派问题 所谓 的指派问题是指工作数与工人数不相等的指派问题. 相应的解决方法(fngf)是虚拟工作数或工人数, 以达到平衡(pnghng). 相应的代价为0.第225页/共245

62、页第二百二十五页，共246页。例21 求下面(xi mian)指派问题的最小值解:解 此时 故添加0列. 有下表第226页/共245页第二百二十六页，共246页。再由列缩减(sujin)法, 得列第227页/共245页第二百二十七页，共246页。最小数为2, 继续(jx), 则有下表最小数为2, 继续(jx)迭代:第228页/共245页第二百二十八页，共246页。此时有 个独立的零. 选择独立的零:最优解为 最小成本为第229页/共245页第二百二十九页，共246页。 指派(zhpi)问题中的最大值解 在某些问题中, 代价矩阵中的元素表示(biosh)完成工作的收 矩阵 称为收益矩阵.益, 此

63、时(c sh)问题将转化为求相应的极大值问题.第230页/共245页第二百三十页，共246页。 问题(wnt) 求收益(shuy)矩阵中的最大值解. 解法(ji f) 令 记则代价矩阵 的最小值解即为原问题的最大值解.第231页/共245页第二百三十一页，共246页。例22 求下面(xi mian)指派问题的最大值解解 此时 故要添加零行, 即有第232页/共245页第二百三十二页，共246页。行最小数为2, 进一步有最小数=1第233页/共245页第二百三十三页，共246页。在最后一个(y )矩阵中, 有4个独立的零, 选择即原问题的最优解为 最大收益为第234页/共245页第二百三十四页，

64、共246页。 多任务要求的指派(zhpi)问题 在某些具体问题中, 当任务(rn wu)数大于人数时, 而工作又必须完成时, 则可通过虚拟第 人, 其代价为每个人中(rnzhng)最小的.第235页/共245页第二百三十五页，共246页。例23 求下面(xi mian)指派问题中的最小值解解 引入第236页/共245页第二百三十六页，共246页。则有第237页/共245页第二百三十七页，共246页。行列第238页/共245页第二百三十八页，共246页。最小数为1最小数为4,第239页/共245页第二百三十九页，共246页。此时(c sh)有5个独立的零: 最优解为第240页/共245页第二百四

65、十页，共246页。注意到 即第二人完成了两项工作.第241页/共245页第二百四十一页，共246页。 在可重复(chngf)情况下, 如何求相应的最大值解?第242页/共245页第二百四十二页，共246页。例24 求下面指派(zhpi)问题的最大值解第243页/共245页第二百四十三页，共246页。112344150260350450302070301050210第244页/共245页第二百四十四页，共246页。感谢您的观看(gunkn)！第245页/共245页第二百四十五页，共246页。内容(nirng)总结一、运输(ynsh)问题的数学模型。而当需求量大于供应量时, 相应的模型为。判定当前解是否为最优解。开始按最大可能进行分配, 直到完成所有分配.。再对第二列及第三列进行分配, 即有下表。本无关, 因而该解一般与最优解的距离较“远”。下面的例子说明对退化问题的处理方式。首先在闭回路上给各顶点以编号: 出发顶点标号为0,。例如在下面问题中, 则最大调整量。2.求出位势及影响系数, 从而判定是否为最优解。感谢您的观看第二百四十六页，共246页。