《线性规划理论与模型应用幻灯片.ppt》由会员分享，可在线阅读，更多相关《线性规划理论与模型应用幻灯片.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性规划理论与模型应用第1页，共51页，编辑于2022年，星期一2.1对偶规划对偶规划1.1.1.1.食谱问题食谱问题食谱问题食谱问题设有设有设有设有n n种食物种食物种食物种食物,各含各含各含各含mm种营养素种营养素种营养素种营养素,第第第第j j种食物中第种食物中第种食物中第种食物中第i i种营养素的种营养素的种营养素的种营养素的含量为含量为含量为含量为a aij ij,所有所有所有所有n n种种种种食物价格分别为食物价格分别为食物价格分别为食物价格分别为c c1 1,c c2 2,c cn n,营养素的价营养素的价营养素的价营养素的价格分别为格分别为格分别为格分别为w w1 1,w w2
2、 2,w wmm,要求食谱中要求食谱中要求食谱中要求食谱中mm种营养素的含量分别不低种营养素的含量分别不低种营养素的含量分别不低种营养素的含量分别不低于于于于b b1 1,b b2 2,b bmm,食谱中食谱中食谱中食谱中n n种食物的数量为种食物的数量为种食物的数量为种食物的数量为x x1 1,x x2 2,x xn n,如下表如下表如下表如下表所示所示所示所示:第2页，共51页，编辑于2022年，星期一对对偶偶规规划划n n消费者希望费用最低且满足营养要求，则有消费者希望费用最低且满足营养要求，则有消费者希望费用最低且满足营养要求，则有消费者希望费用最低且满足营养要求，则有n n食谱厂家在
3、确定营养素价格时，希望收益最大且能吸引食谱厂家在确定营养素价格时，希望收益最大且能吸引食谱厂家在确定营养素价格时，希望收益最大且能吸引食谱厂家在确定营养素价格时，希望收益最大且能吸引消费者，则有消费者，则有消费者，则有消费者，则有第3页，共51页，编辑于2022年，星期一对对偶偶规规划划前述的两个规划是同一问题的两个方面前述的两个规划是同一问题的两个方面前述的两个规划是同一问题的两个方面前述的两个规划是同一问题的两个方面:n n消费者希望费用最低；消费者希望费用最低；n n营养厂家希望收益最大。营养厂家希望收益最大。营养厂家希望收益最大。营养厂家希望收益最大。这一对问题即是我们要研究的线性规划
4、的对偶问题这一对问题即是我们要研究的线性规划的对偶问题这一对问题即是我们要研究的线性规划的对偶问题这一对问题即是我们要研究的线性规划的对偶问题.第4页，共51页，编辑于2022年，星期一对对偶偶规规划划n n对称形式下对偶规划对称形式下对偶规划对称形式下对偶规划对称形式下对偶规划考虑以下两种形式的线性规划问题考虑以下两种形式的线性规划问题考虑以下两种形式的线性规划问题考虑以下两种形式的线性规划问题第5页，共51页，编辑于2022年，星期一对对偶偶规规划划定义定义定义定义2.12.1 称以上两种形式的线性规划问题为一对对偶线性规划问题，称以上两种形式的线性规划问题为一对对偶线性规划问题，称以上两
5、种形式的线性规划问题为一对对偶线性规划问题，称以上两种形式的线性规划问题为一对对偶线性规划问题，其中其中其中其中LPLP问题为原规划，问题为原规划，问题为原规划，问题为原规划，LDLD问题为对偶规划。问题为对偶规划。问题为对偶规划。问题为对偶规划。其矩阵形式表示为其矩阵形式表示为其矩阵形式表示为其矩阵形式表示为其中其中其中其中定义定义定义定义2.22.2 满足下列条件的线性规划问题为成为具有满足下列条件的线性规划问题为成为具有满足下列条件的线性规划问题为成为具有满足下列条件的线性规划问题为成为具有对称形式对称形式对称形式对称形式：变：变：变：变量均具有非负约束；当目标求极小时约束条件均为量均具
6、有非负约束；当目标求极小时约束条件均为量均具有非负约束；当目标求极小时约束条件均为量均具有非负约束；当目标求极小时约束条件均为“”，当目，当目，当目，当目标求极大时约束条件均为标求极大时约束条件均为标求极大时约束条件均为标求极大时约束条件均为“”。第6页，共51页，编辑于2022年，星期一对对偶偶规规划划如果将对偶规划如果将对偶规划如果将对偶规划如果将对偶规划(LD)(LD)作为原规划，其形式为作为原规划，其形式为作为原规划，其形式为作为原规划，其形式为其对偶规划是其对偶规划是其对偶规划是其对偶规划是即是原规划即是原规划即是原规划即是原规划定理定理定理定理2.12.1 对偶规划的对偶规划是原规
7、划，即对偶规划的对偶规划是原规划，即对偶规划的对偶规划是原规划，即对偶规划的对偶规划是原规划，即LDLD是是是是LPLP的对偶的对偶的对偶的对偶规划时，规划时，规划时，规划时，LPLP也也也也是是是是LDLD的对偶规划。的对偶规划。的对偶规划。的对偶规划。第7页，共51页，编辑于2022年，星期一对对偶偶规规划划对称形式下原规划和对偶规划转换规则：对称形式下原规划和对偶规划转换规则：uu原规划原规划原规划原规划min问题问题问题问题，对偶规划对偶规划对偶规划对偶规划maxmax问题问题问题问题uu右端项与目标系数互相转换；右端项与目标系数互相转换；右端项与目标系数互相转换；右端项与目标系数互相
8、转换；uu系数矩阵互为转置关系；系数矩阵互为转置关系；系数矩阵互为转置关系；系数矩阵互为转置关系；uu原规划约束条件对应对偶规划的变量原规划约束条件对应对偶规划的变量原规划约束条件对应对偶规划的变量原规划约束条件对应对偶规划的变量 约束，对偶规划约束，对偶规划约束，对偶规划约束，对偶规划对应对应对应对应 的变量的变量的变量的变量 0 0 0 0；uu原规划的变量对应对偶规划的约束条件原规划的变量对应对偶规划的约束条件原规划的变量对应对偶规划的约束条件原规划的变量对应对偶规划的约束条件变量变量变量变量 0 0 0 0，对偶规划中对偶规划中对偶规划中对偶规划中对应对应 的约束为的约束为的约束为的约
9、束为 约束约束约束约束非对称形式下的特点非对称形式下的特点线性规划问题的约束条件有线性规划问题的约束条件有线性规划问题的约束条件有线性规划问题的约束条件有 、=、约约约约束，变量中有束，变量中有束，变量中有束，变量中有 0 0 0 0、00、自由、自由、自由、自由变量变量变量变量第8页，共51页，编辑于2022年，星期一对对偶偶规规划划n n非对称形式下对偶规划非对称形式下对偶规划非对称形式下对偶规划非对称形式下对偶规划例例例例2.12.1 写出下述线性规划问题的对偶规划写出下述线性规划问题的对偶规划写出下述线性规划问题的对偶规划写出下述线性规划问题的对偶规划第9页，共51页，编辑于2022年
10、，星期一对对偶偶规规划划将约束全变为将约束全变为将约束全变为将约束全变为“”此问题的对偶问题为此问题的对偶问题为此问题的对偶问题为此问题的对偶问题为第10页，共51页，编辑于2022年，星期一对对偶偶规规划划此问题的对偶问题为此问题的对偶问题为此问题的对偶问题为此问题的对偶问题为第11页，共51页，编辑于2022年，星期一对对偶偶规规划划非对称形式下原规划和对偶规划转换规则：非对称形式下原规划和对偶规划转换规则：非对称形式下原规划和对偶规划转换规则：非对称形式下原规划和对偶规划转换规则：uu原规划原规划原规划原规划min问题问题，对偶规划对偶规划对偶规划对偶规划maxmax问题问题问题问题uu
11、右端项与目标系数互相转换；右端项与目标系数互相转换；右端项与目标系数互相转换；右端项与目标系数互相转换；uu系数矩阵互为转置关系；系数矩阵互为转置关系；系数矩阵互为转置关系；系数矩阵互为转置关系；uu原规划约束条件原规划约束条件t t 约束，对偶规划约束，对偶规划约束，对偶规划约束，对偶规划对应对应 的变量的变量的变量的变量 0 0 0 0；t t 约束，对偶规划约束，对偶规划约束，对偶规划约束，对偶规划对应对应对应对应 的变量的变量 0 0 0 0；t t=约束，对偶规划约束，对偶规划约束，对偶规划约束，对偶规划对应对应对应对应 的变量无约束的变量无约束的变量无约束的变量无约束(自由变量自由
12、变量自由变量自由变量)；uu原规划的变量约束原规划的变量约束原规划的变量约束原规划的变量约束t t 0 0 0 0的变量的变量，对偶规划中对偶规划中对偶规划中对偶规划中对应对应对应对应 的约束为的约束为的约束为的约束为 约束；约束；t t 0 0的变量的变量，对偶规划中对偶规划中对应对应对应对应 的约束为的约束为 约束；约束；约束；约束；t t自由变量自由变量，对偶规划中对偶规划中对偶规划中对偶规划中对应对应对应对应 的约束为的约束为的约束为的约束为=约束。约束。约束。约束。第12页，共51页，编辑于2022年，星期一对对偶偶规规划划例例例例2.22.2 写出下述线性规划问题的对偶规划写出下述
13、线性规划问题的对偶规划写出下述线性规划问题的对偶规划写出下述线性规划问题的对偶规划第13页，共51页，编辑于2022年，星期一2.2对偶定理对偶定理为便于讨论，本节仅对对称形式的对偶规划进行讨论，非对称形为便于讨论，本节仅对对称形式的对偶规划进行讨论，非对称形为便于讨论，本节仅对对称形式的对偶规划进行讨论，非对称形为便于讨论，本节仅对对称形式的对偶规划进行讨论，非对称形式的对偶规划同样可证明类似的结论。式的对偶规划同样可证明类似的结论。式的对偶规划同样可证明类似的结论。式的对偶规划同样可证明类似的结论。为方便起见，为方便起见，为方便起见，为方便起见，LPLP简称为简称为简称为简称为P,LDP,
14、LD简称为简称为简称为简称为D D。第14页，共51页，编辑于2022年，星期一对对偶偶定定理理1.1.弱对偶定理弱对偶定理弱对偶定理弱对偶定理定理定理定理定理2.22.2 设设设设x x0 0是是是是P P的可行解，的可行解，的可行解，的可行解，w w0 0是是是是D D的可行解，则的可行解，则的可行解，则的可行解，则1)1)cxcx0 0 w w0 0b b；uu若若若若x x*、w w*分别是分别是分别是分别是P P、D D的可行解且的可行解且的可行解且的可行解且cxcx*=w w*b b，则则则则x x*、w w*分别分别分别分别是是是是P P、D D的最优解；的最优解；的最优解；的最
15、优解；1)1)若若若若P P、D D中有一个目标函数值无界，则另一个可行域为空中有一个目标函数值无界，则另一个可行域为空中有一个目标函数值无界，则另一个可行域为空中有一个目标函数值无界，则另一个可行域为空集；集；集；集；2)2)P P、D D都有最优解的充要条件是都有最优解的充要条件是都有最优解的充要条件是都有最优解的充要条件是P P、D D都有可行解。都有可行解。都有可行解。都有可行解。证：证：证：证：1)1)因为因为因为因为AxAx0 0 b b，x x0 0 0 0，w w0 0A A c c，w w0 0 0 0，对，对，对，对AxAx0 0 b b两边左乘两边左乘两边左乘两边左乘w
16、w0 0则有则有则有则有w w0 0AxAx0 0 w w0 0b b；对；对；对；对w w0 0A A c c两边右乘两边右乘两边右乘两边右乘x x0 0则有则有则有则有w w0 0AxAx0 0 c cx x0 0；从；从；从；从而有而有而有而有cxcx0 0 w w0 0b b。2)2)设设设设x x0 0是是是是P P的任意可行解，由的任意可行解，由的任意可行解，由的任意可行解，由1)1)有有有有cxcx0 0 w w*b=cxb=cx*从而从而从而从而x x*是是是是P P的最的最的最的最优解；同样可证优解；同样可证优解；同样可证优解；同样可证w w*是是是是D D的最优解。的最优解
17、。的最优解。的最优解。用用用用1)1)的结论可容易证明的结论可容易证明的结论可容易证明的结论可容易证明3)3)和和和和4)4)成立。成立。成立。成立。第15页，共51页，编辑于2022年，星期一对对偶偶定定理理2.2.强强强强对偶定理对偶定理对偶定理对偶定理定理定理定理定理2.32.3 一对一对一对一对对偶规划对偶规划对偶规划对偶规划P P和和和和D D中的一个有最优解的充要条件是中的一个有最优解的充要条件是中的一个有最优解的充要条件是中的一个有最优解的充要条件是另一个有最优解，且两问题的最优值相等。另一个有最优解，且两问题的最优值相等。另一个有最优解，且两问题的最优值相等。另一个有最优解，且
18、两问题的最优值相等。证：对问题证：对问题证：对问题证：对问题P P引入松弛变量引入松弛变量引入松弛变量引入松弛变量v v=(=(x xn n+1+1,x xn+mn+m)T T将其变成将其变成将其变成将其变成设该问题的最优解为设该问题的最优解为设该问题的最优解为设该问题的最优解为x x*，B B为最优基，则有为最优基，则有为最优基，则有为最优基，则有令令令令w w*=*=c cB BB B-1 1，则有，则有，则有，则有w*w*是是是是D D的可行解又的可行解又的可行解又的可行解又w*bw*b=c cB BB B-1 1b b=cxcx*，由定理，由定理，由定理，由定理2.22.2可知可知可知
19、可知w*w*是是是是D D的最优解。的最优解。的最优解。的最优解。第16页，共51页，编辑于2022年，星期一对对偶偶定定理理3.3.互补松弛定理及其应用互补松弛定理及其应用互补松弛定理及其应用互补松弛定理及其应用定理定理定理定理2.42.4(互补松弛定理互补松弛定理互补松弛定理互补松弛定理)已知已知已知已知x*,w*x*,w*分别是分别是分别是分别是P P和和和和D D的可行解，的可行解，的可行解，的可行解，则它们分别是则它们分别是则它们分别是则它们分别是P P和和和和D D的最优解的充要条件是的最优解的充要条件是的最优解的充要条件是的最优解的充要条件是w*w*(Ax*Ax*-b b)=0
20、0,(c c-w*A w*A)x*=x*=0 0证：因为证：因为证：因为证：因为x*,w*x*,w*分别是分别是分别是分别是P P和和和和D D的可行解，从而的可行解，从而的可行解，从而的可行解，从而w*b w*b w*Ax*cx*cx*必要性：若必要性：若必要性：若必要性：若x*,w*x*,w*分别是分别是分别是分别是P P和和和和D D的最优解，则的最优解，则的最优解，则的最优解，则w*b=w*b=cx*cx*，从而上式，从而上式，从而上式，从而上式中两中两中两中两“”号等式成立，显然结论成立。号等式成立，显然结论成立。号等式成立，显然结论成立。号等式成立，显然结论成立。充分性：充分性：充
21、分性：充分性：若若若若w*w*(Ax*Ax*-b b)=0 0，则则则则w*Ax*=w*bw*Ax*=w*b，若若若若(c c-w*A w*A)x*=x*=0 0，则则则则cx*=w*Ax*cx*=w*Ax*从而从而从而从而cx*=w*bcx*=w*b，即，即，即，即x*,w*x*,w*分别是分别是分别是分别是P P和和和和D D的最优解的最优解的最优解的最优解第17页，共51页，编辑于2022年，星期一对对偶偶定定理理将互补松弛定理的结论写成如下形式：将互补松弛定理的结论写成如下形式：将互补松弛定理的结论写成如下形式：将互补松弛定理的结论写成如下形式：以上两式表示以上两式表示以上两式表示以上
22、两式表示P P规划的约束严格不等号成立规划的约束严格不等号成立规划的约束严格不等号成立规划的约束严格不等号成立(松松松松)时，时，时，时，D D规划相应的变量必取规划相应的变量必取规划相应的变量必取规划相应的变量必取0(0(紧紧紧紧)；D D规划的约束严格不等号成立规划的约束严格不等号成立规划的约束严格不等号成立规划的约束严格不等号成立(松松松松)时，时，时，时，P P规划相应的变量规划相应的变量规划相应的变量规划相应的变量必取必取必取必取0(0(紧紧紧紧)，非基变量；，非基变量；，非基变量；，非基变量；第二式也就是第二式也就是第二式也就是第二式也就是 j j x xj j=0(=0(j j=
23、1,2,=1,2,n n)表示在表示在表示在表示在P P规划中检验数与变量互规划中检验数与变量互规划中检验数与变量互规划中检验数与变量互为松弛。为松弛。为松弛。为松弛。第18页，共51页，编辑于2022年，星期一对对偶偶定定理理例例例例2.3 2.3 求解线性规划问题求解线性规划问题求解线性规划问题求解线性规划问题其对偶问题：其对偶问题：其对偶问题：其对偶问题：第19页，共51页，编辑于2022年，星期一对对偶偶定定理理对偶规划是两个变量的问题可用图解法求解，得对偶规划对偶规划是两个变量的问题可用图解法求解，得对偶规划对偶规划是两个变量的问题可用图解法求解，得对偶规划对偶规划是两个变量的问题可
24、用图解法求解，得对偶规划的最优解的最优解的最优解的最优解显然，第显然，第显然，第显然，第1 1、5 5个约束等式成立，个约束等式成立，个约束等式成立，个约束等式成立，其它严格不等式成立，由互补其它严格不等式成立，由互补其它严格不等式成立，由互补其它严格不等式成立，由互补松弛定理原规划的最优解中松弛定理原规划的最优解中松弛定理原规划的最优解中松弛定理原规划的最优解中x x2 2*=x x3 3*=*=x x4 4*=0=0，因为，因为，因为，因为w w1 1*和和和和w w2 2*均不均不均不均不等于等于等于等于0 0，从而原规划的最优解中，从而原规划的最优解中，从而原规划的最优解中，从而原规划
25、的最优解中两个约束是紧的，即两个约束是紧的，即两个约束是紧的，即两个约束是紧的，即第20页，共51页，编辑于2022年，星期一对对偶偶定定理理例例例例2.4 2.4 求解线性规划问题求解线性规划问题求解线性规划问题求解线性规划问题的对偶问题：的对偶问题：的对偶问题：的对偶问题：第21页，共51页，编辑于2022年，星期一对对偶偶定定理理用单纯形表格求解线性规划问题用单纯形表格求解线性规划问题用单纯形表格求解线性规划问题用单纯形表格求解线性规划问题第22页，共51页，编辑于2022年，星期一对对偶偶定定理理原问题的最优解为原问题的最优解为原问题的最优解为原问题的最优解为对偶问题的最优解为对偶问题
26、的最优解为对偶问题的最优解为对偶问题的最优解为第23页，共51页，编辑于2022年，星期一作业作业P74P74：4 4，5 5，7 7第24页，共51页，编辑于2022年，星期一2.3对偶单纯形法对偶单纯形法1.理论基础理论基础理论基础理论基础考虑线性规划标准形考虑线性规划标准形考虑线性规划标准形考虑线性规划标准形其对偶规划为其对偶规划为其对偶规划为其对偶规划为第25页，共51页，编辑于2022年，星期一对对偶偶单单纯纯形形法法n n由对偶定理，若有由对偶定理，若有由对偶定理，若有由对偶定理，若有x*,w*x*,w*满足满足满足满足Ax*Ax*=b b,x*x*0,0,0,0,w*A w*A
27、c c,cx*=w*bcx*=w*b，则，则，则，则x*,w*x*,w*是是是是P,DP,D的最优解；的最优解；的最优解；的最优解；n n考虑单纯形法的迭代过程，若考虑单纯形法的迭代过程，若考虑单纯形法的迭代过程，若考虑单纯形法的迭代过程，若x x是基可行解，是基可行解，是基可行解，是基可行解，B B是相应的可行基，是相应的可行基，是相应的可行基，是相应的可行基，则则则则AxAx=b b,x x 0 0 0 0。令令令令w=cw=cB BB B-1 1，则，则，则，则cx=wbcx=wb，检验数可表示为，检验数可表示为，检验数可表示为，检验数可表示为=c=c-c cB BB B-1 1A=c
28、A=c wAwA；n n在单纯形法的迭代中，对偶定理中的在单纯形法的迭代中，对偶定理中的在单纯形法的迭代中，对偶定理中的在单纯形法的迭代中，对偶定理中的4 4个条件由个条件由个条件由个条件由3 3个条件个条件个条件个条件AxAx=b b,x x 0,0,0,0,cx=wbcx=wb始终满足；始终满足；始终满足；始终满足；n n单纯形法的迭代过程实际上可看作验证检验数是否满足单纯形法的迭代过程实际上可看作验证检验数是否满足单纯形法的迭代过程实际上可看作验证检验数是否满足单纯形法的迭代过程实际上可看作验证检验数是否满足 0 0 0 0的过程，也就是验证的过程，也就是验证的过程，也就是验证的过程，也
29、就是验证D D问题约束条件问题约束条件问题约束条件问题约束条件wAwA c c是否满足的是否满足的是否满足的是否满足的过程过程过程过程;n n单纯形法迭代也可看作是从原问题单纯形法迭代也可看作是从原问题单纯形法迭代也可看作是从原问题单纯形法迭代也可看作是从原问题P P的基可行解逐步迭代到对的基可行解逐步迭代到对的基可行解逐步迭代到对的基可行解逐步迭代到对偶问题偶问题偶问题偶问题D D的可行解的过程（两问题的目标函数值始终相等）。的可行解的过程（两问题的目标函数值始终相等）。的可行解的过程（两问题的目标函数值始终相等）。的可行解的过程（两问题的目标函数值始终相等）。n n对偶单纯形法的本质是从对
30、偶问题的可行解逐步迭代到原问题对偶单纯形法的本质是从对偶问题的可行解逐步迭代到原问题对偶单纯形法的本质是从对偶问题的可行解逐步迭代到原问题对偶单纯形法的本质是从对偶问题的可行解逐步迭代到原问题P P的可行解的过程。的可行解的过程。的可行解的过程。的可行解的过程。第26页，共51页，编辑于2022年，星期一对对偶偶单单纯纯形形法法n n定义定义定义定义 若若若若A A=(=(=(=(B,NB,N),),),),其中其中其中其中B B非奇异，非奇异，非奇异，非奇异，w=cw=cB BB B-1-1-1-1称为称为称为称为D D的一个的一个的一个的一个基解基解基解基解，若若若若c c-c cB BB
31、 B-1-1-1-1A A 0,0,0,0,即即即即wAwAc c，称，称，称，称w w为为为为D D的一个的一个的一个的一个基可行解基可行解基可行解基可行解，此时称，此时称，此时称，此时称B B为原规划的一个为原规划的一个为原规划的一个为原规划的一个正则基正则基正则基正则基，称为原规划问题的一个称为原规划问题的一个称为原规划问题的一个称为原规划问题的一个正则正则正则正则基解基解基解基解。n n对偶单纯形法的基本思想对偶单纯形法的基本思想对偶单纯形法的基本思想对偶单纯形法的基本思想：若有一个正则基：若有一个正则基：若有一个正则基：若有一个正则基B B，则，则，则，则w=cw=cB BB B-1
32、-1-1-1满足满足满足满足wAwA c c，Ax=bAx=b，cx=wbcx=wb，若，若，若，若x x 0 0 0 0，则，则，则，则x x已是最优解，否则求另一已是最优解，否则求另一已是最优解，否则求另一已是最优解，否则求另一个正则基解，直到满足若个正则基解，直到满足若个正则基解，直到满足若个正则基解，直到满足若x x 0 0 0 0为止。为止。为止。为止。n n原规划单纯形迭代是在满足原规划单纯形迭代是在满足原规划单纯形迭代是在满足原规划单纯形迭代是在满足Ax=bAx=b和和和和x x 0 0 0 0前提前提前提前提下逐步使解达到最下逐步使解达到最下逐步使解达到最下逐步使解达到最优；对
33、偶单纯形法迭代是在满足优；对偶单纯形法迭代是在满足优；对偶单纯形法迭代是在满足优；对偶单纯形法迭代是在满足Ax=bAx=b和最优性条件和最优性条件和最优性条件和最优性条件前提前提前提前提下逐步下逐步下逐步下逐步使解满足使解满足使解满足使解满足x x 0 0 0 0。第27页，共51页，编辑于2022年，星期一对对偶偶单单纯纯形形法法2 2.对偶单纯形表格对偶单纯形表格对偶单纯形表格对偶单纯形表格不妨设前不妨设前不妨设前不妨设前mm个为基变量，表格形式仍然如同单纯形表格个为基变量，表格形式仍然如同单纯形表格个为基变量，表格形式仍然如同单纯形表格个为基变量，表格形式仍然如同单纯形表格区别在于检验数
34、始终满足区别在于检验数始终满足区别在于检验数始终满足区别在于检验数始终满足j j 0 0，不再要求不再要求不再要求不再要求b bi 0 0 0 0。迭代思想是，迭代思想是，迭代思想是，迭代思想是，如果如果如果如果b br r0，则为则为则为则为x xr r出基变量；选进基变量出基变量；选进基变量出基变量；选进基变量出基变量；选进基变量xk k使所有使所有使所有使所有 j j 0 0仍然成仍然成仍然成仍然成立，进行转轴变换使立，进行转轴变换使立，进行转轴变换使立，进行转轴变换使x xk k所在列为单位向量。所在列为单位向量。所在列为单位向量。所在列为单位向量。第28页，共51页，编辑于2022年
35、，星期一对对偶偶单单纯纯形形法法对检验数行消元之后，目标函数形式为对检验数行消元之后，目标函数形式为对检验数行消元之后，目标函数形式为对检验数行消元之后，目标函数形式为为保证为保证为保证为保证j j 0 0 0 0仍然成立，显然下式确定的仍然成立，显然下式确定的仍然成立，显然下式确定的仍然成立，显然下式确定的k k即可即可即可即可如果如果如果如果y yr,jr,j 0 0，则原问题无可行解。则原问题无可行解。则原问题无可行解。则原问题无可行解。如何使所有如何使所有如何使所有如何使所有 j j 0 0仍然成立，考虑仍然成立，考虑仍然成立，考虑仍然成立，考虑x xr r所在方程和目标函数。所在方程
36、和目标函数。所在方程和目标函数。所在方程和目标函数。第29页，共51页，编辑于2022年，星期一对对偶偶单单纯纯形形法法例例例例2.6 2.6 用对偶单纯形法求解下述线性规划问题用对偶单纯形法求解下述线性规划问题用对偶单纯形法求解下述线性规划问题用对偶单纯形法求解下述线性规划问题解：转化为标准形解：转化为标准形解：转化为标准形解：转化为标准形取取取取x x4 4,x,x5 5为基变量，方程两边乘以为基变量，方程两边乘以为基变量，方程两边乘以为基变量，方程两边乘以-1 1，则有如下标准形，则有如下标准形，则有如下标准形，则有如下标准形第30页，共51页，编辑于2022年，星期一对对偶偶单单纯纯形
37、形法法此问题此问题此问题此问题x x4 4,x,x5 5为基变量时，检验数均为正，是一个正则基，为基变量时，检验数均为正，是一个正则基，为基变量时，检验数均为正，是一个正则基，为基变量时，检验数均为正，是一个正则基，对偶单纯形表格为对偶单纯形表格为对偶单纯形表格为对偶单纯形表格为x x4 4为出基变量，为出基变量，为出基变量，为出基变量，x x2 2为进基变量，以为进基变量，以为进基变量，以为进基变量，以y y1212为主元做转轴变换得为主元做转轴变换得为主元做转轴变换得为主元做转轴变换得第31页，共51页，编辑于2022年，星期一对对偶偶单单纯纯形形法法x x5 5为出基变量，为出基变量，为
38、出基变量，为出基变量，x x3 3为进基变量，以为进基变量，以为进基变量，以为进基变量，以y y2323为主元做转轴变换得为主元做转轴变换得为主元做转轴变换得为主元做转轴变换得原问题的最优解原问题的最优解原问题的最优解原问题的最优解x x=(0,)=(0,)T T，最优值，最优值，最优值，最优值z z*=17/2*=17/2。第32页，共51页，编辑于2022年，星期一作业作业P77P77：8 8第33页，共51页，编辑于2022年，星期一2.4 灵敏度分析灵敏度分析1.1.1.1.目标系数的灵敏度分析目标系数的灵敏度分析目标系数的灵敏度分析目标系数的灵敏度分析1)1)1)1)目标系数变化对最
39、优解的影响目标系数变化对最优解的影响目标系数变化对最优解的影响目标系数变化对最优解的影响为为为为求求求求出出出出数数数数据据据据变变变变化化化化后后后后的的的的最最最最优优优优解解解解，不不不不必必必必从从从从最最最最初初初初的的的的阶阶阶阶段段段段开开开开始始始始求求求求解解解解，仅仅仅仅从从从从原原原原问问问问题题题题最最最最后后后后的的的的单单单单纯纯纯纯形形形形表表表表的的的的基基基基础础础础之之之之上上上上，重重重重新新新新计计计计算算算算检检检检验验验验数数数数，然后求出最优解并与原最优解比较。然后求出最优解并与原最优解比较。然后求出最优解并与原最优解比较。然后求出最优解并与原最优
40、解比较。2)2)2)2)不影响最优基变化时系数不影响最优基变化时系数不影响最优基变化时系数不影响最优基变化时系数c c c ck k的变化范围的变化范围的变化范围的变化范围灵敏度分析，是讨论线性规划问题中原始数据灵敏度分析，是讨论线性规划问题中原始数据灵敏度分析，是讨论线性规划问题中原始数据灵敏度分析，是讨论线性规划问题中原始数据a aij ij，b bi i，c cj j的变化对最的变化对最的变化对最的变化对最优解的影响，所谓对最优解的影响主要有两个层面，一是对最优优解的影响，所谓对最优解的影响主要有两个层面，一是对最优优解的影响，所谓对最优解的影响主要有两个层面，一是对最优优解的影响，所谓
41、对最优解的影响主要有两个层面，一是对最优解的影响，另一是当某个数据在什么范围内变化时，最优基将不解的影响，另一是当某个数据在什么范围内变化时，最优基将不解的影响，另一是当某个数据在什么范围内变化时，最优基将不解的影响，另一是当某个数据在什么范围内变化时，最优基将不会改变。本节讨论会改变。本节讨论会改变。本节讨论会改变。本节讨论b bi i和和和和c cj j的变化、增加变量对最优解的影响。的变化、增加变量对最优解的影响。的变化、增加变量对最优解的影响。的变化、增加变量对最优解的影响。第34页，共51页，编辑于2022年，星期一灵灵敏敏度度分分析析设设设设目目目目标标标标系系系系数数数数ck k
42、的的的的改改改改变变变变量量量量为为为为 ,其其其其中中中中 为为为为变变变变化化化化之之之之后后后后的系数。的系数。的系数。的系数。n n当当当当x xk k不不不不是是是是基基基基变变变变量量量量时时时时，此此此此时时时时只只只只对对对对检检检检验验验验数数数数k k产产产产生生生生影影影影响响响响，只只只只要考虑保持要考虑保持要考虑保持要考虑保持 k k 0 0即可。即可。即可。即可。n n当当当当x xk k是是基基变变量量时时，此此时时ck k的的的的变变变变化化化化将将将将对对对对所所所所有有有有检检检检验验验验数数数数产产产产生生生生影响。设影响。设影响。设影响。设xk k对应第
43、对应第i i个方程，基的新旧目标系数为个方程，基的新旧目标系数为第35页，共51页，编辑于2022年，星期一灵灵敏敏度度分分析析第36页，共51页，编辑于2022年，星期一灵灵敏敏度度分分析析例例例例2.72.7 某某某某工工工工厂厂厂厂用用用用甲甲甲甲乙乙乙乙两两两两种种种种原原原原料料料料生生生生产产产产A A、B B、C C、D D四四四四种种种种产产产产品品品品，每每每每种种种种产产产产品品品品的的的的利利利利润润润润、原原原原料料料料数数数数量量量量、每每每每种种种种产产产产品品品品消消消消耗耗耗耗原原原原料料料料定定定定额额额额如如如如下下下下表表表表所示：所示：所示：所示：问应怎
44、样组织生产才能使总利润最大？如果产品问应怎样组织生产才能使总利润最大？如果产品问应怎样组织生产才能使总利润最大？如果产品问应怎样组织生产才能使总利润最大？如果产品A A、D D的的的的利润均变到利润均变到利润均变到利润均变到1515万元，最优解有何变化？又各产品的利润在何范万元，最优解有何变化？又各产品的利润在何范万元，最优解有何变化？又各产品的利润在何范万元，最优解有何变化？又各产品的利润在何范围内变化时，最优基不变围内变化时，最优基不变围内变化时，最优基不变围内变化时，最优基不变？解：解：解：解：1)1)设设设设x x1 1，x x2 2，x x3 3，x x4 4分别表示分别表示分别表示
45、分别表示A A、B B、C C、D D四种产品的生产数四种产品的生产数四种产品的生产数四种产品的生产数量，可建立如下模型：量，可建立如下模型：量，可建立如下模型：量，可建立如下模型：第37页，共51页，编辑于2022年，星期一灵灵敏敏度度分分析析化为标准形化为标准形化为标准形化为标准形用单纯形法得到最后一个表格如下，最优解产品用单纯形法得到最后一个表格如下，最优解产品用单纯形法得到最后一个表格如下，最优解产品用单纯形法得到最后一个表格如下，最优解产品C C生产生产生产生产1 1万万万万件，产品件，产品件，产品件，产品D D生产生产生产生产2 2万件，总利润万件，总利润万件，总利润万件，总利润8
46、888万元。万元。万元。万元。第38页，共51页，编辑于2022年，星期一灵灵敏敏度度分分析析2)2)计算计算计算计算c c c c1 1 1 1，c c c c4 4 4 4改变后的检验数代入上表格改变后的检验数代入上表格改变后的检验数代入上表格改变后的检验数代入上表格(在当前基下在当前基下在当前基下在当前基下)第39页，共51页，编辑于2022年，星期一灵灵敏敏度度分分析析3)3)讨论讨论讨论讨论c cj j(j j=1,2,3,4)=1,2,3,4)的变化范围的变化范围的变化范围的变化范围(1)(1)(1)(1)非非非非基基基基变变变变量量量量x x1 1，x x2 2的的的的检检检检验
47、验验验数数数数为为为为 1 1=4 4，2 2=2/32/3，系系系系数数数数的的的的变变变变化范围是化范围是化范围是化范围是从而从而从而从而c c1 1，c c2 2变化范围分别是变化范围分别是变化范围分别是变化范围分别是(2)(2)(2)(2)基变量基变量基变量基变量x x3 3，x x4 4的系数的系数的系数的系数，先考虑，先考虑，先考虑，先考虑c c3 3变化范围变化范围变化范围变化范围第40页，共51页，编辑于2022年，星期一灵灵敏敏度度分分析析从而从而从而从而c c3 3变化范围分别是变化范围分别是变化范围分别是变化范围分别是再考虑再考虑再考虑再考虑c c4 4变化范围变化范围变
48、化范围变化范围得到得到得到得到c c4 4变化范围分别是变化范围分别是变化范围分别是变化范围分别是第41页，共51页，编辑于2022年，星期一灵灵敏敏度度分分析析2.2.右端项的灵敏度分析右端项的灵敏度分析右端项的灵敏度分析右端项的灵敏度分析n n右右右右端端端端项项项项的的的的几几几几个个个个分分分分量量量量改改改改变变变变对对对对最最最最优优优优解解解解的的的的影影影影响响响响，此此此此时时时时不不不不影影影影响响响响检检检检验验验验数数数数，但但但但可可可可能能能能影影影影响响响响基基基基变变变变量量量量的的的的非非非非负负负负性性性性，如如如如果果果果B B-1-1-1-1b b 0
49、0 0 0，当当当当前前前前解解解解仍仍仍仍然然然然是是是是最最最最优优优优解，否则，用对偶单纯形法求出最优解。解，否则，用对偶单纯形法求出最优解。解，否则，用对偶单纯形法求出最优解。解，否则，用对偶单纯形法求出最优解。vv另另另另一一一一类类类类有有有有意意意意义义义义的的的的问问问问题题题题是是是是当当当当某某某某一一一一个个个个分分分分量量量量在在在在什什什什么么么么范范范范围围围围内内内内变变变变化化化化，才才才才不不不不影影影影响响响响基基基基变变变变量量量量，设设设设b bk k的的的的改改改改变变变变量量量量为为为为 ，记记记记当当当当前前前前最最最最优优优优解解解解的基解为的基
50、解为的基解为的基解为 ，改变后的基解为，改变后的基解为，改变后的基解为，改变后的基解为 ，则有，则有，则有，则有设设设设 ，如果，如果，如果，如果 ，则应有，则应有，则应有，则应有第42页，共51页，编辑于2022年，星期一灵灵敏敏度度分分析析因此，不改变当前最优基前提下因此，不改变当前最优基前提下因此，不改变当前最优基前提下因此，不改变当前最优基前提下b bk k的变化范围是的变化范围是的变化范围是的变化范围是例例例例2.8 2.8 考虑例考虑例考虑例考虑例2.72.7中在当前最优基下右端项的变化范围。中在当前最优基下右端项的变化范围。中在当前最优基下右端项的变化范围。中在当前最优基下右端项