运筹学运输问题

运筹学运输问题

第3章 运输问题课时： 学时 讲授6学时 演示实验1学时 学时(讲授 学时,演示实验 学时) 课时：7学时 讲授 学时 演示实验 学时

3.1 典例和数学模型 3.2 表上作业法简介 3.3 产销不平衡运输问题及应用 3.4 应用举例 部分习题解答

ExcelORM1.0下载地址 下载地址: 下载地址 /guanwenzhong

运筹学运输问题

3.1 运输问题典例及数学模型引例( 引例(P111)产销平衡表 产 A1 A2 A3 销 B1 B2 B3 B4x11 x12 x13 x14

min z = 4 x11 + 12 x12 + 4 x13 + 11x14 +产量

2 x21 + 10 x22 + 3x23 + 9 x24 + 8 x31 + 5 x32 + 11x33 + 6 x34

16 x21 x22 x23 x24 10 x31 x32 x33 x34 22 48 销量 8 14 12 14 48 单位运价表B1 A1 A2 A3 4 2 8 B2 B3 B4 12 10 5 4 3 11 11 9 6

设：

xij——从产地 运往销地 的运量 从产地Ai运往销地 从产地 运往销地Bj的运量

x11 + x12 + x13 + x14 = 16 x21 + x22 + x23 + x24 = 10 产量约束 x31 + x32 + x33 + x34 = 22 x11 + x21 + x31 = 8 x12 + x22 + x32 = 14 销量约束 s.t. x13 + x23 + x33 = 12 x14 + x24 + x34 = 14 x ≥ 0, (i = 1, 2,3; j = 1, 2,3, 4) ij

运筹学运输问题

一般情况： 一般情况： 单位运价表(cij) 单位运价表 B1 c11 c21 … cm1 B2 c12 c22 … cm2 … … … … … Bn c1n c2n … cmn

A1 A2 … Am

min z = ∑∑ cij xiji =1 j =1

m

n

产销平衡表B1 A1 A2 … Am x11 X21 … xm1 B2 x12 X22 … xm2 … … … … … Bn x1n X2n … xmn

产量 a1 a2 … am

n ∑ xij = ai i = 1, 2,..., m j =1 m s.t. ∑ xij = b j j = 1, 2,..., n i =1 xij ≥ 0 i = 1, 2,..., m; j = 1, 2,..., n

销量

b1

b2

…

bn

运筹学运输问题

3.2 表上作业法简介表上作业法是一种简便而有效的方法,实质是单纯形法 表上作业法是一种简便而有效的方法 实质是单纯形法. 实质是单纯形法 步骤: 步骤1° ° 给出初始解

2° °

求检验数， 求检验数， 是否最优解？ 是否最优解？ 否

是

找到了最优解

3° °

找出新的解

运筹学运输问题

3.2.1 给出初始解给出初始解有西北角法、 给出初始解有西北角法、最小 元素法和Vogel法,我们只介绍 元素法和 法 我们只介绍 最小元素法. 最小元素法 步骤: 步骤 (1)从单位运价表中 找出最小 从单位运价表中 元素,确定供销关系 确定供销关系; 元素 确定供销关系 (2)根据可供量与需求量两者 根据可供量与需求量两者 的较小值,在产销平衡表对应 的较小值 在产销平衡表对应 格中填上该数字. 格中填上该数字 (3)如需求已满足 则从单位运 如需求已满足,则从单位运 如需求已满足 价表中划去相应的列数字,如 价表中划去相应的列数字 如 可供量已用完,则从单位运价 可供量已用完 则从单位运价 表中划去相应行数字.重复 表中划去相应行数字 重复 (1)~(2)直到单位运价表中数字 直到单位运价表中数字 全部被划去为止.(若有产销相 全部被划去为止 若有产销相 同时划去一行一列,并

在任 同,同时划去一行一列 并在任 同时划去一行一列 一运价处填0). 一运价处填 结果:有数字格 有数字格=产 销 结果 有数字格 产+销-1 最小元素法初始方案

B1 A1 A2 8 A3 销量 8 8 4 2

B2 12

B3 4 10 10 2 5 11 12 10 3

B4

产量 11 16

6

6 9 10

14 14

2 6 22 8 8 14 6

运筹学运输问题

3.2.2 解的检验与调整解的最优性检验——位势法 位势法: 解的最优性检验 位势法 (1)把产销平衡表中初始方案中有数 把产销平衡表中初始方案中有数 字格对应的运价写到检验数表中; 字格对应的运价写到检验数表中 (2)对运输表上的每一行 列)赋予一个 对运输表上的每一行(列 赋予一个 对运输表上的每一行 数值u 称为位势.各格子的位 数值 i(vj),称为位势 各格子的位 称为位势 势等于行位势与列位势之和. 势等于行位势与列位势之和 (3)求出检验数 求出检验数: 求出检验数 σij=cij-(ui+vj) 当所有σ 即为即优.当 当所有 ij≥0,即为即优 当σij<0时,由 即为即优 时由 闭回路法修改方案. 闭回路法修改方案 闭回路法: 闭回路法 (1)找到最小的负检验数 其对应的变 找到最小的负检验数,其对应的变 找到最小的负检验数 量为入基变量. 量为入基变量 (2)从入基变量对应的格子出发 遇到 从入基变量对应的格子出发,遇到 从入基变量对应的格子出发 有数字的格子可以转90° 有数字的格子可以转 °(也可 不转) 直到回到出发点 直到回到出发点,形成闭回 不转),直到回到出发点 形成闭回 路. (3)根据供应量与需求量总量不变的 根据供应量与需求量总量不变的 原则,调整供需关系 调整供需关系. 原则 调整供需关系 A1 A2 A3

单位运价表 B1 4 2 8 B1 A1 A2 A3 8 14 B2 12 10 5 B2 B3 4 3 11 B3 10 12 2 B4 11 9 6 B4 6 4 2 8

第1次调整 次调整 初始方案

位势法检验数计算表 B1 A1 A2 A3 vj [1] [0] 2 [10] [9] 3 4 B2 [2] [1] [2] B3 4 [1] 3 [12] 4 4 B4 11 [-1] 9 ui 0 -2 -1 -5

5 6 11 10 10 11 至此,检验数全部大于 检验数全部大于0,第 次调整后的方案为最优方案 作业P130.1) 次调整后的方案为最优方案.(作业 至此 检验数全部大于 第1次调整后的方案为最优方案 作业

运筹学运输问题

演示实验: 演示实验 Excel求解 求解 winQSB求解 求解销地 产地 A1 A2 A3 销量 B1 4 2 8 8 B2 12 10 5 14 B3 4 3 11 12 B4 11 9 6 14 产量 16 10 22

运筹学运输问题

3.3 产销不平衡运输问题及应用 …… 此处隐藏：7913字，全部文档内容请下载后查看。喜欢就下载吧 ……