运筹学第三版之第三章运输问题

运输问题(TransportationProblem)是一类特殊的线性规划问题.最早研究这类问题的是美国学者希奇柯克(Hitchcock)，后来由柯普曼(Koopman)详细加以讨论。在第一章线性规划模型的应用中，我们介绍了运输问题，建立了其数学模型，这类问题属线性规划问题，当然可以使用单纯形法进行求解，但是，由于运输问题的约束系数矩阵有其特殊的结构和性质，因而有比单纯形法更有效的方法来求解。第三章运输问题运输问题的数学模型表上作业法产销不平衡的运输问题求初始基可行解的方法：西北角法、最小元素法、元素差额法基可行解的改进方法：闭回路调整法、位势法例：某运输问题的资料如下：单位销地运价产地产量2910791342584257销量38464321BBBB321AAA一、运输问题的数学模型试制定一个调运方案，使得总运费最省？ijx设为运量111213142122232429107342minZxxxxxxxx313233348425xxxx111213142122232431323334112131122232132333142434957384601231234ijxxxxxxxxxxxxxxxs.t.xxxxxxxxxxi,,,j,,,数学模型的一般形式已知资料如下：单位销运价地产地产量销量nBB1nbb1mnmncccc11111maa1mAA当产销平衡时，其模型如下：11111212011mnijijijnijijmijjiijminZcxxa,i,,...,ms.t.xb,j,,...,nxi,...,m,j,...,n11mnijijab(3.1)当产大于销时，其模型是：11111212011mnijijijnijijmijjiijminZcxxa,i,,...,ms.t.xb,j,,...,nxi,...,m,j,...,n11mnijijab(3.2)当产小于销时，其模型是：11111212011mnijijijnijijmijjiijminZcxxa,i,,...,ms.t.xb,j,,...,nxi,...,m,j,...,n11mnijijab(3.3)运输问题的特征：1、平衡运输问题必有可行解，也必有最优解；11mnijijabQ证设11ijijabxi,...,m,j,...,nQ取011ijxi,...,m,j,...,n则显然有1111nnnijiijjijjjabaxbai,...,mQQ又1111mmmijjijijiiiabbxabj,...,nQQ011ijijci,...,m,j,...,nx由于，所以对于任意一个可行解，31.问题的目标函数值都大于等于零，即目标函数值有下界零。对于求极小值问题，目标函数值有下界，则必有最优值111111111111111111.........A111212122212nnmmmnxxxxxxxxxm行n行01010TijijxP相应于的列向量10ijPimj,.即中的第个分量和第个分量为其余的元素均为第i行第m+j行1212111111111111111111mna...a...a...Abbb111212122212nnmmmnxxxxxxxxx2m,n,mnmnAmn证假设则有于是的秩AmnA又由平衡条件知，的前行之和应等于后行之和，因此Amn的行是线性相关的，故必有的秩1AmnB其次，证明中至少存在一个阶的非奇异方阵1mnB,按下列方式选一个阶的子方阵使得231..AA运输问题的约束方程系数矩阵和增广矩阵的秩相等，1mn且等于3、运输问题的基可行解中应包括m+n－1个基变量。1112121311nmxxxxxx110101111101B前2~m行后n行A可见的秩为m+n-1，又B包含在A中，故A的秩为m+n-1闭回路：凡是能排列成111222231sssijijijijijijx,x,x,x,...,x,x112122321sssijijijijijijx,x,x,x,...,x,x或1212ssi,i,...,ij,j,...,j其中互不相同，互不相同形式的变量集合，若用一条封闭折线将它们连接起来形成的图形称为一个闭回路，其中诸变量称为闭回路的顶点，连接相邻两个顶点及最后一个顶点与第一个顶点的线段称为闭回路的边。B1B2B3B4B5A1x11x14A2x21x22A3x32x35A4x44x451114444535322221x,x,x,x,x,x,x,x闭回路具有以下性质：(1)每一个顶点都是转角点；基格：闭回路的顶点闭回路在基格处可以直行，也可以拐弯，在空格处必须直行，不能拐弯。(2)每一条边都是水平线或垂直线，闭回路是由这些水平线或垂直线构成的一条封闭折线；(3)每一行(或列)若有闭回路的顶点，则必有两个。空格：基格外的格。闭回路的性质：111222231sssijijijijijijx,x,x,x,...,x,x1.构成闭回路的变量组对应的111222231sssijijijijijijP,P,P,P,...,P,P列向量组必线性相关。111222231sssijijijijijijPPPP,...,PP证：直接计算可知=0111222231sssijijijijijijx,x,x,x,...,x,x2.若变量组中有一个部分组构成111222231sssijijijijijijP,P,P,P,...,P,P闭回路，则列向量组是线性相关。11221131mnmnijijijmnx,x,...,x.个变量构成基变量的充要条件是它不含闭回路。41.mn在个基变量中加入任何一个非基变量空格则加入空格后的m+n个格中必含有唯一的闭回路。二、初始基可行解的求法(表上作业法)运输问题(3.1)的解法主要有图上作业法和表上作业法两种。表上作业法又称为运输单纯形法，它是根据单纯形法的原理和运输问题的特征，设计出来的一种便于在表上运算的方法，作为一种迭代方法，它的主要步骤：(1)求一个初始基可行解(又称初始调运方案)；(2)判别当前的基可行解是否为最优解，若是，则迭代停止；否则，转下一步；(3)改进当前的基可行解，得新的基可行解，再返回(2)此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而备受欢迎。1、西北角法（或左上角法）：遵循的原则：优先安排运价表上编号最小的产地和销地之间(即运价表的西北角位置)的运输业务。例1设有某物资共有3个产地A1,A2,A3,其产量分别为9,5,7个单位，另有4个销地B1,B2,B3,B4,其销量分别为3,8,4,6,已知由产地Ai运往销地Bj的单位运价见下表，问应如何调运,才能使总运费最省？1、求初始调运方案：单位销地运价产地B1B2B3B4产量A1291079A213425A384257销量3846单位销地运价产地B1B2B3B4产量A1291079A213425A384257销量3846首先安排产地A1与销地B1之间的运输业务，即从运价表上西北角(或左上角)位置x11开始分配运输量，并使x11取尽可能大的数值。现在产地A1的产量为9,而销地B1的需求量为3.故安排产地A1运送3个单位的货物给销地B1,即取x11=min{a1,b1}=min{3,9}=3，当产地A1运出3个单位货物后，还剩9-3=6个单位，此时销地B1的需求量已得到满足，此时A2,A3不可能再运送货物给销地B1了，此时将B1列划去；再在剩下的运价表上，重复上述过程，即决定x12306602203301160600A1运送6个单位货物给B2,此时A1的供应量为0，划去A1行，B2的需求量为2.用同样的方法得初始基可行解X(0)的各分量为：0326923341265110z111222233334362316x,x,x,x,x,x相应的目标函数值2、最小元素法遵循原则：优先安排单位运价最小的产地与销地之间的运输业务。依次安排最小元素、次小元素，从而得到一个初始基可行解。用此方法制定出来的调运方案，其总运费一般会比用西北角法制定的调运方案要省。单位销地运价产地B1B2B3B4产地A1291079A213425A384257销地3846例2用最小元素法制定例1的初始调运方案。第1个最小元素为c21=1,此时比较A2的产量和B1的销量此时取其最小值，x21=min{5,3}=3,则安排A2运送3个单位货物给B1,此时A2剩余2个单位，B1的需求量已满足，将B1列划去；再在剩余表格中找最小元素c24=2,此时令x24=min{2,6}=2则安排A2运送2个单位货物给B4,则A2的供应量已尽，B4余4个单位，则将A2行划去；再在剩余表格中重复以上过程，最终得初始调运方案。302204403305450500西北角法与最小元素法的比较西北角法的最大优点是实现简单，特别适合编制程序上机计算，但缺点是所制定的初始方案往往离最优解较远，后面的调整量较大。而最小元素法的最大优点是制定的初始方案一般离最优解较近，后面调整量较小。但要在一张大型的运价表上每次搜索最小元素，其计算量也是很可观的。当然，当问题的规模不大，用手工计算时，可以通过人的判断力，很快找到最小元素，因此，用手工计算时，一般采用最小元素法求初始调运方案较好。ijx定理：用西北角法或最小元素法得到的一组变量的值31.是运输问题的一个基可行解，而格中的数恰是对应的基变量的值，个数为m+n-1ij证首先根据x的取法可知，每填一个数，就要修改相应31.行的产量和列的需求量，因而这样得到的一个解必是问题的一个可行解。1mn其次，证明填有数字的格恰是个，因为采用这种方法，每填一个数字，就要划去一行或一列，即行数与列数1.之和总是减少22mn,在填了个数字之后，行数与列数之和为即只剩下一行一列，这时显然只能再填一个数，就把所有的行与列消去了，故一共填了m+n-1个数。1mn下证个填有数字的格对应的变量集合不包含闭回路反证法：假设这组数中含有一个闭回路111211ijijijxxx假定在填这个数时划去的是行，那么这个数比先填122212ijijijxxx并且填时划去的应是列，由此这个数要比先填222122ijijijxxx而且填时划去的应是行，这又说明一定比先填2111ijijxx而且填时划去的应是列，这样一来处根本就不能填数了因而得出矛盾。故这组变量不包含闭回路。11ijx22ijx21ijx12ijx3、元素差额法元素差额法是在最小元素法的基础上改进的一种求初始方案的方法，在分配运量以确定产销关系时，不是从最小元素开始，而是从运价表中各行和各列的最小元素和次小元素之差额来确定产销关系，(按最大差额所在行或列中的最小元素安排产地与销地之间的运输业务)因此称为元素差额法。单位销地运价产地B1B2B3B4产地差额A1291079A213425A384257销地3846差额3061512112212123358222500345221305972501100初始调运方案为111214243233351534x,x,x,x,x,x1闭回路求检验数对于给定的调运方案(基可行解)，从非基变量xij出发作一条闭回路，要求该闭回路上其余的顶点均为基变量，并