第四章运输问题.

1第四章运输问题——特殊线性规划2在经济建设中，经常遇到大宗物资的调运问题，如煤、钢材、粮食等物资的调运。如果在我们考虑范围之内有若干个生产基地和若干消费地点，根据已有的公路网，如何制定调运方案，使总的运费最小。这就是运输问题。运输问题是一个特殊的线性规划问题，特殊在它的约束条件具有特殊的结构。因为运输问题是线性规划问题，因而当然可以用单纯形法来解，又因为它具有特殊性，因而它还具有比单纯形法更为简便的解法——表上作业法。这就是我们专门研究运输问题的目的。§1运输问题的表示3下面我们先通过一个简单的例子来说明运输问题及其模型运输问题的一般描述和运输问题模型的一般形式引例有三家工厂，都将产品运往三个不同的商店（见下图）。每个工厂每周的生产能力和每家商店的平均需求量如下表1、2所示。工厂1工厂3工厂2商店1商店3商店2表1表2工厂123供应量（件/周）507020商店123需求量（件/周）5060304显然，每周的供应总量与需求总量是相等的，这样的问题就是产销平衡问题。由于运货距离和公路的路况不同，各个工厂运往各商店货物的运输费用是不同的，费用如下表所示。我们的问题是确定由哪家工厂运送多少件产品到哪家商店，使得总费用最小？单位产品的运输费用（元）商店工厂123132321058313105在产销平衡条件下，我们也可以把工厂的供应量，商店的需求量和单位产品的运价放在一个表中表示，如下表所示。商店工厂123供应量13235021058703131020需求量5060306模型建立决策变量用双下标决策变量Xij表示从第i家工厂（i=1，2，3）运送到每j家商店（j=1，2，3）的数量。目标函数利用运输费用表中的数据，我们希望其值为最小：MinZ=由工厂1运出产品的总费用----3X11+2X12+3X13+由工厂2运出产品的总费用----10X21+5X22+8X23+由工厂3运出产品的总费用----X31+3X32+10X33即：MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X337约束条件主要是对工厂的产量约束和商店的销量约束。由于产量与销量相同，因而有：对工厂1必须有X11+X12+X13=50对工厂2必须有X21+X22+X23=70对工厂3必须有X31+X32+X33=20对商店1必须有X11+X21+X31=50对商店2必须有X12+X22+X32=60对商店3必须有X13+X23+X33=308于是，解此问题的线性最优化模型是：MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33X11+X12+X13=50X21+X22+X23=70X31+X32+X33=20X11+X21+X31=50X12+X22+X32=60X13+X23+X33=30Xij≥0i=1，2，3j=1，2，3s.t.9运输问题的一般形式为：已知有m个生产地点Ai，i=1，2，…，m，可供应某种物资，其供应量是ai，i=1，2，…，m。有n个销地Bj，需求量是bj，j=1，2，…，n。从Ai到Bj运送单位物资的运价为cij，i=1，2，…，m；j=1，2，…，n，问如何安排运输可使总运费最小？用Xij表示从Ai到Bj的运量，在产销平衡条件下，可知ai=bj。如果ai与bj不等，就称此运输问题为非平衡运输问题。产销平衡运输问题的一般模型为：10MinS=cijxijijxij=ai(i=1,2…..m)jxij=bj(j=1,2……n)ixij0(i=1,2,…,m;j=1,2,…,n)s.t.11当产大于销即ai＞bj时，运输问题的数学模型可以写为:MinZ=CijXijxij≤ai（i=1，2，…，m）xij=bj（j=1，2，…，n）xij≥0（i=1，2，…，m；j=1，2，…，n）12由于总的产量大于销量，就要考虑每个产地的多余物资就地储存的问题。这可以理解为将所有产地的剩余物资运送至一个假想的销地Bn+1，运费为0，这时的总费用与没有假想之前的总费用是一致的，故MinZ=MinZ`。因此解决这种问题的办法是增加一个假想的销地Bn+1，它的需求量是ai-bj，就可以将产大于销的问题转化为产销平衡问题。13当销大于产即ai＜bj时，和产大于销类似，增加一个虚拟的产地Am+1，它的产量设为bj-ai，该产地到各个销地的单位运输费用为0，这样得到的最优解和没有虚拟之前是一致的，因而也可以将它转化为产销平衡问题。通过上述讨论可知，对于产销不平衡的问题，我们总是可以通过增加假想的销地和虚拟的产地将其化为产销平衡问题。因此我们只要解决了产销平衡问题，也就可以解决产销不平衡的问题了。下面我们只考虑产销平衡问题。14运输问题数学模型的特点：1：所有约束条件中决策变量的系数均等于1。2：运输问题有有限最优解。3：运输问题约束条件系数矩阵为A=11…111…1…………………………………………………11…111…1111…………………………………………………111（m+n）×（mn）154：运输问题约束条件的系数矩阵中对应于变量Xij的系数向量Pij，其分量除第i个和第m+j个等于1以外，其余的都为零5：对于产销平衡运输问题，由于ai=bj成立，因而其m+n个约束方程并不是独立的。实际上只有m+n-1个是独立的。即约束方程系数矩阵的秩为m+n-1。而且它总存在基可行解。16平衡运输问题的求解——表上作业法：表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法，其步骤可归纳为：(1)找出初始基可行解(2)求各非基变量的检验数，判别是否达到最优解，如果是最优解，停止。否则转下一步。(3)确定换入变量和换出变量，找出新的基可行解。(4)重复(2)(3),直到得到最优解为止。下面我们就按照表上作业法的步骤，先确定初始基可行解，然后进行调整达到最优解。17§2初始基可行解销地产地B1B2B3B4产量A13113107A219284A3741059销量3656下面以一个例子来说明找初始基可行解的方法，下图表示一个运输问题的产销平衡表和单位运价表(二表合一)。（单位：元/吨吨）18一般来说，找运输问题的初始基可行解主要有三种方法，下面我们依次来说明。1：西北角法(1)从图的西北角开始，填入a1与b1较小的值b1=3，即从A1运给B13吨货物，B1已经满足，划去b1列。销地产地B1B2B3B4产量A133113107A219284A3741059销量365619（2）向a1，b1较大方向移动一格（或向右，或向下）此时向右移动一格（A1，B2）B2需要6吨，而A1只有4吨，在（A1，B2）处填4，A1已发完，划去A1行。销地产地B1B2B3B4产量A1331143107A219284A3741059销量365620（3）继续进行销地产地B1B2B3B4产量A1331143107A2192284A3741059销量365621（4）继续进行销地产地B1B2B3B4产量A1331143107A21922284A3741059销量365622（5）继续进行销地产地B1B2B3B4产量A1331143107A21922284A37410359销量365623（6）继续进行销地产地B1B2B3B4产量A1331143107A21922284A374103569销量365624（7）得到初始方案：X11=3，X12=4，X22=2，X23=2，X33=3，X34=6，总运费=3*3+11*4+9*2+2*2+10*3+5*6=135（元）销地产地B1B2B3B4产量A1331143107A21922284A374103569销量3656252:最小元素法用西北角法很容易得到初始基可行解，但是得到的解往往离最优解相差很远。我们通常希望就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止。这种方法称为最小元素法。仍以刚才的例子来看。销地产地B1B2B3B4产量A13113107A219284A3741059销量365626（1）从最小元素1开始，即A2优先满足B13个单位，B1已经满足，划去B1列销地产地B1B2B3B4产量A13113107A2139284A3741059销量365627（2）再从最小元素2开始，即A2优先满足B31个单位，A2已经满足，划去A2行，销地产地B1B2B3B4产量A13113107A21392184A3741059销量365628（3）再从最小元素3开始，即A1优先满足B34个单位，B3已经满足，划去B3列，销地产地B1B2B3B4产量A131134107A21392184A3741059销量365629（4）再从最小元素4开始即A3优先满足B26个单位，B2已经满足，划去B2列销地产地B1B2B3B4产量A131134107A21392184A37461059销量365630（5）再以最小元素5开始，A3满足B43个单位，A3已满足，划去A3行。销地产地B1B2B3B4产量A131134107A21392184A374610539销量365631（6）最后以元素10开始，A1满足B43个单位，A1和B4都满足，划去A1行和B4列。销地产地B1B2B3B4产量A1311341037A21392184A374610539销量365632（7）得到初始方案：X13=4，X14=3，X21=3，X23=1，X32=6X34=3总运费=3*4+10*3+1*3+2*1+4*6+5*3=86（元）销地产地B1B2B3B4产量A1311341037A21392184A374610539销量3656333：差值法（伏格尔法）最小元素法的缺点是：为了节省一处的费用，有时造成其它处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小费用就近供应，就考虑次小费用，这就有一个差额，差额越大，说明不按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小调运方案。基于此，伏格尔法的步骤是：每次从当前运价表上，计算各行各列中最小费用与次小费用这两个运价的差值，优先取最大差值的行或列中最小的运价来确定运输关系，直到求出初始方案。34仍然考虑先前的例子销地产地B1B2B3B4产量A13113107A219284A3741059销量3656伏格尔法的步骤如下：35销地产地B1B2B3B4产量行差额A131131070A2192841A37410591销量3656列差额2513（1）先分别计算出各行各列最小费用与次小费用的差额，并填入该表的最右列和最下行。36（2）从行差额和列差额中选出最大者，选择它所在的行或列中的最小元素所在的格作为优先的运输方案。在这里优先选A3满足B26个单位，B2列已满足，划去B2列。销地产地B1B2B3B4产量行差额A131131070A2192841A374610591销量3656列差额251337（3）计算剩余元素的行差额和列差额，并选出最大者，选择它所在的行或列中的最小元素所在的格作为优先的运输方案。在这里优先选A3供应B43个单位，A3行已满足，划去A3行。销地产地B1B2B3B4产量行差额A131131070A2192841A3746105392销量3656列差额251338（4）继续进行。在这里优先选A2供应B13个单位，B1列已满足，划去B1列。销地产地B1B2B3B4产量行差额A131131070A21392841A3746105392销量3656列差额251239（5）继续进行销地产地B1B2B3B4产量行差额A1311351077A21392846A3746105392销量3656列差额251240（6）继续进行销地产地B1B2B3B4产量行差额A131135107A21392814A3746105392销量3656列差额251241销地产地B1B2B3B4产量A1311351027A21392814A374610539销量365