第三章 运输问题

第三章运输问题3.1运输问题的表示

3.2初始基础可行解3.3非基变量的检验数3.4基解的调整3.5运输问题的进一步讨论2/5/20231浙江科技学院经济管理学院管工系本章学习要求掌握表上作业法及其在产销平衡运输问题求解中的应用掌握产销不平衡运输问题的求解方法2/5/20232浙江科技学院经济管理学院管工系3.1运输问题的表示网络图表示线性规划模型运输表2/5/20233浙江科技学院经济管理学院管工系某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060求总运费最低的运输方案。2/5/20234浙江科技学院经济管理学院管工系运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）10302060minz=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13=35供应地A1x21+x22+x23=25供应地A2x11+x21=10需求地B1x12+x22=30需求地B2x13+x23=20需求地B3x11,x12,x13,x21,x22,x23≥02/5/20235浙江科技学院经济管理学院管工系运输问题的一般提法：假设有m个生产地点，可以供应某种物资（以后称为产地），用Ai来表示，i=1,…,m,有n个销地，用Bj来表示，j=1,…,n，产地的产量和销地的销量分别为ai,bj，从产地Ai到销地Bj运输一个单位物资的运价为Cij，这些数据可汇总于下表，在假设产销平衡的条件下，即∑ai=∑bj，问该如何调运物品使总运费最小？B1B2…Bn产量A1C11C12…C1na1A2C21C22…C2na2………………AmCm1Cm2…Cmnam销量b1b2…bn2/5/20236浙江科技学院经济管理学院管工系建模：设xij表示从Ai到Bj的运量，则所求的数学模型为：minΖ=ΣΣcijxij

s.t.Σxij=aii=1,…mΣxij=bjj=1,…,nj=1ni=1mi=1mj=1nxij≥0i=1,…m,j=1,…,n2/5/20237浙江科技学院经济管理学院管工系1.运输问题的网络图表示2312341d1=22d2=13d3=12d4=13s2=27s3=19s1=14产地运价销地6753482759106产量销量总产量60吨总销量60吨产销平衡的运输问题2/5/20238浙江科技学院经济管理学院管工系2.运输问题线性规划模型产地约束销地约束由于前m个产地约束和后n个销地约束是线性相关的，因此运输问题系数矩阵的秩<m+n。可以证明，运输问题系数矩阵的秩为m+n-1。即运输问题有m+n-1个基变量，mn-(m+n-1)个非基变量。例如以上问题m=3，n=4，基变量为3＋4－1＝6个，非基变量为12－6＝6个。2/5/20239浙江科技学院经济管理学院管工系3.运输问题的表格表示2/5/202310浙江科技学院经济管理学院管工系3.2初始基可行解运输问题基的表示西北角法最小元素法沃格尔法2/5/202311浙江科技学院经济管理学院管工系1.运输问题基的表示m个产地、n个销地的运输问题，任何一个基要满足以下三个条件：基变量的个数为m+n-1；基变量不能形成闭回路；2/5/202312浙江科技学院经济管理学院管工系123412312341231234123123412312341231234123基在运输表中的表示2/5/202313浙江科技学院经济管理学院管工系2.初始基础可行解—西北角法813131466方法：优先满足运输表中左上角空格的供销要求－填一个数字只能划去一行或一列2/5/202314浙江科技学院经济管理学院管工系3.初始基础可行解—最小元素法12015130113021930120200方法：按单位运价的大小，决定供应的先后，优先满足单位运价最小者的供销要求（就近供应）2/5/202315浙江科技学院经济管理学院管工系4.初始基础可行解—沃格尔法3212323311*3113行罚数列罚数414*13*1219方法：计算出每一行及每一列中单位运价最小和次小的两个元素之间的差值，再从差值最大的行或列中找出单位运价最小者，优先满足其供销关系。2/5/202316浙江科技学院经济管理学院管工系3.3非基变量的检验数闭回路法位势法2/5/202317浙江科技学院经济管理学院管工系1.非基变量检验数—闭回路法(1)方法求非基变量检验数σij,以该变量为定点，其他顶点为基变量找一个闭回路，从该非基变量定点为“＋”，“－”，“＋”，“－”依次加减其运价，即为检验数。意义：以该非基变量充当基变量时单位运量运费的损失。当所有的σij≥0，则已得运输问题的最有解。即单位物品由i-j引起总运费的变化。2/5/202318浙江科技学院经济管理学院管工系8131314661.非基变量检验数—闭回路法(1)σ12

=c12-c22+c21-c11=7-4+8-6=552/5/202319浙江科技学院经济管理学院管工系8131314661.非基变量检验数—闭回路法(2)5σ13

=c13-c23+c21-c11=5-2+8-6=552/5/202320浙江科技学院经济管理学院管工系8131314661.非基变量检验数—闭回路法(3)55σ14

=(c14-c34+c33-c23+c21-c11)=3-6+10-2+8-6=772/5/202321浙江科技学院经济管理学院管工系8131314661.非基变量检验数—闭回路法(4)557σ12

=c24-c34+c33-c23=7-6+10-2=992/5/202322浙江科技学院经济管理学院管工系8131314661.非基变量检验数—闭回路法(5)5579σ32

=c32-c24+c23-c33=9-4+2-10=-3-32/5/202323浙江科技学院经济管理学院管工系8131314661.非基变量检验数—闭回路法(6)5579-3σ31

=c31-c21+c23-c32=5-8+2-10=-11-112/5/202324浙江科技学院经济管理学院管工系2.非基变量检验数—位势法该法也称对偶变量法，我们知道一般标准运输问题的对偶问题为：Ui,Vj无约束由LP中σij的定义：

σij

=Cij-CBB-1Pij＝Cij-YPij=Cij-(u1,u2,……,um,v1,v2,……,vn)Pij=

cij-(ui+vj)对基变量而言：

cij=(ui+vj)由m+n-1个基变量对应m+n-1个线性方程而LD的变量有m+n个，对偶问题有无穷多解，则可设其中一个最优解为0，而推导出其他分量。从而求出非基变量的检验数。2/5/202325浙江科技学院经济管理学院管工系8131314662.非基变量检验数—位势法(1)uivj0622010-42/5/202326浙江科技学院经济管理学院管工系8131314662.非基变量检验数—位势法(2)uivj0622010-45579-13-32/5/202327浙江科技学院经济管理学院管工系3.4基解的调整－闭回路法与单纯形法一样，如果所有非基变量检验数σij≥0，则该基解为最优解，否则不是最优解，需要进行基变换，换入变量的确定方法一样，设换入变量为σlk

，换出变量为σsf：以xlk和基变量为顶点找一个闭回路，分别标号”+”,”-”,”+”,”_”；在标号为”-”的最小的运量为调整量，在闭回路上进行调整，“＋”的加，“-”的减，当存在xsf为0时，为换出变量，得一新的基可行解，再求检验数。2/5/202328浙江科技学院经济管理学院管工系8131314661.基变换-确定换入换出变量5579-3-11-11＋-＋-62/5/202329浙江科技学院经济管理学院管工系8131314661.基变换－得新的基解＋-＋-62122/5/202330浙江科技学院经济管理学院管工系1313141.基变换－得新的基解62122/5/202331浙江科技学院经济管理学院管工系确定初始基础可行解西北角法沃格尔法求非基变量的检验数闭回路法对偶变量法确定进基变量确定离基变量得到新的基础可行解表上作业法总结沿闭回路调整运量最小元素法2/5/202332浙江科技学院经济管理学院管工系单纯形法与表上作业法比较单纯形法（Min）表上作业法确定初始基变量XB+松驰变量+（人工变量）XB——系数矩阵为I，m个其余XN最小元素法、沃格尔法XB——数字格，m+n-1个XN——空格检验数基变量j=0非基变量j=cj-cBB-1pj基变量ij=0非基变量ij=cij-Ui-Vj调整进基：min{j∣j<0}出基：θ＝min{bi/aik，aik＞0}进基：min{ij∣ij<0}出基：θ＝min{闭回路上偶数点xij}2/5/202333浙江科技学院经济管理学院管工系3.5运输问题的进一步讨论一、产销不平衡的运输问题1）产大于销，即∑ai>∑bj方法：虚购一销地Bn+1，其销量bn+1=∑ai-∑bjAi运往Bn+1物资的数量xin+1，就是产地就地贮存的物资量，因此，产地到虚销地的单位运价均为0，即cin+1=0，这样，就转化成了一个产销平衡问题。2/5/202334浙江科技学院经济管理学院管工系例：某建筑公司有A1、A2、A3三个水泥库，其水泥贮存量分别为30吨、50吨、60吨，四个工地B1、B2、B3、B4需要水泥的数量依次为15吨、10吨、40吨、45吨，已知从各库到各工地运送每吨水泥的费用如下表，求使运费最少的调运方案？B1B2B3B4产量27040806050A310030502060销量15104045解：计算∑ai=140，∑bj=110，∑ai>∑bj

所以要虚构一销地B4，其销量b5=30，而ci5=0，这样，就转化成了一个产销平衡问题。

2/5/202335浙江科技学院经济管理学院管工系2）产小于销，即∑ai＜∑bj方法：虚购一产地Am+1，其产量Am+1=∑bj-∑aiAm+1运往Bj物资的数量xm+1j，就是各销地缺货的物资量，因此，虚产地到各销地的单位运价均为0，即cm+1j=0，这样，就转化成了一个产销平衡问题。例如：B1B2B3B4产量A13113109A219284A3741057销量1361562/5/202336浙江科技学院经济管理学院管工系二、一些变形和推广1、最大化问题作法：1）找出单位物资效益表（cij）中的最大元素M，即M=max{cij}2)令bij=M-cij，并视为运价。3）由bij构成单位运价表，按通常的表上作业法求解，求得最优解后还要把所得结果转换为原问题的答案。2、销量不确定（有最高需求和最低需求）设销地Bk的最低需求为bk’，最高需求为bk’’，这时可把看作Bk’和Bk’’两个销地，Bk’需求量bk’，Bk’’的需求量bk’’-bk’2/5/202337浙江科技学院经济管理学院管工系例：设某种材料有A1、A2、A3三个生产厂家，其产品供应B1、B2、B3、B4四个城市，假定等量的材料在这些城市的使用效果相同，已知各建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材的运价如表所示，求使运费最少的调运方案？B1B2B3B4产量A11613221750A21413191560A3192023M50最低需求3070010最低需求507030不限解释c34=M（M是一个无穷大的正数），这意味着不允许从A3运货至B4，或者因为交通不方便等原因，使从A3到B4不可能送货。2/5/202338浙江科技学院经济管理学院管工系B1B2B3B4产量A11613221750A21413191560A3192023M50最低需求3070010最低需求507030不限B1’B1’’B2B3B4’B4’’销量302070301050A1A2A3A4产量50605050161419M1614190131320M22192301715MM1715M02/5/202339浙江科技学院经济管理学院管工系3、指定销售问题如规定销地1的需求量必须由产地4供应，如何处理？1）直接令x41=b12)令c41=-M，或者c11=c21=c31=M这样销地1的需求量肯定是由产地1供应了。2/5/202340浙江科技学院经济管理学院管工系4、缺货损失问题

如下表，设销地1不允许缺货；销地2缺货，单位损失费3元；销地3缺货，单位损失费2元，问如何处理？B1B2B3产量A151710A264680A332515销量655525B1B2B3产量A151710A264680A332515销量655525A440M322/5/202341浙江科技学院经济管理学院管工系三、生产与存储问题例：某厂按合同须于当年每个季度末分别提供10、15、25、20台同一规格的起重机，已知该厂各季度的生产能力及生产每台起重机的成本如表所示，若生产出来的起重机当季不交货，每台每积压一个季度工厂需支付保管及维护费0.15万元，试问在按合同完成任务的情况下，工厂应如何安排生产计划才能使全年消耗的生产与存贮费用的总和最少？季度工厂生产能力（台/季）成本（万元/台）交货量（台）12510.81023511.101533011.002541011.30202/5/202342浙江科技学院经济管理学院管工系发货点：生产起重机的四个季度

发货量：生产能力

收货点：按合同交付起重机的四个季度

收货量：按合同提供起重机的数量

cij=第i季度每台起重机的生产成本+（j-i）个季度每台起重机的存贮费（j>i）12345发量（台）125235330410收量（台）101525203010.8010.9511.1011.25M11.1011.2511.40MM11.0011.15MMM11.3000002/5/202343浙江科技学院经济管理学院管工系四、有转运的运输问题1、运输表的构成1）产地：原产地、中间转运站、转运物资的销地2）销地：原销地、中间转运站、转运物资的产地3）设各转运站转运物资的数量均为∑ai这样专职转运站的产量和销量均为∑ai而原产地Ai的产量均为（ai+∑ai）原销地Bj的销量均为（bj+∑ai）4)将各条线路实际的运输单位列成单位运价表，其中不可能的运输其单位运价用M表示。2/5/20234