第二十二讲 运筹学模型（6）——运输模型（续）

yunjiang

　<b>情形1 产销平衡的运输问题</b>　　
　　3）方案转换——闭回路法
　　由λ<SUB>24</SUB>＜0，故令<I>x</I><SUB>24</SUB>进基，按产销平衡原则在相应的闭回路上进行调整。注意到基变量总数量<I>m</I>+<I>n</I>-1个，则应令原基变量组成员之一出基（取值为0）。易见，令<I>x</I><SUB>24</SUB>=min{该闭回路上偶数顶点运量}={1，3}=1，便知新基变量<I>x</I><SUB>24</SUB>取值为1，被保留下来的基变量为<I>x</I><SUB>13</SUB>=4+1=5，<I>x</I><SUB>14</SUB>=3－1=2，<I>x</I><SUB>21</SUB>=3，<I>x</I><SUB>32</SUB>=6，<I>x</I><SUB>34</SUB>=3，其余为非基变量，其中<I>x</I><SUB>23</SUB>=1－1=0为新增非基变量。
　　重新画一张表4－9，标上新基变量及其取值，便得新运输方案表，总运费为<I>z</I>=3×5+10×2+1×3+8×1+4×6+5×3=85（拾元）。
　　那么这个方案是否最优方案？返回2）步再检验即可。
　　　　　　　　　　　　　表4－9
　　<IMG src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image034.gif">
　　现求新方案中非基变量的检验数：
　　λ<SUB>11</SUB>=3－10+8－1=0，   　λ<SUB>12</SUB>=11－10+5－4＞0，
　　λ<SUB>22</SUB>=9－8+5－４＞0，    λ<SUB>31</SUB>=7－1+8－5＞0，
　　λ<SUB>33</SUB>=10－5+10－3＞0，   λ<SUB>23</SUB>=2－8+10－3＞0，
　　可见所有λ<SUB>ij</SUB>≥0，故表4－9所给方案已是最优方案，用运销图画在下面：
　　<IMG src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image035.gif">

yunjiang

<><B>　　</B>上面我们介绍了标准形运输问题模型的表上作业法。所谓标准型运输问题是指，目标函数为最小值类型，同时约束条件为等式，即所谓产销平衡情形。对于非标准形式是不能使用表上作业法求解的。为应用表上作业法，可先行通过化归为标准形式后再求解，具体说明如下：
　　<b>情形2  产销不平衡的运输问题</b>
　　设上一讲例子中的第二个销地的销量减少为4吨，其他数据不改变，试求该运输问题的最优方案。
　　我们还是用表格形式写出该模型如表4—10。
　　　　　　　　　　　表4—10   　　 单位：拾元/吨
　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image036.gif">
　　本问题为产＞销（供过于求）情形，为了化归为标准形式，可通过虚设一个销地B<SUB>0</SUB>，其销量为<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image010.gif">，相应运价均为零（因为这是个虚设的销地，各个产地都不可能往那里运货，运价自然为零），即可化为产销平衡问题。由此，便得到本问题的产销平衡表如表4—11。使用表上作业法求解得最优方案为：<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image012.gif">
</P>

yunjiang

　　　　　　　　　　表4—11   　　　　 单位：拾元/吨<B>　　</B>
　　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image037.gif">
　　注意： <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image018.gif"> 意味着产地 <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image020.gif"> 将有2吨的产品送往虚设的销地，这是不可能的。我们的解释是，该产地有2吨产品应就地贮存。 <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image022.gif"> 是在求解中为保证基变量个数而保留的一个基变量，因其取值为零，故本问题的解是一个所谓的退化解。这种情形在运输问题求解中是经常发生的，务请注意。因为如果少了这个基变量，将影响检验数的求出而使问题的求解遇到困难。另外，在确定初始方案时，自然虚设销地的运价最小，自然被首先作为基变量选定。但是，这种做法可能导致求解过程复杂化。因此，在开始时，找最小元素时一般先不考虑它们，到最后再加以处理。
　　同理，对于产量小于销量情形，可虚设一个产地而化为产销平衡问题后再求解，其结果是某个销地的产品出现脱销。
　　本讲最后，介绍一个应用运输问题的例子。

yunjiang

<b>　短缺资源的分配问题</b>  
　　设某城市自来水的水源地为A、B、C三个水库，分别由地下管道把水运往该市所辖甲、乙、丙、丁四个地区，惟一的例外是C水库与丁区之间没有地下管道。由于各种原因，自来水公司对各区的引水管理费（元/千吨）各不相同（见表4－12）。但是对各区自来水的其它管理费均为45元/千吨，水费单价统一为90元/千吨。目前水库将临枯水期，公司决策人正考虑如何分配现有供水量问题。首先，必须保证居民生活用水和重要机关、企业和事业单位用水的基本需求，各区的这部分用量由上表的“最低需求”行数字表示，但是拥有一个独立水源的丙地区这部分用水量可自给自足，公司可不供给。其次，除乙区外，其它三个区都已向公司申请额外再分给如下水量（千吨/天）：甲区20，丙区30，丁区要求越多越好，即无上限。这部分水量包含于“最高需求”行中。试建立供水模型，在保障各区最低需求的基础上获利最多。
　　　　　　　　　　　表4－12
　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image038.gif">

yunjiang

　　<b>问题分析与模型假设</b>
　　（1）将最低需求与额外申请量的和作为最高需求量列于上表最后一行。
　　（2）本例为求最大值类型，但是总利润=总收入－总成本，其中的总收入实际上是一个常数，这是因为每天总供水量是常数，而自来水单价也是常数，所以总数入等于二者之积，那么只要能将总供水量全部销出，必能获最大总收入。又丁区最高需求不限，故总供水量全部销出不成问题。这样问题就转化为使总成本达最小。有总成本只是来自自来水管理费，而在对各区的自来水管理费中，仅引水管理费单价不同，问题就变成了，如何分配水量，在满足各区最低需求条件下，总的引水管理费达最小。
　　（3）按照运输问题的要求，这里仅差需求量尚待确定，特别是丁区的“不限”应予限定。其实，作为最高限量，在满足其它地区最低需求时，丁区供水充其量是60千吨/天。这样，四个区最高需求量总数为210（千吨/天），比总供水量多出50（千吨/天）。因此，若把最高需求视作销量，则本例就是一个产量小于销量的不平衡运输问题。为此，虚设一个水库D，其供水量为50（千吨/天），则问题便平衡化了。
　　然而，这样以最高需求为销量构成的运输模型，其结果很可能不能满足某区的最低需求。为此，把具有两层次需求的地区细分成两个销地，例如甲区最低需求为30，额外需求为20，则设有两个区：甲<SUB>1</SUB>与甲<SUB>2</SUB>，甲<SUB>1</SUB>销量30为最低需求，不允许脱销，故不能由虚设水库D供给。可令D供给甲<SUB>1</SUB>的引水费为<I>M</I>＞0，<I>M</I>是一个充分大的数，而甲<SUB>2</SUB>的销量30为额外需求，可供可不供，故可以由虚设水库D供给，可令对应运价为0。依此处理其它类似情况，便有产销平衡运输问题的规范化模型如表4－13。

yunjiang

　　　　　　　　表4－13               单位：元/千吨
　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image039.gif">
　　模型求解与分析
　　使用表上作业法求解即可，只是在求解过程中应注意两件事：其一，M是一个很大的正数，比表中任何一个数字都大;其二是运价“0”在确定初始方案时不应视为最小运价。求解结果如表4—14所示。
　　　　　　　　　　　　表4－14              最优分配方案表
　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image040.gif">

yunjiang

　易见，各区最低需求均得到满足，额外需求中丙一无所得，丁只获得30，甲得到全部满足。最小引水管理费为 19×50+13×70+15×40=2460（元/天）
　　其它管理费为   45×160=7200（元/天），
　　故总成本为       2460+7200=9660（元/天），
　　而总收入为        90×160=14400（元/天），
　　故最大总利润为4740（元/天）。供应方式：
　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image041.gif">
　　模型分析与推广
　　从上述两例可见，由于运输问题模型的求解简单明了，因此在可能的情况下，人们都设法将线性规划问题转化为运输问题模型后再加以解决，因此其应用面十分广泛。也确有不少实际问题可化归为运输模型，参看文字教材第四章学习指导例题选讲及章后习题。

yunjiang

<b>　情形3</b>  若问题为求最大值问题，有两个方面的事情应予注意。其一，求初始方案使用与最小元素法相应的最大元素法，即每次都是选取所余运价中最大的元素所对应的变量为初始基变量；其二，在最优性判定时，要求所有检验数 <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_22/htm/sxjm22.files/image033.gif"> 才达最优。其他步骤不变。这方面的例子从略。

duanshumo

谢谢你的帖子

coeeoc

<>谢谢</P>