《【精品】对偶规划与灵敏度分析精品ppt课件.ppt》由会员分享，可在线阅读，更多相关《【精品】对偶规划与灵敏度分析精品ppt课件.ppt（108页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、对偶规划与灵敏度分析 对偶理论对偶理论是线性规划的重要内容之一。对应是线性规划的重要内容之一。对应于每个线性规划问题都伴生一个相应的线性规划于每个线性规划问题都伴生一个相应的线性规划问题。问题。原问题和对偶问题紧密关联，它们不但有原问题和对偶问题紧密关联，它们不但有相同相同的数据集合的数据集合，相同的最优目标函数值相同的最优目标函数值，而且在，而且在求得求得一个线性规划的最优解的同时，也同步得到对偶线一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解性规划的最优解。由对偶问题引伸出来的对偶解还有着重要的由对偶问题引伸出来的对偶解还有着重要的经经济意义济意义，是研究经济学的重要概念和工具
2、之一。，是研究经济学的重要概念和工具之一。2n对偶问题的提出对偶问题的提出例例1 1、某工厂生产甲、某工厂生产甲,乙两种产品，这两种产品需要在乙两种产品，这两种产品需要在A,B,CA,B,C三种不同三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们设备上加工。每种甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划，即甲台时数均列于表。试问如何安排生产计划，即甲,乙两种产品各生产乙两种产品各生产多少吨，可使该厂所获得利润达到最大。多少吨，
3、可使该厂所获得利润达到最大。p对偶线性规划对偶线性规划设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 3 假设计划期内甲乙两种产品各生产假设计划期内甲乙两种产品各生产 吨，吨，设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 用图解法或单纯形法可求得最优解用图解
4、法或单纯形法可求得最优解 (元元)即在计划期内甲产品生产即在计划期内甲产品生产 吨，乙产品生产吨，乙产品生产8 8吨，可以使总利润达吨，可以使总利润达到最大，为到最大，为 元元。4 现在从另一个角度来考虑该工厂的生产问题现在从另一个角度来考虑该工厂的生产问题:假设该厂的决策者打算不再自己生产甲假设该厂的决策者打算不再自己生产甲,乙产品，而是把各乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。该如何确定各种设备的租价。设设 分别为设备分别为设备A A，B B，C C每台时的租价，每台时的租价
5、，约束条件：约束条件：把设备租出去所获得的租金不应低于利用这些设备自把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润行生产所获得的利润目标函数：所获租金总额尽量少目标函数：所获租金总额尽量少5可以得到另一个线性规划可以得到另一个线性规划：称之为原线性规划问题的对偶问题称之为原线性规划问题的对偶问题，n对偶线性规划对偶线性规划考虑如下具有不等式约束的线性规划问题考虑如下具有不等式约束的线性规划问题891011若令若令线性规划标准型线性规划标准型的对偶规划为：的对偶规划为：n线性规划问题标准型的对偶问题线性规划问题标准型的对偶问题考虑一个标准形式的线性规划问题考虑一个标准形式的线性
6、规划问题 由于任何一个等式约束都可以用两个不等式约束等价地表示，所由于任何一个等式约束都可以用两个不等式约束等价地表示，所以标准形线性规划问题可等价表示为：以标准形线性规划问题可等价表示为：它的对偶规划为：它的对偶规划为：12n对偶线性规划的求法对偶线性规划的求法从任何一个线性规划出发，都可以求出相应的对偶规划，在从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解过程中，通常不通过求标准型，而是利用如下反映原始实际求解过程中，通常不通过求标准型，而是利用如下反映原始问题与对偶问题对应关系的原始问题与对偶问题对应关系的原始对偶表：对偶表：目标函数变量系数目标函数变量系数约束条件右端项约
7、束条件右端项 约束条件右端项约束条件右端项目标函数变量系数目标函数变量系数 约束条件约束条件个数：个数：n n个个 变量变量个数：个数：n n个个 变量变量个数：个数：m m个个 约束条件约束条件个数：个数：m m个个 目标函数目标函数minW minW 目标函数目标函数maxZ maxZ 对偶问题（或原问题）对偶问题（或原问题）原问题（或对偶问题）原问题（或对偶问题）13解：对偶规划：解：对偶规划：例例2 2 写出下列线性规划的对偶问题写出下列线性规划的对偶问题14例例3 3 写出下列线性规划的对偶问题写出下列线性规划的对偶问题解：上述问题的对偶规划：解：上述问题的对偶规划：15本节讨论几条
8、重要的对偶定理，这些定理揭示了原始问题的解和对本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。偶问题的解之间的基本关系。定理定理1 1：（：（对称性对称性）对偶问题的对偶是原问题。）对偶问题的对偶是原问题。证明：设原问题为对偶问题为证明：设原问题为对偶问题为改写对偶问题为对偶问题的对偶为改写对偶问题为对偶问题的对偶为p对偶定理对偶定理16 定理定理2 2：弱对偶定理弱对偶定理 若是原（极小化）问题的可行解，是对偶（极大化）问题的若是原（极小化）问题的可行解，是对偶（极大化）问题的可行解，那么可行解，那么 证明：因为是对偶问题的可行解，所以满足约束条件证明：因
9、为是对偶问题的可行解，所以满足约束条件 又因为是原问题的可行解，可得，又因为是原问题的可行解，可得，,所以所以 。注：原（极小化）问题的最优目标函数值以对偶问题任一注：原（极小化）问题的最优目标函数值以对偶问题任一可行解的目标函数值为下界。可行解的目标函数值为下界。对偶（极大化）问题的最优目标函数值以原问题任一对偶（极大化）问题的最优目标函数值以原问题任一可行解的目标函数值为上界。可行解的目标函数值为上界。推论推论1 1：如果原问题没有下界（即：如果原问题没有下界（即minZminZ），则对偶问），则对偶问题不可行。题不可行。如果对偶问题没有上界（即如果对偶问题没有上界（即maxWmaxW），
10、则原问题），则原问题不可行。不可行。若原问题与对偶问题之一无界，则另一个无可行解。若原问题与对偶问题之一无界，则另一个无可行解。17证明：由弱对偶定理，对于原始问题的证明：由弱对偶定理，对于原始问题的所有可行解所有可行解，都有都有 因此是原问题的因此是原问题的最优解最优解。同理，对于对偶问题的同理，对于对偶问题的所有可行解所有可行解 ，都有，都有 所以所以 是对偶问题的是对偶问题的最优解最优解。推论推论2 2：最优性定理最优性定理若若是是原原问问题题的的可可行行解解，是是对对偶偶问问题题的的可可行行解解，而而且两者的目标函数值相等，即，则和且两者的目标函数值相等，即，则和分别是原问题和对偶问题
11、的最优解。分别是原问题和对偶问题的最优解。18证明：设是原问题证明：设是原问题(min)(min)的最优解，则对应的基必有的最优解，则对应的基必有。若定义，则若定义，则 ，因此为对偶问题的可行解，而且因此为对偶问题的可行解，而且 ，由最优性定理，是对偶问题的最优解。由最优性定理，是对偶问题的最优解。定理定理3:3:强对偶定理强对偶定理 如果原问题（如果原问题（min)min)与对偶问题与对偶问题(max)(max)之一有最优解，之一有最优解，那么另一个也有最优解，而且目标函数值那么另一个也有最优解，而且目标函数值相等相等。19证证明明：设设满满足足原原问问题题(min)(min)的的最最优优性
12、性条条件件，则则对对应应的的基必有基必有。若定义若定义 ，则，则 ，因此为对偶问题的基本可行解。因此为对偶问题的基本可行解。定理定理4 4：设满足原问题设满足原问题(min)的的最优性条件最优性条件的一个的一个基本解基本解，则其对应的线性规划问题则其对应的线性规划问题(min)(min)的的检验数检验数对应对应对偶问题对偶问题的一的一个个基本可行解基本可行解。20原问题与对偶问题可能出现的情况（1）两者都有最优解，且最优值相等；（2）一个有可行解，但无界，则另一个无可行解；（3）两者都无可行解。21定理定理5 5：互补松弛定理互补松弛定理如果如果 分别是原问题分别是原问题(min)(min)和
13、对偶问题（和对偶问题（max)max)的可行解，那的可行解，那么么 和和 为最优解的充要条件是为最优解的充要条件是 通常称通常称 为互补松弛条件。为互补松弛条件。证明：充分性证明：充分性必要性必要性22例例5 5、已知线性规划问题、已知线性规划问题:其对偶问题的最优解。其对偶问题的最优解。试用试用互补松弛定理互补松弛定理找出原问题的最优解。找出原问题的最优解。解：原问题的对偶问题为：解：原问题的对偶问题为：由对偶问题最优解可知，由对偶问题最优解可知，由互补松弛定理，由互补松弛定理，解方程组解方程组 所以原问题最优解所以原问题最优解23 假设计划期内甲乙两种产品各生产假设计划期内甲乙两种产品各生
14、产 吨，吨，设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 用图解法或单纯形法可求得最优解用图解法或单纯形法可求得最优解 (元元)即在计划期内甲产品生产即在计划期内甲产品生产 吨，乙产品生产吨，乙产品生产8 8吨，可以使总利润达吨，可以使总利润达到最大，为到最大，为 元元。例：例：对偶最优解的经济解释对偶最优解的经济解释影子价格影子价格 2425由由强强对对偶偶定定理理可可知知，如如果果原原问问题题有有最最优优解解，那那么么对
15、对偶偶问题也有最优解，而且它们的目标函数值相等，即有：问题也有最优解，而且它们的目标函数值相等，即有：其其中中是是线线性性规规划划原原问问题题约约束束条条件件的的右右端端数据向量，它代表各种资源的拥有量。数据向量，它代表各种资源的拥有量。为为对对偶偶问问题题最最优优解解，它它代代表表在在资资源源最最优优利利用用条条件件下下对对各各种种单单位位资资源源的的估估价价，这这种种估估计计不不是是资资源源的的市市场场价价格格，而而是是根根据据资资源源在在生生产产中中所所作作出出的的贡贡献献（如如创创造造利利润润，产产值值等等）而而作作出出估估价价，为为区区别别起起见见，称称之之为为影影子子价价格格(sh
16、adow(shadow price)price)。26影影子子价价格格的的大大小小客客观观地地反反映映了了各各种种不不同同资资源源在在系系统统内内的的稀稀缺缺程程度度。如如果果第第i i种种资资源源供供大大于于求求，即即在在达达到到最最优优解解时时，该该种种资资源源没没有有用用完完，或或松松弛弛变变量量，由由互互补补松松弛弛定定理理，在在对对偶偶最最优优解解中中，第第i i种种资资源源的的影影子子价价格格。反反之之如如果果第第i i种种资资源源的的影影子子价价格格，那那么么由由互互补补松松弛弛定定理理，原原问问题题的的第第i i个个约约束束为为严严格格等等式式，即即，这这表表明明第第i i种种
17、资源已经用完资源已经用完，成为稀缺资源。，成为稀缺资源。资资源源的的影影子子价价格格同同时时也也是是一一种种机机会会成成本本，在在市市场场经经济济的的条条件件下下，当当某某种种资资源源的的市市场场价价格格低低于于影影子子价价格格时时，企企业业应应买买进进这这种种资资源源用用于于扩扩大大生生产产；相相反反当当某某种种资资源源的的市市场场价价格格高高于于影影子子价价格格时时，企企业业应应卖卖出出这这种种资资源源。随随着着资资源源的的买买进进卖卖出出，企企业业资资源源的的影影子子价价格格也也将将随随之之发发生生变变化化，一一直到直到影子价格与市场价格保持同等水平影子价格与市场价格保持同等水平时，才处
18、于时，才处于平衡状态平衡状态。27设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 例：例：对偶最优解对偶最优解其中为其中为设备设备A A的影子价格的影子价格，在资源最优利用的条件下，设备在资源最优利用的条件下，设备A A每每增加增加一个单位台时一个单位台时，可以使，可以使总利润增加总利润增加元。元。若设备可供台时数，则若设备可供台时数，则2829p对偶单纯形法对偶单纯形法单单纯纯形形法法是是以以保保持持原原问问题题可可行行为为
19、条条件件，即即不不论论进进行行怎怎样样的的基基变换，常数列必须保持非负。变换，常数列必须保持非负。利利用用对对偶偶问问题题的的对对称称性性，我我们们从从另另一一个个角角度度来来考考虑虑求求解解原原问问题题最最优优解解的的方方法法，这这种种方方法法以以保保持持对对偶偶问问题题可可行行为为条条件件，即即不不论论进进行行何何种种基基变变换换，必必须须保保持持所所有有的的检检验验数数非非负负，同同时时取取消消原原问问题题必必须须可可行行的的要要求求，即即取取消消常常数数列列的的非非负负限限制制，通通过过基基变变换换使使原原问问题题在在非非可可行行解解的的基基础础上上逐逐步步转转换换成成基基本本可可行行
20、解解，一一旦旦原原问问题题的的基基本本解解可可行行，则则该该基基本本可可行行解解也也就就是是最最优优解解，这这就就是是对对偶偶单单纯纯形形法法的基本思想。的基本思想。单纯形法：单纯形法：可行性可行性最优性最优性对偶单纯形法：对偶单纯形法：最优性最优性可行性可行性30例例 求解下列线性规划 min z=5x1+2x2+6x32x1+4x2+8x3 244x1+x2+4x38x1、x2，x30解解 min z=5x1+2x2+6x32x1+4x2+8x3-x4 =244x1+x2+4x3 -x5=8x1、x2，x3，x4，x50 min z=5x1+2x2+6x32x1 4x2 8x3+x4 =2
21、44x1 x2 4x3 +x5=8x1、x2，x3，x4，x5031Cj52600bCBXBx1x2x3x4x50 x4-2-4-810-240 x5-4-1-401-85260005/-22/-46/-80032对偶单纯形法基变换的次序和一般单纯形法不同：对偶单纯形法基变换的次序和一般单纯形法不同：一般一般单纯形法单纯形法首先由最大减少原则确定首先由最大减少原则确定换入换入变量变量，然而用最小比值原则确定，然而用最小比值原则确定换出变量换出变量 。对对偶偶单单纯纯形形法法则则是是先先将将具具有有负负分分量量的的基基变变量量 取取出出，作作为为换换出出变变量量，然然后后确确定定某某个个非非基基
22、变变量量作作为为换换入入变变量量。其其变变换换目目的的是是在在保保持持对对偶偶问问题题可可行行性性的的前前提提下下，使使原问题的基本解向可行解靠拢。原问题的基本解向可行解靠拢。33对偶单纯形法对偶单纯形法的计算步骤如下：的计算步骤如下：（4 4）以以 为为主主元元进进行行旋旋转转变变换换，得得新新的的单单纯纯形形表表，返返回（回（2 2）。）。（2 2）确定）确定换出变量换出变量 根根据据 ，确确定定基基变变量量 作为作为换出变量换出变量。检验所在行各元素。检验所在行各元素若若所所有有,则则无无可可行行解解，停停止止计计算算。否否则则转转入入().).（3 3）确定）确定换入变量换入变量（针对
23、针对minmin）按按最大比值最大比值原则，若原则，若确定非基变量确定非基变量 为为换入变量（换入变量（绝对值最小绝对值最小）。（1 1）根根据据原原始始线线性性规规划划，列列出出初初始始单单纯纯形形表表，检检查查b b列列数数字字，若若b b列列数数字字全全部部非非负负，则则已已经经求求得得最最优优解解，停停止止计计算算。若若b b列中至少有一个负分量，则转入（列中至少有一个负分量，则转入（2 2）.34例例 用对偶单纯形法求解下列线性规划 min z=5x1+2x2+6x32x1+4x2+8x3 244x1+x2+4x38x1、x2，x30解解 将问题改写成如下形式 min z=5x1+2
24、x2+6x32x1 4x2 8x3+x4 =244x1 x2 4x3 +x5=8x1、x2，x3，x4，x50p4、p5构成的就是初始基。35据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：1 1/4 001/2-1/2 1/8 107/41x3 6 1-1/2 01-34x2 2 0 1/2204 1-1/4-20-7/2-2 x5 00-1/4211/26 x2 20062510-4-1-4-8 x5 001-8-4-2-24 x4 0 x5 x4 x3 x2 x1 b XB CB 0062 5 C可得最优解可得最优解 X*=(0
25、,4,1)36最最后后一一个个单单纯纯形形表表中中，已已得得到到一一个个可可行行解解，因因而而得得到到问题的最优解为问题的最优解为 X*=（0，4，1）T最优值为最优值为z*=14（1）对对于于形形如如min z=CX，AXb，X0，且且C0的的线线性规划问题。性规划问题。(因为将其改写为因为将其改写为max(z)=CX )AX+XS=b，X0，则立即可以得到，则立即可以得到初始解初始解；（2）在在灵灵敏敏度度分分析析中中，有有时时需需要要用用对对偶偶单单纯纯形形法法，可可使问题的处理简化。使问题的处理简化。对偶单纯形法在以下情况下较为方便对偶单纯形法在以下情况下较为方便。37例例7 7 用对
26、偶单纯形法求解用对偶单纯形法求解解：先化为标准型解：先化为标准型 对偶单纯形允许约束方程右端为负，对偶单纯形允许约束方程右端为负，因此可将方程因此可将方程2 2，3 3两端同乘两端同乘-1-1，可得含单位矩阵的标准型：可得含单位矩阵的标准型：38据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：5/4 7/4 000-1/4 1/4 0102x2 2-1/4-3/4 0014x1 3 5/4 3/4 1004x3 0 2/3 0007/3-1/3 0011/3 10/3 x2 21/3 100-4/3-16/3 x4 0101018 x
27、3 000023100-3-1-10 x5 00101-1-2 x4 00013218 x3 0 x5 x4 x3 x2 x1 b XB CB 0002 3 C可得最优解可得最优解 X X*=（4 4，2 2）T T 或者或者（4，2，4，0，0）T，W*=16 39初始可行基例、用对偶单纯形法求解线性规划问例、用对偶单纯形法求解线性规划问题：题：对偶问题的初始可行基40例、用对偶单纯形法求解线性规划问例、用对偶单纯形法求解线性规划问题：题：换入 换出换出换出这里就是-5/-1=5,-24/-6=441例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求
28、解线性规划问题：例、用对偶单纯形法求解线性规划问题：42最优解最优解例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：例、用对偶单纯形法求解线性规划问题：43对偶单纯形法的优点：对偶单纯形法的优点：不需要人工变量；不需要人工变量；当变量多于约束时，用对偶单纯形法可减当变量多于约束时，用对偶单纯形法可减少迭代次数；少迭代次数；在灵敏度分析中，有时需要用对偶单纯形在灵敏度分析中，有时需要用对偶单纯形法处理简化。法处理简化。对偶单纯形法缺点：对偶单纯形法缺点：在初始单纯形表中对偶问题是基可行解，在初始单纯形表中对偶问题是基可行解，这点对多数线
29、性规划问题很难做到。这点对多数线性规划问题很难做到。因此，对偶单纯形法一般不单独使用。因此，对偶单纯形法一般不单独使用。44p灵敏度分析灵敏度分析 线线性性规规划划问问题题所所对对应应的的数数据据集集合合，b b，常常常常是是通通过过预预测测或或估估计计所所得得到到的的统统计计数数据据，在在实实际际使使用用中中，不不免免会会有有一一定定的的误误差差。而而且且随随着着市市场场环环境境，工工艺艺条条件件和和资资源源数数量量的改变，这些数据完全的改变，这些数据完全可能发生变化可能发生变化。因因此此有有必必要要来来分分析析一一下下当当这这些些数数据据发发生生波波动动时时，对对目目前前的的最最优优解解，
30、最最优优值值或或者者最最优优基基会会产产生生什什么么影影响响，这这就就是是所谓的所谓的灵敏度分析灵敏度分析。45 Max Z=34 x1+40 x24 x1+6 x2 48 2 x1+2 x2 182 x1+x2 16x1、x2 0 0线性规划模型线性规划模型灵敏度分析图解 46x218 16 14 12 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE(8,0)(0,6.8)最优解最优解(3,6)4x1+6x2=48 2x1+2x2=18灵敏度分析图解 4718 16 14 12 10 8 6 4 2 0|2468
31、1012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE目标函数的系数目标函数的系数34x1+40 x2=Z40 x2=-34x1+Zx2=-+34x1Z40404818 16 14 12 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE目标函数的系数目标函数的系数34x1+40 x2=Z40 x2=-34x1+Zx2=-+c1x1Zc2c2若若若若 c c1 1增加增加增加增加（c c2 2 不变）不变）不变）不变）新的最优解新的最优解新的最优解新的最优解4918 16 14 1
32、2 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE目标函数的系数目标函数的系数34x1+40 x2=Z40 x2=-34x1+Zx2=-+c1x1Zc2c2若若若若 c c1 1减少减少减少减少新的最优解新的最优解新的最优解新的最优解5018 16 14 12 10 8 6 4 2 0|24681012141618x14x1+6x2 482x1+2x2 182x1+x2 16ABCDE(斜率斜率=-1)=-1)(斜率斜率=-2/3)=-2/3)最优解不变的范围最优解不变的范围（设（设c1固定固定c2可变）可变）51
33、最优解改变但最优基不变的例最优解改变但最优基不变的例52灵敏度分析主要讨论如下二类问题：灵敏度分析主要讨论如下二类问题：数据集合在数据集合在什么范围内波动什么范围内波动将不影响最优解或最优基？将不影响最优解或最优基？若最优解若最优解发生变化发生变化，应如何找到，应如何找到新的最优解新的最优解。CC1 C2 Cn CB XB b x1 x2 xn CB1 XB1 B-1b B-1A=B-1(P1，P2，Pn)CB2 XB2:CBm XBm C-CBTB-1A 列出标准型线性规划问题列出标准型线性规划问题最优单纯形表最优单纯形表：53n价值向量价值向量C C的改变的改变当价值向量由当价值向量由 时
34、，时，检验行检验行应修改为：应修改为：目标函数值应为目标函数值应为 。只要只要非基变量检验数非基变量检验数那么原最优解那么原最优解仍然为最优仍然为最优。至于目标函数值是否改变，取决于至于目标函数值是否改变，取决于分别就价值系数对应分别就价值系数对应非基变量非基变量或或基变量基变量加以讨论：加以讨论：54l若若是是非基变量非基变量的价值系数，为其改变量，在最的价值系数，为其改变量，在最优表中检验数优表中检验数 发生变化。发生变化。若超出范围，那么若超出范围，那么 ，当前解已不是最优解。，当前解已不是最优解。此时以修改后的此时以修改后的最优单纯形表最优单纯形表出发，进行出发，进行单纯形迭代单纯形迭
35、代，直至求出新的最优解。直至求出新的最优解。由由 只要只要 即即就可以就可以保持现行最优解保持现行最优解仍为最优。仍为最优。55l若若是某是某基变量基变量的价值系数，的价值系数，为改变量，在为改变量，在最优表中所有的非基变量检验数均发生了变化最优表中所有的非基变量检验数均发生了变化.由上式可得到一个由上式可得到一个不等式组不等式组，求解该不等式组就可，求解该不等式组就可得到价值系数得到价值系数 的可变动范围。的可变动范围。由，只要检验数：由，只要检验数：或或则最优解仍然保持为最优则最优解仍然保持为最优.56价值系数价值系数C发生变化：发生变化：一、保持原最优解，求变化范围一、保持原最优解，求变
36、化范围1、若、若 ck 是非基变量的系数：是非基变量的系数：设设 ck 变化为变化为 ck+ck 只要只要 k 0，则最优解不变；否则，将最优则最优解不变；否则，将最优单纯形表中的检验数单纯形表中的检验数 k 用用 k取代，继续单纯取代，继续单纯形法的表格计算形法的表格计算。例例:Max Z=-2x1 -3x2 -4x3 S.t.-x1-2x2 -x3 +x4 =-3 -2x1+x2 -3x3 +x5 =-4 x1,x2,x3,x4,x5 057最优表如下：-2-3-400CBXBbX1X2X3X4X5-3 X2 2/501-1/5-2/51/5-2 X1 11/5107/5-1/5-2/5j
37、00-9/5-8/5-1/5-2-3-4+c300CBXBbX1X2X3X4X5-3 X2 2/501-1/5-2/51/5-2 X1 11/5107/5-1/5-2/5j00-9/5+c3-8/5-1/5从表中看到从表中看到 3=C3+C3 -（C2*a13+C1*a23）可得到可得到 C3 9/5 时，原最优解不变。时，原最优解不变。把新的C3换人表中582、若、若 cs 是基变量的系数：是基变量的系数：例例:Max Z=2x1+3x2+0 x3+0 x4+0 x5 S.t.x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1,x2,x3,x4,x5 0 592、若
38、、若 cs 是基变量的系数：是基变量的系数：例例:Max Z=2x1+3x2+0 x3+0 x4+0 x5 S.t.x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1,x2,x3,x4,x5 0 6023000CBXBBX1X2X3X4X52 X1 41001/400 X5 400-21/213 X2 2011/2-1/80j00-1.5-1/80最优表如下：最优表如下：23+C2000CBXBBX1X2X3X4X52 X1 41001/400 X5 400-21/213+C2 X2 2011/2-1/80j00-1.5-C2/2-1/8+C2/80可得到可得到 -3
39、 C2 1 时，原最优解不变。时，原最优解不变。61例例7 7、某工厂用甲乙、某工厂用甲乙两种原料两种原料生产生产A A，B B，C C，D D四种产品四种产品，每种产品的利润，现有原料数及每种产品消耗原料定额每种产品的利润，现有原料数及每种产品消耗原料定额如表所示：如表所示：原料（公斤）原料（公斤）产品（万件）产品（万件）供应量供应量A B C DA B C D甲甲乙乙3 2 10 43 2 10 40 0 2 1/20 0 2 1/218183 3利润（万元利润（万元/万件）万件）9 8 50 199 8 50 19问应该怎样组织生产，才能使问应该怎样组织生产，才能使总利润最大总利润最大，
40、若，若产品或产品或的利润的利润产生波动，波动范围多大时，原最优解保持不变？产生波动，波动范围多大时，原最优解保持不变？解解：设生产，四种设生产，四种产品各万件，则此产品各万件，则此问题的线性规划模型为：问题的线性规划模型为：62标准化，引入松弛变量标准化，引入松弛变量x x5 5,x,x6 6，利用单纯形表求解：利用单纯形表求解：4 2/3 0 0 13/3 10/3 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/321x4x3-19-50 0 -2 0 -2 3 1026 1 2/3 0 1/2 1/3 -5/3 0 0 1 1/4 0 1/213/2x1
41、x3-9-50 -9 -8 0 -13/2 0 251-3 2 0 3/2 1 -5 0 0 1 1/4 0 1/233/2x5x30-50 -9 -8 -50 -19 0 09/53/2 3 2 10 4 1 0 0 0 2 1/2 0 1183x5x600 x1 x2 x3 x4 x5 x6bXBCB -9 -8 -50 -19 0 0C即最优生产方案是生产产品即最优生产方案是生产产品1 1万件，产品万件，产品2 2万件，万件，不生产不生产,两种产品。可得最大利润为两种产品。可得最大利润为8888万元。万元。63C -9 -8 -50 -19 0 0CBXBbx1 x2 x3 x4 x5
42、x6-19-50 x4x321 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3Z88 4 2/3 0 0 13/3 10/3最优表：最优表：原最优解不变，最优利润值原最优解不变，最优利润值（万元）也不变。（万元）也不变。(1)1)若若 有改变量。因为为非基变量，有改变量。因为为非基变量，由推得即由推得即 或时或时64C -9 -8 -50 -19 0 0CBXBbx1 x2 x3 x4 x5 x6-19-50 x4x321 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3Z88 4 2/3 0 0 13/3 10/3最优
43、表：最优表：()若若 有改变量。因为为基变量，有改变量。因为为基变量，由推得由推得即当或时即当或时原原最优解不变最优解不变，最优利润值，最优利润值 万元万元65线性规划 max z=2x1-x2+4x3 s.t.-3x1+2x2+4x35 x1+x2 +x33 x1 -x2 +x34 x1，x2,x30 的最优表如下：2-14000CBXBbX1X2X3X4X5X6420 X3X1X62110105/72/7-2100 1/7-1/70 3/74/7-1 001 0-31/70-2/7-20/701.如果如果C2变成变成2，求新的最优解。，求新的最优解。2.如果如果C3变成变成1，求新的最优解
44、。，求新的最优解。66解解：1.由最优表可知，由最优表可知，C231/7时最优解不变，时最优解不变，C2=2最优解还是最优解还是（1，0，2，0，0，1）.2.C3=1时原最优表不是最优表，用单纯形方法重新求解。时原最优表不是最优表，用单纯形方法重新求解。2-14000CBXBbX1X2X3X4X5X6420 X3X1X62110105/72/7-2100 1/7-1/70 3/74/7-1 001 0-31/70-2/7-20/702-14-3000CBXBbX1X2X3X4X5X64-320 X3X1X62110105/72/7-2100 1/7-1/70 3/74/7-1 001 0-1
45、6/701/7-11/70672-14-3000CBXBbX1X2X3X4X5X64-320 X3X1X62110105/72/7-2100 1/7-1/70 3/74/7-1 001 0-16/701/7-11/70CBXBbX1X2X3X4X5X6020 X4X1X6143101051-2710 100 31-1 001 0-3-10-20最优解为最优解为X*=（3，0，0，14，0，1）T，最优值为，最优值为Z*=668cj54000CBXBbx1x2x3x4x50 x3250012-55x1351001-14 x2 10 010-12000-1-3最优表如下：最优表如下：教材习题答案教
46、材习题答案694 =c25 05 =52c2 0 5/2 c2 5cj5c2 000CBXBbx1x2x3x4x50 x3250012-55x1351001-1c2 x2 10 010-12000c2-55-2c2最优解最优解X*=（35，10，25，0，0）T 保持不变。保持不变。（1）70Cj56000CBXBbx1x2x3x4x50 x3250012-55x1351001-16 x2 10 010-12j 0001-70 x425/2001/21-5/25x145/210-1/203/26 x2 45/2 011/20-1/2j00-1/20-9/2x1*=45/2，x2*=45/2，x
47、4*=25/2，x3*=x5*=0，z*=495/2（2）71例例 求解下列线性规划 max max z=x1+x2+3 x1+x2+2x3 4 4 x1+2x2+x3 20 x2+x3 40 x1、x2，x30分别求分别求c1、c2、c3的变化范围，使最优解不变。的变化范围，使最优解不变。C 113000CB XB b x1x2x3x4x5x60 x450-201-1-11x1511001-13x315011001 0-300-1-2最优表如下：最优表如下：727374n右端项向量右端项向量b b的改变的改变当当右端项右端项向量时，改变的是表中向量时，改变的是表中右端常数列右端常数列。此时基
48、变量，目标函数值。此时基变量，目标函数值。而检验行的检验向量保持不变。而检验行的检验向量保持不变。若，可用若，可用对偶单纯形法对偶单纯形法再次进行迭代，再次进行迭代，直到求得新最优解。直到求得新最优解。为了使为了使B B可行，只要可行，只要或或75 右端常数右端常数b bi i的变化分析的变化分析1.若若B-1b0 ,则原最优解还是最优解，则原最优解还是最优解，即最优基即最优基B不变，但解的数值发生改变。不变，但解的数值发生改变。（XB=B-1b,其它其它 x为为0）2.若若B-1b 0,则用对偶单纯形法继续求解。则用对偶单纯形法继续求解。3确定使最优基不变的资源限量范围。确定使最优基不变的资
49、源限量范围。用用B-1b0计算计算。7623000CBXBbX1X2X3X4X52 X1 41001/400 X5 400-21/213 X2 2011/2-1/80j00-1.5-1/80线性规划线性规划 max z=2x1+3x2 s.t.x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1,x2,.x50的最优单纯形表如下：的最优单纯形表如下：如果如果b1增加增加4，最优解如何变化？，最优解如何变化？b1在什么范围时最优基不变？在什么范围时最优基不变？这里这里B-1=B-1b=（0 -8 2），单纯形表如下：，单纯形表如下：7723000CBXBbX1X2X3X4X52
50、X1 4+01001/400 X5 4-800-21/213 X2 2+2011/2-1/80j00-1.5-1/802 X1 41001/400 X3 2001-1/4-1/23 X2 301001/4j000-1/2-3/4由对偶单纯形法求解得：由对偶单纯形法求解得：x*=(4,3,2,0,0)T,f*=17.78线性规划问题线性规划问题求得最优单纯形表如下：求得最优单纯形表如下：1.写出对偶问题的最优解。写出对偶问题的最优解。2.求最优基不变的求最优基不变的b1的变化范围。的变化范围。3.约束条件（约束条件（1）的常数由）的常数由20变为变为30后，最优解如何后，最优解如何改变？改变？7