第三章--运输问题

《运筹学》第三章运输问题Slide1第三章运输问题运输问题数学模型表上作业法确定初始基可行解最优解的判别改进的方法---闭回路调整法表上作业法计算中的问题产销不平衡的运输问题及其求解应用举例《运筹学》第三章运输问题Slide2某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：问：应如何调运，使得总运输费最小？引例200150150300556200646Ｂ1Ｂ2Ｂ3产量(件)销地销量产地A1A2《运筹学》第三章运输问题Slide3设xij表示从产地Ai调运到Bj的运输量(i＝1,2；j＝1,2,3)，现将安排的运输量列表如下：满足产地产量的约束条件为：x11+x12+x13=200x21+x22+x23=300200150150300556200646Ｂ1Ｂ2Ｂ3产量(件)销地销量产地A1A2使运输费最小的目标函数为：minz＝6x11+4x12+6x13+6x21+5x22+5x23满足销地销量的约束条件为：x11+x21＝150x12+x22＝150x13+x23＝2000ijx《运筹学》第三章运输问题Slide41运输问题及其模型有m个产地生产某种物资，有n个地区需要该类物资令a1,a2,…,am表示各产地产量，b1,b2,…,bn表示各销地的销量，ai=bj称为产销平衡设xij表示产地i运往销地j的物资量，cij表示对应的单位运费，则我们有运输问题的数学模型如下：《运筹学》第三章运输问题Slide50,,2,1,,2,1min1111ijjmiijnjiijminjijijxnjbxmiaxxcz销量约束产地约束运输问题有mn个决策变量，m+n个约束条件。销量产量销地产地n21nbbb21m21maaa21销地产地n21mnmmnnccccccccc212222111211m210,0..minbXbAXtsCXzC=(c11，c12，…，c1n，c21，c22，c2n，…，cm1，cm2，…cmn)b=（a1，a2，…，am，b1，b2，…bn)TX=(x11，x12，…，x1n，x21，x22，x2n，…，xm1，xm2，…xmn)T其矩阵形式为1001001000100100100010010011110000000001110000000001112121nmvvvuuuA行n行m0,,2,1,,2,1min1111ijjmiijnjiijminjijijxnjbxmiaxxcz销量约束产地约束mnmmnnxxxxxxxxx212222111211《运筹学》第三章运输问题Slide7xij的系数向量Pij的分量除第i个和第m+j个为1外，其余都为0。Pij=(0，…，1，…，0，…，1，…0)T=ei+em+j由于产销平衡条件miiminjijnjmiijnjjaxxb111111)()(最多只有m+n–1个相互独立，因此，运输问题的基变量最多只有m+n–1个对于m，n≥2，有m+n≤m×n，R(A)≤m+n《运筹学》第三章运输问题Slide8注意到在A中去掉第1行而取出第2，第3，…，第m+n行，又取出与所对应的列，则由这些取出的行和列的交叉处的元素构成的一个m+n-1级子式D1312111211,,,,,,,mnxxxxxx01111111111D1)(nmAr所以1nm，由此可知，运输问题的任何一组基都由个变量组成。1312111211mnxxxxxx运输问题的求解方法约束条件非常有规律，技术系数非0即1基变量的个数远小于决策变量的个数采用表上作业法，称为位势法和踏石法运算中涉及两个表：运费表和产销平衡表(分配表)销地产量运量12nai产地1x11x12x1na12x21x22x2na2mxm1xm2xmnam销量bjb1b2bn销地运费12n产地1c11c12c1n2c21c22c2nmcm1cm2cmn2表上作业法《运筹学》第三章运输问题Slide10某公司经销一种产品，它下设三个工厂、四个销售部。三个工厂的日产量分别为：A1—7吨，A2—4吨，A3—9吨；各销售部的日销量分别为：B1—3吨，B2—6吨，B3—5吨，B4—6吨。各厂到各销售部的单位产品的运价如下表。问该公司应如何调运产品，才能完成运输任务而使运费最省。销地产地B1B2B3B4A1A2A3317119433101085例《运筹学》第三章运输问题Slide11x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1,2,3;j=1,2,3,4)用线性规划法处理此问题。设由产地i到销地j的运量为xij，模型为：3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34minz=《运筹学》第三章运输问题Slide12销地产地B1B2B3B4产量A1A2A3749销量3656产销平衡表销地产地B1B2B3B4A1A2A3317119432101085单位运价表运输问题一般用表上作业法求解，需建立表格模型：《运筹学》第三章运输问题Slide13(1)给出初始调运方案。——初始基可行解：即在(m×n)产销平衡表上给出m+n-1个数字格。(2)检验方案是否最优,若是最优解,则停止计算;否则转下一步。求各非基变量的检验数，即在表上计算空格的检验数。(3)调整调运方案，得新的方案。——确定入基和出基变量，找出新的基可行解。在表上用闭环回路法。(4)重复(2),(3)直到求出最优方案。表上作业法步骤类似于单纯形法:表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。《运筹学》第三章运输问题Slide14证:记Xij=aibj/Q就是一个可行解,因为xij≥0,且满足又因为cij≥0,xij≥0,所以目标函数有下界零,因而运输问题一定有最优解.Qnjjbmiia11【定理】：产销平衡的运输问题一定有可行解，且一定有最优解。jmiijnjiijbxax11,0,,2,1,,2,1min1111ijjmiijnjiijminjijijxnjbxmiaxxcz销量约束产地约束《运筹学》第三章运输问题Slide15最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止。2.1确定初始基可行解最常用的方法是最小元素法。——既简便，又尽可能接近最优解。表上作业法要求，调运方案的数字格必须为m+n-1个，且有数字格不构成闭回路。一般用最小元素法给出的方案符合这要求。《运筹学》第三章运输问题Slide16销地产地B1B2B3B4Ａ１Ａ２Ａ３产量ai749３6５6销量bj3B1B2B3B43113101928741015平衡表运价表初始基本可行解为(x13,x14,x21,x23,x32,x34)=(4,3,3,1,6,3)相应运价为：（c13,c14,c21,c23,c32,c34）=（3,10,1,2,4,15）由此表上作业得初始调运方案的总运费为S=4x3+3x10+3x1+1x2+6x4+3x15=86（元）求解运输问题的表上作业法的步骤：143361123343546731）找出最小运价为1，先将A2的产品供应给B1，因a2b1，A2除满足B1的全部需要外，还可多余1吨产品。在(A2,B1)的交叉格处填上3。并将B1列运价划去。销地产地B1B2B3B4产量A1A2A3749销量3656销地产地B1B2B3B4A1A2A33171194321010853146332）在未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3。在(A2,B3)的交叉格处填上1。并将A2行运价划去3）在未划去的元素中再找出最小的运价3，这样一步步进行下去，直到运价表上的所有元素划去为止。最后在(A1,B4)的交叉格处填上3，将A1行和B4列运价同时划去，得到一个初始调运方案。这方案的总运费为86元。《运筹学》第三章运输问题Slide18最小元素法中的退化情况第一次划去第1列B1，第二次最小运价为2，对应的销地B2销量和产地A3的产量未分配量皆为6，故同时划去B2列和A3行。非零的数字格小于(m+n-1)个。出现退化时，要在同时被划去的行列中任选一个空格填0，此格作为有数字格。销地产地B1B2B3B4产量A1A2A3749销量3656销地产地B1B2B3B4A1A2A3331119234101085345602《运筹学》第三章运输问题Slide19销地产地B1B2B3B4行差额A1A2A3317119432101085011列差额2513伏格尔法考虑到：一产地的产品假如不能按最小运费就近供应，就应考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。销地产地B1B2B3B4产量A1A2A3749销量3656315632伏格尔法(Vogel)：最小元素法的缺点是：为了节省一处的费用，有时会造成在其他处要多花几倍的运费。销地产地B1B2B3B4行差额A1A2A3317119432101085002列差额2522销地产地B1B2B3B4行差额A1A2A3317119432101085762列差额2512销地产地B1B2B3B4行差额A1A2A3317119432101085012列差额2512销地产地B1B2B3B4行差额A1A2A3317119432101085012列差额2513《运筹学》第三章运输问题Slide211）分别计算出各行和各列的最小运费和次最小运费的差额，填入表格的最右列和最下行。2）从行或列差额中选出最大者，选择它所在行或列中的最小元素。B2列中的最小元素是4，可确定A3的产品先满足B2的需要，同时将B2列运价划去。3）对未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重新填入表格的最右列和最下行。重复1）2），直到找到初始调运方案。总运费为85元。伏格尔法给出的初始解比用最小元素法给出的更接近最优解。本例用伏格尔法给出的初始解就是最优解。《运筹学》第三章运输问题Slide222.2最优性解的判别判别的方法是计算空格（非基变量）的检验数，若所有的检验数都大于等于0，为最优解。ijBijPBCc1两种方法:闭回路法和位势法表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数σij＝0，非基变量的检验数σij≥0。σij0表示运费减少，σij0表示运费增加。目标函数要求最小化闭环回路法：在给出的初始调运方案表上，从每一空格出发找一条闭环回路，它是以某空格为起点，用水平或垂直线向前划，遇到某一个适当有调运量的格子转90°后，继续前进，直到回到起始空格为止。从每一空格出发一定存在且只有唯一的闭环回路。由闭回路的构成可见，除起点是空格外，其余所有的拐角点都是填有调运量的。从空格开始加减闭环各个顶点的运输单价，可得每个空格对应的检验数。《运筹学》第三章运输问题Slide24从每一空格出发一定存在和可以找到唯一的闭回路。因(m+n-1)个数字格(基变量)对应的系数向量是一个基。任一空格(非基变量)对应的系数向量是这个