资源描述
第二章 对偶理论与灵敏度分析,1,本章内容,对偶理论是线性规划最重要的基础理论之一 是进行经济分析的重要工具,2,一般形式单纯形法计算的矩阵描述,设线性规划问题 : 目标函数 约束条件 AXb; 非负条件 X0,线性规划问题的约束条件加入松弛变量以后，得到标准型：,max z=CX+0Xs,AX+IXs=b; X，X s0,max z=CX,3,矩阵A可以分块记为A=B，N 相应地，向量X和C可以记为,XB=B-1b B-1NXN B-1Xs,对于一个确定的基B，目标函数z可以写成,目标函数z用非基变量表出的形式,4,初始单纯形表,迭代n 步之后的单纯形表,5,影子价格总结：,3.影子价格是在系统达到最优时对系统资源的一种最优估价，并假设第i种资源增加一个单位时最优基没改变。 4. 影子价格可以告诉管理人员，增加哪一种资源对增加经济效益有利，帮助企业调节生产规模； 5.影子价格可以告诉管理人员，花多大的代价来增加资源才是合算的； 6.影子价格可以帮助管理人员进行生产要素对产出贡献的分解； 7.影子价格可以告诉管理人员如何考虑新产品的价格。,1.影子价格的大小客观地反映了资源在系统内的稀缺程度。,2.影子价格的取值与系统的状态有关，系统中任一状态的改变都会引起影子价格的变化。,6,对偶单纯形法是应用对偶原理求解原始线性规划的一种方法在原始问题的单纯形表格上进行对偶处理。 注意：不是解对偶问题的单纯形法！,什么是对偶单纯形法？,7,1.使用条件： 检验数全部0； 右端向量列至少一个元素 0； 2. 实施对偶单纯形法的基本原则： 在保持对偶可行的前提下进行基变换每一次迭代过程中取出基变量中的一个右端负分量作为换出变量去替换某个非基变量（作为换入变量），使原始问题的非可行解向可行解靠近。,对偶单纯形法的实施,8,3. 计算步骤： 建立初始单纯形表，计算检验数行。,9, 基变换： 先确定换出变量右端向量列中的负元素（一般选最小的负元素）对应的基变量出基；,相应的行为主元行。,10,然后确定换入变量原则是：在保持对偶可行的前提下，减少原始问题的不可行性。 如果,（最小比值原则） ，则选 为换入变量，相应的列为主元列，主元行和主元列交叉处的元素 为主元素。,11,按主元素进行换基变换（初等行变换），将主元素变成1，主元列变成单位向量，得到新的单纯形表。,最优解判别法则：右端向量满足非负约束,12,第五节 灵敏度分析,13,以前讨论线性规划问题时，假定ij，bi, cj都是常数，但实际上这些系数往往是估计值或预测值。 如市场条件一变，cj值就会变化；ij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。,14,灵敏度分析：指对系统或事物因周围条件变化显示出来的敏感程度的分析。 线性规划模型的灵敏性分析： 研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程，称为线性规划的灵敏度分析。,一、灵敏度分析的含义和内容,15,目标函数的价值系数变化 约束方程右端向量变化 约束方程组系数阵变化 决策变量或约束条件变化,2. 线性规划灵敏度分析的内容,max z=CX,AX=b X0,1. 最优解保持不变，即基变量和它们的取值没有变化 2. 基变量保持不变，但它们的值改变了 3. 基解完全变了,对解的影响主要有:,可行性 B1b 0 最优性CNCBB1N 0,16,LP灵敏度分析最终回答：,计算量少，充分利用到原最优的单纯形表结果,1. 这些系数在什么范围内变化时，原先求出的线性规划问题的最优解或最优基不变。 2. 如果系数的变化超出了上述范围，如何用最简便的方法求出新的最优解。,17,三、灵敏度分析的步骤,将参数的改变通过计算反映到最终单纯形表上,2. 检查原问题和对偶问题是否还是可行解 3. 按照下表所列情况分别进行讨论,18,1. 价值系数cj 的变化分析,四、灵敏度分析的具体内容,初始单纯形表,最优单纯形表,19,（1）当cj 是非基变量的价值系数它的变化只影响 一个检验数。,（2）当cj 是基变量的价值系数它的变化将影响所有非基变量的检验数，,20,例16：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划：,已知最优表如下： （1）确定x2的系数c2的变化范围，使原最优解保持最优； （2）若c2=6，求新的最优计划。,21,4 = c25 0 5 = 52c2 0 5/2 c2 5,最优解X*=（35，10，25，0，0）保持不变。,最优单纯形表,22,x1*=45/2，x2*=45/2，x4*=25/2，x3*= x5*=0，z*=495/2,23,2. 右端常数bi (资源系数)的变化分析,初始单纯形表,最优单纯形表,24,当bi发生变化时，将影响所有基变量的取值, 保持B-1b0, 当前的基仍为最优基，最优解的结构不变（取值改变）； （B-1b）i0, 当前基为非可行基，但是仍保持为对偶可行基,可用对偶单纯形法求出新的最优解； 如何求出保持最优基不变的bi 的范围? 把bi看作待定参数，令B-1b0，求解该不等式组即可。,25,例17：对于上例中的线性规划作下列分析： （1）b3在什么范围内变化，原最优基不变？ （2）若b3=55，求出新的最优解。,26,最优单纯形表的A中 松弛变量的系数,最优单纯形表,27,解得40b350，即当b340，50 时，最优基B 不变,28,（2）当 b3= 55 时,=,=,29,3. 增加一个新决策变量xj 的变化分析,资源的合理利用问题：,新问题：如开发出一种新产品，已知其有关工艺参数（或消耗的资源量）和单位产品利润，设该种产品的产量为xn+1，则cn+1和Pn+1已知，需要进行“是否投产”的决策。,（1）增加1个新变量：相当于系数阵A增加1列,30,对新问题：,最优单纯形表,此表达到最优,此表未达到最优,用单纯形法迭代 至找到最优解,31,例18： （续例）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示， P6= 。 (1) 问它的价值系数c6符合什么条件才必须安排它的生产？ (2) 设c6=3，新的最优生产计划是什么？,32,解：(1),6=c6CBB1P6 =c6（0，5，4） = c65/2,60,说明新产品D不宜投产，否则会使产品总利润下降,最优单纯形表,33,(2),34,4. 约束条件增减的变化分析,如果当前最优解满足新增约束条件，则最优解不变； 否则，增加约束条件体现在单纯形表中，相当于多了一行，从而增加一个基变量，同时还要增加一列。,增加一个约束后，可行域的变化为 R R,R为空集， 新问题无可行解,删除一个约束条件 若这个约束条件对来说是不起作用约束，即松弛变量，剩余变量不为零，则去掉这个约束条件对最优解无影响。 反之，则使最优解发生变化，将松弛变量、剩余变量或人工变量转为基变量即可。,35,将新增约束标准化，添加到原最优表格中(约束矩阵同时新增1行和1列）； 进行规格化处理用矩阵的行变换将当前基变成单位阵；,用适当方法（通常是对偶单纯形法）进行迭代求出新的最优解。,增加一个约束条件的分析过程,36,例19：假设上例中，还要考虑一个新的资源约束：4x1+2x2150,4x1+2x2+x6=150,X*=（35，10，25，0，0）T,37,4x1+2x2+x6=150,38,39,小结：系数变化对解的结果的影响,灵敏度分析时，要弄清楚：1）系数在什么范围内变化时，最优解（基）不变；2）若系数的变化使最优解发生变化，如何最简便地求得新最优解。 C的变化只影响检验数（对偶问题的解），不影响原问题的基本解； b的变化只影响原问题的基本解，不影响检验数（对偶问题的解）； A中系数的变化可能既影响原问题的基本解，又影响对偶问题的解。,40,的最优单纯形表为：,41,1.为保持现有最优解不变，分别求出C1， C2的变化范围。,2.当C1变为5时，求新的最优解。,3.当C2变为2， C4变为6时，求新的最优解。,42,43,第三章 运输问题,44,4.应用问题举例,3.运输问题的进一步讨论,2.表上作业法,1.运输问题及其数学模型,第三章 运输问题,45,第一节 运输问题及其数学模型,46,一、运输问题的提出,人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。,47,例1：某运输问题的资料如下：,21,48,产地约束,销地约束,为i个产地运往第j个需求地（销地）的运量,49,二、运输问题数学模型的一般形式,1. 已知资料,设某种物品有m个产地A1，A2，Am，产量分别是 a1，a2，am个单位 有n个销地B1，B2，Bn，销量分别为b1，b2，bn个单位； 从Ai 到Bj运输单位物品 的运价是cij； 求总费用最小的运输方案？,50,产销平衡问题 产销不平衡问题 产大于销 销大于产,运输问题分为：,51,解：设xij(i=1,2,，m；j=1,2,n)为第i个产地到第j个销地的运量，则数学模型为：,1. 运输问题存在可行解，也一定存在最优解 2.当供应量和需求量都是整数时，则一定存在整数最优解 3. 有m+n个约束，mn个变量 4. 有m+n1个基变量,产销平衡问题,52,53,销大于模型：,产大于销模型：,54,（1）运输问题有有限最优解。 定理: 运输问题有可行解的充要条件是产销平衡,三、运输问题数学模型的特点,55,（2）运输问题约束条件的系数矩阵,56,矩阵的元素均为1或0；每一列只有两个元素为1，其余元素均为0； 列向量Pij 中元素1分别处于第i行和第m+j行。 将该矩阵分块，特点是：前m行构成m个mn阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，m）；后n行构成m个n阶单位阵。,57,（3）运输问题的解,闭回路：是能折成 形式的变量组集合。其中 i1 , i2 , ， is 互不相同，j1 , j2 , ， js 互不相同。每个变量称为闭回路的顶点，连接闭回路相邻两顶点的直线段叫做闭回路的边。,例：如下 就是一个闭回路。,58,闭回路的特点：,1. 每一个顶点都有两条边与之相接，一条是水平的，一条是铅直的； 2. 每一个顶点都是转角点，与之相邻的两个顶点，分别在它的水平和铅直方向； 3. 每一行（列）如果有闭回路的顶点，则必出现一对，顶点总个数是偶数； 4. 从任何一个顶点出发，沿任何一个方向到它的位于同一行或同一列的相邻 顶点，如此继续下去，经过闭回路的所有顶点和边，最后又回到开始的顶点， 但每一顶点和边在闭回路中只经过一次。,59,练习：下面的折线构成的封闭曲线连接的顶点变量哪些不是闭回路？,60,有关闭回路的一些重要定理,定理1: 设 是一个闭回路，则该闭回路中的变量所对应的系数列向量： 线性相关，具有下面的关系：,61,62,定理2: 若变量组 中有一个部分组构成闭回路，则该变量组对应的系数列向量线性相关。,定理3：r个变量 对应的系数列向量线性无关充要条件是该变量组不包含闭回路。,推论：m+n-1 个变量 构成基的充要条件是它不含闭回路。,63,以上的结果给出了运输问题的基的一个特征，这个结论非常重要，因为用它来判断m+n-1个变量是否构成基变量比直接判断这些变量所对应的系数列向量组是否线性无关要简单和直观。 另外，在以后还将看到利用基的这个特征可以导出求运输问题的初始基可行解的简便的方法。,64,第二节 表上作业法,65,一、表上作业法的基本思想,寻找初始基本可行解 给出基本可行解为最优解的判别准则 给出从目前基本可行解转移到新基可行解的方法,Review,66,67,运输问题作业表（产销平衡表）,68,Step4.重复2. 3，直到找到最优解为止。,二、表上作业法的步骤,Step1.找出初始基本可行解（在m*n产销平衡表上寻找初始调运方案，m+n-1个数字格），用最小元素法、西北角法、伏格尔法；,Step2.求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用闭回路或位势法计算；,Step3.改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；,69,1.求初始方案（寻找初始基可行解）,Step1. 选择一个xij，,对xij的选择采用不同的规则就形成各种不同的方法，比如每次总是在作业表剩余的格子中选择运价（或运距）最小者对应的xij，则构成最小元素法，若每次都选择左上角格子对应的xij就形成西北角法（也称左上角法）。,70,Step2. 调整产销剩余数量：xij值为从ai和bj中选择较小的值。 若ai=xij，则划去产地Ai所在的行，即该产地产量已全部运出无剩余，而销地Bj尚有需求缺口bj-ai；若bj = xij 则划去销地Bj所在的列，说明该销地需求已得到满足，而产地Ai尚有存余量ai-bj；,Step3.当作业表中所有的行或列均被划去，说明所有的产量均已运到各个销地，需求全部满足，xij的取值构成初始方案。否则，在作业表剩余的格子中选择下一个决策变量，返回步骤（2）。,71,可以证明：按照上述步骤产生的一组变量必定不构成闭回路，其取值非负，且变量个数是m+n-1个，因此构成运输问题的初始基本可行解。,72,从单位运价表中选最小元素，然后比较产量和销量，如果产销，则划去列，若销产，则划去行； 修改ai或bj的值； 再从划去一列和一行后的单位运价表中找最小元素，继续下去； 直到单位运价表的所有元素划去为止。,步 骤：,最小元素法,73,例1,74,3,1,4,6,3,3,75,西北角法,基本思想： 优先满足运输表中左上角（即西北角）空格的供销要求。,3,4,2,2,3,3,6,76,考虑到C11与C21之间的差额是82=6，先调运x21，再是x22，其次是x12，总运费 Z2=105+152+51=85Z1。,伏格尔法（Vogel 逼近法）,按最小元素法求得，总运费：Z1=108+52+151=105,77,伏格尔法（Vogel 逼近法）,最小元素法的缺点：为了节省一处的费用，有时造成在其它处要多花几倍的运费。 修正原则：若不能按最小运费就近供应，就选择次最小运费，差额越大，说明不能按最小运费调运时，运费增加越多。 每行（列）中次最小价格元素与最小价格元素的数值之差，称为该行（列）的行（列）罚数最大差额费用（罚数）。 对罚数最大处，采用最小运费调运。,在求一个可行解的过程中注意到包含在矩阵模型中的成本信息。它通过建立“罚数”来达到此目的。罚数表示对一方格不进行分配的可能的成本罚款。,78,步 骤：,Step1. 给定一个平衡的运输矩阵，分别计算行罚数和列罚数；,Step2. 确定具有最大罚数的行或列，然后在罚数所在行（或 列）中选择最小价格元素，将可能的最大单位数分配 给此方格，将相应的行（或列）的供应量和需求量减 去这个量，并划去完全满足的行（或列）；,Step3. 重复step1，step2，直到给出初始解为止。,79,2 5 1 3,6,2 1 3,2 1 2, 1 2, 2,Z=53+210+31 +1 8+64+ 35 = 85,80,2. 解的最优性检验,判别的方法是计算空格(非基变量)的检验数，因运输问题的目标函数是要求实现最小化，故当所有的检验数0时，为最优解。 常用两种求空格检验数的方法为：闭回路法和位势法。,其思路是令表中空格（即非基础解），对应的变量由0增加1单位，然后在保持产品供求平衡（即满足约束条件）情况下，使基本解参与变动，看其费用如何变化，若费用减少，则该非基变量可进入基，否则，加以排除，其思路与单纯形法一致。,81,（1）闭回路法 以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。 该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。 可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。,82,83,非基变量X12的检验数：,非基变量X21的检验数：,=（c12-c13）+（c23-c22） = - 20,=（c21-c11）+（c13-c23） = 15,84,对调运方案中每一空格按闭回路法求出检验数 若所有检验数大于等于零，则此方案为最优方案； 若存在检验数小于零，则需对此方案进行调整。,85,1,2,1,-1,10,12,不是最优解,经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。,86,（2）对偶变量法（位势法）,87,位势法原理,因为,所以,88,定理：任何基可行解对应的方程组都有解。,位势：方程组的任意一组解叫做位势。,89,对于运输问题的一个基可行解，用位势法得到的检验数是唯一的（位势可能不同）。,对基变量，反复利用公式,求出空格的检验数。,求出位势后，就可由公式,90,成本表Cij,u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令： u10,u10 v12 u2 1 v2 9 u3 5 v3 3 v4 10,(ui+vj),91,按ij=cij(ui+vj) 计算检验数，并以ij0 检验，或用(ui+vj) cij 0 检验。,cij,(ui+vj),表中还有负数，说明还未得到最优解，应继续调整。,ij,92,0,-1,-5,1,2,1,-1,10,12,10,2,9,3,93,3. 解的改进闭回路调整法,当 ij 0 时，调运方案需要改进,(-1),(+1),(-1),(+1),偶次顶点 “调整量”；奇次顶点 “ +调整量”,94,ij 0 得到最优解,95,4. 几点说明,（1） 换入变量的选择,若运输问题的某一基可行解有多个非基变量的检验数为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取ij 0中最小者对应的变量为换入变量。,（2） 无穷多最优解,当迭代到运输问题的最优解时，如果某个非基变量的检验数为0，说明该问题有无穷多最优解。以此格为调入格，作闭回路，经调整后得另一最优解。,96,97,98,（3） 退化,用表上作业法求解运输问题出现退化时，在相应的格中一定要填一个0，以表示此格为数字格。,当确定初始解时，若在（i，j）格填入某数字后，出现 ai = bj，这时在在运价表上相应的要划去一行和一列，需特别注意的是：要在划去的那行或那列的任一空格处填一个“0”，这样才能保证运输表上有m+n-1个数字格。,在用闭回路法调整时，当闭回路上两个和两个以上 顶点有相同的最小值时，这是只能选择一个作为调入格，调整后只能有一个空格，其余均要保留数“0”，以保证m+n1个基变量要求的需要。,99,100,第三节 运输问题的进一步讨论,101,一、产销不平衡的运输问题,增加虚拟销地,增加虚拟产地,产销平衡的运输问题,对应的运距（或运价） ？,102,1、产大于销：模型,先将原问题变成平衡问题，需假设一个销地Bn+1 ，该销地的总需要量为 ，即在运输表上增加一虚拟列,相应的单位运价为0。,解决方法,103,例题：,因为有：,所以是一个产大于销的运输问题。,104,表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180160=20的销地B5，Ci5=0，i=1，2，3，4。表的右边增添一列,这样可得新的运价表：,105,下表为计算结果。可看出：产地A4还有20个单位没有运出。,106,将原问题变成平衡问题，需假设一个产地Am+1 ，该产地的产量为 ，即在运输表上增加一虚拟行,相应的单位运价为0。,2、销大于产,解决方法,107,上例中，假定B1的需要量是20到60之间，B2的需要量是50到70，试求极小化问题的最优解。,3. 产销量不确定的运输问题,原则：不平衡化为平衡，不确定化为确定,108,先作如下分析： （1）总产量为180，B1，B4的最低需求量 20+50+35+45=150，这时属产大于销；,（2）B1，B4的最高需求是60+70+35+45=210，这时属销大于产,（3）虚设一个产地A5，产量是210180=30，A5的产量只能供应B1或B2。,（4）将B1与B2各分成两部分 的需求量是20， 的需求量是40， 的需求量分别是50与20，因此 必须由A1，A4供应， 可由 A1、A5供应。,（5）上述A5不能供应某需求地的运价用大M表示，A5到 其他 的运价为零。得到下表的产销平衡表。,109,得到这样的平衡表后，计算得到最优方案表。,110,表中：x131=0是基变量,说明这组解是退化基本可行解,空格处的变量是非基变量。B1，B2，B3，B4实际收到产品数量分别是50，50，35和45个单位。,111,第四节 应用问题举例,112,有三个产地A1，A2，A3和三个销地B1，B2，B3，各产地至销地的单位运价见下表，各销地的需求量分别为10，4，6个单位。由于客观条件的限制和销售需要，产地A1至少要发出6个单位的产品，最多只能生产11个单位； A1必须发出7个单位； A3至少要发出4个单位。,解：当 a1= 6，a2=7 时，,例6（p100),113,总产量总销量,114,115,116,117,118,119,120,121,在下列不平衡运输问题中，已知三个收点的需求量一旦不能满足，就要承担缺货损失费。单位物资的缺货损失费分别为4、3 和 7,试建立运输模型。,例8,122,解：增加虚拟产地 A3,123,某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。已知(1)各条航线的起点、终点城市及每天航班数（表1）;(2)各城市间的航行时间（表2）；（3）所有航线都使用同一种船只，船只每次装卸的时间均需1天，则该航运公司至少应配备多少条船，才能满足所有航线的要求。,例9（p101),表1,124,解： 该公司所需配备船只分两部分： （1）载货航程需要的周转船只数,载货需要 57+10+9+15=91 条船,表2,ED BC AF DB,125,（2）各港口调度所需船只数,港口城市 每天到达 每天需求 余缺数 A 0 1 -1 B 1 2 -1 C 2 0 2 D 3 1 2 E 0 3 -3 F 1 0 1,由每天到达某一港口的船只数量与它所需发出的船只数量不相等而产生。各港口城市每天到达船只、需求船只数量及其差额见下表。,终点城市航班数量决定,起点城市航班数量决定,126,2,1,1,1,为使配备船只数最少，应做到周转空船数为最少。建立运输问题。,最少需周转空船数：25+114+113+13=40,故至少应配备 91+40=131 条船,127,Thanks,128,
展开阅读全文