第二十一讲 运筹学模型（5）——运输模型

yunjiang

　运输问题是一类特殊的线性规划问题，针对其特殊性，人们创造了特殊的解法，即所谓表上作业法，使用起来方便快捷，也易于推广。这里，我们先来建立其数学模型，然后介绍这个解法。值得注意的是，运输问题模型在中学数学应用竞赛中也是很常见的题目。
　　<b>情形1 产销平衡的运输问题</b>
　　设有一批产品要从三个生产地A<SUB>1</SUB>、A<SUB>2</SUB>和A<SUB>3</SUB>运往四个销售地B<SUB>1</SUB>、B<SUB>2</SUB>、B<SUB>3</SUB>和B<SUB>4</SUB>（生产地和销售地以后简称为产地和销地）。三个产地运往四个销地的运价，三个产地的产量和四个销地的需求量如表4－5所示，试策划一个运输方案，使得在满足需求条件下，总运输费用最少。
　　　　　　　　表4－5 产销平衡运价表     单位：拾元/吨
　　<IMG src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image040.gif">
　　<b>问题分析</b>
　　易见，三产地总产量为20吨，四个销地总销量也是20吨，这个运输问题被称为产销平衡问题。当总产量<SUB><IMG src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image005.gif"></SUB>总销量时统称为产销不平衡问题。下面的解法将针对的是产销平衡问题。

yunjiang

　<b>模型假设与构建</b>
　　以<I>x<SUB>ij</SUB></I>表示从第<I>i</I>个产地运送到第<I>j</I>个销地的运量，则依供需关系有下列约束条件：
　　供给方面：   <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image007.gif"> </SUB>
　　　　　　　　<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image009.gif"> </SUB>
　　　　　　　　<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image011.gif"> </SUB>
　　需求方面：  <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image013.gif"> </SUB>
　　　　　　　　<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image015.gif"> </SUB>
　　　　　　　　<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image017.gif">
　　　　　　　　　</SUB><SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image019.gif"> </SUB>
　　非负性：  <I>x<SUB>ij</SUB></I>≥0    <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image021.gif"> </SUB>
　　总运费： <SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image023.gif"> </SUB>
　　将上述目标函数与约束条件合在一起便构成所谓具有三个产地和四个销地的产销平衡运输问题的数学模型。本例很容易推广为具有<I>m</I>个产地<I>n</I>个销地且产销平衡运输问题。<SUB> </SUB>

yunjiang

<TABLE height=367 cellSpacing=0 cellPadding=0 width=476 align=center border=0><TR vAlign=top align=left><TD colSpan=2 height=309><B>　　<b>模型的求解——表上作业法</b>
　　</B>这一段只讲方法和有关结论。以本例为例，运输问题的数学模型常以表4－6形式及前述的表4－5（称运价表）形式出现。
　　运输问题的求解就是根据一定的优化法则在这张表上进行的，称为<U>表上作业法</U>。那么这个优化法则是什么？根据又是什么？具体求解步骤又是什么？下面就来回答这些问题。
　　注意到<I>x<SUB>ij</SUB></I>≥0，即<I>x<SUB>ij</SUB></I>要么取值为正，要么取值为零。我们称取正值的<I>x<SUB>ij</SUB></I>为基本变量，简称为基变量（基变量可能退化为取值为零，但它仍具有基变量的地位和功能）；不是基变量的变量称为非基本变量，简称为非基变量，其取值一定为零。因此，在众多的<I>x<SUB>ij</SUB></I>中，决定基变量及其取值是关键。那么，基变量有多少个？它们具有什么特征？我们有以下结论。 </TD></TR></TABLE>

yunjiang

　　　　　　　表4－6  运量表             单位：吨
　　 　<OBJECT codeBase=http://download.macromedia.com/pub/shockwave/cabs/flash/swflash.cab#version=6,0,29,0 height=200 width=400 classid=clsid27CDB6E-AE6D-11cf-96B8-444553540000><ARAM><ARAM><ARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM><PARAM>                        <embed src="sxjm21.files/01.swf" quality="high" pluginspage="http://www.macromedia.com/go/getflashplayer" type="application/x-shockwave-flash" width="400" height="200"></embed></OBJECT>

yunjiang

　<B>结论</B><B>1</B><B>  </B>具有<I>m</I>个产地<I>n</I>个销地的运输问题中，基变量个数是<I>m</I>+<I>n</I>－1个。
　　例如本例中<I>m</I>=3，<I>n</I>=4，故本例的基变量有3+4－1=6个。于是剩下的问题是如何求出这<I>m</I>+<I>n</I>－1个基变量及其取值。下面的确定基变量的定义方法别具特色。如表4－6，我们来考虑这个排好序的运量表中各变量<I>x<SUB>ij</SUB></I>间的关系。
　　定义  <I>x<SUB>ij</SUB></I>中，以<I>x<SUB>ij</SUB></I>为拐角点（又称顶点），其间用水平、铅直线段联结后形成的首尾相接的拐角点全体构成的变量组，称为一个闭回路。
　　例如表4－6中，变量组{<I>x</I><SUB>11</SUB>，<I>x</I><SUB>12</SUB>，<I>x</I><SUB>22</SUB>，<I>x</I><SUB>21</SUB>}就是一个闭回路；变量组
<SUB><img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image027.gif"> </SUB>也是一个闭回路。　　<B>
　　结论</B><B>2</B><B> </B> 运输问题中，一组<I>m</I>+<I>n</I>－1个变量构成基变量组<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image029.gif"> </SUB>这<I>m</I>+<I>n</I>－1个变量中不存在以其为顶点的闭回路。
　　如表4－6，由于<I>m</I>+<I>n</I>－1=6，则<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image031.gif"> </SUB>即为一个基变量组。这是因为该组内不存在闭回路，而一旦再加进一个变量，就立刻会形成且仅形成一条闭回路。
　　一般地，求解运输问题分三步走：
　　1）先设法求出一个运输方案面不论其优劣。即找一组基变量，然后按产销量要求给予赋值。这个方案称为<U>初始方案</U>。
　　2）对已得方案进行最优性检验。若是最优方案则停止运算，否则转到下一步。这中间将给出一个判定最优性法则。
　　3）从现行非最优方案向比它更好的另一个方案转换，标准是新方案的运费要比现行方案的低。
　　4）返回2），直到求得最优方案。　　

yunjiang

　<b>1）初始方案的确定方法——最小元素法</b>
　　　　　　　　　　　表4－5   　　   单位：拾元/吨
　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image042.gif">
　　如表4－5所示运输问题为例说明。由于是求最小值问题，因此，选择基变量时，总是选择所有运价中的最小运价对应的变量为基变量，这样可以尽量减少总运费，故此方法称为最小元素法。
　　整个运价中，由于1最小，于是决定由A<SUB>2</SUB>供应B<SUB>1</SUB>，于是第一个基变量被确定为<SUB> <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image035.gif"> </SUB>。再看供求关系，B<SUB>1</SUB>需要3吨，而A<SUB>2</SUB>产量为4吨，于是尽量满足需求，由A<SUB>2</SUB>供应B<SUB>1</SUB>3吨。在运价1的右下角写上③。由于B<SUB>1</SUB>的需求已满足，故A<SUB>1</SUB>，A<SUB>3</SUB>不必再向B<SUB>1</SUB>供应，于是在运价3与7右下角打×，表示变量<I>x</I><SUB>11</SUB>与<I>x</I><SUB>31</SUB>被确定为非基变量。
　　在剩下的9个运价中再找最小运价为2，并按上述方法确定第二个基变量<I>x</I><SUB>23</SUB>=1，同时变量<I>x</I><SUB>22</SUB>与<I>x</I><SUB>24</SUB>被确定为非基变量。

yunjiang

<b>　</b>依此类推，便可确定4个基变量和6个非基变量如表4－7<B><SUB>　
　　　　 <img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image043.gif"></SUB></B>
　　此时，只有两个变量<I>x</I><SUB>14</SUB>和<I>x</I><SUB>34</SUB>未被确定，但它们必须成为基变量。于是根据产销平衡关系确定10下画③，5下画③。终于得到初始基变量组及其取值为：<B><SUB>
　　 </SUB></B><I>x</I><SUB>13</SUB>=4，  <I>x</I><SUB>14</SUB>=3，  <I>x</I><SUB>21</SUB>=3，  <I>x</I><SUB>23</SUB>=1，  <I>x</I><SUB>32</SUB>=6，  <I>x</I><SUB>34</SUB>=3， 其余<I>x<SUB>ij</SUB></I>=0
　　即为初始运输方案（表4－8），其总运费也在表上计算为
　　Z<SUP>（0）</SUP>=3×4+10×3+1×3+2×1+4×6+5×3=86（拾元）
　　 　　　　　　　　　　　　　　表4－8
<B>　　　　<img src="http://202.205.160.49:8080/media_file/rm/ip3/zhangxh/2004_03_01/sxjm_21/htm/sxjm21.files/image044.gif"></B>

yunjiang

<b>　2）方案的最优性检验——闭回路法</b>
　　检验一个方案的最优性说到底是看此方案是否还有改进的余地。而方案是否有改进余地，关键是看非基变量中是否有能转变为基变量（取值大于零）而使目标值进一步改善，若有，则称这个变量为进基变量。就本例，我们试令<I>x</I><SUB>11</SUB>进基，让它从取值为0变化为取值为1（增加一个单位）看运费的变化。
<I>　　</I><I>x</I><SUB>11</SUB>增加1，按照产销平衡原则，<I>x</I><SUB>13</SUB>必须减值为3，否则与产量为7矛盾。而当<I>x</I><SUB>13</SUB>减值为3时，<I>x</I><SUB>23</SUB>必须增值一个单位，否则又与销量为5矛盾，依此又知，<I>x</I><SUB>21</SUB>需减少一个单位。以上变化导至总运费发生的变化值为
　　　　　　　 λ<SUB>11</SUB>=3－3+2－1=1＞0
　　这就是说，令<I>x</I><SUB>11</SUB>变为基变量，总运费将增加1个单位，故此举不合适。由此可知，λ<SUB>11</SUB>具有检验<I>x</I><SUB>11</SUB>进基是否能改善目标值的作用，称为非基变量<I>x</I><SUB>11</SUB>的检验数。如果非基变量的检验数大于零，则该变量进基不合适;若检验数等于零，则该变量进基也无助于目标值的改进。由此可推出：若所有非基变量的检验数均≥0，则目前这个方案便没有改进的余地，即已是最优方案。反之，若至少有一个非基变量的检验数＜0，则目前的方案便非最优方案。这就是运输问题的方案最优性检验原理。
　　值得注意的是，在求非基变量<I>x</I><SUB>11</SUB>的检验数时，恰好是在不存在闭回路的基变量组内引进一个非基变量后所形成的唯一闭回路中进行的相应运算：以进基变量为第一个顶点，按逆时针（或顺时针）将闭回路的奇数顶点运价赋以“+”号，偶数顶点运价赋以“－”号所形成的代数和便是该变量的检验数。按此法则，可求得所有非基变量的检验数如下：
　　λ<SUB>11</SUB>=3－3+2－1＞0，    　λ<SUB>12</SUB>=11－10+5－4＞0
　　λ<SUB>22</SUB>=9－2+3－10+5－４＞0，λ<SUB>24</SUB>=8－10+3－2＝-1＜0
　　λ<SUB>31</SUB>=7－5+10－3+2－1＞0， λ<SUB>33</SUB>=10－5+10－3＞0
　　由于λ<SUB>14</SUB>＜0，故初始方案非最优方案。

duanshumo

谢谢你的帖子

coeeoc

<>谢谢</P>