文档介绍：§ 对偶规划及对偶单纯形算法
三个问题:对偶问题、对偶理论、对偶单纯形算法
一、对偶线性规划
1、标准形式线性规划的对偶规划
(1):称LP问题
(D)
为线性规划
(P)
的对偶问题,其中,。
(2)联系: <1> (D) 的价值向量为(P) 的右端向量,
<2> (D) 的右端向量为(P) 的价值向量,
<3> (D) 的约束矩阵为(P) 的约束矩阵的转置。
(3)区别:<1> 最大与最小<2>等式与不等式<3> 非负与自由
2、一般形式线性规划的对偶规划
()
为了把()化为标准形式,
<1> 对每个线性不等式约束,减去一个非负的剩余变量
<2> 对每个自由变量,用两个非负的变量和来替换它。
因此,可得标准的Lp问题
()
其中
均为维向量,
()
是一个阶的矩阵,右上角是一个阶的零矩阵,右下角的是一个阶的单位矩阵。
其中。分三组展开线性不等式
(即) ()
第一组:对应于非负变量有
。()
第二组:对应于自由变量有
,
,
所以, ()
第三组:对应于的不等式,有
,
即, ()
定义
注意:<1> 最大与最小
<2> 等式对应自由变量,不等式对应非负变量,
<3> 不等式符号()
步骤:<1> 写变量:在每个线性等式和线性不等式左边写出一个相应的变量,记
<2> 写出目标函数: ,即与对应相乘,再求和。
<3> 写线性约束:考察(P)的每个变量,让与的系数向量相乘,再与的价值系数进行比较。若是非负变量,则取;若是自由变量,则取。
<4> 决定的符号:若对应的是等式,则是自由变量;若对应的是不等式,则是非负变量。
两种特殊情况:
(P) (D)
(P) (D)
写出下面LP问题的对偶问题
解:其对偶问题为
二、对偶理论
(P)有最优解,则其对偶规划(D)也有最优解,且它们的最优值相等。
证明:设和分别是原规划(P)和对偶规划(D)的任一可行解。:
对于, 有为自由变量
所以
对于, 有
所以
所以即
同理
所以()
由条件知原问题(P)有最优解。所以,其标准形式
有最优基本可行解,则()存在一个相应于的可行基,使得检验数向量
令,则是线性约束
(即)
的一个解。从而, 是对偶规划(D)的一个可行解。且
所以,对对偶规划(D)的任一可行解,由()有
所以, 是对偶规划(D)的一个最优解。
结论: (由()可得)
<1>若原问题(P)有可行解,则对偶问题(D)一定不可能无界。
<2>若对偶问题(D)有可行解,则原问题(P)一定不可能无界。
:若和分别是原规划和对偶规划的可行解,则和分别是原规划(P)和对偶规划(D)的最优解的充要条件是。
证明: 可得
设和分别是原规划(P)和对偶规划(D)的任一可行解,则由()可得
所以和分别是原规划和对偶规划的最优解。
线性规划的对偶规划的对偶规划是原始规划。
证明:
P D
有最优解
问题无界
无可行解
有最优解
①
×
×
问题无界
×
×
③
无可行解
×
③
②
给定一个原规划和对偶规划,则下面三种情况必有其一
①都有有最优解
②都没有可行解
③一个没有可行解,而另一个问题无界
证明: 及其结论,只需举例说明:当(P)和(D)中有一个无可行解时,另一个可能是问题无界,也可能是没有可行解。
(P) 无解(D) 无解
(P) 无解(D) 无界
若和分别是原规划(P) 和对偶规划(D)的可行解,则和分别是原规划(P) 和对偶规划(D)的最优解的充要条件是
, ()
, ()
含义:
证明:(P) 和对偶规划(D)的最优解的充要条件是。再由()知
。
所以,
另外, 知
所以
定理得证。
知
(P)
的最优解为,最优值为。用互补松紧性定理求它的对偶问题(D)的最优解。
解:设(D)的最优解为。由()知
, 。
由于,所以
, 。