文档介绍：一. 运输问题模型与性质
运输问题的数学模型
例、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3,各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示,问:应如何调运可使总运输费用最小?
第六节运输问题的表上作业法
解: 产销平衡问题: 总产量= 总销量
设 xij 为从产地Ai运往销地Bj的运输量,得到下列运输量表:
Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23
. x11+ x12 + x13 = 200
x21 + x22+ x23 = 300
x11 + x21 = 150
x12 + x22 = 150
x13 + x23 = 200
xij ≥ 0 ( i = 1、2;j = 1、2、3)
系数矩阵
1 1 1 0 0 0
0 0 0 1 1 1
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
特点:
1、共有m+n行,分别表示产地和销地;mn列分别表示各变量;
2、每列只有两个 1,其余为 0,分别表示只有一个产地和一个销地被使用;
设 xij 为从产地Ai运往销地Bj的运输量,得到下列一般运输量问题的模型:
m n
Min f = cij xij
i=1 j=i
n
. xij = si i = 1,2,…,m
j=1
m
xij = dj j = 1,2,…,n
i=1
xij ≥ 0 (i = 1,2,…,m ; j = 1,2,…,n)
一般运输问题的数学模型(产销平衡)
A1、 A2、…、 Am 表示某物资的m个产地; B1、B2、…、Bn 表示某物质的n个销地;si 表示产地Ai的产量; dj 表示销地Bj 的销量; cij 表示把物资为从产地Ai运往销地Bj的单位运价。
其系数矩阵为
变化:
1)有时目标函数求最大,如求利润最大或营业额最大等;
2)当某些运输线路上的能力有限制时,模型中可直接加入(等式或不等式)约束;
3)产销不平衡时,可加入虚设的产地(产大于销时)或销地(销大于产时)。
求解思路是
基本可行解最优否结束
否
换基
运输问题基变量的特点
* 运输问题的基变量共有 m + n -1 个,A的秩为 m + n -1。
* 运输问题的可行解一定存在。
* 运输问题的最优解一定存在。
⑷.重复⑵. ⑶,直到找到最优解为止。
步骤:
⑴.找出初始基本可行解(初始调运方案,一般m+n-1个数字格),用西北角法、最小元素