[理学]运筹第4章运输问题

《[理学]运筹第4章运输问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、1a2┆am销量b1b2…bn32、运输问题的数学模型设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足：4同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足：总运费为：5运输问题的数学模型6二、运输问题的特点与性质1．约束方程组的系数矩阵具有特殊的结构写出系数矩阵A，形式如下：m行n行7矩阵的元素均为1或0；每一列只有两个元素为1，其余元素均为0；列向量Pij=(0,…，0，1，0…,0,1,0,…0)T，其中两个元素1分别处于第i行和第m+j行。将该矩阵分块，特点

3、是：前m行构成m个m×n阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，…，m）；后n行构成m个n阶单位阵。82.运输问题的基变量总数是m+n-1写出增广矩阵9定义4.1凡是能排成或形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中互不相同,互不相同。3.m+n-1个变量构成基变量的充要条件是它们不构成闭回路。10X11X13X21X24X33B1B2B3B4A1X12X14A2X22X23A3X31X32X34例4-1设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路在表中的表示法——用折线连接起

4、来的顶点变量。11练习4-1请给出闭回路和在表中的表示法。X11X13X21X24X33B1B2B3B4A1X12X14A2X22X23A3X31X32X3412练习4-2下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？（a）（b）（c）（d）（e）表中的折线构成一条封闭曲线，且所有的边都是水平或垂直的；为什麽？表中的每一行和每一列由折线相连的闭回路的顶点只有两个；为什麽？13三.运输问题求解—表上作业法一、表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图4-1所示。表上作业

5、法和单纯形法的求解思想完全一致，但是具体作法更加简捷。14确定初始方案(初始基本可行解)改进调整（换基迭代）否判定是否最优？是结束最优方案图4-1运输问题求解思路图15调销地运量产地B1B2B3产量A1c11X11c12X12c13X13a1A2c21X21c22X22c23X23a2销量b1b2b3表4-2运输问题作业表（产销平衡表）161、初始基本可行解的确定找到m+n–1个不构成闭回路的基变量。较常用的方法有西北角法、最小元素法和伏格尔法。二、产销平衡问题—表上作业法步骤17—西北角法甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各

6、城市的运输距离见表3-4，求使总运输量最少的调运方案。18调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用西北角法确定例4-2初始调运方案100100100505020020019得到初始调运方案为：x11=100，x12=100，x22=50，x23=200运输费用为3425020调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用最小元素法确定例3-2初始调运方案1501001001

7、0010010010021得到初始调运方案为：x11=100，x13=100，x22=150，x23=100运输费用为3625022B1B2B3产量A190X1170X12100X13200A280X2165X2275X23250销量100150200450用伏格尔法确定例3-2初始调运方案5050200150505050两最小元素之差101525101510两最小元素之差202001015023得到初始调运方案为：x11=50，x12=150，x21=50，x23=200运输费用为34000242、最优性检验检查当前调运方案是不是最优方案的过程就是