第08次课--第二章对偶理论与灵敏度分析

1、 国防科技大学 1温故知新 国防科技大学 2第四节 单纯形法的进一步讨论 单纯形法进一步讨论的几个问题单纯形法进一步讨论的几个问题n单纯形法的异常情况处理单纯形法的异常情况处理退化问题退化问题l大大M M法法 n 人工变量的两种处理方法人工变量的两种处理方法l两阶段法两阶段法 n算法复杂性讨论算法复杂性讨论n检验数的几种表示形式检验数的几种表示形式 国防科技大学 3第四节 单纯形法的进一步讨论 第一阶段：第一阶段： 不考虑原问题是否存在基可行解，给原线性规划问题加不考虑原问题是否存在基可行解，给原线性规划问题加入人工变量，并构造入人工变量，并构造仅含人工变量仅含人工变量的目标函数的目标函数（人

2、工变量加（人工变量加和）和）并要求实现最小化，代替原问题目标函数，得到新的线并要求实现最小化，代替原问题目标函数，得到新的线性规划问题性规划问题。 用用单纯形法求解此新的线性规划问题，若目标函数不为单纯形法求解此新的线性规划问题，若目标函数不为零，则原问题无可行解，应停止计算，否则进入第二阶段。零，则原问题无可行解，应停止计算，否则进入第二阶段。 第二阶段：第二阶段： 对第一阶段计算得到的最终表：对第一阶段计算得到的最终表：去掉人工变量；去掉人工变量；目目标函数行的系数换成原问题的目标函数系数。作为第二阶段标函数行的系数换成原问题的目标函数系数。作为第二阶段计算的初始表，再求解。计算的初始表，

3、再求解。 两阶段法 国防科技大学 4第四节 单纯形法的进一步讨论 单纯形法进一步讨论的几个问题单纯形法进一步讨论的几个问题n单纯形法的异常情况处理单纯形法的异常情况处理退化问题退化问题l大大M M法法 n 人工变量的两种处理方法人工变量的两种处理方法l两阶段法两阶段法 n算法复杂性讨论算法复杂性讨论n检验数的几种表示形式检验数的几种表示形式 国防科技大学 5退化问题退化问题 第四节 单纯形法的进一步讨论 退化问题 单纯形法计算中用规则规则确定换出变量时，有时可能存在两个以上相同的最小值两个以上相同的最小值。这样在下一次迭代中就有一个或几个基变量等于零有一个或几个基变量等于零，这就出现退化解退化

4、解。 这时如果确定其中某个等于零的基变量为换出变量等于零的基变量为换出变量（可以等于零）可以等于零），迭代后目标函数值不变，这时不同基表示为同一个顶点。 国防科技大学 6退化问题退化问题 第四节 单纯形法的进一步讨论 出现退化时，就可能出现循环，永远达不出现退化时，就可能出现循环，永远达不到最优解。到最优解。退化问题 国防科技大学 7第四节 单纯形法的进一步讨论 有效避免循环勃兰特法则： 尽管计算过程的循环现象极少出现，但还是有可能。遵循勃兰特法则进行计算，一定能避免出现循环。退化问题 国防科技大学 8第四节 单纯形法的进一步讨论 单纯形法进一步讨论的几个问题单纯形法进一步讨论的几个问题n单纯

5、形法的异常情况处理单纯形法的异常情况处理退化问题退化问题l大大M M法法 n 人工变量的两种处理方法人工变量的两种处理方法l两阶段法两阶段法 n算法复杂性讨论算法复杂性讨论n检验数的几种表示形式检验数的几种表示形式 国防科技大学 9第四节 单纯形法的进一步讨论 检验数检验数1111BNBNBBNNZC B bCC B N XC B bC B NCX目标函数目标函数经变换可得：经变换可得：检验数判别的情况汇总表检验数判别的情况汇总表 国防科技大学 10第四节 单纯形法的进一步讨论 单纯形法进一步讨论的几个问题单纯形法进一步讨论的几个问题n单纯形法的异常情况处理单纯形法的异常情况处理退化问题退化问

6、题l大大M M法法 n 人工变量的两种处理方法人工变量的两种处理方法l两阶段法两阶段法 n算法复杂性讨论算法复杂性讨论n检验数的几种表示形式检验数的几种表示形式 国防科技大学 11第四节 单纯形法的进一步讨论 n算法复杂性讨论算法复杂性讨论单纯形法真是不好吗？单纯形法真是不好吗？实际上人们遇到的问题在使用单纯形算法时非常有效实际上人们遇到的问题在使用单纯形算法时非常有效! !l 实践表明迭代次数约为O(n)，即约在n与2n次之间l Smale发现单纯形法是“坏的”例子出现的概率是0l 1983年Samale证明单纯形方法平均运算次数是多项式次的算法复杂性算法复杂性 国防科技大学 12第二章第二

7、章 对偶理论与灵敏度分析对偶理论与灵敏度分析 第一节第一节 单纯形法的矩阵描述单纯形法的矩阵描述第二节第二节 改进单纯形法（软件实现）改进单纯形法（软件实现）第三节第三节 对偶问题的提出对偶问题的提出第四节第四节 线性规划的对偶理论线性规划的对偶理论第六节第六节 对偶单纯形法对偶单纯形法第七节第七节 灵敏度分析灵敏度分析 国防科技大学 13第一节第一节 单纯形法的矩阵描述单纯形法的矩阵描述 国防科技大学 14单纯形表单纯形表 1cmc1mcnc1mcc1mxx1mbb1m10011,1,1mm maa1nmnaa01,11mmii micc a1mniinicca0决策变量的价值系数决策变量的

8、价值系数基变量基变量基变量价值系数基变量价值系数基变量的取值基变量的取值基矩阵的逆矩阵左乘系数矩阵基矩阵的逆矩阵左乘系数矩阵B B-1-1A A值值决策变量的检验数决策变量的检验数第一节 单纯形法的矩阵描述 B-1bB-1AB-1(B,N)(I,B-1N)(B-1P1,B-1Pn)(0,CN-CBB-1N)？ 国防科技大学 15第一节 单纯形法的矩阵描述 从上述论述可以看出，在单纯形法的迭代过程中基矩阵的逆矩阵 求出后，单纯形表上的其他行和列也可随着确定。1B- 国防科技大学 16第一节 单纯形法的矩阵描述 国防科技大学 17第二节 改进单纯形法 假设已对线性规划模型进行标准化假设已对线性规划

9、模型进行标准化 国防科技大学 18基本过程基本过程 第二节 改进单纯形法 国防科技大学 19第二节 改进单纯形法 国防科技大学 20第二节 改进单纯形法 换入变量在单纯形换入变量在单纯形表中对应的列表中对应的列 国防科技大学 21第二节 改进单纯形法 国防科技大学 22第二节 改进单纯形法 ？ 国防科技大学 23怎样由 直接计算得到 ？第二节 改进单纯形法 1B1B 10001011,mmiirjsiriTjsiiBPPPPPB P 01111,mmmrrTjsiimTiiiiiirPBPPP因为所以 国防科技大学 24第二节 改进单纯形法 则1110 0001,rrrrmmiiiiiir s

10、rBPPP PPBE11010100010000100(,) 000000000001rmrrmiiiiiiiPPrr 行列 国防科技大学 25第二节 改进单纯形法 则又已知故只需求考虑增广矩阵0 0111r sBEB1B0 01r sE0 0()r sEI 国防科技大学 26第二节 改进单纯形法 11001000010000000001rrmriii10 0001 0000 1000 01 0 0()r sEI 国防科技大学 27第二节 改进单纯形法 经初等变换得：10001000100000001rrmriiiiiI 国防科技大学 28第二节 改进单纯形法 则100000100010000

11、0000rrmriiiiirr 0 01r sE行列改进单纯形法计算流程图改进单纯形法计算流程图 国防科技大学 30例例 1.11 用改进单纯形法求解以下线性规划问题：用改进单纯形法求解以下线性规划问题： 12123124125max250622101,5jZxxxxxxxxxxxxj 解： 1110051101002,1,0,0,06200121Abc 第二节 改进单纯形法 第一次迭代：第一次迭代： 第二次迭代：第二次迭代： 21611222616101110 0 20113002jBcC B P 取取02022sjjs 12300001611126161012 4 1011(, )3 3

12、3002ssssTTji ji ji jB PB P ， 31212300037732222241233339min,min,4sssiiii ji ji jaaa 0011,3rrii 决决定定202sjjxxx进进基基，103riixxx出出基基。 12312, ,2,4,1,5,3Ri i isjj 13311000104622112100121621110001106242B 12312415310421(,),21021104212TTiiiB ba aaa a a 9 1 11,4 2 4T 第三步迭代：第三步迭代： 11 9131,0,04 424TXZ 111222314211

13、12555112431421112333112400101 0 2210040101101 0 22100200jjBjBjjBjBcC B PcC B PcC B PcC B P 最最优优解解为为： *11 9131,0,044 42TXZ 国防科技大学 36编写改进单纯形法软件 基本要求：基本要求：1、用大M法，软件先设计，再编程实现2、以统一文本文件形式存储模型数据3、具有一定的人机交互，可以选择模型数据文本文件4、能对读入的模型数据进行错误检验5、计算结果写入结果文本文件6、通过测试题检验 国防科技大学 37编写改进单纯形法软件 参考意见：参考意见：1、手工标准化模型（不加入人工变量）

14、2、利用已有文本文件编辑工具实现模型数据编辑3、模型数据文本文件名与计算结果文本文件名相关4、用大M法，设一个全局变量，取为很大的值5、读入数据后，给每个约束加入一个人工变量，注意记录人工变量下标。 国防科技大学 38编写改进单纯形法软件 更高期望：更高期望：1、良好的人机交互界面（例如用表格形式表现）2、集成数据编辑、运算、结果输出等功能3、体现迭代过程，实现中间结果输出4、能用于求解上千维的问题，计算速度较快 国防科技大学 39n理解单纯形法的矩阵表示。理解单纯形法的矩阵表示。nP87 3.1（1）、）、3.2n开发改进单纯形法软件开发改进单纯形法软件课后作业课后作业 国防科技大学 40第

15、三节第三节 对偶问题的提出对偶问题的提出 国防科技大学 41第三节第三节 对偶问题的提出对偶问题的提出 对偶是普遍的现象：对偶是普遍的现象：两个黄鹂鸣翠柳，一行白鹭上青天。两个黄鹂鸣翠柳，一行白鹭上青天。 n 文学中的对称与美文学中的对称与美n 中国传统哲学中国传统哲学太极生两仪，两仪生四相，太极生两仪，两仪生四相，四相生八卦四相生八卦, , 易传易传落霞与孤鹜齐飞，秋水共长天一色落霞与孤鹜齐飞，秋水共长天一色. . 杜甫杜甫绝句绝句 王勃王勃滕王阁序滕王阁序 国防科技大学 42第三节第三节 对偶问题的提出对偶问题的提出 对偶是普遍的现象：对偶是普遍的现象：n 自然与艺术中的对称与美自然与艺术

16、中的对称与美 国防科技大学 43第三节第三节 对偶问题的提出对偶问题的提出 对偶是普遍的现象：对偶是普遍的现象：n初等数学的对称问题研究初等数学的对称问题研究n物理学中的对称与不对称物理学中的对称与不对称轴对称，中心对称轴对称，中心对称正物质与反物质；宇称不守恒；相对论与时间反演正物质与反物质；宇称不守恒；相对论与时间反演 国防科技大学 44第三节第三节 对偶问题的提出对偶问题的提出 对偶是普遍的现象：对偶是普遍的现象：n 外在与内心的对称外在与内心的对称人最大的烦恼往往是自己看自己的态度人最大的烦恼往往是自己看自己的态度 国防科技大学 45第三节第三节 对偶问题的提出对偶问题的提出 本节所讨

17、论的本节所讨论的对偶的含义对偶的含义是指：是指： 对同一事物（问题）从不同角度（立场）对同一事物（问题）从不同角度（立场）观察，有两种对立的表述。观察，有两种对立的表述。 如如“平面中矩形的面积与周长的关系平面中矩形的面积与周长的关系”，有两种表述：有两种表述： 1.1.周长一定，面积最大的矩形是？周长一定，面积最大的矩形是？ 2.2.面积一定，周长最短的矩形是？面积一定，周长最短的矩形是？正方形正方形 国防科技大学 46第三节第三节 对偶问题的提出对偶问题的提出 国防科技大学 47第三节第三节 对偶问题的提出对偶问题的提出 国防科技大学 48第三节第三节 对偶问题的提出对偶问题的提出 现假设

18、该工厂决定不生产产品现假设该工厂决定不生产产品、，而将其所有，而将其所有资源出租或出售。资源出租或出售。这时工厂就要考虑给每种资源如何定价的问题。这时工厂就要考虑给每种资源如何定价的问题。 国防科技大学 49第三节第三节 对偶问题的提出对偶问题的提出 国防科技大学 50第三节第三节 对偶问题的提出对偶问题的提出 1231213123min8161242243,0yyyyyyyy y y 国防科技大学 51原问题对偶问题第三节第三节 对偶问题的提出对偶问题的提出 12121212ax2328416412,0mZxxxxxxx x1231213123min8161242243,0yyyyyyyy

19、y y 国防科技大学 52第三节第三节 对偶问题的提出对偶问题的提出 线性规划的对偶问题是线性规划的重要课题之线性规划的对偶问题是线性规划的重要课题之一，它是为研究一对形式上对称，解的性质相互关一，它是为研究一对形式上对称，解的性质相互关联的线性规划问题而创立的联的线性规划问题而创立的 线性规划问题的对偶问题是线性规划问题的对偶问题是J.VonJ.Von Neumann Neumann于于19471947年提出的，并于年提出的，并于1950195019561956年期间创立并完善年期间创立并完善对偶理论。对偶理论。 国防科技大学 53max0zCXAXbXmin0YbYACY第三节第三节 对偶

20、问题的提出对偶问题的提出 原问题（对偶问题） 对偶问题（原问题） 现实意义：研究资源最优利用时，一是在资源定量下使收益最大；二是完成额定指标，使用资源最少，或因故出让资源以保证获利不低于原来水准（目标为买方，约束为卖方） 国防科技大学 54n对称形式的变换关系描述对称形式的变换关系描述A(mn)bC目标函数约束条件决策变量原问题（对偶问题）原问题（对偶问题）约束系数矩阵资源向量价值向量Max z=CXAX bX0(列向量列向量，n个元素个元素)对偶问题（原问题）对偶问题（原问题）约束系数矩阵的转置价值向量资源向量min=YbYACY0（行向量行向量，m个元素个元素）第三节第三节 对偶问题的提出

21、对偶问题的提出 国防科技大学 55n一个简单的例子一个简单的例子第三节第三节 对偶问题的提出对偶问题的提出 那么一般形式的线性规划问题如何找出对偶问题？那么一般形式的线性规划问题如何找出对偶问题？ 国防科技大学 56第三节第三节 对偶问题的提出对偶问题的提出 n一般形式到对称形式的转换一般形式到对称形式的转换n一般形式的变换关系描述一般形式的变换关系描述 国防科技大学 58第三节第三节 对偶问题的提出对偶问题的提出 国防科技大学 59123412341342341234min2353522460;00Zxxxxxxxxxxxxxxxxxx; 无约束例例 写出下述线性规划问题的对偶问题：写出下述

22、线性规划问题的对偶问题： 第三节第三节 对偶问题的提出对偶问题的提出 国防科技大学 601231213123123123max54622332510,0,zyyyyyyyyyyyyyyyy 无约束。 解：解： 上上述线性规划的对偶形式为：述线性规划的对偶形式为： 第三节第三节 对偶问题的提出对偶问题的提出 国防科技大学 61第三节第三节 对偶问题的提出对偶问题的提出 例例 写出下述线性规划问题的对偶问题：写出下述线性规划问题的对偶问题：12121212min110,0 xxxxxxxx 国防科技大学 62第三节第三节 对偶问题的提出对偶问题的提出 例例 写出下述线性规划问题的对偶问题：写出下述

23、线性规划问题的对偶问题：12341234123412341234max234356735812999200,0,0,Zxxxxxxxxxxxxxxxxxxxx无约束 国防科技大学 63第四节第四节 线性规划的对偶理论线性规划的对偶理论 国防科技大学 64max0zCXAXbXmin0YbYACY考察考察 原问题 对偶问题第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 国防科技大学 65n对偶问题的基本性质对偶问题的基本性质 第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 （1 1）对称性）对称性 对偶问题的对偶是原问题。对偶问题的对偶是原问题。 国防科技大学 66n对偶

24、问题的基本性质对偶问题的基本性质 第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 （4 4）强对偶性）强对偶性( (或称对偶定理或称对偶定理) ) 若原问题有最优解，那么对若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。偶问题也有最优解，且目标函数值相等。（5 5）互补松弛性）互补松弛性 在线性规划问题的在线性规划问题的最优解最优解中，如果对应中，如果对应某一某一约束条件的对偶变量值为非零约束条件的对偶变量值为非零，则该，则该约束条件取等式约束条件取等式；反之如果反之如果约束条件取严格不等式约束条件取严格不等式，则其，则其对应的对偶变量一对应的对偶变量一定为零定为零。

25、国防科技大学 67（1 1）对称性对称性 对偶问题的对偶是原问题对偶问题的对偶是原问题第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 原问题原问题对偶问题对偶问题对偶问题的对偶问题对偶问题的对偶问题问题变换问题变换问题变换问题变换原问题原问题 国防科技大学 68第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 国防科技大学 69（4 4）强对偶性）强对偶性( (或称对偶定理或称对偶定理) ) 若原问题有最优解，那么对偶问题也有最优若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。解，且目标函数值相等。 第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论

26、国防科技大学 70弱对偶性与强对偶性的几个推论弱对偶性与强对偶性的几个推论 1.1.原问题任一可行解的目标函数值是其对偶问题目标函数原问题任一可行解的目标函数值是其对偶问题目标函数值的值的下界下界；反之对偶问题任一可行解的目标函数值是其原；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的问题目标函数值的上界。上界。 2.2.如原问题有可行解且目标函数值无界如原问题有可行解且目标函数值无界( (具有无界解具有无界解) )，则，则其对偶问题无可行解；同理对偶问题有可行解且目标函数其对偶问题无可行解；同理对偶问题有可行解且目标函数值无界，则其原问题无可行解值无界，则其原问题无可行解。 ( (

27、注意：此推论的逆不成立，当对偶问题无可行解时，注意：此推论的逆不成立，当对偶问题无可行解时，其原问题具有无界解或无可行解，反之亦然其原问题具有无界解或无可行解，反之亦然) ) 3. 3.若若原问题有可行解而其对偶问题无可行解，则原问题目原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。解，则对偶问题的目标函数值无界。第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 国防科技大学 7112121212min11,0 xxxxxxx x 例例2.5 2.5 原问

28、题和对偶问题都无可行解的例子原问题和对偶问题都无可行解的例子 原问题（对偶问题）原问题（对偶问题） 对偶问题（原问题）对偶问题（原问题） 12121212max11,0zyyyyyyy y 第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 国防科技大学 72第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 原问题原问题（对偶问题）对偶问题） 最优解最优解 无界解无界解 无可行解无可行解对偶问题对偶问题（原问题）（原问题） 最优解最优解 无可行解无可行解无界解或无可行解无界解或无可行解 国防科技大学 73第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 国防科技大学

29、 74第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 国防科技大学 75例例2.6 2.6 已知线性规划问题已知线性规划问题 12123123123max221,0zxxxxxxxxx x x 试用对偶理论，证明上述问题无最优解。试用对偶理论，证明上述问题无最优解。 第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 国防科技大学 76无可行解？无可行解？无界解？无界解？第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 国防科技大学 77例例2.7 2.7 已知线性规划问题已知线性规划问题 123451234512345min235232342330,1,2,5j

30、wxxxxxxxxxxxxxxxxj第四节第四节 线性规划问题的对偶理论线性规划问题的对偶理论 国防科技大学 78第五节第五节 对偶问题的经济解释对偶问题的经济解释 国防科技大学 79max0zCXAXbXmin0YbYACY原问题对偶问题为原问题最优解第五节第五节 对偶问题的经济解释对偶问题的经济解释1*0B bX 国防科技大学 80为对偶问题最优解第五节第五节 对偶问题的经济解释对偶问题的经济解释*1BYC B原问题最优目标函数值为：*1*BzC B bY b 若将目标函数在最优点处的取值视为向量b的函数，则有：*1,2,iizyimb 国防科技大学 81 对偶解的经济含义是在其他条件不变

31、的情况下，单位资源变化引起的目标函数最优值的变化。 这是该资源的一种价格表征，经济学上称之为“影子价格”。第五节第五节 对偶问题的经济解释对偶问题的经济解释*1,2,iizyimb 国防科技大学 82在完全市场经济条件下： 当某种资源的市场价格低于影子价格时，可以买进该资源用于扩大生产； 当某种资源的市场价格高于影子价格时，则应把已有资源卖掉。 影子价格对市场具有调节作用。第五节第五节 对偶问题的经济解释对偶问题的经济解释 国防科技大学 83n理解对偶理论的背景及其实践意义。理解对偶理论的背景及其实践意义。课后习题课后习题P88, P89： 3.3（1）（）（3） ，3.5，3.7 ，3.8

32、。课后作业课后作业 国防科技大学 84第六节第六节 对偶单纯形法对偶单纯形法 国防科技大学 85第六节第六节 对偶单纯形法对偶单纯形法 国防科技大学 86单纯形表单纯形表 1cmc1mcnc1mcc1mxx1mbb1m10011,1,1mm maa1nmnaa01,11mmii micc a1mniinicca0决策变量的价值系数决策变量的价值系数基变量基变量基变量价值系数基变量价值系数基变量的取值基变量的取值基矩阵的逆矩阵左乘系数矩阵基矩阵的逆矩阵左乘系数矩阵B B-1-1A A值值决策变量的检验数决策变量的检验数第六节第六节 对偶单纯形法对偶单纯形法 国防科技大学 87第六节第六节 对偶单

33、纯形法对偶单纯形法 国防科技大学 88第六节第六节 对偶单纯形法对偶单纯形法 l 单纯形法的基本立足点：单纯形法的基本立足点： 始终保持始终保持基变量值非负基变量值非负，逐步使全部的，逐步使全部的检验数检验数变成非正，变成非正，最后求得最优或判断无最优。最后求得最优或判断无最优。出发点出发点l 对偶单纯形法的基本立足点：对偶单纯形法的基本立足点： 根据对偶问题的对称性，同样可以始终保持根据对偶问题的对称性，同样可以始终保持检验数检验数非正，非正，原问题在非可行解的基础上，逐步迭代，达到基可行解得最优原问题在非可行解的基础上，逐步迭代，达到基可行解得最优或判断无最优解。或判断无最优解。 国防科技大学 89 保持保持对偶问题的解是基可行解对偶问题的解是基可行解（即保持单纯型表中即保持单纯型表中检验数行为非正检验数行为非正），而原问题在），而原问题在非可行解非可行解的基础上，通的基础上，通过逐步迭代达到基可行解，这样就得到了最优解。过逐步迭代达到基可行解，这样就得到了最优解。对偶单纯形法的思路对偶单纯形法的思路第六节第六节 对偶单纯形法对偶单纯形法 优点优点：原问题的初始解不一定要是基可行解，可从：原问题的初始解不一定要是基可行解，可从非基可行解开始迭代。非基可行解开始迭代。 国防科技大学 90例例2.7 2.7 用对偶单纯形法求解