原始对偶算法理解过很多次,每一个的理解都不一样,这次将其记录一下
这里定义原始问题为资源有限下的价值最大化模型,A是资源消耗矩阵,b是资源量,c是产品价值向量
max cTx
s.t. Ax <= b
对偶的定义是啥呢,它先组合一下原始的约束,组合权重用y表示,那么组合出来的向量为ATy,我约束其在每个维度的值都大于c,强行赋一个定义可以是保证价值情况下的资源最小化,这样对偶问题就被构造出来了,不难可以知道bTy >= xTATy >= xTc,
min bTy
s.t. ATy >= c
2、
如果x0,y0分别是原始问题和对偶问题的最优解,那么有bTy0 = x0TATy0 = x0Tc。
证明:因为原始问题有最优解,由单纯形法可知,x0 = B-1b,故x0Tc = bT(B-1)Tc >= bTy0,而bTy0 >= x0TATy0 >= x0Tc ,故bTy0 = x0Tc, 故bTy0 = x0TATy0 = x0Tc
这里证明不难,但结论是非常好的,给大家一个体感就是原始问题紧的地方(最优解时为等号的约束)在对偶问题里往往是松的(有可能为紧),但原始问题松的地方对偶问题一定是紧的
3、
互补松弛条件是原始对偶算法的基础,流程为:原始P–对偶D–限制原始RP-限制原始对偶DRP,其基本思想有一个可行解时,再去找对偶问题的可行解,然后按互补松弛的条件不断的迭代
附:
单纯形法从原问题(P)的一个可行解出发, 在满足互补松弛条件的前提下, 使得其对偶变量朝着对偶可行解的方向迭代.