欢迎来到天天文库
浏览记录
ID：65452648
大小：138.00 KB
页数：9页
时间：2022-01-09
《对偶工管重点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、6、互补松弛定理：设X*和Y*分别是问题P和D的可行解，则它们分别是最优解的充要条件是同时成立一般而言，我们把某一可行点（如X*和Y*）处的不等式约束（包括对变量的非负约束）称为松约束，而把等式约束称为紧约束。互补松弛定理也称松紧定理，它描述了线性规划达到最优时，原问题（或对偶问题）的变量取值和对偶问题（或原问题）约束松紧之间的对应关系例4、已知试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为用图解法求出：Y*=（1，3），W=11。将y*1=1，y*2=3代入对偶约束条件，（1）（2）（5
2、）式为紧约束，（3）（4）为松约束。令原问题的最优解为X*=（x1.x2.x3.x4.x5），则根据互补松弛条件，必有x3=x4=0(1.3)（1）（2）（3）（4）（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）也是原问题的一个最优解，Z=11。步骤1写出对偶问题（注意符号）2由问题的最
3、优解（实质是变量）的松紧（是否＝0），判断另一个问题的松紧约束3最优解代入判断约束条件符号，找出松紧约束，从而得出另一个问题的紧变量（＝0）变量---约束（松紧对应）例5、已知原问题的最优解为X*=（0.0.4），Z=12试求对偶问题的最优解。解：（1）（2）（3）将X*=（0.0.4）代入原问题中，有下式：由x3≠0，得对偶问题的第三个约束条件为紧约束（＝）所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3=3。因此，对偶问题的最优解为Y*=（0.0.3），W=12。练习已
4、知线性规划问题Min.Z=2x1+3x2+5x3+2x4+3x5S.t.x1+x2+2x3+x4+3x5≥42x1–x2+3x3+x4+x5≥3xi≥0(i=1,2,3,4,5)已知对偶问题的最优解为y1=4/5,y2=3/5,试应用对偶理论解原问题。
此文档下载收益归作者所有
