第三章第三章 特殊的线性规划特殊的线性规划运输问题运输问题&模型及其特点模型及其特点&求解思路及相关理论求解思路及相关理论&求解方法求解方法表上作业法表上作业法&运输问题的推广运输问题的推广产销不平衡的运输问题产销不平衡的运输问题转运问题转运问题&运输问题的线性规划软件求解运输问题的线性规划软件求解3.0 3.0 运输问题引例运输问题引例1.施工组织多供点调运问题 大型施工企业,工程建筑中所需的材料、混合料会存放在多个中心仓库或由多个拌和站提供,而每个仓库或拌和站又会给多个不同的施工工地供应材料,这样就出现了多个供点与多个需点间调运优化的问题。1.1工程实例某大型建筑施工公司,有6个施工工地需使用水泥砼混合材料,公司经过技术经济分析后,决定购买商品砼给这6个工地使用。通过市场调查,有3家砼供应商的水泥砼能满足这6个工地的施工使用要求。各供应商供货的原始资料见表1,各工地砼的需要量及各供应商可供砼的数量见表2。确定各工地应从这3个砼供应商处分别购买多少砼可使该建筑公司对此商品砼投入的费用最低。2.垃圾运输问题随着人民生活水平的提高,人们对环境质量的要求越来越高,城市垃圾作为城市公害问题越来越受到各级政府部门的重视. 如何科学合理地运输城市垃圾,成为一个重要问题.2.1工程实例沈阳市内5区为沈河区,和平区,铁西区,皇姑区,大东区,要把这5个区的垃圾运到赵家沟处理场,塔山处理场,沈阳市处理场,畜牧场垃圾处理场,马古垃圾处理场进行处理.怎样调运各区垃圾量才能使总的运输吨公里最小?各区,各处理场及其运距的量见表1.3.土方工程施工中的运输问题一个土方工程项目中,往往会有多个挖区和填区,特别是当工程为分期分批施工时,先期工程与后期之间的土方堆放和调运问题应当全面考虑,力求避免重复挖运和场地混乱,为使土方总运输量最小或土方运输成本最小或土方施工费用最小,土方施工前先进行土方调配设计非常有必要.3.1工程实例青山湖电排站扩建工程位于南昌市青山湖区塘山镇,青山湖北部出入口处,北邻赣江。该工程土方开挖总量为4.8万3,土方回填总量为5.7万3,为弥补回填料不足需另取土料0.9万3。具体见表1。3.1 3.1 运输问题模型与性质运输问题模型与性质一、运输问题的数学模型一、运输问题的数学模型 1 1、 运输问题的一般提法：运输问题的一般提法： 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数产量总数等于销量总数。已知各产地的产量产量和各销地的销量销量以及各产地到各销地的单位运价（或运距）单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量总运费（或总运输量）最省）最省？单位单位根据具体问题选择确定。表3-1有关信息单位运价销或运距地产地B1B2Bn产量A1A2Amc11c12c1nc21c22c2ncm1cm2cmna1a2am销量b1b2bn2 2、运输问题的数学模型、运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量（i=1，m；j=1，n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足： 同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足： 总运费为：运输问题的数学模型运输问题的数学模型（3-6）二、运输问题的特点与性质二、运输问题的特点与性质1 1约束方程组的系数矩阵具有特殊的结构约束方程组的系数矩阵具有特殊的结构写出式（写出式（3-13-1）的系数矩阵）的系数矩阵A A，形式如下：，形式如下：m行n行 矩阵的元素均为矩阵的元素均为1 1或或0 0； 每一列只有两个元素为每一列只有两个元素为1 1，其余元素均为，其余元素均为0 0； 列向量列向量P Pij ij=(0,=(0,，0 0，1 1，0 0，,0,1,0,0),0,1,0,0)T T，其中两个元素，其中两个元素1 1分别处于第分别处于第i i行和第行和第m+jm+j行。行。 将该矩阵分块，特点是：将该矩阵分块，特点是：前前mm行构成行构成mm个个mnmn阶矩阵阶矩阵，而且，而且第第k k个矩阵只有第个矩阵只有第k k行元素全行元素全为为1 1，其余元素全为，其余元素全为0 0（k=1k=1，mm）；后后n n行行构成构成mm个个n n阶单位阵阶单位阵。2. 2.运输问题的基变量总数是运输问题的基变量总数是m+n-1m+n-1写出增广矩阵写出增广矩阵 证明系数矩阵证明系数矩阵A A及其增广矩阵的秩都是及其增广矩阵的秩都是m+n-1m+n-1S S 前前mm行相加之和减去后行相加之和减去后n n行相加之和结果是行相加之和结果是零向量，说明零向量，说明m+nm+n个行向量线性相关，因此个行向量线性相关，因此的秩小于的秩小于m+nm+n； ？ 因此因此的秩恰好等于的秩恰好等于m+n-1m+n-1，又，又D D本身就含于本身就含于A A中，故中，故A A的秩也等于的秩也等于m+n-1m+n-1S S 由由的第二至的第二至m+nm+n行和前行和前n n列及列及对应的列交叉处元素构成对应的列交叉处元素构成m+n-1m+n-1阶方阵阶方阵DD非奇非奇异；异； ？可以证明可以证明：m+nm+n个约束方程中的任意个约束方程中的任意m+n-1m+n-1个个都是线性无关的都是线性无关的。定义定义3.13.1 凡是能排成凡是能排成 (3-4)(3-4)或或(3-5)(3-5)形式的形式的变量集合变量集合称为一个称为一个闭回路闭回路, ,并称式中并称式中变变量量为该为该闭回路的顶点闭回路的顶点；其中；其中 互不互不相同相同,互不相同。互不相同。3.m+n-13.m+n-1个变量构成基变量的个变量构成基变量的充要条件充要条件是是它们不构成它们不构成闭回路闭回路。X11 X13X21X24 X33B1B2B3B4A1X12X14A2X22X23A3X31X32X34例例3-13-1 设设m=3m=3，n=4n=4，决策变量，决策变量x xij ij表示从产地表示从产地A Ai i到销地到销地B Bj j的调运量，列表如下，给出闭回路的调运量，列表如下，给出闭回路在表中的表示法在表中的表示法用折线连接起来的顶点变量用折线连接起来的顶点变量。 练习练习3-13-1请给出闭回路请给出闭回路和和在表中的表示法。在表中的表示法。X11 X13X21X24 X33B1B2B3B4A1X12X14A2X22X23A3X31X32X34练习练习3-23-2 下面的折线构成的封闭曲线连接的顶下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？点变量哪些不可能是闭回路？为什麽？（a）（b）（c）（d）（e）表中的折线构成一条封闭曲线，且所有的边都是水平水平或垂直垂直的；表中的每一行每一行和每一列每一列由折线相连的闭回由折线相连的闭回路的顶点路的顶点只有两个只有两个；有关闭回路的一些重要结果有关闭回路的一些重要结果定理定理3-13-1 设设 是一个闭是一个闭回路，则该闭回路中的变量所对应的系数列回路，则该闭回路中的变量所对应的系数列向量向量 具有下面的具有下面的关系：关系：注意：注意：列向量列向量P Pij ij=(0,0,1,0,0,1,0,0)=(0,0,1,0,0,1,0,0)T T中两中两个元素个元素1 1分别处于第分别处于第i i行和第行和第m+jm+j行，直接计算行，直接计算即可得到结果。即可得到结果。 定理的证明可定理的证明可借助定理借助定理3-13-1和高等和高等代数中代数中“ “向量组中，若向量组中，若部分向量线性部分向量线性相关，则整个向量组就线性相关相关，则整个向量组就线性相关” ”的的定理得到。定理得到。定理定理3-23-2 若变量组若变量组中有一个部分组构成闭回路，则该变中有一个部分组构成闭回路，则该变量组对应的系数列向量线性相关。量组对应的系数列向量线性相关。定理定理3-33-3 不包含任何闭回路的变量组中不包含任何闭回路的变量组中必有孤立点。必有孤立点。所谓所谓孤立点孤立点是指是指在所在行或列中出现于该变在所在行或列中出现于该变量组中的唯一变量。量组中的唯一变量。可用反证法证明结论成立。可用反证法证明结论成立。定理定理3-43-4 r r个变量个变量 对应对应的系数列向量线性无关的系数列向量线性无关充要条件充要条件是该变是该变量组量组不包含闭回路。不包含闭回路。必要性的证明可考虑用反证法结合定理必要性的证明可考虑用反证法结合定理3-23-2的结果进行，充分性的证明可借助的结果进行，充分性的证明可借助定理定理3-33-3，根据向量组线性无关的定义，根据向量组线性无关的定义用归纳法得证。用归纳法得证。 推论推论 m+n-1m+n-1个变量构成基变量的充要个变量构成基变量的充要条件是该变量组不含闭回路。条件是该变量组不含闭回路。三、运输问题的求解方法三、运输问题的求解方法1、单纯形法（为什麽？）2、表上作业法 由于问题的特殊形式而采用的由于问题的特殊形式而采用的更简洁、更方便的方法更简洁、更方便的方法1.两个工厂B1、B2，它们需要同一种原料，数量分别是72吨、102吨，另外有两个座仓库A1、A2可以供应上述原料56吨、118吨，由于工厂和仓库位置不同，单位运价不用，具体数据如下：试找到总运价最小的解决方案.（应用单纯形法求解）B1B2供应应（吨）A14856A21624118需求（吨）72102174单位（元/吨）