运筹学教学演示系统⑵

《运筹学教学演示系统⑵》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章对偶问题及灵敏度分析第一节单纯形法的矩阵描述矩阵描述的目的是将单纯形法用矩阵来加以解释及有助于对偶问题的分析。一、标准型规划问题的矩阵描述设线性规划问题为：所对应的单纯形表为：CBCNXBbXBXNXBB-1bIB-1N-Z-CBB-1b0CN-CBB-1N关于检验数的再讨论！①检验数的统一表示（不论是基变量还是非基变量）②某一个变量检验数的表示方法二、存在松弛变量模型的矩阵描述设线性规划问题为：引入松弛变量的模型为：注意特别强调了松弛变量在模型矩阵描述中的作用！在下面的矩阵描述中，松弛变量独立表示，不归入非基变量。看下面的模型变化！约

2、束方程两边左乘B-1把XB代入目标函数目标函数整理以此模型构造单纯形表如下：CBCN0XBbXBXNXSXBB-1bIB-1NB-1-Z-CBB-1b0CN-CBB-1N-CBB-1此表的一个重要目的就是在于B-1所在的位置。结合教材中，表1-3～表1-5的约束方程的系数矩阵，了解B-1的位置及作用。表1-3所对应的模型为：第二节对偶问题的提出线性规划问题具有对偶性！什么是对偶性？任何一个求最大值的线性规划问题都有一个求最小值的线性规划问题与之相对应。一个叫“原始问题”，另一个称为它的“对偶问题”。原始问题和对偶问题所依据的数据资料是一致的！

3、仍以前述模型为例说明对偶问题。例1某厂计划在下一个生产周期内生产甲、乙两种产品，这两种产品分别要经过两种设备加工，有关数据如下表，问应如何安排生产计划使总利润最大？其依据的数据资料及模型为：甲乙机器台时设备A2480设备B3260单件利润6050现在从另一个角度讨论该问题①为什么能够获利呢？因为有资源：A—80、B—60②不生产甲、乙产品能否获利呢？把已有设备出租③租金或设备使用费用如何收取？不低于自己创收、承租方可以接受④假设设备的每台时使用费分别为Y1、Y2根据原始数据，用于加工一件产品的设备台时出租后的收益不应低于产品的利润，则得到另一

4、组约束条件：但是，承租方希望其设备台时的使用费越小越好，则必有：则原问题的对偶问题为：原问题对偶问题第三节线性规划的对偶理论一、对偶问题的定义设原始线性规划问题为：则称下列规划问题为原始问题的对偶问题。注意：Y是行向量还是列向量；其分量的个数？例2写出下列规划问题的对偶问题。注意：一个方程对应一个对偶变量！原问题对偶问题二、非对称规划问题的对偶问题若原始线性规划问题为：关键在于将原模型进行转变如下:变形则其对偶问题为；例3写出下列规划问题的对偶问题分析一个一般的线性规划问题？如何得到其对偶问题，又能够得到什么结论！原问题（对偶问题）对偶问题（

5、原问题）目标函数max变量：n个≥0≤0无约束目标函数min约束条件：n个≥号≤号＝约束条件：m个≤号≥号＝约束条件右端项目标函数变量的系数变量：m个≥0≤0无约束目标函数变量的系数约束条件右端项例4写出下列规划问题的对偶问题三、对偶问题的基本性质这是基于对称型问题而言的1.对称性：对偶问题的对偶问题是原问题2.弱对偶性；若X(1)和Y(1)分别是可行解，则结论表明：对偶问题的下界与原问题上界之间的关系3.无界性：若原问题无界，则其对偶问题无可行解注意：该问题的逆不存在！4.最优性：原问题和对偶问题都存在可行解，且目标函数值相等，该可行解分别

6、是原问题和对偶问题的最优解。综上所述，一对对偶问题必然是以下的三种情况：①都存在最优解，且最优的目标函数值相等②都无可行解③一个是无界，另一个无可行解四、互补松弛条件设X*和Y*分别是原问题和对偶问题的可行解，则它们分别是最优解的充分必要条件是：注意：互补松弛条件的意义！五、对偶问题的解原问题单纯形表的检验数反号后，就是对偶问题的一个基解。证明：对于原问题其标准型为：设A中存在一个可行基B，则模型为：则相应的对偶问题为：原问题对应于可行基B的检验数可表示为：代入对偶问题的约束条件，得到：可见，松弛变量检验数的反号正好对应对偶问题的一个基解。若

7、B为最优基，则为对偶问题的最优解（松弛变量的检验数）。问题：如果存在人工变量，对偶问题的最优解如何得到？例5求下列规划对偶问题的解加入人工变量后，得到：其初始和最终单纯形表如下：3-1-100-M-MXBbX1X2X3X4X5X6X7X4X6X711３11-4-2-2101211000-10010001-Z4M3-6M-1-M-1+3M0-M00X1X2X34191000100011/302/3-2/3-1-4/32/314/3-5/3-2-7/3-Z-2000-1/3-1/31/3-M2/3-M讨论这样几个问题：①原问题的最优解及最优的目标

8、函数值②最优基及其基的逆矩阵是什么？③初始单纯形表与最终单纯形表的系数矩阵之间的联系对偶问题的解如何从原问题单纯形表的检验数中得到④对偶问题的解第四节影子价格对偶问