系统工程---第三章 线性规划.ppt

第三章 线性规划,LP问题的数学模型 LP问题的图解法 LP问题的标准型及其解的概念 单纯形法 对偶理论 灵敏度分析 运输问题,（Linear Programming）,3.1 线性规划及其数学模型,3.1.1 线性规划简介 3.1.2 线性规划的数学模型 小结 作业,运筹学中应用最广泛的方法之一 运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是以线性规划为基础的 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大,3.1 线性规划及其数学模型,3.1.1 线性规划简介,简介,历史悠久 理论成熟 应用广泛,根据一般的说法, 线性规划问题是由G. B. Dantzig教授在1947年前后孕育出来的。那个时候他担任美国空军的数学顾问, 负责发展一套机械式的方法来做兵力调遣, 人员训练, 以及后勤补给这些计划方案。由于这类问题牵涉很广也很复杂, 所以Dantzig 博士先考虑最简单的线性结构, 将有关的函数一律简化成线性形式来处理。其结果便在1948 年以“线性结构的规划” (Programming in Linear Structure) 的标题发表。 至于“线性规划”这个名称, 则是另一位名家T. C. Koopmans 和Dantzig 两人于1948年夏天在美国加州圣塔摩尼加(Santa Monica) 海滩散步时拟定的。在1947到1949两年间, 线性规划里的一些重要观念, 包括最有名的“单纯形法” (Simplex method), 都陆续见诸于世。而且从1947年开始,T. C. Koopmans 便明确指出线性规划可以做为传统经济分析的利器。,G. B. Dantzig教授,简介,历史悠久 理论成熟 应用广泛,线性规划的理论基础绝不是一夕生成。早在1826年左右法国的大数学家傅立叶便研究过如何解决一组联立线性不等式的问题。这以后还有不少的数学家做过相关的研究工作。到了1939年, W.Karush 在芝加哥大学的硕士论文更提出在有限维空间里满足不等式约束的函数其最优化的条件(optimality conditions)。在同一年里, 苏联的L. V. Kantorovich 更提出一些很特殊的线性规划模式来做简单的生产计划。他甚至还有一套简化的方法来求解呢!不幸的是Kantorovich的工作始终未为苏联之外的世界所知, 一直到了Dantzig 建立起完整的线性规划理论之后数十年方为世人所知。 在1950和1960年代, 线性规划的内容愈变愈丰富, 更有许多成功的实用案例, 所以愈来愈受世人瞩目。到了1975年, 瑞典皇家科学院决定将当年的诺贝尔经济奖颁发给前面提到的L. V. Kantorovich 和T. C.Koopmans 以表彰他们在“资源最佳分配理论”的贡献。由于这项最佳分配是藉由线性规划模式来达成, 所以线性规划便成了万众瞩目的焦点。,简介,历史悠久 理论成熟 应用广泛,四年之后(亦即1979年), 线性规划再次成了报章杂志的头条新闻。这次是因为一位苏联数学家L. G. Khachian, 他利用N. Z. Shor,D. B. Yudin, 以及A. S. Nemirovskii的“椭球法”(ellipsoid method) 概念印证出线性规划问题可在多项式时间内求得解答。从纯理论的观点而言,Khachian 的“椭球法”在最恶劣的情况下所需要的计算量要比“单纯形法”增长的缓慢。所以有希望用之解决超大型的线性规划问题, 包括全球资源的最佳分配在内。这也就是华尔街日报(Wall Street Journal) 将“椭球法” 的发现列为头条新闻的重要原因。不幸的是理论归于理论, 在实际计算上, “椭球法”的一般表现反倒不如传统的“单纯形法”来得有效。于是这方面的学者专家重新构想是否能设计出一套解法无论在理论上和实际计算上均能超越“单纯形法” ? 这个问题的答案到了1984 年由一位美国电话电报公司贝尔实验室的印度裔科学家N. Karmarkar 揭晓。他设计出一项“内点法” 来解线性规划问题, 不但理论上较“单纯形法”为优, 而且经由实际验证适合解决超大型的问题。从此之后,“内点法”的研究蔚为一时风潮, 不断有推陈出新的结果。,简介,历史悠久 理论成熟 应用广泛,与其它传统数学学科相比较, 线性规划算是非常“年轻”却非常“实用”的一门应用数学。 根据八十年代的一项调查, 在美国财富杂志(Fortune) 名列前五百名的大公司中, 百分八十五均曾应用线性规划的方法来协助公司的营运。 由此可见线性规划应用面的宽广与普及。,研究对象,给定一定的人力、财力、资源条件下，如何合理安排使用这些资源，使完成的任务最多或效益最高？ 给定任务的前提下，如何安排人、财、物，使得既完成任务，又使资源最省？,3.1 线性规划及其数学模型,例1 生产计划问题（资源利用问题）,3.1 线性规划及其数学模型,3.1.2 线性规划数学模型,解: 设产品A, B的产量分别为x1 ， x2 ，f 为总利润，则该问题可归结为，求一组变量x1 ， x2满足下列条件：,3.1 线性规划及其数学模型,例2：原料混合方案,3.1 线性规划及其数学模型,利用四种原料生产由维生素ABC组成的一种添加剂，详细数据见下表：,求：最低成本的原料混合方案,解：设每单位添加剂中原料i的用量为xi (i =1,2,3,4)， f 为总成本。,min f= 2x1 + 5x2 +6x3+8x4,3.1 线性规划及其数学模型,（1）线性规划模型特点,决策变量： x1， ， xn 决策人要考虑和控制的因素且非负 约束条件：线性等式或不等式 目标函数：=(x1 xn) 线性式，求最大或最小值。,3.1 线性规划及其数学模型,3.1.2 线性规划数学模型,14,max(min) f=c1x1+ c2x2+cnxn,3.1 线性规划及其数学模型,3.1.2 线性规划数学模型,（2）线性规划数学模型的一般形式,3.1 线性规划及其数学模型,3.1.2 线性规划数学模型,（3）线性规划数学模型的简化形式,（4）隐含的假设,比例性：决策变量变化引起目标的改变量与决策变量改变量成正比 可加性：每个决策变量对目标和约束的影响独立于其它变量 连续性：每个决策变量取连续值 确定性：线性规划中的参数aij , bi , ci为确定值,3.1 线性规划及其数学模型,3.1.2 线性规划数学模型,例3：（下料问题）某工厂制造一种机床，每台机床需A，B，C三种不同长度的轴各一根，其毛坯长度：A为2.9m，B为2.1m，C为1.5m，它们用同一种圆钢来下料，每根圆钢长为7.4m。要造100台机床，问如何下料最好？试建立其数学模型（不考虑下料截口损耗）。,3.1 线性规划及其数学模型,3.1.2 线性规划数学模型,解：由题意，将各种可能的下料方案排列如下表： 各种下料方案一览表,3.1 线性规划及其数学模型,解：设按第i种方案下料的原材料为xi根，f 为所需圆钢总数。,3.1 线性规划及其数学模型,若设 f 为总料头，则目标函数变为,min f = 0.1x2 + 0.3x2+0.9x3+1.1x5 +0.2x6 +0.8x7 +1.4x8,思考：1. 机床数变化? 2. A、B、C三种轴的配套比例发生变化？,例4: 运输问题,由甲、乙、丙三个仓库向A、B、C、D四个商店运送某种商品，已知三个仓库该商品的库存量、四个商店对该商品的需求量（见上表）。从仓库向商店运送单位商品的运费见上表。 问：如何运输，可是总运输费用最少？,3.1 线性规划及其数学模型,解：设xij为i 仓库运到 j 商店的货物数量(i 1,2,3； j 1,2,3,4)，则根据题意有：,3.1 线性规划及其数学模型,小结 线性规划模型就是求一组非负变量在满足一系列线性等式或线性不等式的条件下，使线性目标目标函数取得最大值或最小值。 线性规划模型可以表示为：,3.1 线性规划及其数学模型,3.1 线性规划及其数学模型,作业,3.2 线性规划图解法,max (min) f = CX (1) AX(= ) b (2) X 0 (3),定义1：满足约束(2)、(3)的X=(x1 xn)T称为LP问题的可行解，全部可行解的集合称为可行域。,定义2：满足(1)的可行解称为LP问题的最优解。,图解法即是用图示的方法来求解线性规划问题。 一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。,3.2 线性规划图解法,max f=40x1+ 50x2,x1+2x2 30 3x1+2x2 60 2x2 24 x1 , x2 0,例1：用图解法求解下列线性规划问题：,3.2 线性规划图解法,解：(1) 可行域的确定 x1 0 x1 =0 (纵) x2 0 x2=0 (横),x1+2x2 30 x1+2x2 =30 (0,15) (30,0),3x1+2x2 =60 (0,30) (20,0),2x2 =24,3.2 线性规划图解法,(2) 最优解的确定,解得：x* = (15，7.5) fmax =975,f=40x1+50x2 ，令 f = 0，则 0=40x1+50x2 (0,0)， (10,-8),令 f = 200，则 200 = 40x1+50x2 (0，4)， (5，0),等值线：位于同一直线上的点的目标函数值相同。,3.2 线性规划图解法,例2：用图解法求解下列线性规划问题：,3.2 线性规划图解法,最优解：BC线段 B点 C点 X(1)=(6,12) X(2)=(15,7.5) X= X(1)+(1-) X(2) (0 1),解:,max f=40x1+ 80x2,3.2 线性规划图解法,X= = +(1- ),3.2 线性规划图解法,最优值无界 无有限最优解,max f=2x1+ 4x2,例3：用图解法求解下列线性规划问题：,3.2 线性规划图解法,因为该线性规划问题无可行解，因此，无最优解。,例4：用图解法求解下列 线性规划问题：,3.2 线性规划图解法,例5：求下列线性规划问题：,解：（1）确定可行域为OABCD,（2）画等值线，找出使目标 函数值减少的平移方向。,（3）平移等值线，找出最优点C，求出该点的坐标（4，1），即为最优解。,3.2 线性规划图解法,无可行解,有解,无解,LP问题的解,唯一解,无穷多解,无有限最优解,3.2 线性规划图解法,小结：,两个变量的LP问题的解：,(1) 可行域为凸多边形。,(2) 若有最优解，一定可在可行域的顶点得到。,3.2 线性规划图解法,结论：,补充作业,用图解法求解下列LP问题,用图解法求解下列LP问题,3.3 线性规划问题的标准型及解的概念,3.3.1 线性规划问题的标准型 1. LP问题标准型的定义 2. LP模型的标准化 3.3.2 线性规划问题解的概念 1. LP问题解的概念 2. LP问题解的性质,41,LP问题数学模型的一般形式,max(min) f = c1x1+ c2x2+cnxn,a11x1+ a12x2+ a1nxn (=, )b1 a21x1+ a22x2+ a2nxn (=, )b2 am1x1+ am2x2+ amnxn (=, )bm xj 0( 0，正负不限) j = 1, , n,回顾,1. LP标准型的定义,max f=c1x1+ c2x2+cnxn,其中 bi 0 (i =1,2,m),3.3.1 线性规划问题的标准型,LP标准型的特点：,(1) LP问题标准型的矩阵表达形式,max f=CX AX=b X 0,C=(c1 c2 cn ),3.3.1 线性规划问题的标准型,(2) LP问题标准型的向量表达形式,3.3.1 线性规划问题的标准型,(1) 约束条件的标准化,(2) 变量的标准化,(3) 目标函数的标准化,2. LP模型的标准化,3.3.1 线性规划问题的标准型,(4) 约束条件右端常数的标准化,(1) 约束条件的标准化,例1 max f=40x1+ 50x2,+0x3 +0x4+0x5,松弛变量,+x3 =,+x4 =,+x5 =,x1 , , x5 0,3.3.1 线性规划问题的标准型,(1) 约束条件的标准化,例2 max f =2x1+ 5x2+6x3 +8x4,- x5 =,- x6 =,- x7 =,x1 , , x7 0,剩余变量,3.3.1 线性规划问题的标准型,(2) 变量的标准化,例3,令x1= x1- x1“ , x1 , x1“ 0, 将上式转化为：,3.3.1 线性规划问题的标准型,(2) 变量的标准化,-6+6 x1+6 10+6,例4,3.3.1 线性规划问题的标准型,令x1 = x1 +6,0 x1 16,x1 16 x1 0,(3) 目标函数的标准化,3.3.1 线性规划问题的标准型,LP模型标准化方法总结：,3.3.1 线性规划问题的标准型,(4) 约束条件右端常数的标准化,若某个约束条件右端常数的为负值，只需在该约束条件两端同乘以（-1）即可。,min f = -x1+2x2 3x3,例5 将下列LP模型标准化,3.3.1 线性规划问题的标准型,解： 令f = - f, 引入松弛变量x6, 引入剩余变量x7,令x3 = x4 - x5,max f= x1 2x2 +3x4 3x5,3.3.1 线性规划问题的标准型,课下练习：将下列线性规划模型化为标准型,3.3.1 线性规划问题的标准型,3.3.2 线性规划问题解的概念,假定：,(1) R(A)=m,(2) n m,我们考虑标准型的线型规划问题：,1. LP问题解的概念,定义1 基(基矩阵) 若系数矩阵A的一个m阶子矩阵B是可逆矩阵，则称B为LP问题的一个基。,1. LP问题解的概念,也就是说，基矩阵B是由A的m个线性无关的列向量组成。,AX=b的求解过程：,A = ( B N ),1. LP问题解的概念,定义2 基本解对应于基B，令非基变量为0，求得基变量的 值 ，则称 为LP问题的一个基本解。,定义3 基本可行解满足非负约束条件的基本解，称为基本可行解。对应的基矩阵称为可行基矩阵（简称可行基）。, 基本解中非零分量的数目，不大于方程的个数m。,1. LP问题解的概念,1. LP问题解的概念,B=(P3 P4 P5)=I 显然B可逆，为一基矩阵,令x1 = x2 =0, 解得：x3=30, x4=60, x5=24,1. LP问题解的概念,称为对应于基矩阵B的基本解。,1 2 1 1 =(P1 P2 P3 )= 3 2 0 0 2 0,|B1|=60, B1可逆,1. LP问题解的概念,令x4=x5=0 解得 X=(12, 12, -6, 0, 0)T,X为非基可行解，B1不是可行基。,62,约束方程的 解空间,线性规划问题解的概念之间的关系,基本解,可行解,非可行解,基本 可行解,最优解,2. LP问题解的性质,若LP问题有可行解，则可行解集(可行域)是凸集(可能有界，也可能无界)，有有限个顶点。,LP问题的基本可行解对应于可行域的顶点。,若LP问题有最优解，则一定可以在基本可行解中找到。,本节课的重点是线性规划模型的标准化,小 结,本节课的难点是线性规划的基本解和基本可行解的概念,作业,66,2. 单纯型表及其格式,67,3.单纯形法的主要步骤,Step1.找初始基可行解 对于(max , )，松弛变量对应的列构成一个单位阵 Step2.检验当前基可行解是否为最优解 所有检验数 j 0，则为最优解，否则进行下一步。 Step3.换基迭代（改进基可行解） 从 j 0 中找最大者，其对应变量xk称为换入变量， xk所在列称为主元列 确定换入变量的最大值和换出变量 最小比值原则,68,设第 l 行使 最小，则第 l 行对应的基变量x l称为换出变量，第 l 行称为主元行 迭代过程 主元行 l 行与主元列 k 列相交的元素alk 称为主元，迭代以主元为中心进行 迭代的实质是线性变换，即要将主元 alk变为1，主列上其它元素变为0。,max f =40x1+ 50x2,例1 用单纯形法求解下列LP问题,max f =40x1+ 50x2+0x3 +0x4+0x5,标准化,建立初始单纯形表,基变量,*,30/2=15,60/2=30,24/2=12,j,第一步迭代,基变量,6/1=6,36/3=12,_,j,第二步迭代,基变量,18/2=9,12/0.5=24,_,j,第三步迭代,基变量,该问题的最优解为：X*=(15, 7.5, 0, 0, 9)T, f * = 975,j,例2 用单纯形法求解下列LP问题,基变量,0,-1,2,8,9,3,-2,0,0,2,-1,-2,x1,该问题具有无界解,j,用单纯形法求解下列LP问题,课堂练习,基变量,15/3=5,j,*,10/5=2,基变量,45/19,j,*,5,最优解为 X*=( 2, 0, 9, 0 )T max f = 20,基变量,j,最优解为 X*=( 20/19, 45/19, 0, 0 )T max f = 20,3.6 线性规划问题的对偶理论,3.6.1 线性规划的对偶问题 3.6.2 对偶问题的基本性质 3.6.3 对偶问题的经济意义 3.6.4 对偶单纯形法 小结 作业,3.6.1 线性规划的对偶问题,一、原问题与对偶问题 例1、某厂在计划期内要安排生产A、B两种产品，这两种产品分别需要在甲、乙丙三种不同的设备上加工，有关数据如表3-14所示。问应如何安排生产计划才能使利润最大？,该问题的数学模型,设A、B两种产品的产量分别为x1, x2 ,则这个问题可以归结为求解下列线性规划问题：,设 y1, y2, y3分别表示设备甲、乙、丙每台时的加工费（或租金）,则,如果工厂准备将设备进行出租，请为该厂的决策者进行决策。,问题（P）： 问题（D）：,出租方（生产者）,希望获利最大 希望付出（成本、费用）最小,承租方,原问题与对偶问题,例2:某种作物，全部生产过程至少需氮肥32公斤，磷肥24公斤，钾肥42公斤。已知甲、乙、丙、丁四种复合肥料每公斤的价格以及氮磷钾的含量，如下表所示：,问：应如何选购这些肥料，即能满足作物对氮磷钾的需要，又使施肥成本最低？,现从另外一个角度考虑：有一化肥公司生产氮、磷、钾三种单成分化肥，现要为这三种化肥定价，既要获利最大，又要和生产甲乙丙丁四种复合肥料公司竞争，因此以这些单成分化肥的价格、施肥满足作物需要时，要求利润最大。,（P）,（D）,对称的对偶问题,原问题,对偶问题,=,0,min,Y,C,YA,Yb,g,=,0,max,X,b,AX,CX,f,例3：写出下面问题的对偶规划,解：,对偶问题,令 y1 = y1 -y1 “ ，则,非对称的对偶问题,原问题,对偶问题,=,=,0,max,X,b,AX,CX,f,=,无正负限制,Y,C,YA,Yb,g,min,混合形式的对偶问题,=,+,-,-,-,+,-,+,-,+,+,=,无限制,3,2,1,3,2,1,3,2,1,3,2,1,3,2,1,0,0,5,2,2,2,3,.,3,2,25,min,x,x,x,x,x,x,x,x,x,x,x,x,t,s,x,x,x,f,例4：写出下列线性规划的对偶规划,解：原线性规划的对偶规划为：,课堂练习,写出下列线性规划问题的对偶规划,原问题和对偶问题的关系,二、对偶问题的基本性质,1.弱对偶性 若X和Y分别是原问题和对偶问题的任一可行解，则必有,该性质告诉我们，最大化问题的任一可行解的目标函数值都是其对偶最小化问题目标函数的下界；而最小化问题的任一可行解的目标函数值都是其对偶最大化问题目标函数的上界。,2.若X* 和 Y* 分别为原问题和对偶问题的可行解，且可行解对应的原问题和对偶问题的目标函数值相等，即 CX* = Y*b ，则 X* 和 Y*分别为原问题和对偶问题的最优解。,3.无界性 若原问题（对偶问题）的目标函数无界，则其对偶问题 （原问题）必无可行解。,该性质说明，原问题和对偶问题之一无最优解，则另一个也无最优解。,4.对偶定理 若原问题和对偶问题之一有最优解，则另一个也有最优解，且两者的最优目标函数值相等。,6.若原问题的最优解为XB = B-1b，则对偶问题的最优解为Y=CBB-1.,5.若原问题和对偶问题同时有可行解，则他们必都有最优解。,7.根据原问题最优单纯形表中的检验数可以读出对偶问题的最优解。,例1、 原问题,对偶问题,初始单纯形表,最优单纯形表,原问题,对偶问题最优单纯形表：,综上所述，一对对偶问题的解必然是下列三种情况之一：,1.原问题和对偶问题都有最优解，且最优目标函数值相等。,3.原问题和对偶问题都无可行解。,2.一个问题具有无界解，则另一个问题无可行解。,例3 已知线性规划问题,试用对偶理论证明上述问题无最优解。,三、对偶解的经济涵义影子价格,通过求解：原问题和对偶问题的最优解分别为,1.影子价格的定义,对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）。,影子价格是指在最优解的基础上，当第 i 个约束条件的右端项 bi 增加一个单位时，目标函数的变化量。,由对偶定理可知，当达到最优解时，原问题与对偶问题的目标函数值相等，即有f *=CX*=Y*b=y1* b1+ y2* b2+ ym* bm,现考虑在最优解处，右端项bi的微小变动对目标函数值的影响，由上式，将f *对bi求偏导数：,该式表明了，若原问题的某一个约束条件的右端项bi每增加一个单位，则由此引起的最优目标函数值的增加量，就等于与该约束条件相对应的对偶变量的最优解的值。,2.影子价格的求法 例4,某工厂生产三种产品，三种产品对于原材料、劳动力、电力的单位消耗系数，资源限量和单位产品价格如下表所示：,资源,产品,1.求最佳生产方案使总产值最大。,2.求各资源的影子价格，并解释其经济意义。,3.影子价格的作用,影子价格可以告诉管理人员，增加哪一种资源对增加经济效益最有益。,影子价格可以告诉管理人员，花多大的代价增加资源才是合算的。,影子价格在新产品开发决策中的应用。,影子价格在资源购销决策中的应用。,例: 一个大学教授用部分时间从事于咨询工作。通过这项工作，他的总收入将有所提高，该教授掌握了咨询补偿的基本规律：“一个专家的价值正比于厂商和专家之间的距离”。也就是说，要求咨询的单位愈远，他得到的报酬愈多。遗憾的是，旅行时间也将增加。目前他有较多的咨询机会，但可用时间有限，他希望详细分析这种情况，他是否要雇助手？如果这样，他应付多少工资？,设： x1 = 每月为A企业咨询的小时数（利润：100元/h） x2 = 每月为B企业咨询的小时数（利润：120元/h） x3 = 每月为C企业咨询的小时数（利润：160元/h） 进一步假定该教授每月有40小时用于咨询工作，并且希望他的旅行时间每月在24小时以内。每小时咨询工作所要求的旅行时间对于企业A、B、C来说分别为0.1、0.2、0.2小时。教授估计三个企业每月要求最大的咨询时间分别是80、60、20小时。据此，我们可以很快建立该问题的线性规划模型。,式中 f从事咨询工作每月可得的利润总和（元/月）。 对偶问题的模型为：,思路：,单纯形法：找基B，满足右端常数非负，但检验数 不全 0。,对偶单纯形法：找基B，满足检验数 0，但右端常数不全0。,四、对偶单纯形法,例1：,例2.,1,1/2,-1/2,0,0,3/2,0,-1/2,-3/2,1,0,1/2,0,-3/2,-1/2,0,1,1/2,0,-5/2,-1/2,0,0,3/2,对偶单纯形法基本步骤:,（3）作初始单纯形表，要求全部j 0,（4）判定：若单纯形表中右端常数全0，停止。 否则，取min bi | bi 0= bl，则bl 为主元行， bl 所 对应的基变量xl 为换出变量。,（5）确定换入变量，并开始迭代,若x l行的alj 全0，停止，原问题无可行解。,（1）将原问题标准化,（2）找初始基变量，并将目标函数中的基变量用非基变量代替, 若x l行的alj 有alj 0 ,则求,xk为换入变量，以alk 为主元，进行换基迭代得到新的单纯形表，转回（4）。,练习,例3,1,-1,-1,1,0,1,2,-3,0,-2,-1,1,该问题无可行解。,3.8 运输问题,3.8.1 运输问题的提出 3.8.2 产销平衡运输问题的数学模型 3.8.3 产销平衡运输问题的求解方法 3.8.4 产销不平衡的运输问题 3.8.5 运输问题的应用和推广 小结 作业,例：有一家罐头厂，下设甲、乙、丙三个分厂，向A、B、C三个地区供应其产品，其数据如下表所示。问如何调运才能使总运费最少？,3.8 运输问题,3.8.1 运输问题的提出,已知:有m个生产地Ai（i=1,2,m），可供应某种物资其供应量（产量）分别为ai（i=1,2,m）。 另有n个销地Bj， （j=1,2,n），需要该物资其需要量分别为bj （j=1,2,n）.从Ai到Bj运输单位物资的运价为cij， （i=1,2,m;j=1,2,n）。 问：产销平衡的条件下，如何组织调运，才能使总运费最小？,3.8 运输问题,3.8.1 运输问题的提出,（一）一般的运输问题,产销平衡表,运价表,3.8 运输问题,3.8.1 运输问题的提出,（二）一般的运输问题的数据表,运输问题的数据表（运输表）,3.8 运输问题,3.8.1 运输问题的提出,设 xij表示从Ai运输到Bj的物资的数量，i=1,2,m；j=1,2,n。,3.8 运输问题,3.8.2 产销平衡运输问题的数学模型,产地约束,销地约束,矩阵形式：,i =1,2,m; j =1,2, ,n,3.8 运输问题,3.8.2 产销平衡运输问题的数学模型,运输问题数学模型的特征,1.m+n个约束条件，且每个约束条件都是等式,2.mn个变量,3.系数矩阵A是一个 稀疏矩阵,4.系数矩阵A的秩为 m+n-1， 即R(A)=m+n-1,3.8 运输问题,（一）表上作业法的流程图：,3.8 运输问题,3.8.3 产销平衡运输问题的求解方法表上作业法,Step3:调整（或改进）方案-用闭回路调整法,Step1:确定初始方案,Step2:判别方案是否最优-利用检验数来判别,3.8 运输问题,3.8.3 产销平衡运输问题的求解方法表上作业法,（二）表上作业法的计算步骤：,某公司经销甲产品。它下设三个加工厂A1、A2、A3 ，其产量分别为7t，4t，9t。该公司把这些产品分别运往四个销售点B1、B2、B3、B4，各销售点销量为3t，6t，5t，6t。已知从各工厂到各销售点的单位运价为下表所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总运费为最少。,3.8 运输问题,Step1 确定初始方案 1.最小元素法,运费 f = 86,3,1,4,6,3,3,3.8 运输问题,Step1 确定初始方案 2.Vogel法（元素差额法）,运费 f = 85， 比最小元素法低1。,3,1,5,6,3,2,0,1,1,2,5,1,3,*,2,*,*,762,*,2,0 0,*,3.8 运输问题,课堂练习1,用最小元素法求下列运输问题的初始方案,3.8 运输问题,课堂练习解答,4,2,2,0,3,3.8 运输问题,课堂练习答案,4,2,2,0,3,运费 f = 51 退化的基可行解,3.8 运输问题,发点,列差额,行差额,收点,0,2,1,3,2,*,5,2,3,*,10,0,0,*,15,5,例：用Vogel法求下列运输问题的初始方案,35,35,3.8 运输问题,发点,收点,5,10,15,5,运费 =115,35,35,初始运输方案,3.8 运输问题,课堂练习2,用Vogel法求下列运输问题的初始方案,3.8 运输问题,课堂练习2解答,行差额,4,2,1,2,1,1,*,10,3,2,*,20,0,0,0,*,20,50,10,3.8 运输问题,课堂练习2答案,运费 f = 530,3.8 运输问题,Step2 判别运输方案是否最优,用检验数 来判别,判别的规则如何？,3.8 运输问题,1.闭回路法求检验数（原理）,为了求某一空格（非基变量）的检验数，先要找出它所对应的闭回路。,闭回路的顶点，除这个空格外其它的均应有数字格组成。,每一个空格都存在唯一一条闭回路。,用闭回路求某一空格（非基变量）的检验数的方法:,首先给闭回路的顶点标号：空格为第1个顶点，依次为第2，第3，,检验数=奇数顶点的单位运费之和减去偶数顶点的单位运费之和,3.8 运输问题,实例 用闭回路法求检验数,销地,加工厂,4,3,3,3,1,6,+1,+1,-1,-1,1,检验数：利用单位运费求检验数！,3.8 运输问题,实例 用闭回路法求检验数,销地,加工厂,4,3,3,3,1,6,1,2,3.8 运输问题,实例 用闭回路法求检验数,销地,加工厂,3.8 运输问题,2.位势法求检验数（原理）,对产销平衡的运输问题，若用u1，u2，um分别表示前m个约束条件的对偶变量，用v1，v2，vn分别表示后n个约束条件的对偶变量，即有对偶变量 Y=(u1，u2，um， v1，v2，vn) 由于线性规划问题的变量xj对应的检验数 由此可知运输问题的变量xij对应的检验数为,3.8 运输问题,位势法求检验数（公式）,对于基变量格（数字格）有：cij = ui + vj 令u1 = 0，和m + n 1个基变量，就可以求出ui和vj。 利用公式 ，就可以求出所有非基变量的检验数。,3.8 运输问题,实例：用位势法求检验数,销地,加工厂,4,3,3,3,1,6,1,销量,产量,行位势,列位势,0,3,10,-1,2,-5,9,2,1,-1,10,12,3.8 运输问题,3.8.3 产销平衡运输问题的求解方法,Step3 调整(改进)运输方案 闭回路调整法,当表中某个空格的检验数为负值时，表明未得到最优解，需要进一步改进。改进的方法就是闭回路调整法。,闭回路调整法的具体步骤：,(1)选择换入变量 选取负的检验数所对应的非基变量为换入变量。以它对应的空格为出发点作一条闭回路。,(2)确定调整量 在闭回路上所有偶数顶点基变量的最小值。,(3)确定换出变量 在闭回路的各偶数个顶点中，取值为零的变量就是换出变量。,(4)调整的规则 在闭回路上所有奇数顶点的运输量都加上，所有偶数顶点的运输量都减去。闭回路以外的运输量都不变。,3.8 运输问题,闭回路调整法（举例）,销地,加工厂,4,3,3,3,1,6,12,10,-1,1,2,1,+,+,_,_,调整量：利用奇数（标有“-”号的）顶点的运量求调整量！,3.8 运输问题,闭回路调整结果（新的运输方案）,销地,加工厂,5,3,3,2,1,6,销量,3.8 运输问题,判别新方案是否最优,行位势,销地,加工厂,5,3,3,2,1,6,12,9,2,0,销量,列位势,0,3,10,-2,-5,3,9,2,1,3.8 运输问题,最优运输方案,销量,最少运费=53+210+31+18+64+35=85,3.8 运输问题,其处理方法： 虚设一个销地Bn+1 从各产地到假想销地的单位运费为0（ci,n+1=0）,1.产大于销（ ） 的运输问题的数学模型：,3.8 运输问题,3.8.4 产销不平衡运输问题,（一）产大于销的情况,产销不平衡运输问题举例,3.8.4 产销不平衡运输问题,3.8 运输问题,转化为产销平衡的运输问题,3.8.4 产销不平衡运输问题,3.8 运输问题,最小元素法确定初始方案,4,2,2,2,3,3,3,3.8.4 产销不平衡运输问题,3.8 运输问题,初始运输方案,4,2,2,2,3,3,3,3.8 运输问题,3.8.4 产销不平衡运输问题,用位势法求检验数并判别最优性,4,2,2,2,3,3,3,行位势,列位势,0,0,4,0,2,3,-2,3,8,0,8,2,5,7,7,2,3.8.4 产销不平衡运输问题,3.8 运输问题,最优运输方案,运费=32 甲、乙产地的物资有剩余,3.8.4 产销不平衡运输问题,3.8 运输问题,其处理方法： 虚设一个产地Am+1 从该产地到各销地的单位运费为0（cm+1,j=0）,2.产小于销（ ） 的运输问题的数学模型：,3.8 运输问题,3.8.4 产销不平衡运输问题,（二）产小于销的情况,产地,销地,35,45,3.8 运输问题,3.8.4 产销不平衡运输问题,（二）产小于销的情况,利用表上作业法求解下面的产销不平衡运输问题,产地,销地,35,45,10,10,15,运费=370 B的销量还差10没有满足,3.8 运输问题,3.8.4 产销不平衡运输问题,（二）产小于销的情况,思考题：考虑如下的运输问题,此时可用表上作业法求出最优调运方案（见表中黑圈），最小运费为：444元；现在让A1，A3都多运5吨， A3多销10吨，则可求出相应的最优调运方案（见表中红圈