1、第二章 对偶理论与灵敏度分析线性规划问题的引出|线性规划问题的概念和模型|线性规划的标准型|线性规划模型的标准化 本章内容p 对偶理论是线对偶理论是线性规划性规划最重要最重要的基的基础理论之一础理论之一p 是进行是进行经济分经济分析的重要工具析的重要工具一般形式单纯形法计算的矩阵描述设线性规划问题设线性规划问题:目标函数目标函数 约束条件约束条件 AXb;非非负条件负条件 X0线性规划线性规划问题的约束条件加入松弛变量以后，得到标准型：问题的约束条件加入松弛变量以后，得到标准型：m max z=CX+0XsAX+IXs=b;X，X s0mmI 1001m max z=CX矩阵矩阵A A可以分块
2、记为可以分块记为A=A=B B，N N 相应地，向量相应地，向量X X和和C C可以记为可以记为 CCNBNB,CXXXXB=B-1b B-1NXN B-1Xs 对于一个确定的基对于一个确定的基B B，目标函数，目标函数z z可以写成可以写成NNBBNBNBXCXCXX.C,CXCz目标函数目标函数z z用非基变量表出的形式用非基变量表出的形式S1BN1BN1BNNS1N11BXBCN)XBC(CbBCXC)XBNXBb(BCz0 x,x,xbIxNxBxs.t.0 xxCxCmaxzsNBsNBsNNBB0,0maxSNBSNBSNNBBXXXbEXNXBXXXCXCZCBCN00XBXNX
3、Sb0 XSBNIb检验数检验数CBCN00XBXNXSbCB XBIB1NB1B1b检验数检验数0CNCBB1NCBB1CBB1b初始单纯形表 迭代n 步之后的单纯形表S1BN1BN1BNNS1N11BXBCN)XBC(CbBCXC)XBNXBb(BCz线性规划问题的引出|线性规划问题的概念和模型|线性规划的标准型|线性规划模型的标准化 影子价格总结：3 3.影子价格影子价格是在系统达到最优时对系统资源的是在系统达到最优时对系统资源的一种一种最优估价，并假设第最优估价，并假设第i i种资源增加一个单位种资源增加一个单位时最时最优基没改变。优基没改变。4.4.影子价格可以告诉管理人员，增加哪一
4、种资源影子价格可以告诉管理人员，增加哪一种资源对增加对增加经济效益有利，经济效益有利，帮助企业调节生产规模；帮助企业调节生产规模；5.5.影子价格可以告诉管理人员，花多大的代价来影子价格可以告诉管理人员，花多大的代价来增加资源增加资源才是合算的；才是合算的；6.6.影子价格可以帮助管理人员进行生产要素对产出贡献的分解；影子价格可以帮助管理人员进行生产要素对产出贡献的分解；7.7.影子价格可以告诉管理人员如何考虑新产品的价格。影子价格可以告诉管理人员如何考虑新产品的价格。1.1.影子价格影子价格的大小客观地反映了资源在系统内的大小客观地反映了资源在系统内的稀缺程度。的稀缺程度。2.2.影子价格影
5、子价格的取值与系统的状态有关，系统中的取值与系统的状态有关，系统中任一状态任一状态的改变都会引起的改变都会引起影子价格的影子价格的变化。变化。对偶单纯形法是应用对偶原理求解原始线性规划的一种方法在原始问题的单纯形表格上进行对偶处理。注意：不是解对偶问题的单纯形法！什么是对偶单纯形法？1.使用条件：检验数全部0；右端向量列至少一个元素 0；2.实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换每一次迭代过程中取出基变量中的一个右端负分量作为换出变量去替换某个非基变量（作为换入变量），使原始问题的非可行解向可行解靠近。对偶单纯形法的实施3.计算步骤：建立初始单纯形表，计算检验数行。端向量
6、列0已得最优解；右端向量至少一个元素0,转下步;右端向量列0原始单纯形法；至少一个元素0,另外处理 检验数全部0（非基变量检验数0 基变换：基变换：先确定先确定换出变量右端向量列中的负元素（一般选最小的负元素）对应的对应的基变量出基；基变量出基；出出基基，则则选选lliiixbBbBbB,)(0)()(min111 相应的行相应的行为主元行为主元行。然后然后确定换入变量原则是：在保持对偶可原则是：在保持对偶可行的前提下，减少原始问题的不可行性。行的前提下，减少原始问题的不可行性。如果如果 0minlkkkljljjjjazcaazc （最小比值原则）（最小比值原则），则选，则选 为换入变量，相
7、应的为换入变量，相应的列为列为，主元行和主元列交叉处的元素，主元行和主元列交叉处的元素 为为主元素。主元素。kxlka 按按主元素进行换基变换（初等行变（初等行变换），换），将主元素变成将主元素变成1，主元列变成单位向量，主元列变成单位向量，得到新的单纯形表。得到新的单纯形表。最优解判别法则：右端向量满足非负约束第五节 灵敏度分析 以前讨论线性规划问题时，假定ij，bi,cj都是常数，但实际上这些系数往往是估计值或预测值。如市场条件一变，cj值就会变化；ij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。灵敏度分析：指对系统或事物因周围条件变化显示出来的敏感程度
8、的分析。线性规划模型的灵敏性分析：研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程，称为线性规划的灵敏度分析。一、灵敏度分析的含义和内容p 目标函数的价值系数变化p 约束方程右端向量变化p 约束方程组系数阵变化p 决策变量或约束条件变化2.线性规划灵敏度分析的内容m max z=CXAX=bX01.最优解保持不变，即基变量和它们的取值没有变化2.基变量保持不变，但它们的值改变了3.基解完全变了对解的影响主要有:可行性 B1b 0最优性CNCBB1N 0 LP灵敏度分析最终回答：计算量少，充分利用到原最优的单纯形表结果 1.这些系数在什么范围内变化时，原先求出的线性规划问题
9、的最优解或最优基不变。2.如果系数的变化超出了上述范围，如何用最简便的方法求出新的最优解。三、灵敏度分析的步骤1.将参数的改变通过计算反映到最终单纯形表上2.检查原问题和对偶问题是否还是可行解3.按照下表所列情况分别进行讨论原问题对偶问题结论或继续计算方法可行解可行解问题的最优解保持不变可行解非可行解用单纯形法继续求解非可行解可行解对对偶单纯形法求解非可行解非可行解引用人工变量，构造基，重新计算1.价值系数cj 的变化分析四、灵敏度分析的具体内容XBXNXSbCB XBIB1NB1B1b检验数检验数0CNCBB1NCBB1CBB1bCBCN00XBXNXSb0 XSBNIb检验数检验数CBCN
10、00初始单纯形表最优单纯形表 当cj 变化时，如能保持 ，则当前解仍为最优解，否则可用单纯形法继续迭代求出新的最优解。0 N 将cj 看作待定参数，令 01 NBCCBNN 解这n-m个不等式，可算出保持最优解不变时cj的变化范围。（1）当cj 是非基变量的价值系数它的变化只影响 一个检验数。j（2）当cj 是基变量的价值系数它的变化将影响所有非基变量的检验数，NBCCBNN1 例16：某企业利用三种资源生产两种产品的最优计划问题归结为下列线性规划：0,45 802903 45 max2121212121xxxxxxxxxxZ已知最优表如下：（1）确定x2的系数c2的变化范围，使原最优解保持最
11、优；（2）若c2=6，求新的最优计划。cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-3cj5c2 000CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2 x2 10 010-12000c2-55-2c24 =c25 05 =52c2 0 5/2 c2 5最优解X*=（35，10，25，0，0）保持不变。最优单纯形表Cj56000CBXBbx1x2x3x4x50 x3250012-55x1351001-16 x2 10 010-12j 0001-70 x425/2001/21-5/
12、25x145/210-1/203/26 x2 45/2 011/20-1/2j00-1/20-9/2x1*=45/2，x2*=45/2，x4*=25/2，x3*=x5*=0，z*=495/22.右端常数bi(资源系数)的变化分析XBXNXSbCB XBIB1NB1B1b检验数检验数0CNCBB1NCBB1CBB1bCBCN00XBXNXSb0 XSBNIb检验数检验数CBCN00初始单纯形表最优单纯形表当bi发生变化时，将影响所有基变量的取值 保持B-1b0,当前的基仍为最优基，最优解的结构不变（取值改变）；（B-1b）i0,当前基为非可行基，但是仍保持为对偶可行基,可用对偶单纯形法求出新的最
13、优解；如何求出保持最优基不变的bi 的范围?把bi看作待定参数，令B-1b0，求解该不等式组即可。例17：对于上例中的线性规划作下列分析：（1）b3在什么范围内变化，原最优基不变？（2）若b3=55，求出新的最优解。0,45 802903 45Z max2121212121xxxxxxxxxxcj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-32 1-01 1 05-2 1最优基：B=（P3，P1，P2）B1=最优单纯形表的A中松弛变量的系数最优单纯形表（1）2 1-01 1 05-2 1 3b8090 333b2
14、80b805b -250 3b8090B1=0 解得40b350，即当b340，50 时，最优基B 不变z*=5（80b3）+4（80+2b3）=80+3b3 333b280b805b-250 *2*1*3xxx=（2）当当 b3=55 时时 333b280b805b-250 30 25 25=x2 x1x50-11/5-3/500j0-1/52/51020 4 03/5-1/5013051-2/5-1/50050-32-1-5x50-1000j-101030 x2 4 100125x152100-25x30 x4x3x2x1bXBCB0045CjbBXB1=3.增加一个新决策变量xj 的变化
15、分析资源的合理利用问题：新问题：如开发出一种新产品，已知其有关工艺参数（或消耗的资源量）和单位产品利润，设该种产品的产量为xn+1，则cn+1和Pn+1已知，需要进行“是否投产”的决策。（1）增加1个新变量：相当于系数阵A增加1列112211maxnnnnxcxcxcxcz mnmnnmnmmnnnnnnnnbxaxaxaxabxaxaxaxabxaxaxaxa11221121122222121111112121110,121nnxxxx对新问题：X XB B X XN N检验行检验行I I B B-1-1N NB B-1-1b bX XB B0 0 C CN N-C-CB BB B-1-1N
16、 N-C-CB BB B-1-1b b最优单纯形表1nx111nBnPBCc11nPB，此时此时01 NBCCBN01 bB：若若0111 nBnPBCc此表达到最优为为非非基基变变量量1 nx：若若0111 nBnPBCc此表未达到最优为为入入基基变变量量，1 nx用单纯形法迭代至找到最优解0*1 nx新新产产品品不不投投产产例18：（续例）设企业研制了一种新产品，对三种资源的消耗系数列向量以P6表示，P6=。(1)问它的价值系数c6符合什么条件才必须安排它的生产？(2)设c6=3，新的最优生产计划是什么？2/112/36P 2 1-01 1 05-2 1 2/112/3 02/11=B1P
17、6=解：解：(1)6=c6CBB1P6=c6（0，5，4）=c65/2 02/11 6 60,销，则划去列，若销产，则划去行；p 修改ai或bj的值；p 再从划去一列和一行后的单位运价表中找最小元素，继续下去；p 直到单位运价表的所有元素划去为止。步 骤：就近供应。按单位运价的大小决定供应的先后，优先满足单位运价最小者的供销要求。基本思想：最小元素法单位单位 销地销地 运价运价 产地产地产量产量311310719284741059销量销量36564321 BBBB321AAA例例13 3124433 436供供销销 B1 B2 B3 B4 产量产量A1A2A3销量销量3113101794210
18、853 6 5 6 74911865346211310334 Z353366西北角法基本思想：优先满足运输表中左上角（即西北角）空格的供销要求。3 34142222 433566供供销销 B1 B2 B3 B4 产量产量A1A2A3销量销量3113101794210853 6 5 6 749663213556103229211433 Z10515108520211515C10155108520211515C 考虑考虑到到C11与与C21之间的差额是之间的差额是82=6，先调运先调运x21，再是，再是x22，其次是，其次是x12，总总运费运费Z2=105+152+51=85Z1。伏格尔法（Vog
19、el 逼近法）按按最小元素法求得，总最小元素法求得，总运费：运费：Z1=108+52+151=105伏格尔法（Vogel 逼近法）最小元素法的缺点：为了节省一处的费用，有时造成在其它处要多花几倍的运费。修正原则：若不能按最小运费就近供应，就选择次最小运费，差额越大，说明不能按最小运费调运时，运费增加越多。每行（列）中次最小价格元素与最小价格元素的数值之差，称为该行（列）的行（列）罚数最大差额费用（罚数）。对罚数最大处，采用最小运费调运。在求一个可行解的过程中注意到包含在矩阵模型中在求一个可行解的过程中注意到包含在矩阵模型中的成本信息。它通过建立的成本信息。它通过建立“罚数罚数”来达到此目的。来
20、达到此目的。罚数表示对一方格不进行分配的可能的成本罚款。罚数表示对一方格不进行分配的可能的成本罚款。步 骤：Step1.给定一个平衡的运输矩阵，分别计算行罚数和列罚数；Step2.确定具有最大罚数的行或列，然后在罚数所在行（或 列）中选择最小价格元素，将可能的最大单位数分配 给此方格，将相应的行（或列）的供应量和需求量减 去这个量，并划去完全满足的行（或列）；Step3.重复step1，step2，直到给出初始解为止。例例见下页！见下页！0 11供供销销 B1 B2 B3 B4 产量产量 行罚数行罚数 A1A2A3销量销量3113101794210853 6 5 6 20 749列列 罚罚 数
21、数 2 5 1 3 60 12 2 1 3 13012 1 232376 1 2 00 2331152267542Z=5 3+2 10+3 1+1 8+6 4+3 5 =852.解的最优性检验n 判别的方法是计算空格(非基变量)的检验数，因运输问题的目标函数是要求实现最小化，故当所有的检验数0时，为最优解。n 常用两种求空格检验数的方法为：闭回路法和位势法。其思路是令表中空格（即非基础解），对应的变量由0增加1单位，然后在保持产品供求平衡（即满足约束条件）情况下，使基本解参与变动，看其费用如何变化，若费用减少，则该非基变量可进入基，否则，加以排除，其思路与单纯形法一致。（1）闭回路法l 以确定
22、了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。l 该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。l 可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100100150非基变量X12的检验数：非基变量X21的检验数：=（c12-c13）+（c23-c22）=-201
23、2=（c21-c11）+（c13-c23）=1521ij=（闭回路上奇数次顶点运距或运价之和）-（闭回路上偶数次顶点运距或运价之和）对调运方案中每一空格按闭回路法求出检验数 若所有检验数大于等于零，则此方案为最优方案；若存在检验数小于零，则需对此方案进行调整。供供销销 B1 B2 B3 B4 产量产量A1A2A3销量销量3113101794210853 6 5 6 749 364133112332123131111 cccc 124510113234141212 cccc 21451032932341413232222 cccccc 11231082313142424 cccc-1105103
24、21734141323213131 cccccc 10123105101314343333 cccc 12不是最优解不是最优解此种此种颜色颜色代表代表检验检验数数经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。（2 2）对偶变量法（位势法）对偶变量法（位势法）位势法原理位势法原理因为所以定理：任何基可行解对应的方程组都有解。cvucvucvunmnmnmnmjijijijijiji111122221111 运输问题的基可行解 在这一组基变量下，建立求解ui，vj的方程组：TjijijinmnmxxxX),(112211 位势：方程组的任意一组解叫做
25、位势。对于运输问题的一个基可行解对于运输问题的一个基可行解，用位势法得用位势法得到的检验数是唯一的到的检验数是唯一的（位势可能不同位势可能不同）。对基变量对基变量，反复利用公式反复利用公式 jijiiijjvcuucv jiijijvuc 求出空格的检验数求出空格的检验数。求出位势后求出位势后，就可由公式就可由公式B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表成本表CijB1B2B3B4A1293100A218291A33425529310 u2+v1=1 u2+v3=2 u3+v2=4 u1+v4=10 u1+v3=3 u3+v4=5 令：令：u10u10 v1
26、2u2 1 v2 9u3 5 v3 3 v4 10(ui+vj)按ij=cij(ui+vj)计算检验数，并以ij0 检验，或用(ui+vj)cij 0 检验。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A334-25(ui+vj)B1B2B3B4A11200A20101A3100120表中还有负数，说明还未得到最优解，应继续调整。ij0-1-5121-11012此种此种颜色颜色代表代表检验检验数数10311310179421085供供销销 B1 B2 B3 B4 uiA1A2A3 Vj 364133此种此种颜色颜色代表代表初始初始解
27、解2933.3.解的改进解的改进闭回路调整法闭回路调整法当 ij 0 时，调运方案需要改进00minjiijijo 点点的的最最小小值值 m mi in n 闭闭回回路路偶偶数数顶顶调整量121-11012311310179421085供供销销 B1 B2 B3 B4 aiA1A2A3 bj 3641337493 6 5 6(-1)(+1)(-1)(+1)偶次顶点偶次顶点“调整量调整量”；奇次顶点；奇次顶点“+调整量调整量”供供销销 B1 B2 B3 B4 uiA1A2A3 Vj3113101794210853 9 3 10 0-2-5 36 5123022 1 912 ij 0 得到最优解得
28、到最优解4.4.几点说明几点说明（1 1）换入变量的选择换入变量的选择 若运输问题的某一基可行解有多个非基变量的检验数为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取 ij 总销量总销量供供销销 B1 B2 B3 B4 产量产量A1A1A2销量销量2 43M21453 60M10 4 6 5 6 5 7 332244M0A3A3 4 3 在下列不平衡运输问题中，已知三个收点的需求量一旦不能满足，就要承担缺货损失费。单位物资的缺货损失费分别为4、3 和 7,试建立运输模型。供供销销 B1 B2 B3 产量产量A1A2销量销量4 52683 8 7 14 10
29、15例例8 8供供销销 B1 B2 B3 产量产量A1A2A3销量销量4 5264833 7 8 7 14 1015 4解：解：增加虚拟产地增加虚拟产地 A3航线 起点城市 终点城市 每天航班数 1 E D 3 2 B C 2 3 A F 1 4 D B 1 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。已知(1)各条航线的起点、终点城市及每天航班数（表1）;(2)各城市间的航行时间（表2）；（3）所有航线都使用同一种船只，船只每次装卸的时间均需1天，则该航运公司至少应配备多少条船，才能满足所有航线的要求。例例9 9（p101)p101)表1 A B C D E
30、 F A 0 1 2 14 7 7 B 1 0 3 13 8 8 C 2 3 0 15 5 5 D 14 13 15 0 17 20 E 7 8 5 17 0 3 F 7 8 5 20 3 0到到从从解：解：该公司所需配备船只分两部分：该公司所需配备船只分两部分：（1 1）载货航程需要的周转船只数）载货航程需要的周转船只数 航线航线 装货天数装货天数 航程天数航程天数 卸货天数卸货天数 小计小计 航班数航班数 需周转船只数需周转船只数 1 1 17 1 19 3 57 2 1 3 1 5 2 10 3 1 7 1 9 1 9 4 1 13 1 15 1 15载货需要载货需要 57+10+9+1
31、5=91 条船条船表表2 2EDBCAFDB（2 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 由每天到达某一港口的船只数量与它所需由每天到达某一港口的船只数量与它所需发出的船只数量不相等而产生。各港口城市每发出的船只数量不相等而产生。各港口城市每天到达船只、需求船只数量及其差额见下表。天到达船只、需求船只数量及其差额见下表。终点城市航班终点城市航班数量决定数量决定起点城市航起点城市航班数量决定班数量决定到到 A B E 每天多余船只每天多余船只CDF每天缺少船只每天缺少船只2 3514713817 3 1 1 3 221从从2111为使配备船只数最少，应做到周转空船数为最少。建立为使配备船只数最少，应做到周转空船数为最少。建立运输问题。运输问题。最少需周转空船数：最少需周转空船数：2 5+1 14+1 13+1 3=40故至少应配备故至少应配备 91+40=131 条船条船线性规划问题的引出|线性规划问题的概念和模型|线性规划的标准型|线性规划模型的标准化 Thanks
