运筹学第七周灵敏度分析运输问题ppt课件.pptx

第二章对偶理论与灵敏度分析,1,本章内容,对偶理论是线性规划最重要的基础理论之一是进行经济分析的重要工具,2,一般形式单纯形法计算的矩阵描述,设线性规划问题:目标函数约束条件AXb;非负条件X0,线性规划问题的约束条件加入松弛变量以后，得到标准型：,maxz=CX+0Xs,AX+IXs=b;X，Xs0,maxz=CX,3,矩阵A可以分块记为A=B，N相应地，向量X和C可以记为,XB=B-1bB-1NXNB-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.线性规划灵敏度分析的内容,maxz=CX,AX=bX0,1.最优解保持不变，即基变量和它们的取值没有变化2.基变量保持不变，但它们的值改变了3.基解完全变了,对解的影响主要有:,可行性B1b0最优性CNCBB1N0,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=c2505=52c205/2c25,最优解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）i产，则划去行；修改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,2513,6,213,212,12,2,Z=53+210+31+18+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=1u2+v3=2u3+v2=4u1+v4=10u1+v3=3u3+v4=5令：u10,u10v12u21v29u35v33v410,(ui+vj),91,按ij=cij(ui+vj)计算检验数，并以ij0检验，或用(ui+vj)cij0检验。,cij,(ui+vj),表中还有负数，说明还未得到最优解，应继续调整。,ij,92,0,-1,-5,1,2,1,-1,10,12,10,2,9,3,93,3.解的改进闭回路调整法,当ij0时，调运方案需要改进,(-1),(+1),(-1),(+1),偶次顶点“调整量”；奇次顶点“+调整量”,94,ij0得到最优解,95,4.几点说明,（1）换入变量的选择,若运输问题的某一基可行解有多个非基变量的检验数为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取ij总销量,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,EDBCAFDB,125,（2）各港口调度所需船只数,港口城市每天到达