根据对偶问题的定义知道，原问题与对偶问题是互为对偶的。

在给出原问题的对偶问题过程中应注意的几点关系：(1) 原问题各约束条件中的限制符号，必须统一是“≤”或统一为“≥”，不必考虑向量b 的元素是否是正值；(2) 如原问题有等式约束，则将该条件用等价的两个不等式约束条件替换，即“k f =)x (”可改写成两个不等式条件“k f ≤)x (，k f -≤-)x (”；(3) 对偶前后都要求变量是非负的；(4) 对偶关系是，“极大”对“极小”；“≤”对“≥”；向量c 与向量b 对调位置；矩阵A 转置。

例3-14 给出以下线性规划问题的对偶问题212max x x z +=12321≤+x x ； 521=+x x ； 16421≤+x x ； 21≥x ；02≥x 。

解：原问题的规范形式及对偶形式写在表3-17中。

表3-17 线性规划对偶问题原问题对偶问题min 543212551612w w w w w s --++=max 212x x z +=1354321≥--++w w w w w12321≤+x x ； 244321≥-++w w w w16421≤+x x ；0≥i w ，51≤≤i 。

521≤+x x ；对偶问题的线性规划标准形式521-≤--x x ； max 543212551612w w w w w s ++---= 21-≤-x ； 13654321=---++w w w w w w 01≥x ，02≥x 。

2474321=--++w w w w w0≥i w ，71≤≤i 。

下面介绍线性规划对偶问题的一些性质。

定理3-4 在式(3-23)定义的对偶问题中，若x 和w 分别是原问题和对偶问题的任意可行解，则一定有w b x c T T ≤。

(3-24)证 因为是可行解，必然满足各自的全部约束条件，即b A ≤x ，0x ≥；c w T ≥A ，0w ≥。

由此导出，b w x w T T ≤A ；c x w x T T T ≥A 。

标量的转置就是标量本身，即b w x w w xc x x c T T T T T T ≤=≤=A A 。

证毕 该性质表明，若*x 是求极大值问题的最优解，则*x c T 是对偶问题目标函数的下界；若*w 是求极小值问题的最优解，则*w b T 是对偶问题目标函数的上界。

其次，若其中一个问题的解是无穷大(或无穷小)，则对偶问题无可行解；若其中一个问题无可行解，则对偶问题无可行解或解是无穷大(或无穷小)。

例3-15 讨论以下互为对偶问题的解max 212x x z +=； min 214w w s +=；4221≤+-x x ； 121≥--w w ； 121≤+-x x ； 2221≥+w w ； 01≥x ，02≥x 。

01≥w ，02≥w 。

解由图3-3可知，原问题解为无穷大，对偶问题无可行解。

定理3-5 在式(3-23)定义的对偶问题中，若*x 和*w 分别是原问题和对偶问题的可行解，且**=w b x c T T ，则*x 和*w 分别是原问题和对偶问题的最优解。

证 该定理的结论可直接有定理3-4导出，即**=≤xc w b x c T T T ；**=≥w b x c w b T T T 。

证毕定理3-6 在式(3-23)定义的对偶问题中，若*x 是原问题的最优解，则对偶问题也必有最优解，且最优值相等，即**=w b x c T T 。

证 应用单纯形法求解结果证明本定理。

引入松弛(辅助)变量，原问题表示为x c max T =zb A s =I +x x ；0x ≥；0x ≥s 。

(3-24)式中 n m R A ⨯∈，n R ∈x ，m m R ⨯∈I 单位矩阵，mR ∈b 。

用j a 表示系数矩阵][I A 中的 第j 个列向量。

设*n x 是原问题(3-24)的最优解(*n x 中除去辅助变量后就是原问题的最优解*x )，与最优解对应的基底为B ，加权系数向量为Bc 。

最优解*n x 的值是b 1-B 。

由于*n x 是原问题(3-24)的最优解，对应的判别数0≥-=j j B j c z σ；从式(3-7)和式(3-8)j B j B B z a c 1T -=；-x 1+2x -x 1+x 2图3-3(a )原问题代入最优解判别数的表达式，得到c )c (c c 0a c T 1T T T1T 1T ≥⇔≥⇔≥----B A A B c B B B j j B 。

(3-25)考虑到最右边的表达式形同对偶问题的约束条件，取T 1T )c (w -*=B B 。

将式(3-25)中第一个表达式用于所有辅助变量对应的列，因辅助变量在目标函数中的加权系数均为零，得到0c 1T ≥-B B ，表明*w 是对偶问题的一个可行解。

因*x 是原问题的最优解，目标函数最优值为b c x c 1T T -**==B z B n ；而对偶问题的一个可行解*w 对应的目标函数值是**-*====z B s n B x c b c w b T 1T T ，由定理3-4得知，*w 为对偶问题的最优解，而且两个问题的最优函数值相等。

证毕 定理3-6表明，如果已得到式(3-23)中的原问题的最优解*x ，那么就可以得到对偶问题的最优解BB c )(w T 1-*=，其中B 是原问题中对应于*x 的基底，B c 是相应的加权向量。

由式(3-25)的第一个表达式知道，在单纯形表格法的最终表格的最后一行中，已经给出了对偶问题的最优解，即对应辅助变量的判别数的矩阵表达形式1T c -B B 就是对偶问题的最优解*w 。

从对偶问题的最终表格中，也能得到原问题的最优解。

定理3-7 (互补松弛定理)在式(3-23)定义的对偶问题中，若*x 和*w 分别是原问题和对偶问题最优解，记T 21][x ****=n x x x 、T21][w ****=m w w w 。

引入辅助变 量记为si x ,)1(m i ≤≤和sj w ,)1(n j ≤≤。

约束条件表示为i si nj j ji b x x a=+∑=*1，)1(m i ≤≤； (3-26)j j s mi i ji c w w a=-∑=*1，)1(n j ≤≤； (3-27)0≥si x ，)1(m i ≤≤；0≥sj w ，)1(n j ≤≤。

则一定有0=*i si w x ，)1(m i ≤≤； 0=*j sj x w ，)1(n j ≤≤。

证 用*i w 和*j x 分别乘到式(3-26)和式(3-27)的两边，得到**=**=+∑i i i si nj i j ji w b w x w x a1，)1(m i ≤≤； (3-28) **=**=-∑j j j j s m i j i ji x c x w x w a1，)1(n j ≤≤； (3-29)式(3-28)和式(3-29)各自累加，得到*=*=**==+∑∑∑w b T 111mi i si nj ijji mi w x w x a；*=*=**==-∑∑∑x c T 111nj j j s m i j i ji nj x w x w a；因**=w b x c TT，上述两式相减，得到0=+∑∑**nj sj m isix w w x；考虑到 0≥*i w ，0≥si x ，)1(m i ≤≤；0≥*j x ，0≥sj w ，)1(n j ≤≤，上式成立只能是 各项都等于零，即定理命题得证。

证毕 定理3-7表明，如果原问题(对偶问题)的最优解中的某个变量si x (sj w )具有非零值，则 对偶问题(原问题)的最优解中的变量*i w (*j x )值为零。

若原问题的最优解中的变量(对偶问题) *j x (*i w )值非零，则对偶问题(原问题) 的最优解中的变量sj w (si x )值为零。

例3-16 讨论以下互为对偶问题的解max 214x x z +=； min 321412w w w s ++=；122321≤-x x ； 43321≥-+w w w ； 1621≤-x x ；1262321≥+--w w w ；4221≤+-x x ； 01≥w ，02≥w ，03≥w 。

01≥x ，02≥x 。

解：采用单纯形表格法求解，对应的最终表格分别为表3-18和表3-19。

38=*z ；T ]029068[x =*；T x ]4/1104/900[=σ；38=*s ；T ]004/1104/9[w =*； T w ]680290[=σ。

这个简单例子验证了定理3-6和定理3-7。

注意，4x 是原问题的第2个松弛变量，显然，满足024=*w x 。

3-6 对偶单纯形法本节首先介绍对偶单纯形法的解题思路，然后给出具体操作步骤。

设线性规划原问题为x c max T =z ；b x =A ， 0x ≥。

下面导出适合采用对偶单纯形法的形式。

把等式约束转化为b x ≤A ，b x -≤-A ；则原线性规划问题的对偶问题为2T 1T w b w b min -=s ；c w w 2T 1T ≥-A A ，0w 1≥，0w 2≥；令自由变量21w w w -=，于是原等式约束问题的对偶问题为w b min T =s ；c w T ≥A ，w 自由。

(3-30)定理3-5表明，如果原问题的一个基本可行解*x 中的基本变量值为b x 1-*=B B ， (3-31) T 1T )c (w -*=B B (3-32)是对偶问题的可行解，则*x 和*w 分别是原问题和对偶问题的最优解。

因此，若得到对偶问题的一个可行解w ，且w 使(3-30)约束具有m 个等式关系，由式(3-31)和式(3-32)可得到原问题的基本变量值B x 。

若0x ≥B，由B x 和零值的非基本变量构成基本解就是原问题的最优解。

若有0<B i x ，在保持w 为对偶问题可行解的基础上，逐步改变基底B ，以达 到0b x 1≥=-B B。

这就是对偶单纯形法的解题思路。

对偶问题的可行解是满足约束方程c w T≥A 的，即满足0c )(c T -1T T ≥-B A B 。

这就是说，原问题的基本解Bx 是满足最优性判据的，但不一定是可行的。

因此，对偶单纯形法的各次迭代都是在保证满足最优性的基础上进行的，逐步使不可行的基本解变为可行基本解，得到的基本可行解就是最优解。

作为比较，单纯形法的各次迭代是在保证基本解是可行的条件下进行的，逐步使基本可行解达到最优解。

应用对偶单纯形法的线性规划问题标准形式x c min T =z ；0b Ix x =+s A ，0x ≥，0x ≥s ，0c ≥，0b 自由。

(3-33)注意：一般线性规划问题转换成标准形式(3-33)的操作顺序如下， (1) 确认目标函数求极小值；若为求极大值，则目标函数反号；(2) 确认加权系数均为非负值；若0<j c ，则变量j x 用j j x x -=替换；(3) 确认约束条件均改换成“≤”形式，引入松弛变量s x ，构成等式约束条件。