【最优化笔记4】线性规划 | 您所在的位置:网站首页 › 线性规划的实验原理是什么 › 【最优化笔记4】线性规划 |
对偶问题(必考点),要会把原问题的对偶问题写出来,知道对偶定理,会对偶单纯形法。 每一个线性规划问题,都有一个被称为对偶的线性规划问题与它相对应,二者可以看做是对同一个问题从不同的角度所进行的分析与研究。 文章目录 1.对偶线性规划问题1.1 对称形式的对偶问题1.2 非对称形式的对偶问题 2.对偶定理2.1 引理1(弱对偶定理)2.2 引理1的推论2.3 线性规划的对偶定理(强对偶定理) 3.互补松弛定理3.1 非对称形式的互补松弛定理3.2 对称形式的互补松弛定理 4.对偶单纯形法4.1 基本思想4.2 使用条件4.3 计算步骤 来吧,先从原问题写对偶问题开始。 1.对偶线性规划问题我的理解是,只有不等式约束就是对称形式的对偶问题;有等式约束的(比如标准型)就是非对称形式的对偶问题。 1.1 对称形式的对偶问题{ m i n f = c T x s . t . A x ≥ b , x ≥ 0 (1) \begin{cases}min \,f=c^Tx \\ s.t.\,Ax \geq b, \\\,\,\,\,\,\,\,\,\,x \geq0 \end{cases} \tag{1} ⎩⎪⎨⎪⎧minf=cTxs.t.Ax≥b,x≥0(1) 问题(1)的对偶线性规划问题定义为: { m a x f = b T λ s . t . λ T A ≤ c T , λ ≥ 0 (2) \begin{cases}max \,f=b^T \lambda \\ s.t.\, \lambda^TA \leq c^T, \\ \,\,\,\,\,\,\,\,\,\lambda \geq0 \end{cases} \tag{2} ⎩⎪⎨⎪⎧maxf=bTλs.t.λTA≤cT,λ≥0(2) 从原始问题(1)构成对偶问题(2)的方法是(对称形式): 交换常矢量c,b的位置,变矢量x由 λ \lambda λ替代;改变约束不等式的等号方向把min 换成 max交换A与变矢量的位置,并按需要进行转置。 1.2 非对称形式的对偶问题考虑标准形式的线性规划问题:
{
m
i
n
f
=
c
T
x
s
.
t
.
A
x
=
b
,
x
≥
0
(3)
\begin{cases}min \,f=c^Tx \\ s.t.\,Ax = b, \\\,\,\,\,\,\,\,\,\,x \geq0 \end{cases} \tag{3}
⎩⎪⎨⎪⎧minf=cTxs.t.Ax=b,x≥0(3) 其可以看作一种特殊的对称形式:
{
m
i
n
f
=
c
T
x
s
.
t
.
A
x
≥
b
,
−
A
x
≥
b
,
x
≥
0
(
3
′
)
\begin{cases}min \,f=c^Tx \\ s.t.\,Ax \geq b, \\\,\,\,\,\,\,-Ax \geq b,\\\,\,\,\,\,\,\,\,\,x \geq0 \end{cases} \tag{$3'$}
⎩⎪⎪⎪⎨⎪⎪⎪⎧minf=cTxs.t.Ax≥b,−Ax≥b,x≥0(3′) 经过推导,(3)的最终对偶线性规划问题如下:
{
m
a
x
f
=
w
T
b
s
.
t
.
w
T
A
≤
c
T
(4)
\begin{cases}max \,f=w^Tb \\ s.t.\,w^TA \leq c^T\end{cases} \tag{4}
{maxf=wTbs.t.wTA≤cT(4)(注意这里的变矢量
w
w
w已经是自由变量了)。 综合上面的,给出对偶的一般规则 若 x x x和 w w w分别是原问题(3)和对偶问题(4)的可行解,则 c T x ≥ w T b c^Tx \geq w^Tb cTx≥wTb。 证明:(就利用是可行解证明就好啦~) w T b = w T ( A x ) = ( w T A ) x ≤ c T x w^Tb=w^T(Ax)=(w^TA)x\leq c^Tx wTb=wT(Ax)=(wTA)x≤cTx这个引理说明原问题的任一可行解所对应的目标函数值都是对偶问题目标函数值的上界,或者说对偶问题的任一可行解对应的目标函数值是原问题目标函数值的下界。那原问题要最小,对偶问题要最大,它们相等的时候不是互相达到了吗!!! 2.2 引理1的推论设 x ∗ x^* x∗和 w ∗ w^* w∗分别是原问题(3)和对偶问题(4)的可行解,且 c T x = w T b c^Tx = w^Tb cTx=wTb,则 x ∗ x^* x∗和 w ∗ w^* w∗分别是原问题(3)和对偶问题(4)的最优解。(证明的话,利用引理1反正就好了) 2.3 线性规划的对偶定理(强对偶定理)若(3)或(4)二者有一个有有限的最优解,则另一个也有有限的最优解,而且二者的(最优)目标函数数值相同。若任一个问题的目标函数值无界,则另一个问题没有可行解。 设 x , w x,w x,w分别为原问题(3)和对偶问题(4)的可行解,则 x , w x,w x,w分别是(3)和(4)的最优解的充要条件是: ( w T A − c T ) x = 0 (6) (w^TA-c^T)x=0 \tag{6} (wTA−cT)x=0(6)或者表述为: (1) 如果 x j > 0 x_j >0 xj>0,就有 w T p j = c j w^Tp_j=c_j wTpj=cj (2) 如果 w T p j < c j w^Tp_j0 xj>0,就有 λ T p j = c j \lambda^Tp_j=c_j λTpj=cj (2) 如果 λ T p j < c j \lambda^Tp_j0 λi>0,就有 a i x = b i a_ix=b_i aix=bi (4) 如果 a i x > b i a_ix>b_i aix>bi,就有 λ i = 0 \lambda_i=0 λi=0 其中 p j p_j pj是 A A A的第 j j j列, a i a_i ai是 A A A的第 i i i行。 具体的证明这里不再给出,可详见陈宝林先生的《最优化理论与算法》P129。 下面重点来了哦~ 4.对偶单纯形法对偶单纯形法是什么呢? 对偶单纯形法是应用对偶原理求解原始线性规划的一种方法——在原始问题的单纯形表格上进行对偶处理。 没错,还是从原来的单纯形表出发,换一种方法求解原问题的最优解咯~ 还记得当线性规划存在有限最优解,上节单纯形法停止的条件吗?没错,所有的检验数 c B T B − 1 N − c N ≤ 0 → c B T B − 1 A − c ≤ 0 → w T A ≤ A c_B^TB^{-1}N-c_N \leq 0 \rightarrow c_B^TB^{-1}A - c \leq0 \rightarrow w^TA \leq A cBTB−1N−cN≤0→cBTB−1A−c≤0→wTA≤A,其中 w T = c T B − 1 w^T=c^TB^{-1} wT=cTB−1为单纯形乘子,同时我们也看到她是对偶问题的一个可行解。 进一步来看 w T b = c B B − 1 b = c B ( B − 1 b ) = c B x b w^Tb=c_BB^{-1}b=c_B(B^{-1}b)=c_Bx_b wTb=cBB−1b=cB(B−1b)=cBxb即原问题的目标函数值与对偶问题的函数值相同,由引理1的推论知, x x x和 w w w为原问题和对偶问题的最优解,B是两问题的最优基。 定理: B是线性规划的最优基的充要条件是,B是 可行基,同时也是对偶可行基。 4.1 基本思想从原始问题(3)的一个对偶可行的基本解开始,逐次进行迭代,在保持对偶可行性的条件下,逐步使原始问题(3)的基本解的不可行性消失(即使 x = b ‾ = B − 1 b ≥ 0 ) x=\overline{b}=B^{-1}b \geq 0) x=b=B−1b≥0),直到获得(3)的一个基本可行解为止,而它即为原始问题的最优解。 单纯形法的求解过程就是: 在保持原始可行的前提下( b ‾ \overline{b} b列保持≥0),通过逐步迭代实现对偶可行(检验数行≤0)。 对偶单纯形法思想: 换个角度考虑LP求解过程: 保持对偶可行的前提下(检验数行保持≤0), 逐步迭代实现原始可行( b ‾ \overline{b} b列≥0)。 4.2 使用条件(1) 检验数全部 ≤ 0 \leq0 ≤0 (2) 解答列至少一个 b ‾ < 0 \overline{b}< 0 byrjzj−cj∣yrj |
CopyRight 2018-2019 实验室设备网 版权所有 |