文档介绍：第三章特殊的线性规划——运输问题
& 模型及其特点
& 求解思路及相关理论
& 求解方法——表上作业法
& 运输问题的推广
产销不平衡的运输问题
转运问题
运输问题模型与性质
一、运输问题的数学模型
1、运输问题的一般提法: 某种物资有若干产地和销地,现在需要把这种物资从各个产地运到各个销地,产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价(或运距),问应如何组织调运,才能使总运费(或总运输量)最省?
单位根据具体问题选择确定。
表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
2、运输问题的数学模型
设xij为从产地Ai运往销地Bj的物资数量(i=1,…m;j=1,…n),由于从Ai运出的物资总量应等于Ai的产量ai,因此xij应满足:
同理,运到Bj的物资总量应该等于Bj的销量bj,所以xij还应满足: 总运费为:
运输问题的数学模型
(3-6)
二、运输问题的特点与性质

写出式(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阶单位阵。
+ n -1
写出增广矩阵
证明系数矩阵A及其增广矩阵的秩都是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 非奇异; ?