运输问题模型与算法

4运输问题—数学模型及其解法

4.1运输问题数学模型

4.2运输问题的求解方法

4.3对解进行检验及改进

4.4运输问题的进一步讨论

4.5应用问题举例

P&T公司的配送问题案例Figure1LocationofthecanneriesandwarehousesfortheP&TCompanyproblem.运输数据CanneryOutputWarehouseAllocationBellingham75truckloadsSacramento80truckloadsEugene125truckloadsSaltLakeCity65truckloadsAlbertLea100truckloadsRapidCity70truckloadsTotal300truckloadsAlbuquerque85truckloadsTotal300truckloads目前的运输计划WarehouseFrom\ToSacramentoSaltLakeCityRapidCityAlbuquerqueCanneryBellingham75000Eugene565550AlbertLea001585卡车的运输成本WarehouseFrom\ToSacramentoSaltLakeCityRapidCityAlbuquerqueCanneryBellingham$464$513$654$867Eugene352416690791AlbertLea995682388685总的运输成本=75($464)+5($352)+65($416)+55($690)+15($388)+85($685)

=$165,595运输问题的特点供应/需求假设每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。每一个目的地都有一个固定得需求量，整个需求量都必须由出发地满足。可行解的特性当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解。成本假设从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系。这个成本就等于配送的单位成本乘以所配送的数量。网络表示4.1运输问题的一般数学模型有m个产地生产某种物资，有n个地区需要该类物资令a1,a2,…,am表示各产地产量，b1,b2,…,bn表示各销地的销量，ai=bj

称为产销平衡设xij表示产地i

运往销地j

的物资量，wij表示对应的单位运费，则我们有运输问题的数学模型如下：运输问题有mn个决策变量，m+n

个约束条件。由于产销平衡条件，只有m+n–1个相互独立，因此，运输问题的基变量只有m+n–1个.例1某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：产销平衡问题：总产量=总销量设xij

为从产地Ai运往销地Bj的运输量，得到下列运输量表：

Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200

xij≥0(i=1、2；j=1、2、3）运输问题有有限最优解约束条件非常有规律，技术系数非0即1平衡运输问题数学模型特点m行n行每个变量Xij对应的矩阵列中,除第i个元素和第m+j个元素为1外,其余元素为零.每行有n个1，其余为0。所有结构的约束条件是等式约束各产地产量之和等于各销地销量之和运输问题的解解满足所有的约束条件;基变量对应的约束方程组的系数列向量线性无关;解中非零变量Xij的个数不能大于(m+n-1)个;为使迭代求解顺利进行,基变量的个数在迭代过程中保持为(m+n-1)个;基变量的个数远小于决策变量的个数.4.2运输问题的求解方法采用表上作业法，称为位势法运算中涉及两个表：运费表和产销平衡表(分配表)运费表分配表寻找初始可行解的方法

1、西北角法从x11开始分配，从西北向东南方向逐个分配xij

的分配公式例2

例4.2.1西北角法

2、最低费用法

采用最小费用优先分配的原则f(x)=121，费用比西北角法低84

3、运费差额法（沃格尔法-Volge）最小元素法初看十分合理。但是，有时按某一最小单位运价优先安排物品调运时，却可能导致对其它代销点配送时费用更高，从而使总费用增加。对每一个供销地或销售地，均可由它到各销售地或各供应地的单位运价中找出最小单位运价和次小单位运价，并称这两个单位运价之差为该供应地或销售地的罚数。若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大的损失，故应尽量按最小单位运价安排运输。采用最大差额费用(即利用每行或列中最小费用与次最小之间的差额中选最大)优先分配的原则。f(x)=98，比最低费用法又低了23

某种物品先放在A1、A2和A3三个仓库中，再运往使用地B1、B2、B3和B4，其间的距离（或单位运价）如下表所示，各仓库的存量和使用地的需要量也都表示于下表中，试建立使总运输费用最小的运输问题数学模型。用前面讲的三种方法分别求可行解用上面的三种表上作业法，求下列运输问题的解

销地产地B1B2B3B3产量A116A210A322销量81412144124112103985116表1用上面的三种求下列运输问题的解

销地产地B1B2B3B3产量A18816A26410A381422销量81412144124112103985116用西北角法求的可行解表2412用上面的三种求下列运输问题的解

销地产地B1B2B3B3产量A110616A28210A314822销量81412144124112103985116用最小元素法求的可行解表3用上面的三种求下列运输问题的解

销地产地B1B2B3B3产量A112416A28210A314822销量81412144124112103985116用沃尔格法求的可行解表44.3对解的可行性进行检验

运输表中的格子是空的,则代表是非基变量.若存在非基变量的检验数小于零,说明得到的解不是最优解！运输问题常用的解检验方法有2种：闭回路法；位势法

销地产地B1B2B3B3产量A110616A28210A314822销量81412144124112103985116检验用最小元素法求的可行解（下表）是否最优表34.3.1利用闭回路法检验分配方案是否最优运量表中的空格中无数字，表示该空格所对应的变量为非基变量。判断运输问题的解是否是最优解，可以参照单纯形法，非基变量的检验数是否均大于等于0。如何计算检验数？某一非基变量值调整为1个单位，为保证供需平衡，闭回路（除1个非基变量外，其它顶点上均为基变量）上的基变量值做相应的调整，由此而出现的运费变化值为检验数。闭回路形式有：4.3.1利用闭回路法检验分配方案是否最优表3中的可行解用闭回路法计算的检验数

销地产地B1B2B3B3产量A112A21-1A31012销量因X23的检验数小于0，表3的调运方案不是最优解表5

4.3.2利用位势法检验分配方案是否最优思路：不用闭回路法，如何获得xij的检验数?找到原问题的基础可行解，保持互补松弛条件:(YA-C)X=0，求出对应对偶问题的解。若该对偶问题的解非可行，则原问题的解不是最优解；否则，达到最优解。复习：若X,Y分别为(P),(D)的可行解，则X,Y为最优解的充要条件是：利用位势法检验分配方案是否最优

平衡运输问题数学模型

平衡运输问题的对偶问题uivj对偶变量动输问题变量的检验数表示为:设已得到运输问题的基可行解,其基变量是:

由于基变量的检验数等于0,故对于这组基变量可写出方程组:

可以证明上面的方程有解,且由于对偶变量数比方程数多一个,故解不唯一.称上面方程的解为位势.

对上面的方程组求解,然后计算运输问题的检验数,若有检验数小于零,则原运输问题的解不是最优解.

位势法的原理为满足互补松弛条件，原问题中xij被选为基变量，即xij0，则要求对偶问题中ui+vj=cij，即该行的松弛变量为0共有m+n1个基变量xij

，因此可得m+n1个等式ui+vj=cijm+n1个等式中有m+n个变量ui

和vj

（？），因此，令任一个ui

或vj=0，从而解出其它m+n1个的值；这就是位势法若对所有非基变量有cij

(ui

+vj)

0，即ui

+vjcij，表明当前ui

和vj

是对偶问题的可行解，由互补松弛定理可知当前m+n1个基变量xij

是最优解，否则从cij

(ui

+vj)<0中找最小者，对应xij

就是入变量

销地产地B1B2B3B4产量A110616A28210A314822销量81412144124112103985116检验用最小元素法求的可行解（下表）是否最优表3利用位势法检验计算位势根据基变量的检验数为0，有下面的方程令U2=0,得各变量的值为：V1=2,V3=3,U1=1,V4=10U3=-4,V2=9

销地产地B1B2B3B4uiA1121A21-10A31012-4vj293104124112103985116检验用最小元素法求的可行解（下表）是否最优表6利用位势法检验4.3.3解的改进

运输问题中,若某一非基变量的检验数小于零,说明这个非基变量作为基变量时,运输费用将更小.因而当前解不是最优解.用闭回路法进行调整.

将检验数最小的非基变量作为换入变量,找出它在运输表中的闭回去路,取闭回路中所有偶数点中最小运量,在所有奇数点上都增加这一最小运量,在所有偶数点上减少这一最小运量.

然后,再对调整后的解进行最优性检验,如不是最优解,就重复以上步骤继续进行调整,一直到得出最优解为止.

销地产地B1B2B3B4产量A110+26-216A282-2+210A314822销量81412144124112103985116改进用最小元素法求的可行解把x24作为进基变量表7目标函数值z=244

销地产地B1B2B3B4uiA1021240A28212-2A3914128-5vj4104114124112103985116再次进行最优性检验，并将非基变量检验数填在表格上中（红色带圈数字）：表8表中解为最优解！4.3.4需要说明的几个问题若运输问题的某一可行解有几个非基变量的检验数均为负,在继续进行迭代时,取它们中的任一变量为换入变量均可使目标函数值得到改善,但通常取检验数小于零中最小者对应的变量为换入变量.当迭代到运输问题有最优解时,如果有某非基变量的检验数等于零,则说明该运输问题有无穷多最优解.当运输问题某部分产地的产量和,与某一部分销地的销量和相等时,在迭代过程中有可能在某个格填入一个运量时需要同时划去运输表的一行和一列,这时就出现了退化.在运输问题中,退化解是时常发生的,为了使一表上作业法的迭代工作进行下去,退化时在同时划去一行或一列的某个格中填入数字0,表示这个格中的变量是取值为0的基变量,使迭代过程中可行解的分量恰好为(m+n-1)个.4.4运输问题的进一步讨论4.4.1产销不平衡

1)供过于求，即a

i>bj.数学模型为:

为借助于产销平衡时的表上作业法求解,可增加一个假想的销地Bn+1,由于实际上它不存在,因而由产地Ai(i=1,2,…,m)调运到这个假想销地的物品数量xi,n+1(相当于松驰变量),实际上是就地存贮在Ai的物品数量.就地存贮的物品不经运输,故其单位运费ci,n+1=0(i=1,2,…,m)令假想销地的销量为bn+1,且

注意相对应的运输表!4.4.1产销不平衡

1)供不应求，即ai<bj.假想产地Am+1,它的产量等于:

由于这个假想的产地不存在,求出的由它发往各个销地的物品数量xm+1,j(j=1,2,…,n),实际上是各销地所需物品的欠缺额,显然有:例某市有三个造纸厂A1、A2、A3，其纸的产量分别为8、5和9个单位。有4个集中用户，其需要量分别是4、3、5和6个单位。由各造纸厂到各用户的单位运输价格如下表所示，请确定总运费最小的调运方案。

销地产地B1B2B3B4产量A18A25A39销量435631234112596715

假定m个产地A1,A2,…,Am

和n销地B1,B2,…,Bn

都可以作为中间转运站使用，从而发送物品的地点和接收物品的地点都有m+n个，这就是转运问题。为建立数学模型，令：4.4.2有转运的运输问题ai:第i个产地的产量（净供应量）；bj:第j个销地的销量（净需要量）；Xij:由第i个发送地运到第j个接收地的物品数量；cij

:由第i个发送地到第j个接收地的单位运价；ti:第i个地点转运物品的数量；ci:第i个地点转运物品的费用。

现将产地和销地统一编号，并把产地排在前面，销地排在后面，则有：am+1=am+2=…=am+n=0b1=b2=…=bm=0假定为平衡运输问题，即有有转运的运输问题有转运的运输问题的数学模型令：

将上式中各约束条件中的ti或tj移到等式左侧，然后两侧加上Q并令：有下面的运输表达式：有转运的运输问题的运量表

接收发送产地销地发送量1…mm+1…m+n产地1X11…X1mX1m+1…X1m+nQ+a1…………………

……mXm1…XmmXm,m+1…Xm,m+nQ+am+1销地m+1Xm+1,1…Xm+1,mXm+1,m+1…Xm+1,m+nQ……………………m+nXm+n,1…Xm+n,mXm+n,m+1…Xm+n,n+nQ接收量Q…QQ+bm+1Q+bm+n有转运的运输问题运价表

接收发送产地销地发送量1…mm+1…m+n产地1-c1…c1mc1m+1…c1m+nQ+a1…………………

……mcm1…-cmcm,m+1…cm,m+nQ+am+1销地m+1cm+1,1…cm+1,m-cm+1…cm+1,m+nQ……………………m+ncm+n,1…cm+n,mcm+n,m+1…-cm+nQ接收地Q…QQ+bm+1Q+bm+n例一个运输系统包括了二个产地①和②、二个销地④和⑤及一个中间转运站③，各产地的产量和各销地的销量用相应节点处箭线旁的数字表示，节点联线上的数字表示期间的运输单价，节点旁的数字为该地的转运单价，试确定最优运输方案。123410532254041332012424041310532144353242401356530520105321443532424013

接收发送产地转运销地12345发送量产地-4532M605-12M490转运32-35550销地2M5-3650M456-550接收量5050508070

运价表56530520105321443532424013用最小元素法得初始运输方案如下表所示。

接收发送12345发送量15010602502020903500504505055050接收量5050508070再经过两次迭代后得最优解。其运输方案如下表所示：

接收发送12345发送量15010602502020903500504505055050接收量5050508070再经过两次迭代后得最优解。其运输方案如下表所示：

接收发送12345发送量150106025020209033020504505055050接收量5050508070最优时的总运输成本为3004.5应用问题举例

由于运输问题的表上作业法,远比一般单纯形法计算简单,因而人们在解决有些实际问题时,常设法将其转化为运输问题的数学模型求解,下面通过几个例子加以说明.

例4.5.1

某企业和用户签订了设备交货合同,已知该企业各季度的生产能力，每台设备的生产成本和每季度末的交货量（见下表），若生产出来的设备当季不交货，每台设备每季度需支付保管维护费0.1万元,试问在遵守合同的条件下,企业应如何安排生产计划,才能使年消耗费用最低?季度工厂生产能力交货量(台)每台设备生产成本(万元)1251512.02352011.03302511.54202012.5求解步骤:1)设xij表示第i季度生产第j季度交货的设备台数,ai表示第i季度的生产能力,表示bj第j季度的交货量;2)计算成本,第i季度生产第j季度交货的每台设备成本(生产成本+保管成本);3)建立数学模型;4)当j<i时,cij是一个充分大的正数；5）把不平衡运输问题转化为平衡运输问题,设计运输表:

生产季交货季1234112.012.112.212.32？11.011.111.2311.511.6412.5成本表表9生产能力交货量2035302515202520Minz=12.0x11+12.1x12+12.2x13+12.3x14+

Mx21+11.0x22+11.1x23+11.2x24

+Mx31+Mx32+11.5x33+11.6x34+Mx41+Mx41+MX41+12.5x44x11+x12+x13+x14≤25x22+x23+x24≤35x33+x34≤30x44≤20X11=15X12+x22=20X13+x23+x33=25X14+x24+x34+x44=20Xij0(i,j=1,2,3,4)

生产季交货季1234D生产量1252

353

30420交货量152025203012.012.112.212.3011.011.111.2011.511.6012.50MMMMMMM是一个很在的正数.运价表表10该类问题一般的数学模型表示：

当j<i时，cij=M,M是一个很大的正数！

例

有三个产地A1、A2和A3生产同一种物品，使用者为B1、B2和B3，各产地到各使用者的单位运输价格表示于下表中，这三个使用者的需求量分别为10、4和6个单位。由于销售需要和客观条件的限制，产地A1至少要发出6个单位的产品，它最多只能生产11个单位的产品；A2必须发出7个单位的产品；A3至少要发出4个单位的产品。试根据上述条件用表上作业法求该运输问题的最优运输方案。例题的单位运输价格表

使用生产B1B2B3生产量A12436≤a1≤11A2156a2=7A3324a3≥4使用量1046表11分析:总需求量为20,当a1=6时,A3的最大生产量为7.如果A1和A3都取最大值,总产量为25,大于实际需求量20.增加虚拟的销地.将A1和A3的产量分为两部分,1)必须发出的,运往实在需求地,不能运往虚销地;2)非必须发出的,可以运往虚拟地,单位运输价格为0.

生产季交货季B1B2B3B4生产量A16A‘15A27A34A‘33交货量10465242433M0156M324M3240表12例某公司承担4条航线的运输任务,已知(1)各条航线的起点城市和终点城市,及每天的航班数(见表A);(2)各城市间的