《运筹学运输问题-ppt课件》由会员分享，可在线阅读，更多相关《运筹学运输问题-ppt课件（80页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 运运输与指派与指派问题运运输问题的表示的表示运输问题模型、运价表运运输问题的求解的求解 表上作表上作业法法 指派指派问题 1-运输、指派和转运问题，实际上都可以用 L.P. 模型加以描述，所以可以认为它们是 L.P. 的特例单列一章的原因在于：应用面极广，实践性很强，而特有的数学结构使得人们设计出了特别有效的方法对此类模型进行求解本章的重点在：掌握表格化方法求解求解运输简述2-提出提出问题问题有A1，A2，A3三个砖瓦厂月产量分别为14，27，19万块，供应B1，B2，B3，B4四个工地，月需要量分别为22，13，12，13万块，每万块运费如下表，求总运费最少的方案。A114A2
2、27A31922131213B1B2B3B46(千元）千元）753842759106运运输问题3-运运输问题线性性规划模型划模型供应地约束需求地约束4-3.1 运运输问题模型与性模型与性质一、运一、运输问题的数学模型的数学模型 1、 运运输问题的的一一般般提提法法： 某某种种物物资有有若若干干产地地和和销地地，现在在需需要要把把这种种物物资从从各各个个产地地运运到到各各个个销地地，产量量总数数等等于于销量量总数数。已已知知各各产地地的的产量量和和各各销地地的的销量量以以及及各各产地地到到各各销地地的的单位位运运价价（或或运运距距），问应如如何何组织调运运，才才能能使使总运运费（或或总运运输量量
3、）最省最省？5-运输问题的一般数学模型有有m个个产地生地生产某种物某种物资，有，有n个地区需要个地区需要该类物物资令令a1, a2, , am表示各表示各产地地产量，量， b1, b2, , bn表示各表示各销地的地的销量，量， ai= bj 称称为产销平衡平衡设xij表示表示产地地 i 运往运往销地地 j 的物的物资量，量，cij表示表示对应的的单位运位运费，则我我们有运有运输问题的数学模型如下：的数学模型如下：运运输问题6-二、运二、运输问题的特点与性的特点与性质1约束方程束方程组的系数矩的系数矩阵具有特殊的具有特殊的结构构写出式（写出式（3-1）的系数矩）的系数矩阵A，形式如下：形式如下
4、：m行行n行行7- 矩矩阵的元素均的元素均为1或或0； 每一列只有两个元素每一列只有两个元素为1，其余元素均，其余元素均为0； 列向量列向量Pij =(0,，0，1，0，,0,1,0,0)T，其中两个元素其中两个元素1分分别处于第于第i行和第行和第m+j行。行。 8-三、运输问题的求解方法1、单纯形法（形法（为什麽？）什麽？）2、表上作、表上作业法法 由于由于问题的特殊形式而采用的的特殊形式而采用的更更简洁、更方便的方法、更方便的方法9-3.2 运运输问题的表上作的表上作业法法 一一、表表上上作作业法法的的基基本本思思想想是是:先先设法法给出出一一个个初初始始方方案案,然然后后根根据据确确定定
5、的的判判别准准则对初初始始方方案案进行行检查、调整整、改改进，直直至至求求出出最最优方案方案，如，如图3-1所示。所示。表表上上作作业法法和和单纯形形法法的的求求解解思思想想完完全全一一致致，但是具体作法更加但是具体作法更加简捷。捷。10- 确定初始确定初始方案方案( ( 初初 始始 基本可行解基本可行解) ) 改改进调整整（换基迭代）基迭代）否否 判定是否判定是否 最最 优？是是结 束束最最优方案方案图3-1 运运输问题求解思路求解思路图11- 二、二、 初始方案的确定初始方案的确定 1、作、作业表（表（产销平衡表）平衡表） 初始方案就是初始基本可行解。初始方案就是初始基本可行解。 将运将运
6、输问题的有关信息表和决策的有关信息表和决策变量量调运运量量结合在一起构成合在一起构成“作作业表表”（产销平衡表平衡表）。）。 表表3-3是两个是两个产地、三个地、三个销地的运地的运输问题作作业表。表。 12-调 销地地 运运 量量产地地 B1 B2 B3 产 量量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 销 量量 b1 b2 b3表表3-3 运运输问题作作业表（运价表）表（运价表） 13-3、举例 例例3-2 甲甲、乙乙两两个个煤煤矿供供应A、B、C三三个个城城市市用用煤煤，各各煤煤矿产量量及及各各城城市市需需煤煤
7、量量、各各煤煤矿到到各各城城市市的的运运输距距离离见表表3-4，求求使使总运运输量量最最少少的的调运方案。运方案。 14-表3-4 例3-2有关信息表 450 200 150 100 日销量（需求量） 250 75 65 80 乙 200 100 70 90 甲 日日产量量（供（供应量）量） C B A运距运距 城市城市煤煤矿15-例3-2 的数学模型16-初始解的确定初始解的确定一、最小元素法一、最小元素法& & 最小元素法的基本思想是最小元素法的基本思想是最小元素法的基本思想是最小元素法的基本思想是“ “就近供就近供就近供就近供应应” ” ；二、西北角法二、西北角法& 西北角法西北角法西北
8、角法西北角法则则不考不考不考不考虑虑运距（或运价），每次都运距（或运价），每次都运距（或运价），每次都运距（或运价），每次都选选剩余表剩余表剩余表剩余表格的左上角（即西北角）元素作格的左上角（即西北角）元素作格的左上角（即西北角）元素作格的左上角（即西北角）元素作为为基基基基变变量，其它量，其它量，其它量，其它过过程程程程与最小元素法相同与最小元素法相同与最小元素法相同与最小元素法相同 ；三、沃格三、沃格尔法（法（VOGLE）17-调 销地地 运运 量量产地地 B1 B2 B3 产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23
9、250 销 量量 100 150 200 450 用最小元素法确定例用最小元素法确定例3-2初始初始调运方案运方案 15010010010010010010018-调 销地地 运运 量量产地地 B1 B2 B3 产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量量 100 150 200 450 用西北角法确定例用西北角法确定例3-2初始初始调运方案运方案 100100100 50 5020020019- 得到初始得到初始调运方案运方案为： x11=100，x12=100，x22=50，x23=200 20-元元素
10、素差差额法法（Vogel近近似似法法）最最小小元元素素法法只只考考虑了了局局部部运运输费用用最最小小。有有时为了了节省省某某一一处的的运运费，而而在在其其它它处可可能能运运费很很大大。元元素素差差额法法对最最小小元元素素法法进行行了了改改进，考考虑到到产地地到到销地地的的最最小小运运价价和和次次小小运运价价之之间的的差差额，如如果果差差额很很大大，就就选最最小小运运价价先先调运，否运，否则会增加会增加总运运费。例如下面两种运。例如下面两种运输方案方案前一种按最小元素法求得，前一种按最小元素法求得，总运运费是是Z1=108+52+151=105后后一一种种方方案案考考虑到到C11与与C21之之间
11、的的差差额是是82=6，先先调运运x21，再是再是x22，其次是，其次是x12这时总运运费Z2=105+152+51=85 bj ，增加一个虚收点增加一个虚收点Dn+1，bn+1= ai - bj , 令令 wi,n+1=0, i=1,2,m供小于求，即供小于求，即 ai bj ，增加一个虚增加一个虚发点点Wm+1，am+1= bj - ai , 令令 wm+1,j=0, j=1,2,n48-运运输问题应用用举例例如产地3的产量变为130，又B地区需的115单位必须满足，试重新确定最优调拨方案49-B1B2B3B4B5aiA1101520204050A22040153030100A330354
12、05525130A4(虚）虚）0M00020bj25115603070210得到得到这样的平衡表后的平衡表后50-应用用举例例1杭州某电视机厂在三个经济区建立分厂，生产产品销往上海，北京，广州。运价表如下，假定产地2的物资至少运出38个单位，产地3的物资至少运出27个电位，试列出新的运价表51-上海上海北京北京广州广州虚虚拟B4aiA1122020A2145M 38A2114502A3233M27A3123303bj30202020得到得到这样的平衡表后的平衡表后52-应用用举例例2已知某运输问题一个最优调运方案如下表，求K值范围53-指派指派问题问题例：有一份中文产品说明书需译成英、日、德、
13、俄四种语言，现有甲、乙、丙、丁四人都可以胜任，他们译成不同语言所需时间不同，如下表。求如何分配使所需总时间最少（每人只译一种） 语言人员EJGR甲215134乙1041415丙9141613丁78119整数整数规划划54-指派指派问题的的标准形式及其数学模型准形式及其数学模型指派指派问题的的标准形式（以人和事准形式（以人和事为例）是：例）是： 有有 n 个人和个人和 n 件事，已知第件事，已知第 i 人做第人做第 j 事的事的费用用为 Cij（i，j = 1，2，n），），要求确定人和事之要求确定人和事之间的一一的一一对应的指派方案，使完成的指派方案，使完成这件事的件事的总费用最少。如用最少。
14、如指派指派问题（assignment problem）例：有一份中文例：有一份中文产品品说明明书需需译成英、日、德、俄四种成英、日、德、俄四种语言，言，现有甲、乙、丙、丁四人都有甲、乙、丙、丁四人都可以可以胜任，他任，他们译成不同成不同语言所需言所需时间不同，如下表。求如何分配使所需不同，如下表。求如何分配使所需总时间最少最少（每人只（每人只译一种）一种） 语言言人人员EJGR甲甲215134乙乙1041415丙丙9141613丁丁7811955建立模型：建立模型：设 xij=10译英文：x11+ x12 + x13 + x14 =1译日文：x21+ x22 + x23 + x24 =1译德文
15、：x31+ x32 + x33 + x34 =1译俄文：x41+ x42 + x43 + x44 =1甲：x11+ x21 + x31 + x41 =1乙：x12+ x22 + x32 + x42 =1丙：x13+ x23 + x33 + x43 =1丁：x14+ x24 + x34 + x44 =1xij =0或1 (i=1,2,3,4; j=1,2,3,4)Min z= aijxij(aij-效率)i=1j=14 4若第i项工作交与第j个人完成若第i项工作不交与第j个人完成56-一般模型一般模型一般模型一般模型指派指派问题的的标准形式，令准形式，令 1 当指派第当指派第 i 人完成第人完成
16、第 j 项任任务 0 当不指派第当不指派第 i 人完成第人完成第 j 项任任务xij =min z = cijxij xij = 1， j = 1，2，n xij = 1， i = 1，2，n xij = 1 或或 057匈牙利解法匈牙利解法匈牙利解法匈牙利解法 标准的指派准的指派问题是一是一类特殊的特殊的 0-1 整数整数规划划问题，可以用多种相可以用多种相应的解法来求解。但是，的解法来求解。但是，这些方法都没些方法都没有充分利用指派有充分利用指派问题的特殊性的特殊性质来有效减少来有效减少计算量。算量。1955年，年，库恩（恩（W.W.Kuhn）利用匈牙利数学家康尼利用匈牙利数学家康尼格（格
17、（D.Knig）的关于矩的关于矩阵中独立零元素的定理，提中独立零元素的定理，提出了指派出了指派问题的一种解法，由此，的一种解法，由此，习惯上称之上称之为匈牙匈牙利解法。利解法。58 匈牙利解法的关匈牙利解法的关键是利用了指派是利用了指派问题最最优解的如解的如下下性性质： 若从指派若从指派问题的系数矩的系数矩阵 C = （ cij ）nn 的某的某行（或某列）各元素分行（或某列）各元素分别减去一个常数减去一个常数 k ，得到一个得到一个新的系数矩新的系数矩阵C = （ cij ）则以以 C 和和 C 为系数矩系数矩阵的两个指派的两个指派问题有有相同的最相同的最优解解。匈牙利解法匈牙利解法匈牙利解
18、法匈牙利解法59步步骤一：一： 变换系数矩系数矩阵。使其每行及每列至少。使其每行及每列至少有一个零元素，同有一个零元素，同时不出不出现负元素。元素。步步骤二：二： 进行行试指派，即确定独立零元素。指派，即确定独立零元素。步步骤三：三： 继续变换系数矩系数矩阵，然后返回步，然后返回步骤二。二。匈牙利解法的一般步匈牙利解法的一般步骤60以上例以上例说明步明步骤 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 0 13 11 2 6 0 10 11 0 5 7 4 0 1 4 22497min（ cij ）=匈牙利解法的一般步匈牙利解法的一般步骤61指派指派问题（a
19、ssignment problem）匈牙利解法的一般步匈牙利解法的一般步骤以上例以上例说明步明步骤 0 13 11 2 6 0 10 11 0 4 7 4 0 1 4 2 0 0 4 2min 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0= （ cij ）指派指派问题（assignment problem）62以上例以上例说明步明步骤 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0此此时加圈加圈 0 元素的个数元素的个数 m = n = 4，所以得到最所以得到最优解解指派指派问题（assignment problem）63匈牙利解法的一般步匈牙利解法的一般
20、步骤以上例以上例说明步明步骤 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0（ xij ）=指派指派问题（assignment problem）64匈牙利解法的一般步匈牙利解法的一般步骤例例任任务人人员ABCDE甲甲乙乙丙丙丁丁戊戊1287154791714109612677614610969109指派指派问题（assignment problem）65匈牙利解法的一般步匈牙利解法的一般步骤 12 7 9 7 9 8 9 6 6 6 7 17 12 14 9 15 14 6 6 10 4 10 7 10 976764 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2
21、 9 8 0 0 4 0 6 3 6 5指派指派问题（assignment problem）66匈牙利解法的一般步匈牙利解法的一般步骤 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5 此此时加圈加圈 0 元素的个数元素的个数 m = 4， 而而n = 5，所以解所以解题没没有完成。独立零元素（加圈零有完成。独立零元素（加圈零元素）少于元素）少于 n 个，表示个，表示还不能不能确定最确定最优指派方案。此指派方案。此时需确定需确定能覆盖所有能覆盖所有零元素的最少直零元素的最少直线数数目的直目的直线集合。方法如下：集合。方法如下：指派指派问题（a
22、ssignment problem）67匈牙利解法的一般步匈牙利解法的一般步骤1)对没有加圈零元素的行打没有加圈零元素的行打号；号；2)对所有打所有打号行的所有含零元素的列打号行的所有含零元素的列打号；号；3)再再对已打已打号的列中含零元素的行打号的列中含零元素的行打号；号；4)重复重复2）和）和3），直到再也不能找到可以打），直到再也不能找到可以打号行或号行或列列为止；止；5)对没有打没有打号的行画一横号的行画一横线，对打打号的列画一号的列画一竖线，这样就得到就得到能覆盖所有能覆盖所有零元素的最少直零元素的最少直线数目数目的直的直线集合。集合。指派指派问题（assignment proble
23、m）68匈牙利解法的一般步匈牙利解法的一般步骤 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5指派指派问题（assignment problem）69匈牙利解法的一般步匈牙利解法的一般步骤 继续变换系数矩系数矩阵。其方法是在未被直。其方法是在未被直线覆盖的覆盖的元素中找出一个最小元素。然后在打元素中找出一个最小元素。然后在打号号行行各元素都各元素都减减去去这一最小元素，而在打一最小元素，而在打号号列列的各元素都的各元素都加加上上这一最小元素，以保一最小元素，以保证原来的原来的 0 元素不元素不变。这样得到新得到新系数矩系数矩阵（其最（其最优
24、解和原解和原问题相同）。若得到相同）。若得到 n 个独个独立的立的 0 元素，元素，则已得最已得最优解，否解，否则重复重复该步步骤继续变换系数矩系数矩阵。指派指派问题（assignment problem）70匈牙利解法的一般步匈牙利解法的一般步骤 5 0 2 0 2 2 3 0 0 0 0 10 5 7 2 9 8 0 0 4 0 6 3 6 5最小元素最小元素= 2 7 0 2 0 2 4 3 0 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 3指派指派问题（assignment problem）71匈牙利解法的一般步匈牙利解法的一般步骤 7 0 2 0 2 4 3 0
25、 0 0 0 8 3 5 0 11 8 0 0 4 0 4 1 4 3 此此时加圈加圈 0 元素的个数元素的个数 m = 5， 而而n = 5，独立零元素独立零元素（加圈零元素）等于（加圈零元素）等于 n 个，个，此此时已得到最已得到最优解，其解矩解，其解矩阵为指派指派问题（assignment problem）72匈牙利解法的一般步匈牙利解法的一般步骤（ xij ）= 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 最最优指派：指派：甲甲 B乙乙 C丙丙 E丁丁 D戊戊 A指派指派问题（assignment problem）73 在在实际应
26、用中，常会遇到各种非用中，常会遇到各种非标准形式的制派准形式的制派问题。一般的。一般的处理方法是先将其理方法是先将其转化化为标准形式，然后再用匈牙利法求解。准形式，然后再用匈牙利法求解。1.最大化指派最大化指派问题设最大化指派最大化指派问题系数矩系数矩阵 C = （ cij ） ，其中最大元素其中最大元素为 m 。令矩令矩阵 B = （ bij ）= （ m - cij ），），则以以 B 为系数矩系数矩阵的最小化指派的最小化指派问题和以和以 C 为系数矩系数矩阵的最大化指的最大化指派派问题有相同最有相同最优解。解。2.人数和事数不等的指派人数和事数不等的指派问题若若人少事多人少事多，则添加一
27、些虚添加一些虚拟的的“人人”，其，其费用系数取用系数取 0 ，若，若人多事少人多事少，则添加一些虚添加一些虚拟的的“事事”，其，其费用系数取用系数取 0 。 非非标准形式的指派准形式的指派问题74非非标准形式的指派准形式的指派问题3.一个人可做几件事的指派一个人可做几件事的指派问题若某个人可以做几件事，若某个人可以做几件事，则将将该人化作几个人化作几个“人人”来接受指派。来接受指派。这几个几个“人人”做同一件事的做同一件事的费用系数当然都一用系数当然都一样。4.某事一定不能由某人做的指派某事一定不能由某人做的指派问题若某事一定不能由某人做，若某事一定不能由某人做，则可将相可将相应的的费用系数取
28、用系数取为足足够大的数大的数 M 。非非标准形式的指派准形式的指派问题75非非标标准指派准指派问题问题例：分派甲、乙、丙、丁四人完成五项任务，每人完成任务的时间如下表，请就以下要求分别求解分配情况。 任务人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁24423623451）要求每人只完成一项2）甲完成两项，其他人每人完成一项3）丁因某种原因不能承担A工作，其他每人一项，E必须承担任务整数整数规划划76-1）要求每人只完成一项 任务人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345戊戊0000
29、077-2）甲完成两项，其他人每人完成一项 任务人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345戊戊252931423778-3）丁因某种原因不能承担A工作，其他每人一项，E必须承担任务 任务人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁M42362345戊戊0000M79-Operational/operations research 运筹学运筹学Linear programming 线性性规划划 feasible domain 可行域可行域convex set 凸集凸集 Basic f
30、easible solutions 基基础可行解可行解Simplex algorithm 单纯型法型法 Pivot 主元主元 Pivoting 主元主元变换Revised, dual simplex algorithm 修正、修正、对偶偶单纯型法型法Relative cost 相相对成本成本(机会成本机会成本) Shadow price 影子价格影子价格Slack, Surplus, Artificial variable 松弛，剩余，人工松弛，剩余，人工变量量unbounded, Infeasible, Degenerate solution 无界解无界解, 无可行解无可行解, 退化退化解解solution Duality 对偶性偶性 Primal, dual problem 原原问题，对偶偶问题Revised, dual simplex algorithm 修正、修正、对偶偶单纯型法型法complementary slackness 互互补松弛松弛 Sensitivity analysis 灵敏度分析灵敏度分析Transportation problem 运运输问题Assignment problem 任任务分配分配(指派指派) 问题Bipartite matching 两部两部图匹配匹配 Hungarian method 匈牙利算法匈牙利算法线性规划有关的英文词汇总汇80-
