节线性规划的对偶理论.pptVIP

例4 已知线性规划问题 max z=x1+x2 - x1+x2+x3≤2 -2x1+x2-x3≤1 x1,x2,x3≥0 试用对偶理论证明上述线性规划问题无最优解。 上述问题的对偶问题为 min ω=2y1+y2 -y1-2y2≥1 y1+ y2≥1 y1- y2≥0 y1，y2≥0 由第1约束条件，可知对偶问题无可行解 因原问题有可行解，故无最优解。 例5 已知线性规划问题 min ω=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x5≥4 2x1-x2+3x3+x4+ x5≥3 xj≥0，j=1,2,…,5 已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解 。 解：先写出它的对偶问题 max z=4y1+3y2 y1+2y2≤2 ① y1-y2≤3 ② 2y1+3y2≤5 ③ y1+y2≤2 ④ 3y1+y2≤3 ⑤ y1，y2≥0 将y1* =4/5,y2* =3/5的值代入约束条件， 得②=1/53, ③=17/55, ④=7/52 它们为严格不等式； 由互补松弛性得 x2*=x3*=x4*=0。 因y1,y2≥0；原问题的两个约束条件应取等式，故有 x1*+3x5*=4, 2x1*+x5*=3 求解后得到x1*=1, x5*=1；故原问题的最优解为 X*=(1，0，0，0，1)T；ω*= 5 思考题（继第1章） 用单纯形法求解下列线性规划问题。 Max Z=x1+ x2+3x3 x1+ x2+2x3 ≤ 40 x1+2x2+ x3 ≤ 20 x2+ x3 ≤ 15 x1、x2、x3≥0 写出对偶问题并求出对偶问题的最优解。 Cj 1 1 3 0 0 0 θ CB XB b x1 x2 x3 x4 x5 x6 0 x4 5 0 -2 0 1 -1 -1 1 x1 5 1 1 0 0 1 -1 3 x3 15 0 1 1 0 0 1 Cj-Zj 0 -3 0 0 -1 -2 最后一张单纯形表 X=(5,0,15)T，Z=50 * 第2章 对偶理论和灵敏度分析 第4节 线性规划的对偶理论 从理论上讨论线性规划的对偶问题 4.1 原问题与对偶理论 原问题（LP）： 对偶问题(DP) 标准型原问题与对偶问题的关系 例2 根据表2-3写出原问题与对偶问题的表达式。 表2-3 x y x1 x2 b y1 1 2 8 y2 4 0 16 y3 0 4 12 c 2 3 标准形式的变换关系为对称形式  原问题 （LP） 对偶问题(DP) 非对称形式的变换关系 原问题的约束条件中含有等式约束条件时，按以下步骤处理。 设等式约束条件的线性规划问题 第一步：先将等式约束条件分解为两个不等式约束条件。 第二步：按对称形式变换关系可写出它的对偶问题 设yi′是对应(2-13)式的对偶变量 yi″是对应(2-14)式的对偶变量。 这里i=1,2,…，m 将上述规划问题的各式整理后得到 综合上述，线性规划的原问题与对偶问题的关系，其变换形式归纳为表2-4中所示对应关系。 例3 试求下述线性规划原问题的对偶问题 则由表2-4中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题， 4.2 对偶问题的基本性质 (1)对称性 对偶问题的对偶是原问题； (2)弱对偶性 若X是原问题的可行解，Y是对偶问题的可行解。则存在CX≤Yb； (3)无界性 若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解； (4)可行解是最优解时的性质； (5)对偶定理 若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等； (6)互补松弛性； (7)原问题检验数与对偶问题解的关系。 (1) 对称性 对偶问题的对偶是原问题 证明： 设原问题是 max z=CX; AX≤b; X≥0 根据对偶问题的对称变换关系，可以找到它的对偶问题是 min ω=Yb; YA≥C; Y≥0 若将上式两边取负号，又因minω=max(-ω)可得到 max(-ω)=-Yb; -YA≤-C; Y≥0 根据对称变换关系，得到上式的对偶问题是 min(-ω′)=-C