3.运输问题

第三章 运输问题 Transportation Problems — 数学模型及其解法 2 第一节 运输问题的数学模型 一、问题的提出 的运量。则到 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示设 jiij BAx 232221131211 556646 xxxxxxMinZ +++++= 3,2,1;2,1;0 200 150 150 300 200.. 2313 2212 2111 232221 131211 ==≥ =+ =+ =+ =++ =++ jix xx xx xx xxx xxxts ij 例1 销地 6 4 6 6 5 5 500 a iB2 B3 x 12 200A1 A2 b j B1 x 11 x 21 150 产地 300x 22 x 13 150 200 x 23 产销平衡表 3 二、运输问题的一般数学模型 • 有m个产地生产某种物资，有n个 地区需要该类物资； ⎪⎪⎩ ⎪⎪⎨ ⎧ ≥ ==∑ =∑ = ∑ ∑= = = = = 0 ,,2,1 ,,2,1 .. min 1 1 1 1 ij j m i ij n j iij m i n j ijij x njbx miax ts xcZ 销量约束 产地约束 Λ Λ • 设xij表示产地 Ai 运 往销地B j 的物资量， cij表示对应的单位运 费，则我们有运输问 题的数学模型如下： • 令a1, a2, …, am表示各产地产量， b1, b2, …, bn表示各销地的销 量； 一般满足产销平衡：∑ai=∑bj 4 三、约束系数矩阵的特征 1. 系数矩阵的形式 在例1中，运输问题的系数矩阵A为： ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ 100100 010010 001001 111000 000111 11x 12x 13x 21x 22x 23x 行。行对应平衡表的第的第 衡表的行。行对应产地约束，即平前 imiiA m )( ≤ 列。行对应平衡表的第的第 衡表的列。行对应销地约束，即平后 jjmA n + 2. 系数矩阵的特征 特征1：矩阵的行与平衡表行、列一一对应 5 一般情况下,运输问题的决策变量xij的系数列向量为: 位置 位置 jm i Pij +→ → ⎟⎟ ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎝ ⎛ = 0 1 1 0 Μ Μ Μ 特征2：矩阵的列向量只有两个元素为1 6 。，故，则、设 nmArnmnmnm +≤×≤+≥ )(2 特征3：r(A)=m + n－1 ∑=∑ ∑ ∑=∑⇒=∑ ∑ ∑=∑⇒=∑ == = === = === n j j m i i n j n j j m i ijj m i ij m i m i i n j iji n j ij ba bxbx axax 11 1 111 1 111 题，有对于产销平衡的运输问 由 由 ∑−∑=∑ ∑ ∑−∑⇔=∑ ≤≤ ≠=== ≠= === m ki i i n j j n j m ki i n j ij m i ijk n j kj abxxax mkk 111 1 111 )1( 个约束条件可表示为：第 1)( 1 1 −+= + −+ nmAr nm nmk 个是多余的，因此个约束条件中有故 个约束条件线性表示，个约束条件可以由另外上式表明第 7 。个数为所以运输问题基变量的 ）维。（）－应该是（，故基个数为 性无关向量的个系数列向量的最大线中由此可见， 1 111 −+ −+×+−+ × nm nmnmBnm nmA 量为零。个取正值，而其它的变最多只能有 个变量中行解，则平衡表上运输问题的解若是基可 1−+ × nm nm 8 四、闭回路 1. 概念 销地 3 11 3 10 1 9 2 8 7 4 10 5 206 5 9 6 4 A1 A2 b j B1 3 产地 A3 a iB2 B3 7 B4 ③ ④ ① ⑥ ③ ③ 例2 1) 数字格 2) 空格 3) 闭回路 9 2. 闭回路上的变量所对应的系 数列向量组线性相关性 结论1： 运输问题一组变量构成闭回路 的充要条件是这组变量所对应的系数列向 量线性相关 系数列向量线性相关。 ）所对应的所以（ ）构成闭回路，则（ 21231311 21231311 ,,, 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 ,,, xxxx xxxx ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ = ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ + ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ − ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ + ⎟⎟ ⎟⎟ ⎟⎟ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎜⎜ ⎜⎜ ⎜ ⎝ ⎛ − 销地 3 11 3 10 1 9 2 8 7 4 10 5 20 a iB2 B3 7 B4 A1 A2 b j B1 3 产地 A3 6 5 9 6 4③ ④ ① ⑥ ③ ③ 10 结论2： 运输问题的一个可行解 是基可行解的充要条件是： 1）数字格的个数为m+n-1个 2） m+n-1个数字格不构成闭回路。 11)( −+∴−+= nmnmAr 基变量个数为Θ 个数字格不构成闭回路 性无关基变量的系数列向量线 1−+∴ nm Θ 11 第二节 表上作业法 运输问题模型是线性 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 模型，当然 可以用单纯形法求解，但由于其系数矩阵 具有特殊形式，可以使单纯形法的操作更 为简便，这就是表上作业法（其实质是单 纯形法）。 12 初始基可行解 的确定 ?0≥ijσ 结束 Y 调整 N 一、表上作业法的步骤 13 二、初始基可行解的确定 与一般LP问题不同，产销平衡的运输问题一定 存在可行解。 d ba xdba jiij m i n j ji =∑ ∑ >=== = 设已知 ,01 1 满足产量约束；i n j j n j iji n j ij abd a d ba x =∑∑ ==∑ === 111 Θ 满足销量约束；j m i i m i jjim i ij bad b d ba x =∑∑ ==∑ === 111 0≥= d ba x jiij又 为可行解。＝ TmnxxxX ),,,( 1211 Λ∴ 14 1.最小元素法 基本思想: 就“近”供应，从运输表中最小运价所在格开始确定供销关系。 缺点: 为节省一处费用，会使别处费用增加很多，因此，其初始 基可行解往往离最优解甚远，需要较多的迭代过程。 15 销地 3 11 3 10 1 9 2 8 7 4 10 5 206 5 9 6 4 A1 A2 b j B1 3 产地 A3 a iB2 B3 7 B4 ③ ④ ① ⑥ ③ ③ 例4 865346211310334 =×+×+×+×+×+×=Z 9 9 9 9 9 9 16 2.伏格尔法（Vogel） 基本思想: 同时考虑每一产地（销地）与每一销地（产地）之间的最 小运价和次小运价，若两者差额大，说明若不能按最小运价 供应，就有可能按次小运价供应，从而运费很高。因此，应 先对最大差额所在的行或列，按最小元素确定供销关系。 优点: 按此法所得基可行解较最小元素法所得可行解更接近最优解。 17 例5 销地 3 11 3 10 1 9 2 8 7 4 10 5 206 5 9 6 4 A1 A2 b j B1 3 产地 A3 a iB2 B3 7 B4 ② 0 1 1 2 5 1 3 ⑥ 0 1 2 2 — 1 3 ③ 0 1 — 2 — 1 2 ③ 若同时有多个相同的最大 差额，选取最小元素确定 供应关系 7 6 — — — 1 2 ⑤ — — — 2 ① 855346811310235 =×+×+×+×+×+×=Z 18 1)在运输表上写出各行﹑各列最小运价和次小 运价差额； 步骤: 2)选最大差额所在行或列的最小元素确定供销关系； 3)对未确定的行列，重新计算差额，重复2)、3)， 直至得出 初始解。 19 在以上两种方法中，有几点需要注意： • 这两种方法得出的解均为初始可行解。 • 在以上方法中，每填写一个数字划去一行(列)，只有在填 写最后一个数字时，同时划去该数字所在行和列。从而保证 基变量个数为（m+n-1）个。 20 ⎩⎨ ⎧ =− =−= 列待分物资量列已分配的总量 行尚余物资量行已分配的总量 ) ( ) (min jjb iiax j i ij 例6 销地 产量 运费 1 2 3 4 ai 产地 1 20 11 3 6 5 2 5 9 10 2 10 3 18 7 4 1 15 销量 bj 3 3 12 12 xij 的分配 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 3. 左上角法（西北角法） 从 x11开始分配，从西北向东南方向逐个分配。 21 销地 产量 运量 1 2 3 4 ai 产地 1 5 2 10 3 15 销量 bj 3 3 12 12 销地 产量 运量 1 2 3 4 ai 产地 1 3 x12 5 2 10 3 15 销量 bj 3 3 12 12 销地 产量 运量 1 2 3 4 ai 产地 1 3 2 5 2 x22 10 3 15 销量 bj 3 3 12 12 销地 产量 运量 1 2 3 4 ai 产地 1 3 2 5 2 1 x23 10 3 15 销量 bj 3 3 12 12 销地 产量 运量 1 2 3 4 ai 产地 1 3 2 5 2 1 9 10 3 x33 15 销量 bj 3 3 12 12 销地 产量 运量 1 2 3 4 ai 产地 1 3 2 5 2 1 9 10 3 3 x33 15 销量 bj 3 3 12 12 ∑∑ = = ===−+ 3 1 4 1 20561 i j ijij xcZnm 个基变量 例6 左上角法解题演示 销地 产量 运量 1 2 3 4 ai 产地 1 3 2 5 2 1 9 10 3 3 12 15 销量 bj 3 3 12 12 22 三、求检验数并进行最优解的判定 1. 闭回路法 就是求调运 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 中空格的检验数σij， 当所有σij ≥0，则得最优解。 的变化量。 变化一个单位所引起为上式表明： 变，则变化而其它非基变量不当某个非基变量 计算公式为：迭代过程中的在第一章， Z x x Z x xZZ Z jj j j j j n mj j σ σ σ ∂ ∂= ∑+= += 10 LP 23 注: 数字格检验 数均为0 解。时，运输问题达到最优当所有 最优性判别 准则 租赁准则应用指南下载租赁准则应用指南下载租赁准则应用指南下载租赁准则应用指南下载租赁准则应用指南下载 ： 0≥ijσ 显然该问题至此尚未达到最优解。 例7：以最小元素法求得的调运方案为例 销地 3 11 3 10 1 9 2 8 7 4 10 5 206 5 9 6 4 A1 A2 b j B1 3 产地 A3 a iB2 B3 7 B4 ③ ④ ① ⑥ ③ ③1 2 1 -1 10 12 24 2. 位势法 例8 由最小元素法得出初始解,如下表 销地 3 11 3 10 1 9 2 8 7 4 10 5 206 5 9 6 4 A1 A2 b j B1 3 产地 A3 a iB2 B3 7 B4 ③ ④ ① ⑥ ③ ③ ijji cvu =+对数字格而言计算）行势、列势的定义与注： :1 0),()2 =+−= ijjiijij vuc σσ 数字格检验数的计算：空格 3）行势、列势可不唯一，但检验数是一致的。 25 销地 3 11 3 10 1 9 2 8 7 4 10 5 206 5 9 6 4 A1 A2 b j B1 3 产地 A3 a iB2 B3 7 B4 例8：以最小元素法求得的调运方案为例 位势法的计算过程 ui vj 0 3 10 -1 -5 92 1 2 1 -1 10 12 ③ ④ ① ⑥ ③ ③ • 令u1=0 • 根据数字格的单 价按ui+vj=cij相继确 定其他的ui和vj • 计算空格的检验数。 σij= cij-(ui+vj)，如σ11=3-(0+2)=1 因为σ 24=-1<0,因而该问题至此尚未达到最优解. 26 销地 3 11 3 10 1 9 2 8 7 4 10 5 206 5 9 6 4 A1 A2 b j B1 3 产地 A3 a iB2 B3 7 B4 四、 调整 从最小负检验数所对应的空格进行调整 例9 对由最小元素法得出的初始解进行调整 调整方法： 1）找出闭回路 2）确定调整量θ 使最小负检验数所 对应的空格达到最 大的调整量，即 θ=min(1,3)=1 213;514;011;110 =−=+=−=+即 再按调整后的解由位势法计算空格的检验数 ③ ① ⑥ ③ ③1 2 1 -1 10 12 (+) (-)(+) (-) ④ ① ⑤ ② 27 销地 3 11 3 10 1 9 2 8 7 4 10 5 206 5 9 6 4 A1 A2 b j B1 3 产地 A3 a iB2 B3 7 B4 ③ ④ ① ⑥ ③ ③ 865346211310334 =×+×+×+×+×+×=Z 9 9 9 9 9 9 五、典型运输问题解题步骤示例 1.由最小元素法求得初始基可行解 28 销地 3 11 3 10 1 9 2 8 7 4 10 5 206 5 9 6 4 A1 A2 b j B1 3 产地 A3 a iB2 B3 7 B4 ui vj 0 -1 -5 1 2 1 -1 10 12 ③ ④ ① ⑥ ③ ③ • 令u1=0 • 按ui+vj=cij相 继确定其他数 字格的ui和vj3 1092 • 计算空格的检验数。 σij= cij-(ui+vj)，如σ11=3-(0+2)=1 因为σ 24=-1<0,因而该问题至此尚未达到最优解. 2.由位势法求检验数 29 销地 3 11 3 10 1 9 2 8 7 4 10 5 206 5 9 6 4 A1 A2 b j B1 3 产地 A3 a iB2 B3 7 B4 3.从最小负检验数所对应的空格进行调整 调整方法： 1）找出闭回路 2）确定调整量θ 使最小负检验数所 对应的空格达到最 大的调整量，即 θ=min(1,3)=1 213;514;011;110 =−=+=−=+即 ③ ① ⑥ ③ ③1 2 1 -1 10 12 (+) (-)(+) (-) ④ ① ⑤ ② 30 销地 3 11 3 10 1 9 2 8 7 4 10 5 206 5 9 6 4 A1 A2 b j B1 3 产地 A3 a iB2 B3 7 B4 ui vj 0 3 10 -2 -5 93 0 2 2 1 9 12 ③ ① ⑥ ③ • 令u1=0 • 按ui+vj=cij相 继确定其他数 字格的ui和vj • 计算空格的检验数。 σij= cij-(ui+vj)，如σ11=3-(0+3)=0 ⑤ ② 因为σij≥0,至此该问题已经达到最优解. 4. 再按调整后的解由位势法计算空格的检验数 855346811310235 =×+×+×+×+×+×=Z最优解 31 六、位势法的理论依据（互补松弛定理） ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ == ≥ =∑ =∑ ∑ ∑= = = = = ),,1;,,1( 0 .. min )( 1 1 1 1 njmi x bx ax ts xcZ PP ij j m i ij i n j ij m i n j ijij ΛΛ ⎪⎩ ⎪⎨ ⎧ ≤+ ∑+∑= == 无约束ji ijji n j jj m i ii vu cvu ts vbuaZ DP , .. max )( 11 0)( 0)( )0(0)0( )0(0)0( ≥+− +− jiijij jiijij vucx vucx ）（ ）（ 为非基变量时，当 ＝为基变量时，当 对偶变量 iu jv [ ] 0)()()( ),(,)()(),( )0(0)0( )0()0()0()0(0)0( =+−⋅ jiijij jiijjiij vucxDPPP vuxDPPPvux ）（ ）（ 的最优解的充要条件是、是 、则的可行解、是、结论：设 32 七、表上作业法的说明 •无穷多最优解判别：存在非基变量的检验数=0的空格 •确定初始解时，若数字格不够（m+n-1），需任选一些空格填 为0，使其成为数字格；用闭回路调整时，若减去θ后成为0的 格多于1个，需将多出的格（任选）填0。 •若调入格调整量θ=0，也要按步骤求调整方案，尽管实际并未 调整，但解的性质有了变化（原空格变成基变量），从而影响 检验数结果。 第三章 运输问题��Transportation Problems�� — 数学模型及其解法 第一节 运输问题的数学模型 二、运输问题的一般数学模型 第二节 表上作业法 二、初始基可行解的确定