运筹学第三章3.1运输问题模型与性质.ppt

《运筹学第三章3.1运输问题模型与性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章特殊的线性规划——运输问题&模型及其特点&求解思路及相关理论&求解方法——表上作业法&运输问题的推广产销不平衡的运输问题转运问题3.1运输问题模型与性质一、运输问题的数学模型1、运输问题的一般提法：某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？单位根据具体问题选择确定。表3-1有关信息单位运价销或运距地产地B1B2…Bn产量A1

2、A2┆Amc11c12…c1nc21c22…c2n………cm1cm2…cmna1a2┆am销量b1b2…bn2、运输问题的数学模型设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足：同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足：总运费为：运输问题的数学模型（3-1）二、运输问题的特点与性质1．约束方程组的系数矩阵具有特殊的结构写出式（3-1）的系数矩阵A，形式如下：m行n行矩阵的元素均为1或

3、0；每一列只有两个元素为1，其余元素均为0；列向量Pij=(0,…，0，1，0，…,0,1,0,…0)T，其中两个元素1分别处于第i行和第m+j行。将该矩阵分块，特点是：前m行构成m个m×n阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，…，m）；后n行构成m个n阶单位阵。2.运输问题的基变量总数是m+n-1写出增广矩阵证明系数矩阵A及其增广矩阵的秩都是m+n-1前m行相加之和减去后n行相加之和结果是零向量，说明m+n个行向量线性相关，因此的秩小于m+n；？因此的秩恰好等于

4、m+n-1，又D本身就含于A中，故A的秩也等于m+n-1由的第二至m+n行和前n列及对应的列交叉处元素构成m+n-1阶方阵D非奇异；？可以证明：m+n个约束方程中的任意m+n-1个都是线性无关的。定义3.1凡是能排成(3-4)或(3-5)形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中互不相同,互不相同。3.m+n-1个变量构成基变量的充要条件是它们不构成闭回路。X11X13X21X24X33B1B2B3B4A1X12X14A2X22X23A3X31X32X34例3-1设m=3，n=

5、4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路在表中的表示法——用折线连接起来的顶点变量。三、运输问题的求解方法1、单纯形法（为什么？）2、表上作业法由于问题的特殊形式而采用的更简洁、更方便的方法3.2运输问题的表上作业法一、表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图3-1所示。表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。确定初始方案(初始基本可行解)改进调整（换基迭代）否判

6、定是否最优？是结束最优方案图3-1运输问题求解思路图二、初始方案的确定1、作业表（产销平衡表）初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”（产销平衡表）。表3-3是两个产地、三个销地的运输问题作业表。调销地运量产地B1B2B3产量A1c11X11c12X12c13X13a1A2c21X21c22X22c23X23a2销量b1b2b3表3-3运输问题作业表（产销平衡表）其中xij是决策变量，表示待确定的从第i个产地到第j个销地的调运量，cij为从第i个

7、产地到第j个销地的单位运价或运距。2、确定初始方案的步骤：（1）选择一个xij，令xij=min{ai，bj}=将具体数值填入xij在表中的位置；（2）调整产销剩余数量：从ai和bj中分别减去xij的值，若ai-xij=0，则划去产地Ai所在的行，即该产地产量已全部运出无剩余，而销地Bj尚有需求缺口bj-ai；若bj-xij=0，则划去销地Bj所在的列，说明该销地需求已得到满足，而产地Ai尚有存余量ai-bj；（3）当作业表中所有的行或列均被划去，说明所有的产量均已运到各个销地，需求全部满足，xij

8、的取值构成初始方案。否则，在作业表剩余的格子中选择下一个决策变量，返回步骤（2）。按照上述步骤产生的一组变量必定不构成闭回路，其取值非负，且总数是m+n-1个，因此构成运输问题的基本可行解。对xij的选择采用不同的规则就形成各种不同的方法，常用的方法有最小元素法和伏格尔法。下面通过具体实例分别介绍。3、举例例3-2甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4，求使总运输量最少的调运方案。表3-4例3-2有关信息