第三章特殊的线性规划 运輪闷题 &模型及其特点 &求解思路及相关理论 &求解方法表上作业法 &运输问题的推广 产销不平衡的运输问题 转运问题
第三章 特殊的线性规划 ——运输问题 & 模型及其特点 & 求解思路及相关理论 & 求解方法——表上作业法 & 运输问题的推广 产销不平衡的运输问题 转运问题
3.1运输问题模型与性质 、运输问题的数学模型 1、运输问题的一般提法:某种物资有若 干产地和销地,现在需要把这种物资从各个 产地运到各个销地,产量总数等于销量总数 已知各产地的产量和各销地的销量以及各产 地到各销地的单位运价(或运距),问应如 何组织调运,才能使总运费(或总运输量) 最省?
3.1 运输问题模型与性质 一 、运输问题的数学模型 1、 运输问题的一般提法： 某种物资有若 干产地和销地，现在需要把这种物资从各个 产地运到各个销地，产量总数等于销量总数。 已知各产地的产量和各销地的销量以及各产 地到各销地的单位运价（或运距），问应如 何组织调运，才能使总运费（或总运输量） 最省？
表3-1有关信息 单位运价、销 或运距地B1B2 B 产量 n 产地 2 C1 a 21 22 2 m m2 m n 销量 2 ∑a1=∑b L= 单位根据具体问题选择确定
单位根据具体问题选择确定。 表3-1 有关信息 单位 运价 销 或运距 地 产地 B1 B2 … Bn 产 量 A1 A2 ┆ Am c11 c12 … c1 n c21 c22 … c2n … … … cm1 cm2 … cm n a1 a2 ┆ am 销 量 b1 b2 … bn = = = n j j m i i a b 1 1
2、运输问题的数学模型 设x;为从产地A运往销地B的物资数量 (i=1,…m;j=1,…n),由于从A 运出的物资总量应等于A的产量a,因此 x:应满足: ∑x1=a4 1,2,…,m
2、运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量 （i=1，…m；j=1，…n），由于从Ai 运出的物资总量应等于Ai的产量ai，因此 xij应满足： x a i m n j i j i 1,2, , 1 = = =
同理,运到B的物资总量应该等于B 的销量b,所以x还应满足: ∑x=bj 总运费为: z=∑∑Cnx i=1j=1
同理，运到Bj的物资总量应该等于Bj 的销量bj，所以xij还应满足： 总运费为： = = = m i xi j bj j n 1 1,, = = = m i n j i j i j z c x 1 1
运输问题的数学模型 Minz=>∑cnx ∑ 72 (3-6) b x=O,i=1,…1;j=1,·…,H ∑a=∑b产销平衡条件 i=1 j=1
运输问题的数学模型 = = = = = = = = = = = x i m j n x b j n x a i m st MinZ c x i j m i i j j n j i j i m i n j i j i j 0, 1, ; 1, , 1, , 1, , . . 1 1 1 1 （3-6） = = = m i n j ai bj 1 1 产销平衡条件
、运输问题的特点与性质 1.约束方程组的系数矩阵具有特殊的结构 写出式(3-1)的系数矩阵A,形式如下: 11121n2“21:22 x n。 2ml“m2 行 ::::: 11 n行
二、运输问题的特点与性质 1．约束方程组的系数矩阵具有特殊的结构 写出式（3-1）的系数矩阵A，形式如下： n n m m mn x , x , , x ; x , x , x , , , , , x , x , x 1 1 1 2 1 2 1 2 2 2 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 m行 n行
今矩阵的元素均为1或0; 今每一列只有两个元素为1,其余元素均为0; 令列向量P=(0,…,0,1,0,…,0,1,0,…,0), 其中两个元素1分别处于第和第m+行。 ◆将该矩阵分块,特点是:前m行构成m个 m×n阶矩阵,而且第k个矩阵只有第k行元素 全为1,其余元素全为0(k=1,…,m);后n 行构成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 写出增广矩阵 xI X 112 X:X x n521“22 x x…1,x x A b
2.运输问题的基变量总数是m + n -1 写出增广矩阵 = n m b b b a a a A 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 n n m m mn x , x , , x ; x , x , x , , , , , x , x , x 1 1 1 2 1 2 1 2 2 2 1 2
证明系数矩阵A及其增广矩阵的秩都是m+n1 ◆前m行相加之和减去后n行相加之和结果是 零向量,说明m+n个行向量线性相关,因此 孑的秩小于m+n? ●由的第二至m+n行和前n列及x2x3p…,xn 对应的列交叉处元素构成m+n-1阶方阵D非奇 异:<? 因此A的秩恰好等于m+n-1,又D本身就含于 A中,故A的秩也等于m+n-1
证明系数矩阵A及其增广矩阵的秩都是m+n-1 前m行相加之和减去后n行相加之和结果是 零向量，说明m+n个行向量线性相关，因此 A 的秩小于m+n； ？ 因此 A 的秩恰好等于m+n-1，又D本身就含于 A中，故A的秩也等于m+n-1 由 的第二至m+n行和前n列及 对应的列交叉处元素构成m+n-1阶方阵D 非奇 异； ？ A 2 1 3 1 1 , , , m x x x