运输问题模型与性质

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

1、第三章特殊的线性规划——运输问题&模型及其特点&求解思路及相关理论&求解方法——表上作业法&运输问题的推广产销不平衡的运输问题转运问题1.运输问题模型及有关概念问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。1.运输问题模型及有关概念例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？

2、解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：1.运输问题模型及有关概念Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）1.运输问题模型及有关概念111000000111100100010010001001系数矩阵1.运输问题模型及有关概念模型系数矩阵特征1.共有m+n行，分别表示各产地和销地；mn列，分别表示各

3、决策变量；2.每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用。1.运输问题模型及有关概念一般运输问题的线性规划模型及求解思路一般运输问题的提法：假设A1,A2,…,Am表示某物资的m个产地；B1,B2,…,Bn表示某物资的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价（表4-3）。如果s1+s2+…+sm=d1+d2+…+dn则称该运输问题为产销平衡问题；否则，称产销不平衡。首先讨论产销平衡问题。1.运输问题模型及有关概念表4-3运输问题数据表1.运输问题模型及有关概念销地产

4、地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmns1s2┇sm销量d1d2…dn设xij为从产地Ai运往销地Bj的运输量，根据这个运输问题的要求，可以建立运输变量表（表4-4）。表4-4运输问题变量表1.运输问题模型及有关概念销地产地B1B2…Bn产量A1A2┇Amx11x12…x1nx21x22…x2n┇┇┇┇xm1xm2…xmns1s2┇sm销量d1d2…dn3.1运输问题模型与性质一、运输问题的数学模型1、运输问题的一般提法：某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地

5、，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？单位根据具体问题选择确定。表3-1有关信息单位运价销或运距地产地B1B2…Bn产量A1A2┆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

6、还应满足：总运费为：运输问题的数学模型（3-6）二、运输问题的特点与性质1．约束方程组的系数矩阵具有特殊的结构写出式（3-1）的系数矩阵A，形式如下：m行n行矩阵的元素均为1或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及其增广矩阵的秩

7、都是m+n-1前m行相加之和减去后n行相加之和结果是零向量，说明m+n个行向量线性相关，因此的秩小于m+n；？因此的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1由的第二至m+n行和前n列及对应的列交叉处元素构成m+n-1阶方阵D非奇异；？203.2运输问题的求解方法约束条件非常有规律，技术系数非0即1基变量的个数远小于决策变量的个数采用表上作业法，称为位势法和踏石法运算中涉及两个表：运费表和产销平衡表(分配表)213.2.1寻找初始可行解的方法1、西北角法从x11开始分配，从西北向东南方向逐个分配xij的分配公式例3.2.122

8、例3.2.1西北角法232、最低费用法采用最小费用优先分配的原则，看一步f(x)=121，比西北角法低842