《5 线性规划的对偶理论与对偶单纯形法》由会员分享，可在线阅读，更多相关《5 线性规划的对偶理论与对偶单纯形法（12页珍藏版）》请在金锄头文库上搜索。
1、 1 5 线性规划的对偶理论与对偶单纯形法线性规划的对偶理论与对偶单纯形法 随着线性规划问题的提出，人们发现，任何一个线性规划问题，都伴随着另一个与之相互关联的线 性规划问题，这个新问题具体非常重要的性质，利用这些性质可有效地获得原来问题的解。为区别起见， 我们称原来的问题为原问题，新的问题为对偶问题。 本章首先给出对偶问题的形式，并研究原始问题与对偶问题的关系，然后由此引出求解线性规划问 题的另一有效方法对偶单纯形法。 51 对偶问题对偶问题 我们先通过一个例子说明对偶线性规划问题的意义，然后讨论一般情况下对偶问题的形式，并得到 标准形式线性规划问题的对偶问题。 例例 5.1(配料问题配料问
2、题) 设种某一作物，整个生产过程中至少需要氮肥 32 kg，磷肥 24kg，钾肥 42kg。已 知含有这三种成分的四种化肥的单价和含量如下表。 营养素的单位含量 基变量 甲 乙 丙 丁 最低量 氮 0.03 0.3 0 0.15 32 磷 0.05 0 0.2 0.10 24 钾 0.14 0 0 0.07 42 单价 0.4 1.5 1.0 1.3 表 5.1 配料问题 问应如何选用这四种化肥，才能既满足作物的需要，又使施肥的总成本最小？ 我们设 x1，x2，x3，x4分别是四种化肥的用量，则配料问题的数学模型为： min 0.4x1+1.5x2+1.0 x3+1.3x4 s.t. 0.03
3、x1+0.3x2 +0.15x432 0.05x1 +0.2x3+0.1x424 (5.1) 0.14x1 +0.07x442 x1, x2, x3, x40 例例 5.2(利润问题利润问题) 某企业准备生产氮磷钾三种单成分的化肥， 该企业已知人们也可以从甲乙丙丁四 种化肥中获取氮磷钾，有关数据如表 5.1。那么，该企业应对这氮磷钾如何定价，才能在可与生产甲乙 丙丁四种化肥的企业竞争的前提下，使利润最大？ 设 w1、w2和 w3依次是氮磷钾的单价，则利润问题的数学模型为： max 32w1+24w2 +42w3 s.t. 0.03w1+0.05w2+0.14w30.4 (1.2) 0.3w1
4、1.5 0.2w2 1 0.15w1+0.1w2+0.07w31.3 w1, w2, w30 我们可以看出，上述两个问题之间有着极其密切的关系。若将配料问题的数学模型(5.1)记作 2 0 x bx xcT Ats . . min (5.3) 那么利润问题的数学模型(5.2)为 max . . 0 T stA T b w wc w (5.4) 考虑一般形式的线性规划问题 1122 1111221 2112222 1 min . . 0 TT st AA AA + += + c xc x xxb xxb x (GLP) 其中矩阵( ,1,2) ij mn ij ARi j =，向量(1,2) i
5、 m i Ri=b，(1,2) j n j Rj=c。 我们将(GLP)转化为(1.3)的形式。令 x2=u-v，则(GLP)可写成： 1122 11112121 11112121 21122222 1 min . . , ,0 TTT st AAA AAA AAA + + + + c xc uc v xuvb xuvb xuvb x u v 因此其对偶问题为： 12 111122 111111122121 121112122222 121112122222 11122 max . . ,0 TTT TTT TTT TTT st AAA AAA AAA + + + + b wb wb w ww
6、wc wwwc wwwc www 令 w1=w11-w12，则上式可写为： 1122 1112121 1212222 2 max . . + 0 TT TT TT st AA AA + += b wb w wwc wwc w (DGLP) 根据(GLP)和(DGLP)之间的关系，我们可归纳得到建立一般线性规划问题的对偶问题的如下规律： 原问题min 对偶问题max 目标函数系数 右端系数 右端系数 目标函数系数 约束矩阵 系数矩阵转置 第i个约束为“”型 第i个变量0 第i个约束为“=”型 第i个变量为自由变量 3 第j个变量0 第j个约束为变量“”型 第j个变量为自由变量 第j个约束为变量“
7、=”型 表5.2 原问题和对偶问题的转化规律 例例5.3 考虑线性规划问题 min 2x1-3x2-5x3 s.t. -x1+2x2+4x33 2x1+4x2 5 x1+ x2+ 3x3=9 x1, x20 写成(GLP)的形式： min 2x1-3x2-5x3 s.t. x1-2x2-4x3-3 2x1+4x2 5 x1+ x2+3x3=9 则其对偶问题为： max 3w1+5w2+9w3 s.t. w1+2w2 + w32 -2w1+4w2 + w3-3 -4w1 + 3w3 =-5 w10, w20 定义定义5.1 若 12 (,)x x是(GLP)的可行解， 12 (,)w w是(DG
8、LP)的可行解，则称 1212 (,)x x w w是(GLP)与 (DGLP)的可行对，并称 1212 (,)x x w w= 1122 TT +c xc x-( 1122 TT +b wb w)是可行对 1212 (,)x x w w的对偶间隙。 设 1212 (,)x x w w是(GLP)与(DGLP)的可行对，则容易推得其对偶间隙为 1212 (,)x x w w= 11112121 () TTT AAcwwx+ 21122222 ()TAA+xxbw (5.5) 现在考虑标准形式的线性规划问题(LP)。根据表5.2，得(LP)的对偶问题为： max . . T T st A b w
9、 wc (DLP) 并且对于(LP)与(DLP)的可行对( ,)x w，其对偶间隙为 ( ,)x w =() TT Acwx (5.6) 5.5.2 对偶定理对偶定理 本小节讨论一般线性规划问题(GLP)与其对偶问题(DGLP)之间的对称性、对偶性和互补性等关系。 由于(LP)和(5.3)是(GLP)的特殊情况，因此(LP)与(DLP)、(5.3)与(5.4)之间也存在这些关系。 定理定理5.1 (GLP)是(DGLP)的对偶问题。 证明证明：首先将(DGLP)等价地转化成极小化问题： 4 1122 1112121 1212222 2 min . . 0 TT TT TT stAA AA =
10、b wb w wwc wwc w 根据表5.1，可得其对偶问题为 1122 1111221 2112122 1 max . . 0 TT stAA AA = c xc x xxb xxb x 即为(GLP)。证毕。 根据定理5.1知，(GLP)和(DGLP)互为对偶问题，因此(LP)与(DLP)、(5.3)与(5.4)也互为对偶问题。 利用(5.5)马上得到如下的弱对偶性。 定理定理5.2(弱对偶性弱对偶性) 设 1212 (,)x x w w是(GLP)与(DGLP)的可行对，则 1212 (,)0 x x w w，即 1122 TT +c xc x 1122 TT +b wb w。 根据定
11、理5.2可以得到以下两个重要结论。 推论推论5.1 设 0000 1212 (,)xxww是(GLP)与(DGLP)的可行对。若 00 1122 TT +c xc x= 00 1122 TT +b wb w，即 0000 1212 (,)xxww=0，则 00 12 (,)xx和 00 12 (,)ww分别是(GLP)和(DGLP)的最优解，并且(GLP)和(DGLP)的 最优值相等。 证明证明：先证 00 12 (,)xx是(GLP)的最优解。任取(GLP)的可行解 12 (,)x x，根据定理5.2并利用已知条件 得， 1122 TT +c xc x 00 1122 TT +b wb w=
12、 00 1122 TT +c xc x 因此 00 12 (,)xx是(GLP)的最优解。 同理可证 00 12 (,)ww是(DGLP)的最优解。由此，根据条件得知(GLP)和(DGLP)的最优值相等。证毕。 推论推论5.2 设(GLP)无下界(或(DGLP)无上界)，则(DGLP)(或(GLP)无可行解。 证明证明： （反证法） 设(GLP)无下界， 但(DGLP)存在可行解 00 12 (,)ww。 则对(GLP)的任一可行解 12 (,)x x， 根据定理5.2， 1122 TT +c xc x 00 1122 TT +b wb w 即(GLP)有下界，与条件矛盾。同理可证另一结论。证
13、毕。 根据推论5.2得知，如果(GLP)和(DGLP)均存在可行解，那么(GLP)和(DGLP)一定均存在最优解。下 面证明，如果(GLP)和(DGLP)中的一个存在最优解，那么另一个也存在最优解。其实，根据定理5.1的 对称性，我们只需证明以下定理即可。 定理定理5.3(强对偶性强对偶性) 设(GLP)存在最优解，则(DGLP)也存在最优解，并且(GLP)和(DGLP)的最优值 相等。 证明证明：由于(GLP)可转化成标准形式(LP)，故为简便起，我们仅关于(LP)和其对偶问题(DLP)进行证 5 明。 首先根据第三章定理2.4，(LP)一定存在最优基本可行解， 我们可用单纯形法求得其最优基
14、B和相应 的最优基可行解 * 1 * * 0 B N B = xb x x (可采用Bland规则以避免出现循环)。因此，(LP)的最优值为 bcxc T B T1* =B (5.7) 并且关于B的检验向量满足 11 ()()0 TTTTT BB A AB = T B rcccc (5.8) 若令 *1 () TT BB =wc，则由(5.8)知 *T Awc，即 * w是(DLP)的可行解，并且由(5.7)得 *T b w = 1*T BB = T cbc x 于是，根据推论5.1得 * w是(DLP)的最优解，并且(LP)和(DLP)的最优值相等。证毕。 根据定理5.3得知，对于(LP)，如果其系数矩阵中含有单位矩阵，则从(LP)的最优单纯形表中可以直 接得出对偶问题的最优解。 推论推论5.3 设(LP) 系数矩阵A中含有单位矩阵 1 (,) m ttm I
