运输、指派和转运问题，实际上都可以用 L.P.模型加以描述，所以可以认为它们是 L.P.的特例单列一章的原因在于：应用面极广，实践性很强，而特有的数学结构使得人们设计出了特别有效的方法对此类模型进行求解本章的重点在：掌握表格化方法求解求解运输简述第1页/共80页提出问题 有A1，A2，A3三个砖瓦厂月产量分别为14，27，19万块，供应B1，B2，B3，B4四个工地，月需要量分别为22，13，12，13万块，每万块运费如下表，求总运费最少的方案A114A227A31922131213B1B2B3B46(千元）753842759106运输问题第2页/共80页运输问题线性规划模型0 xxxxxxxxxxxx13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxs.t.x6x10 x9x5x7x2x4x8x3x5x7x6zmin343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211供应地约束需求地约束第3页/共80页 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，。
已知各产地的和各销地的以及各产地到各销地的，问应如何组织调运，才能使？第4页/共80页运输问题的一般数学模型 有有m个产地生产某种物资，有个产地生产某种物资，有n个地区需要该类物个地区需要该类物资资 令令a1,a2,am表示各产地产量，表示各产地产量，b1,b2,bn表示各销地的销量，表示各销地的销量，ai=bj 称为产销平衡称为产销平衡 设设xij表示产地表示产地 i 运往销地运往销地 j 的物资量，的物资量，cij表示对表示对应的单位运费，则我们有运输问题的数学模型如应的单位运费，则我们有运输问题的数学模型如下：下：0 ,2,1 ,2,1min1111ijjmiijnjiijminjijijxnjbxmiaxxcw销量约束产地约束运输问题第5页/共80页mnmmnnxxxxxxxxx,;,212222111211111111111111111111m行n行第6页/共80页第7页/共80页1、单纯形法（为什麽？）2、表上作业法 第8页/共80页第9页/共80页 确定初始方案(初 始 基本可行解)改进调整（换基迭代）否 判定是否 最 优？是结 束最优方案图3-1 运输问题求解思路图第10页/共80页 表3-3是两个产地、三个销地的运输问题作业表。
第11页/共80页调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 销销 量量 b1 b2 b33121jjiiba表3-3 运输问题作业表（运价表）第12页/共80页3、第13页/共80页表3-4 例3-2有关信息表 450 200 150 100 日销量（需求量）250 75 65 80 乙 200 100 70 90 甲 日产量日产量（供应量）（供应量）C B A运距运距 城市城市煤矿煤矿第14页/共80页;3,2,1;2,1,0200150100250200.7565801007090min231322122111232221131211232221131211jixxxxxxxxxxxxxt sxxxxxxZij需求约束日产量约束总运输量第15页/共80页初始解的确定一、最小元素法二、西北角法三、沃格尔法（VOGLE）第16页/共80页调调 销地销地 运运 量量产地产地 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初始调运方案 150100100100100100100第17页/共80页调调 销地销地 运运 量量产地产地 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 50200200第18页/共80页第19页/共80页元素差额法（Vogel近似法）最小元素法只考虑了局部运输费用最小。
有时为了节省某一处的运费，而在其它处可能运费很大元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费例如下面两种运输方案10515108520211515C10155108520211515C前一种按最小元素法求得，总运费是Z1=108+52+151=105后一种方案考虑到C11与C21之间的差额是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,n第47页/共80页运输问题应用举例运输问题应用举例 1 2 3 4 5 10 15 20 20 40 1 15 35 50 20 40 15 30 30 2 10 60 100 30 35 40 55 25 3 80 70 150 25 115 60 30 70 如产地3的产量变为130，又B地区需的115单位必须满足，试重新确定最优调拨方案第48页/共80页B1B2B3B4B5aiA1101520204050A22040153030100A33035405525130A4(虚）虚）0M00020bj25115603070210得到这样的平衡表后第49页/共80页应用举例1杭州某电视机厂在三个经济区建立分厂，生产产品销往上海，北京，广州。
运价表如下，假定产地2的物资至少运出38个单位，产地3的物资至少运出27个电位，试列出新的运价表 上海上海 北京北京 广州广州 1 2 2 1 20 1 4 5 2 40 2 3 3 3 30 30 20 20 第50页/共80页上海上海北京北京广州广州虚拟虚拟B4aiA1122020A2145M 38A2114502A3233M27A3123303bj30202020得到这样的平衡表后第51页/共80页应用举例2已知某运输问题一个最优调运方案如下表，求K值范围 A B C D 10 1 20 11 1 5 10 15 12 K 9 20 2 0 10 15 25 2 14 16 18 3 5 5 5 15 15 10 第52页/共80页指派问题例：有一份中文产品说明书需译成英、日、德、俄四种语言，现有甲、乙、丙、丁四人都可以胜任，他们译成不同语言所需时间不同，如下表求如何分配使所需总时间最少（每人只译一种）语言人员EJGR甲215134乙1041415丙9141613丁78119整数规划第53页/共80页54指派问题的标准形式及其数学模型指派问题的标准形式（以人和事为例）是：有 n 个人和 n 件事，已知第 i 人做第 j 事的费用为 Cij（i，j=1，2，n），要求确定人和事之间的一一对应的指派方案，使完成这件事的总费用最少。
如指派问题（assignment problem）例：有一份中文产品说明书需译成英、日、德、俄四种语言，现有甲、乙、丙、丁四人都可以胜任，他们译成不同语言所需时间不同，如下表求如何分配使所需总时间最少（每人只译一种）语言语言人员人员EJGR甲甲215134乙乙1041415丙丙9141613丁丁78119第54页/共80页建立模型：设 xij=10译英文：x11+x12+x13+x14=1译日文：x21+x22+x23+x24=1译德文：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个人完成第55页/共80页56一般模型指派问题的标准形式，令 1 当指派第 i 人完成第 j 项任务 0 当不指派第 i 人完成第 j 项任务xij=min z=cijxij xij=1，j=1，2，n xij=1，i=1，2，n xij=1 或 0第56页/共80页57匈牙利解法 标准的指派问题是一类特殊的 0-1 整数规划问题，可以用多种相应的解法来求解。
但是，这些方法都没有充分利用指派问题的特殊性质来有效减少计算量1955年，库恩（W.W.Kuhn）利用匈牙利数学家康尼格（nig）的关于矩阵中独立零元素的定理，提出了指派问题的一种解法，由此，习惯上称之为匈牙利解法第57页/共80页58 匈牙利解法的关键是利用了指派问题最优解的如下性质：若从指派问题的系数矩阵 C=（cij ）nn 的某行（或某列）各元素分别减去一个常数 k，得到一个新的系数矩阵C=（cij ）则以 C 和 C 为系数矩阵的两个指派问题有相同的最优解匈牙利解法第58页/共80页59步骤一：变换系数矩阵使其每行及每列至少有一个零元素，同时不出现负元素步骤二：进行试指派，即确定独立零元素步骤三：继续变换系数矩阵，然后返回步骤二匈牙利解法的一般步骤第59页/共80页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 ）=匈牙利解法的一般步骤第60页/共80页61指派问题（assignment 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）第61页/共80页62以上例说明步骤 0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0此时加圈 0 元素的个数 m=n=4，所以得到最优解指派问题（assignment problem）第62页/共80页63匈牙利解法的一般步骤以上例说明步骤 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0（xij ）=指派问题（assignment problem）第63页/共80页64匈牙利解法的一般步骤例任务任务人员人员ABCDE甲甲乙乙丙丙丁丁戊戊1287154791714109612677614610969109指派问题（assignment problem）第64页/共80页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 9 8 0 0 4 0 6 3 6 5指派问题（assignment problem）第65页/共80页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 个，表示还不能确定最优指派方案此时需确定能覆盖所有零元素的最少直线数目的直线集合方法如下：指派问题（assignment problem）第66页/共80页67匈牙利解法的一般步骤对没有加圈零元素的行打号；对所有打号行的所有含零元素的列打号；再对已打号的列中含零元素的行打号；重复2）和3），直到再也不能找到可以打号行或列为止；对没有打号的行画一横线，对打号的列画一竖线，这样就得到能覆盖所有零元素的最少直线数目的直线集合指派问题（assignment problem）第67页/共80页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）第68页/共80页69匈牙利解法的一般步骤 继续变换系数矩阵其方法是在未被直线覆盖的元素中找出一个最小元素然后在打号行各元素都减去这一最小元素，而在打号列的各元素都加上这一最小元素，以保证原来的 0 元素不变这样得到新系数矩阵（其最优解和原问题相同）若得到 n 个独立的 0 元素，则已得最优解，否则重复该步骤继续变换系数矩阵。
指派问题（assignment problem）第69页/共80页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）第70页/共80页71匈牙利解法的一般步骤 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 此时加圈 0 元素的个数 m=5，而n=5，独立零元素（加圈零元素）等于 n 个，此时已得到最优解，其解矩阵为指派问题（assignment problem）第71页/共80页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）第72页/共80页73 在实际应用中，常会遇到各种非标准形式的制派问题一般的处理方法是先将其转化为标准形式，然后再用匈牙利法求解。
n最大化指派问题设最大化指派问题系数矩阵 C=（cij ），其中最大元素为 m令矩阵 B=（bij ）=（m-cij ），则以 B 为系数矩阵的最小化指派问题和以 C 为系数矩阵的最大化指派问题有相同最优解1.人数和事数不等的指派问题若人少事多，则添加一些虚拟的“人”，其费用系数取 0，若人多事少，则添加一些虚拟的“事”，其费用系数取 0非标准形式的指派问题第73页/共80页74非标准形式的指派问题n一个人可做几件事的指派问题若某个人可以做几件事，则将该人化作几个“人”来接受指派这几个“人”做同一件事的费用系数当然都一样3.某事一定不能由某人做的指派问题若某事一定不能由某人做，则可将相应的费用系数取为足够大的数 M非标准形式的指派问题第74页/共80页非标准指派问题 例：分派甲、乙、丙、丁四人完成五项任务，每人完成任务的时间如下表，请就以下要求分别求解分配情况任务人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁24423623451）要求每人只完成一项2）甲完成两项，其他人每人完成一项3）丁因某种原因不能承担A工作，其他每人一项，E必须承担任务整数规划第75页/共80页1）要求每人只完成一项 任务人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345戊戊00000第76页/共80页2）甲完成两项，其他人每人完成一项 任务人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345戊戊2529314237第77页/共80页3）丁因某种原因不能承担A工作，其他每人一项，E必须承担任务 任务人员ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁M42362345戊戊0000M第78页/共80页Operational/operations research 运筹学Linear programming 线性规划 feasible domain 可行域convex set 凸集 Basic feasible 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 匈牙利算法线性规划有关的英文词汇总汇第79页/共80页感谢您的观看！第80页/共80页。