- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
特殊的线性规划 ——运输问题 ——运输问题
& 模型及其特点 & 求解思路及相关理论 & 求解方法——表上作业法 求解方法——表上作业法 & 运输问题的推广 产销不平衡的运输问题 转运问题
一、运输问题的数学模型
1、 运输问题的一般提法： 某种物资有若 运输问题的一般提法： 干产地和销地， 干产地和销地，现在需要把这种物资从各个 产地运到各个销地，产量总数等于销量总数。 产地运到各个销地，产量总数等于销量总数。 已知各产地的产量和各销地的销量以及各产 各产地的产量和各销地的销量 已知各产地的产量和各销地的销量以及各产 地到各销地的单位运价 或运距） 单位运价（ 地到各销地的单位运价（或运距），问应如 何组织调运，才能使总运费 或总运输量） 总运费（ 何组织调运，才能使总运费（或总运输量） 最省？ 最省？
x11, x12,L x1n ; x21, x22,Lx2n ,LLLL xm1, xm2 ,Lxmn , , , , ,
1 1 L 1 1 1 L 1 O O O A= 1 1 L 1 1 1 1 1 L 1 1 O O L O 1 1 L 1 a1 a2 M M M am b1 b2 M bn
2、运输问题的数学模型
为从产地A 运往销地B 设xij为从产地 i运往销地 j的物资数量 （ i=1， …m； j=1， …n） ， 由于从 i ， ； ， ） 由于从A 运出的物资总量应等于A 的产量a 运出的物资总量应等于 i的产量 i，因此 xij应满足： 应满足：
∑x
j =1
n
ij
= ai
n m ∑ ai = ∑ b j j =1 i =1
产销平衡条件
二、运输问题的特点与性质
1．约束方程组的系数矩阵具有特殊的结构 写出式（ 写出式（3-1）的系数矩阵A，形式如下： 的系数矩阵A 形式如下：
x11, x12,L, x1n ; x21, x22,Lx2n ,L,L,L,L, xm1 , xm2 ,Lxmn
i = 1,2, L , m
同理，运到 的物资总量应该等于B 同理，运到Bj的物资总量应该等于 j 的销量b 所以x 还应满足： 的销量 j，所以 ij还应满足：
∑x
i =1
m
ij
= bj
m
j = 1, L, n
n
总运费为： 总运费为：
z = ∑∑ cij xij
i =1 j =1
运输问题的数学模型
MinZ =
∑ ∑
i=1
m
n
j =1
c ij x ij
n i = 1,L , m ∑ x ij = a i jm= 1 s . t . ∑ x ij = b j j = 1,L , n i=1 x ij ≥ 0 , i = 1 , L m ; j = 1 , L , n
表1
单位 运价 销 或运距 地 产地 A1 A2 ┆ Am 销 量 B1 B2
有关信息
… Bn 产 量 a1 a2 ┆ am
c11 c12 …n
m
b1
b2
…
bn
∑ ai = ∑b j
i =1 j =1
n
单位根据具体问题选择确定 单位根据具体问题选择确定。
m行 行
1 1 1 L 1 1 1 L 1 O O O 1 1 1 O 1 1 O 1 L L L 1 1 O 1 L 1 1
n行 行
矩阵的元素均为1 矩阵的元素均为1或0； 每一列只有两个元素为1 其余元素均为0 每一列只有两个元素为1，其余元素均为0； 列向量P =(0,…， 列向量Pij =(0,…，0，1，0，…,0,1,0,…0)T， 其中两个元素1分别处于第i行和第m+j行 其中两个元素1分别处于第i行和第m+j行。 将该矩阵分块，特点是： 行构成m 将该矩阵分块，特点是：前m行构成m个 m×n阶矩阵，而且第k个矩阵只有第k行元素 阶矩阵，而且第 个矩阵只有第k 全为1 其余元素全为0 k=1， 全为1，其余元素全为0（k=1，…，m）；后n 行构成m 阶单位阵。 行构成m个n阶单位阵。
证明系数矩阵A及其增广矩阵的秩都是m+n证明系数矩阵A及其增广矩阵的秩都是m+n-1 前m行相加之和减去后n行相加之和结果是 行相加之和减去后n 零向量，说明m+n个行向量线性相关 个行向量线性相关， 零向量，说明m+n个行向量线性相关，因此 的秩小于m+n； A 的秩小于m+n； ？ 由 A 的第二至m+n行和前n列及 x21, x31,L, xm1 的第二至m+n行和前 行和前n 对应的列交叉处元素构成m+n- 阶方阵D 对应的列交叉处元素构成m+n-1阶方阵D 非奇 异； ？ 因此 A 的秩恰好等于m+n-1，又D本身就含于 的秩恰好等于m+nA中，故A的秩也等于m+n-1 的秩也等于m+n-
2.运输问题的基变量总数是m + n -1 运输问题的基变量总数是m
写出增广矩阵 x11, x12 ,L, x1n ; x21, x22 ,Lx2n ,L,L,L,L, xm1 , xm2 ,Lxmn
1 1 L 1 1 1 L 1 O O O A= 1 1 L 1 1 1 1 1 L 1 1 O O L O 1 1 L 1 a1 a2 M M M am b1 b2 M bn
