《对偶规划与灵敏度分析PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《对偶规划与灵敏度分析PPT讲稿.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、对偶规划与灵敏度分析1第1页，共60页，编辑于2022年，星期六 对偶理论对偶理论是线性规划的重要内容之一。对应于每是线性规划的重要内容之一。对应于每个线性规划问题都伴生一个相应的线性规划问题。个线性规划问题都伴生一个相应的线性规划问题。原问题和对偶问题紧密关联，它们不但有原问题和对偶问题紧密关联，它们不但有相同的相同的数据集合数据集合，相同的最优目标函数值相同的最优目标函数值，而且在，而且在求得一个线性求得一个线性规划的最优解的同时，也同步得到对偶线性规划的最优解规划的最优解的同时，也同步得到对偶线性规划的最优解。由对偶问题引伸出来的对偶解还有着重要的由对偶问题引伸出来的对偶解还有着重要的经
2、济意义经济意义，是研究经济学的重要概念和工具之一。是研究经济学的重要概念和工具之一。2第2页，共60页，编辑于2022年，星期六n对偶问题的提出对偶问题的提出例例1 1、某工厂生产甲、某工厂生产甲,乙两种产品，这两种产品需要在乙两种产品，这两种产品需要在A,B,CA,B,C三种不同设备上加工。三种不同设备上加工。每吨甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，每吨甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润，以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划，即甲计划
3、，即甲,乙两种产品各生产多少吨，可使该厂所获得利润达到最大。乙两种产品各生产多少吨，可使该厂所获得利润达到最大。1对偶线性规划对偶线性规划设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 3第3页，共60页，编辑于2022年，星期六 假设计划期内甲乙两种产品各生产假设计划期内甲乙两种产品各生产 吨，吨，设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44
4、 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 用图解法或单纯形法可求得最优解用图解法或单纯形法可求得最优解 (元元)即在计划期内甲产品生产即在计划期内甲产品生产 吨，乙产品生产吨，乙产品生产8 8吨，可以使总利润达吨，可以使总利润达到最大，为到最大，为 元元。4第4页，共60页，编辑于2022年，星期六 现在从另一个角度来考虑该工厂的生产问题现在从另一个角度来考虑该工厂的生产问题:假设该厂的决策者打算不再自己生产甲假设该厂的决策者打算不再自己生产甲,乙产品，而是把各种设备乙产品，而是把各种设备的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确
5、定各的有限台时数租让给其他工厂使用，这时工厂的决策者应该如何确定各种设备的租价。种设备的租价。设设 分别为设备分别为设备A A，B B，C C每台时的租价，每台时的租价，约束条件：约束条件：把设备租出去所获得的租金不应低于利用这些设备自把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润行生产所获得的利润目标函数：所获租金总额尽量少目标函数：所获租金总额尽量少5第5页，共60页，编辑于2022年，星期六由此可得两个对称的线性规划：由此可得两个对称的线性规划：6第6页，共60页，编辑于2022年，星期六矩阵形式矩阵形式：7第7页，共60页，编辑于2022年，星期六可以得到另一个线性规
6、划可以得到另一个线性规划：称之为原线性规划问题的对偶问题称之为原线性规划问题的对偶问题，n对偶线性规划对偶线性规划考虑如下具有不等式约束的线性规划问题考虑如下具有不等式约束的线性规划问题8第8页，共60页，编辑于2022年，星期六9第9页，共60页，编辑于2022年，星期六10第10页，共60页，编辑于2022年，星期六11第11页，共60页，编辑于2022年，星期六若令若令线性规划标准型线性规划标准型的对偶规划为：的对偶规划为：n线性规划问题标准型的对偶问题线性规划问题标准型的对偶问题考虑一个标准形式的线性规划问题考虑一个标准形式的线性规划问题 由于任何一个等式约束都可以用两个不等式约束等价
7、地表示，所以由于任何一个等式约束都可以用两个不等式约束等价地表示，所以标准形线性规划问题可等价表示为：标准形线性规划问题可等价表示为：它的对偶规划为：它的对偶规划为：12第12页，共60页，编辑于2022年，星期六n对偶线性规划的求法对偶线性规划的求法从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解过程中，从任何一个线性规划出发，都可以求出相应的对偶规划，在实际求解过程中，通常不通过求标准型，而是利用如下反映原始问题与对偶问题对应关系的原始通常不通过求标准型，而是利用如下反映原始问题与对偶问题对应关系的原始对偶表：对偶表：目标函数变量系数目标函数变量系数约束条件右端项约束条件右端项
8、 约束条件右端项约束条件右端项目标函数变量系数目标函数变量系数 约束条件约束条件个数：个数：n n个个 变量变量个数：个数：n n个个 变量变量个数：个数：m m个个 约束条件约束条件个数：个数：m m个个 目标函数目标函数minW minW 目标函数目标函数maxZ maxZ 对偶问题（或原问题）对偶问题（或原问题）原问题（或对偶问题）原问题（或对偶问题）13第13页，共60页，编辑于2022年，星期六解：对偶规划：解：对偶规划：例例2 2 写出下列线性规划的对偶问题写出下列线性规划的对偶问题14第14页，共60页，编辑于2022年，星期六例例3 3 写出下列线性规划的对偶问题写出下列线性规
9、划的对偶问题解：上述问题的对偶规划：解：上述问题的对偶规划：15第15页，共60页，编辑于2022年，星期六本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和对偶本节讨论几条重要的对偶定理，这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。问题的解之间的基本关系。定理定理1 1：（：（对合性对合性）对偶问题的对偶是原问题。）对偶问题的对偶是原问题。证明：设原问题为对偶问题为证明：设原问题为对偶问题为改写对偶问题为对偶问题的对偶为改写对偶问题为对偶问题的对偶为2对偶定理对偶定理16第16页，共60页，编辑于2022年，星期六 定理定理2 2：弱对偶定理弱对偶定理 若是原（极小化）问题
10、的可行解，是对偶（极大化）问题的可行解，若是原（极小化）问题的可行解，是对偶（极大化）问题的可行解，那么那么 证明：因为是对偶问题的可行解，所以满足约束条件证明：因为是对偶问题的可行解，所以满足约束条件 又因为是原问题的可行解，可得，又因为是原问题的可行解，可得，,所以所以 。注：原（极小化）问题的最优目标函数值以对偶问题任一可注：原（极小化）问题的最优目标函数值以对偶问题任一可行解的目标函数值为下界。行解的目标函数值为下界。对偶（极大化）问题的最优目标函数值以原问题任一可行解对偶（极大化）问题的最优目标函数值以原问题任一可行解的目标函数值为上界。的目标函数值为上界。推论推论1 1：如果原问题
11、没有下界（即如果原问题没有下界（即minZminZ），则对偶问题），则对偶问题不可行。不可行。如果对偶问题没有上界（即如果对偶问题没有上界（即maxWmaxW），则原问题不可行。），则原问题不可行。若原问题与对偶问题之一无界，则另一个无可行解。若原问题与对偶问题之一无界，则另一个无可行解。17第17页，共60页，编辑于2022年，星期六证明：由弱对偶定理，对于原始问题的证明：由弱对偶定理，对于原始问题的所有可行解所有可行解，都有，都有 因此是原问题的因此是原问题的最优解最优解。同理，对于对偶问题的同理，对于对偶问题的所有可行解所有可行解 ，都有，都有 所以所以 是对偶问题的是对偶问题的最优解最
12、优解。推论推论2 2：最优性定理最优性定理若若是是原原问问题题的的可可行行解解，是是对对偶偶问问题题的的可可行行解解，而而且两者的目标函数值相等，即，则和且两者的目标函数值相等，即，则和分别是原问题和对偶问题的最优解。分别是原问题和对偶问题的最优解。18第18页，共60页，编辑于2022年，星期六证明：设是原问题证明：设是原问题(min)(min)的最优解，则对应的基必有的最优解，则对应的基必有。若定义，则若定义，则 ，因此为对偶问题的可行解，而且因此为对偶问题的可行解，而且 ，由最优性，由最优性定理，是对偶问题的最优解。定理，是对偶问题的最优解。定理定理3:3:强对偶定理强对偶定理 如果原问
13、题（如果原问题（min)min)与对偶问题与对偶问题(max)(max)之一有最优解，那么之一有最优解，那么另一个也有最优解，而且目标函数值另一个也有最优解，而且目标函数值相等相等。19第19页，共60页，编辑于2022年，星期六证证明明：设设满满足足原原问问题题(min)(min)的的最最优优性性条条件件，则则对对应应的的基基必有必有。若定义若定义 ，则，则 ，因此为对偶问题的基本可行解。因此为对偶问题的基本可行解。定理定理4 4：设满足原问题设满足原问题(min)的的最优性条件最优性条件的一个的一个基本解基本解，则，则其对应的线性规划问题其对应的线性规划问题(min)(min)的的检验数检
14、验数对应对应对偶问题对偶问题的一个的一个基本可基本可行解行解。20第20页，共60页，编辑于2022年，星期六原问题与对偶问题可能出现的情况（1）两者都有最优解，且最优值相等；（2）一个有可行解，但无界，则另一个无可行解；（3）两者都无可行解。21第21页，共60页，编辑于2022年，星期六定理定理5 5：互补松弛定理互补松弛定理如果如果 分别是原问题分别是原问题(min)(min)和对偶问题（和对偶问题（max)max)的可行解，那的可行解，那么么 和和 为最优解的充要条件是为最优解的充要条件是 通常称通常称 为互补松弛条件。为互补松弛条件。证明：充分性证明：充分性必要性必要性22第22页，
15、共60页，编辑于2022年，星期六例例5 5、已知线性规划问题、已知线性规划问题:其对偶问题的最优解。其对偶问题的最优解。试用试用互补松弛定理互补松弛定理找出原问题的最优解。找出原问题的最优解。解：原问题的对偶问题为：解：原问题的对偶问题为：由对偶问题最优解可知，由对偶问题最优解可知，由互补松弛定理，由互补松弛定理，解方程组解方程组 所以原问题最优解所以原问题最优解23第23页，共60页，编辑于2022年，星期六 假设计划期内甲乙两种产品各生产假设计划期内甲乙两种产品各生产 吨，吨，设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 5
16、9 9 4 44 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 用图解法或单纯形法可求得最优解用图解法或单纯形法可求得最优解 (元元)即在计划期内甲产品生产即在计划期内甲产品生产 吨，乙产品生产吨，乙产品生产8 8吨，可以使总利润达吨，可以使总利润达到最大，为到最大，为 元元。例：例：对偶最优解的经济解释对偶最优解的经济解释影子价格影子价格 24第24页，共60页，编辑于2022年，星期六25第25页，共60页，编辑于2022年，星期六由由强强对对偶偶定定理理可可知知，如如果果原原问问题题有有最最优优解解，那那么么对对偶偶问题也有最优解，而且它们的目标
17、函数值相等，即有：问题也有最优解，而且它们的目标函数值相等，即有：其其中中是是线线性性规规划划原原问问题题约约束束条条件件的的右右端端数据向量，它代表各种资源的拥有量。数据向量，它代表各种资源的拥有量。为为对对偶偶问问题题最最优优解解，它它代代表表在在资资源源最最优优利利用用条条件件下下对对各各种种单单位位资资源源的的估估价价，这这种种估估计计不不是是资资源源的的市市场场价价格格，而而是是根根据据资资源源在在生生产产中中所所作作出出的的贡贡献献（如如创创造造利利润润，产产值值等等）而而作作出出估估价价，为为区区别别起起见见，称称之之为为影影子子价价格格(shadow(shadow price)
18、price)。26第26页，共60页，编辑于2022年，星期六影影子子价价格格的的大大小小客客观观地地反反映映了了各各种种不不同同资资源源在在系系统统内内的的稀稀缺缺程程度度。如如果果第第i i种种资资源源供供大大于于求求，即即在在达达到到最最优优解解时时，该该种种资资源源没没有有用用完完，或或松松弛弛变变量量，由由互互补补松松弛弛定定理理，在在对对偶偶最最优优解解中中，第第i i种种资资源源的的影影子子价价格格。反反之之如如果果第第i i种种资资源源的的影影子子价价格格，那那么么由由互互补补松松弛弛定定理理，原原问问题题的的第第i i个个约约束束为为严严格格等等式式，即即，这这表表明明第第i
19、 i种种资源已经用完资源已经用完，成为稀缺资源。，成为稀缺资源。资资源源的的影影子子价价格格同同时时也也是是一一种种机机会会成成本本，在在市市场场经经济济的的条条件件下下，当当某某种种资资源源的的市市场场价价格格低低于于影影子子价价格格时时，企企业业应应买买进进这这种种资资源源用用于于扩扩大大生生产产；相相反反当当某某种种资资源源的的市市场场价价格格高高于于影影子子价价格格时时，企企业业应应卖卖出出这这种种资资源源。随随着着资资源源的的买买进进卖卖出出，企企业业资资源源的的影影子子价价格格也也将将随随之之发发生生变变化化，一一直直到到影影子子价价格格与与市市场场价格保持同等水平价格保持同等水平
20、时，才处于时，才处于平衡状态平衡状态。27第27页，共60页，编辑于2022年，星期六设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 例：例：对偶最优解对偶最优解其中为其中为设备设备A A的影子价格的影子价格，在资源最优利用的条件下，设备在资源最优利用的条件下，设备A A每每增加增加一个单位台时一个单位台时，可以使，可以使总利润增加总利润增加元。元。若设备可供台时数，则若设备可供台时数，则28第28页，共60页，编辑于2022
21、年，星期六3对偶单纯形法对偶单纯形法单单纯纯形形法法是是以以保保持持原原问问题题可可行行为为条条件件，即即不不论论进进行行怎怎样样的的基基变换，常数列必须保持非负。变换，常数列必须保持非负。利利用用对对偶偶问问题题的的对对称称性性，我我们们从从另另一一个个角角度度来来考考虑虑求求解解原原问问题题最最优优解解的的方方法法，这这种种方方法法以以保保持持对对偶偶问问题题可可行行为为条条件件，即即不不论论进进行行何何种种基基变变换换，必必须须保保持持所所有有的的检检验验数数非非负负，同同时时取取消消原原问问题题必必须须可可行行的的要要求求，即即取取消消常常数数列列的的非非负负限限制制，通通过过基基变变
22、换换使使原原问问题题在在非非可可行行解解的的基基础础上上逐逐步步转转换换成成基基本本可可行行解解，一一旦旦原原问问题题的的基基本本解解可可行行，则则该该基基本本可可行行解解也也就就是是最最优优解解，这这就就是是对对偶偶单单纯纯形形法法的基本思想。的基本思想。单纯形法：单纯形法：可行性可行性最优性最优性对偶单纯形法：对偶单纯形法：最优性最优性可行性可行性29第29页，共60页，编辑于2022年，星期六例例6求解下列线性规划min z=5x1+2x2+6x32x1+4x2+8x3 244x1+x2+4x38x1、x2，x30解解min z=5x1+2x2+6x32x1+4x2+8x3-x4 =24
23、4x1+x2+4x3 -x5=8x1、x2，x3，x4，x50min z=5x1+2x2+6x32x1 4x28x3+x4 =244x1 x2 4x3 +x5=8x1、x2，x3，x4，x5030第30页，共60页，编辑于2022年，星期六Cj52600bCBXBx1x2x3x4x50 x4-2-4-810-240 x5-4-1-401-85260005/-22/-46/-80031第31页，共60页，编辑于2022年，星期六对偶单纯形法基变换的次序和一般单纯形法不同：对偶单纯形法基变换的次序和一般单纯形法不同：一一般般单单纯纯形形法法首首先先由由最最大大减减少少原原则则确确定定换换入入变变量
24、量，然然而而用最小比值原则确定用最小比值原则确定换出变量换出变量 。对对偶偶单单纯纯形形法法则则是是先先将将具具有有负负分分量量的的基基变变量量 取取出出，作作为为换换出出变变量量，然然后后确确定定某某个个非非基基变变量量作作为为换换入入变变量量。其其变变换换目目的的是是在在保保持持对对偶偶问问题题可可行行性性的的前前提提下下，使使原原问问题题的的基基本本解解向可行解靠拢。向可行解靠拢。32第32页，共60页，编辑于2022年，星期六对偶单纯形法对偶单纯形法的计算步骤如下：的计算步骤如下：（4 4）以以 为为主主元元进进行行旋旋转转变变换换，得得新新的的单单纯纯形形表表，返返回（回（2 2）。
25、）。（2 2）确定）确定换出变量换出变量 根根据据 ，确确定定基基变变量量 作为作为换出变量换出变量。检验所在行各元素。检验所在行各元素若若所所有有,则则无无可可行行解解，停停止止计计算算。否否则则转转入入().).（3 3）确定）确定换入变量换入变量按按最大比值最大比值原则，若原则，若确定非基变量确定非基变量 为为换入变量换入变量。（1 1）根根据据原原始始线线性性规规划划，列列出出初初始始单单纯纯形形表表，检检查查b b列列数数字字，若若b b列列数数字字全全部部非非负负，则则已已经经求求得得最最优优解解，停停止止计计算算。若若b b列列中中至至少少有有一一个负分量，则转入（个负分量，则转
26、入（2 2）.33第33页，共60页，编辑于2022年，星期六例例6用对偶单纯形法求解下列线性规划min z=5x1+2x2+6x32x1+4x2+8x3 244x1+x2+4x38x1、x2，x30解解将问题改写成如下形式min z=5x1+2x2+6x32x1 4x28x3+x4 =244x1 x2 4x3 +x5=8x1、x2，x3，x4，x50显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正则基。34第34页，共60页，编辑于2022年，星期六Cj52600bCBXBx1x2x3x4x50 x4-2-4-810-240 x5
27、-4-1-401-85260005/-22/-46/-800-2x21/212-1/4060 x5-7/20-2-1/41-24021/20-1204/(-7/2)02/-2(1/2)/(-1/4)0-2x2-310-1/214-6x37/4011/8-1/211/2001/40-3235第35页，共60页，编辑于2022年，星期六最最后后一一个个单单纯纯形形表表中中，已已得得到到一一个个可可行行的的正正则则解解，因因而而得得到到问题的最优解为问题的最优解为X*=（0，4，1）T最优值为最优值为z*=14（1）对对于于形形如如minz=CX，AXb，X0，且且C0的的线线性性规规划划问问题题。
28、因因为为将将其其改改写写为为max(z)=CX，AX+XS=b，X0，则立即可以得到则立即可以得到初始正则解初始正则解；（2）在在灵灵敏敏度度分分析析中中，有有时时需需要要用用对对偶偶单单纯纯形形法法，可可使使问问题的处理简化。题的处理简化。对偶单纯形法在以下情况下较为方便对偶单纯形法在以下情况下较为方便。36第36页，共60页，编辑于2022年，星期六例例7 7 用对偶单纯形法求解用对偶单纯形法求解解：先化为标准型解：先化为标准型 对偶单纯形允许约束方程右端为负，对偶单纯形允许约束方程右端为负，因此可将方程因此可将方程2 2，3 3两端同乘两端同乘-1-1，可得含单位矩阵的标准型：可得含单位
29、矩阵的标准型：37第37页，共60页，编辑于2022年，星期六据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：据此列出初始单纯形表，并施行对偶单纯形法迭代步骤如下：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 x3 000023100-3-1-10 x5 00101-1-2 x4 00013218 x3 0 x5 x4 x3 x2 x1 b XB CB 0002 3 C可得最优解可得最优解 3
30、8第38页，共60页，编辑于2022年，星期六例例8用对偶单纯形法求解下列线性规划min z=x1+2x2x1+x242x1+3 x218x1、x20解解将问题改写成如下形式min z=x1+2x2x1+x2+x3 =42x13x2 +x4=18x1、x2，x3，x40显然，p3、p4可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p3、p4构成的就是初始z正则基。39第39页，共60页，编辑于2022年，星期六4灵敏度分析灵敏度分析 线线性性规规划划问问题题所所对对应应的的数数据据集集合合，b b，常常常常是是通通过过预预测测或或估估计计所所得得到到的的统统计计数数据据，
31、在在实实际际使使用用中中，不不免免会会有有一一定定的的误误差差。而而且且随随着着市市场场环环境境，工工艺艺条条件件和和资资源源数数量量的的改改变变，这这些些数数据据完完全全可能发生变化可能发生变化。因因此此有有必必要要来来分分析析一一下下当当这这些些数数据据发发生生波波动动时时，对对目目前前的的最最优优解解，最最优优值值或或者者最最优优基基会会产产生生什什么么影影响响，这这就就是是所所谓谓的的灵灵敏敏度度分析分析。40第40页，共60页，编辑于2022年，星期六灵敏度分析主要讨论如下二类问题：灵敏度分析主要讨论如下二类问题：数据集合在数据集合在什么范围内波动什么范围内波动将不影响最优解或最优基
32、？将不影响最优解或最优基？若最优解若最优解发生变化发生变化，应如何找到，应如何找到新的最优解新的最优解。CC1 C2 CnCB XB b x1 x2 xnCB1 XB1 B-1b B-1A=B-1(P1，P2，Pn)CB2 XB2:CBm XBm C-CBTB-1A 列出标准型线性规划问题列出标准型线性规划问题最优单纯形表最优单纯形表：41第41页，共60页，编辑于2022年，星期六n价值向量价值向量C C的改变的改变当价值向量由当价值向量由 时，时，检验行检验行应修改为：应修改为：目标函数值应为目标函数值应为 。只要只要非基变量检验数非基变量检验数那么原最优解那么原最优解仍然为最优仍然为最优
33、。至于目标函数值是否改变，取决于至于目标函数值是否改变，取决于分别就价值系数对应分别就价值系数对应非基变量非基变量或或基变量基变量加以讨论：加以讨论：42第42页，共60页，编辑于2022年，星期六l若是若是非基变量非基变量的价值系数，为其改变量，在最优的价值系数，为其改变量，在最优表中检验数表中检验数 发生变化。发生变化。若超出范围，那么若超出范围，那么 ，当前解已不是最优解。，当前解已不是最优解。此时以修改后的此时以修改后的最优单纯形表最优单纯形表出发，进行出发，进行单纯形迭代单纯形迭代，直至求出新的最优解。直至求出新的最优解。由由 只要只要 即即就可以就可以保持现行最优解保持现行最优解仍
34、为最优。仍为最优。43第43页，共60页，编辑于2022年，星期六l若是某若是某基变量基变量的价值系数，为改变量，在的价值系数，为改变量，在最优表中所有的非基变量检验数均发生了变化最优表中所有的非基变量检验数均发生了变化.由上式可得到一个由上式可得到一个不等式组不等式组，求解该不等式组就可，求解该不等式组就可得到价值系数得到价值系数 的可变动范围。的可变动范围。由，只要检验数：由，只要检验数：或或则最优解仍然保持为最优则最优解仍然保持为最优.44第44页，共60页，编辑于2022年，星期六例例7 7、某工厂用甲乙、某工厂用甲乙两种原料两种原料生产生产A A，B B，C C，D D四种产品四种产
35、品，每种，每种产品的利润，现有原料数及每种产品消耗原料定额如表所示：产品的利润，现有原料数及每种产品消耗原料定额如表所示：原料（公斤）原料（公斤）产品（万件）产品（万件）供应量供应量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问应该怎样组织生产，才能使问应该怎样组织生产，才能使总利润最大总利润最大，若，若产品或的利润产品或的利润产生波动，波动范围多大时，原最优解保持不变？产生波动，波动范围多大时，原最优解保持不变？解解：设生产，四种设生产，四种产品各万
36、件，则此产品各万件，则此问题的线性规划模型为：问题的线性规划模型为：45第45页，共60页，编辑于2022年，星期六标准化，引入松弛变量标准化，引入松弛变量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/2x1x3-9-50 -9 -8 0 -13/2 0 251-3 2 0 3/2 1 -5 0 0 1 1/4 0 1
37、/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万元。万元。46第46页，共60页，编辑于2022年，星期六C -9 -8 -50 -19 0 0CBXBbx1 x2 x3 x4 x5 x6-19-50 x4x321 2 4/3 0 1 2/3 -10/
38、3 -1/2 -1/3 1 0 -1/6 4/3Z88 4 2/3 0 0 13/3 10/3最优表：最优表：原最优解不变，最优利润值原最优解不变，最优利润值（万元）也不变。（万元）也不变。(1)1)若若 有改变量。因为为非基变量，有改变量。因为为非基变量，由推得即由推得即 或时或时47第47页，共60页，编辑于2022年，星期六C -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最优表：最优表：()若若 有
39、改变量。因为为基变量，有改变量。因为为基变量，由推得由推得即当或时即当或时原原最优解不变最优解不变，最优利润值，最优利润值万元万元48第48页，共60页，编辑于2022年，星期六n右端项向量右端项向量b b的改变的改变当当右端项右端项向量时，改变的是表中向量时，改变的是表中右端常数列右端常数列。此时基变量，目标函数值。此时基变量，目标函数值。而检验行的检验向量保持不变。而检验行的检验向量保持不变。若，可用若，可用对偶单纯形法对偶单纯形法再次进行迭代，再次进行迭代，直到求得新最优解。直到求得新最优解。为了使为了使B B可行，只要可行，只要或或49第49页，共60页，编辑于2022年，星期六例例8
40、 8、在例、在例7 7中，若想增加甲种原料，问增加多少时原最优基中，若想增加甲种原料，问增加多少时原最优基不变？不变？解：设甲种原料的改变量为解：设甲种原料的改变量为 ,则则由由 即即 最优目标函数值最优目标函数值 (万元万元)由此可以推得，由此可以推得，即当即当 时，原最时，原最优基不变。此时最优解优基不变。此时最优解 或或50第50页，共60页，编辑于2022年，星期六l约束矩阵约束矩阵A A的改变的改变 假设原线性规划问题假设原线性规划问题有一个最优解其中为最优基，有一个最优解其中为最优基，约束矩阵约束矩阵A A的改变可能导致不同的最优解和最优基的改变可能导致不同的最优解和最优基.以下只
41、以下只涉及两种较简单的情形：涉及两种较简单的情形：l增加一个变量增加一个变量，l增加一个约束条件增加一个约束条件。51第51页，共60页，编辑于2022年，星期六l 增加一个变量增加一个变量增加增加一个新变量，对应的价值系数为，一个新变量，对应的价值系数为，对应的系数列向量为，可得新的线性规划问题：对应的系数列向量为，可得新的线性规划问题：设，则设，则 为为新问题新问题的一个的一个可行解可行解。因此可在此基础上开始因此可在此基础上开始单纯形法单纯形法，求新的最优解。，求新的最优解。如果如果 ，则，则，是新问题的最优解。是新问题的最优解。否则以为换入变量进行基变换，继续使用否则以为换入变量进行基
42、变换，继续使用单纯形算法单纯形算法为为新的线性规划寻求一个最优解。新的线性规划寻求一个最优解。52第52页，共60页，编辑于2022年，星期六l增加一个约束增加一个约束如如果果加加入入一一个个新新的的约约束束条条件件，不不妨妨假假设设此此约约束束条条件件为为不等式形式不等式形式，即，即在附加不等式约束左端加上一个在附加不等式约束左端加上一个松弛变量松弛变量,新的线性规划变成新的线性规划变成 53第53页，共60页，编辑于2022年，星期六由由此此可可以以在在原原来来最最优优基基的的基础上定义一个基础上定义一个新的基新的基,是非奇异矩阵，是非奇异矩阵，得到新问题的一个得到新问题的一个基本解基本解
43、在原最优解基础上对新问题作在原最优解基础上对新问题作初等行变换初等行变换，使基变量对应的，使基变量对应的系数列向量为系数列向量为单位矩阵单位矩阵，该基本解该基本解不一定是可行解不一定是可行解，但是由于，但是由于是原线性规划问题的是原线性规划问题的最优基最优基，所以能保证该线性规划的，所以能保证该线性规划的对偶规划是对偶规划是可行的可行的。54第54页，共60页，编辑于2022年，星期六结论：如果由新基定义的结论：如果由新基定义的基本解基本解l是非负的是非负的。那么该基本解就是有附加约束条件的新线性规划问题的最。那么该基本解就是有附加约束条件的新线性规划问题的最优解。优解。l不满足非负条件不满足
44、非负条件。那么至少有一个基变量小于零，此时可用。那么至少有一个基变量小于零，此时可用对偶单对偶单纯形法纯形法求出新问题的最优解。求出新问题的最优解。55第55页，共60页，编辑于2022年，星期六解：（解：（1 1）设生产）设生产产品产品x x7 7万件，万件，1 1万件万件E E产品的利润为产品的利润为c c7 7万元，万元，则数学模型变为：则数学模型变为：例例9 9、在例、在例7 7中，若考虑生产另一种中，若考虑生产另一种产品产品，已知每生产，已知每生产1 1万件产万件产品要消耗品要消耗甲原料甲原料3 3公斤公斤，乙原料乙原料1 1公斤公斤，那么，产品的每万件，那么，产品的每万件利利润润为
45、多少时才有利于该种产品投产？为多少时才有利于该种产品投产？若假设该工厂又若假设该工厂又增加了用电量不超过增加了用电量不超过9 9千瓦的限制千瓦的限制，已知生，已知生产，四种产品各产，四种产品各1 1万件分别耗电万件分别耗电4 4，3 3，5 5，2 2千瓦千瓦，问此约束是否问此约束是否改变了原最优决策方案改变了原最优决策方案？56第56页，共60页，编辑于2022年，星期六已知已知 是是原问题的最优解原问题的最优解，若令，若令，则是现问题的一个则是现问题的一个可行解可行解，但未必是最优解。，但未必是最优解。若要产品投产，即若要产品投产，即 ，则，则其检验数其检验数 ,即即 得每万件得每万件E
46、E产品利润产品利润万元时，有利于生产万元时，有利于生产E E产品。产品。57第57页，共60页，编辑于2022年，星期六由此可的新的最优解，即最优生产方案为由此可的新的最优解，即最优生产方案为生产万件产品和件产品，总利润为万元。生产万件产品和件产品，总利润为万元。C-9-8-50-1900-17CBXBbx1x2x3x4x5x6x7-19X4224/3012/3-10/3-4/3-50 x31-1/2-1/310-1/64/35/642/30013/310/3-2/3-19X418/56/54/58/512/5-6/50-17x76/5-3/5-2/56/50-1/58/5118/52/54/
47、5021/522/50例如当例如当万元时，代入原线性规划的最优单纯形表，得万元时，代入原线性规划的最优单纯形表，得增增加新变量加新变量的单纯形表，的单纯形表，其中其中58第58页，共60页，编辑于2022年，星期六（）假假设设生生产产，四四种种产产品品各各1 1万万件件分分别别耗耗电电4 4，3 3，5 5，2 2千千瓦瓦，工工厂厂又又增增加加了了用用电电量量不不超超过过9 9千千瓦瓦的的限限制制，则则相相当当于于原原问问题约束方程组题约束方程组增加了一个约束方程增加了一个约束方程增加松弛变量，得增加松弛变量，得利利用用原原线线性性规规划划最最优优单单纯纯形形表表，增增加加一一行行和和一一列列
48、得得一一张张新新表表，作作初初等等行行变变换换，使使基基变变量量对对应应的的系系数数列列向向量量为为单单位位矩矩阵阵，若若变变换换结结果果使使基基变变量量取取了了负负值值，则则对对应应的的基基不不是是可可行行基基，要要用用对对偶偶单单纯纯形形法法进进行行了了基基变变换换，并并求求得得最优解，否则变换结果已为最优解。最优解，否则变换结果已为最优解。59第59页，共60页，编辑于2022年，星期六-20100-2-52-1/34/3001-1-4/34/34/3-10/30104-16/32/3X4x3x5-19-50010-1/20025/2-104/3-1/601-1/3-1/210-10/32/3104/322X4x3x7-19-50010025348x7004/3-1/601-1/3-1/21x3-500-10/32/3104/322X4-1926/310/30001877/3010/313/3002/34010/313/3002/34x7x6x5x4x3x2x1bXBCB000-19-50-8-9c可可见见增增加加用用电电约约束束以以后后，最最优优生生产产方方案案是是 万万件件产产品品，万万件件产产品，总利润为品，总利润为 万元，比原问题的最大利润减少万元，比原问题的最大利润减少 。60第60页，共60页，编辑于2022年，星期六