资源描述：
《对偶理论31041》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、对偶理论(DualityTheory)对偶性是线性规划问题的最重要的内容之一。每一个线性规划（LP[linearprogramming]）必然有与之相伴而生的另一个线性规划问题，即任何一个求maxZ的LP都有一个求minZ的LP。其中的一个问题叫“原问题”，记为“P”，另一个称为“对偶问题”，记为“D”。例一、资源的合理利用问题已知资料如表所示，问应如何安排生产计划使得既能充分利用现有资源有使总利润最大？1810单件利润150（设备）51C100（煤炭）32B170（钢材）25A资源限制乙甲单件产消耗品资源一、问题的提出下面从另
2、一个角度来讨论这个问题：假定：该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工任务，只收取加工费。即将资源出租。试问该决策者应制定怎样的收费标准（合理的）？分析问题：1、每种资源收回的费用不能低于自己生产时的可获利润；2、定价又不能太高，要使对方能够接受。一般而言，W越大越好，但因需双方满意，故为最好。该问题的数学模型为：模型对比：项目原问题对偶问题A约束的系数矩阵约束的系数矩阵的转置b约束条件的右端项向量目标函数的价值系数系数向量C目标函数的价值系数系数向量约束条件的右端项向量目标函数约束条件决
3、策变量1、对称型对偶问题：已知P，写出D。二、线性规划的对偶理论（一）、对偶问题的形式例一、写出线性规划问题的对偶问题解：首先将原式变形注意：以后不强调等式右段项b≥0，原因在对偶单纯型表中只保证而不保证，故b可以是负数。2、非对称型对偶问题例二、原问题2、混合型对偶问题首先变形其对偶问题为令Y2=Y21-Y22,Y3=-Y31,并综合后两个约束。例三、原问题对偶问题对偶问题的一般规则例四、线性规划问题如下：x1x2x3x423-51Minfy111-31≥5y2-20-24≥-4y30111=6≤0≥0≥0无约束minZ’=-
4、CXs.t.-AX≥-bX≥01、对称性：对偶问题的对偶是原问题。minW=Ybs.t.YA≥CY≥0maxZ=CXs.t.AX≤bX≥0对偶的定义对偶的定义maxW’=-Ybs.t.-YA≤-CY≥0（二）、对偶问题的性质2、弱对偶原理（弱对偶性）：设和分别是问题（P）和（D）的可行解，则必有推论.若和分别是问题（P）和（D）的可行解，则是（D）的目标函数最小值的一个下界；是（P）的目标函数最大值的一个上界。例试估计它们目标函数的界。（P）解：（D）可知：=（1，1，1，1），=（1，1），分别是（P）和（D）的可行解。Z=1
5、0，W=40，故有，弱对偶定理成立。由推论可知，W的最小值不能小于10，Z的最大值不能超过40。＜3、无界性.在一对对偶问题（P）和（D）中，若其中一个问题有可行解，但目标函数无界，则另一个问题不可行；反之不成立。关于无界性有如下结论：问题无界无可行解无可行解问题无界对偶问题原问题无界如：P无可行解D注意：反之不成立，即当原问题（对偶问题）无可行解时，其对偶问题（原问题）或具有无界解或无可行解。例：两者皆无可行解4、最优性：若X*和Y*分别是P和D的可行解且CX*=Y*b，则X*.Y*分别是问题P和D的最优解。5、对偶性：若一对
6、对偶问题P和D都有可行解，则它们都有最优解，且目标函数的最优值必相等。推论:若P和D的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：①.都有最优解，分别设为X*和Y*，则必有CX*=Y*b；②.一个问题无界，则另一个问题无可行解；③.两个都无可行解。6、互补松弛定理：设X*和Y*分别是问题P和D的可行解，则它们分别是最优解的充要条件是同时成立由于变量都非负，要使求和等式等于零，则必定每一分量为零。所以：一般而言，我们把某一可行点（如X*和Y*）处的严格不等
7、式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。例、已知试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为用图解法求出：Y*=（1,3），W=11。将y*1=1，y*2=3代入对偶约束条件，（1）（2）（5）式为紧约束，（3）（4）为松约束。令原问题的最优解为X*=（x1,x2,x3,x4,x5），则根据互补松弛条件，必有x3=x4=0(1.3)（1）（2）（3）（4）（
8、5）又由于y*1＞0，y*2＞0，原问题的约束必为等式，即化简为此方程组为无穷多解令x5=0,得到x1=1，x2=2即X*1=（1,2,0,0,0）为原问题的一个最优解，Z=11。再令x5=2/3，得到x1=5/3，x2=0即X*2（5/3,0,0,0,2/3）
