首页 > 代码库 > 单纯形算法与对偶论总结
单纯形算法与对偶论总结
一直以来都对影子价格、对偶解等概念不是特别清楚,最近工作空余,就重新回顾了下线性规划,总结了如下几点,以来供其他小伙伴参考;二来为了自己以后重温;
先将研究对象的定义贴出来吧,方便大家找一找熟悉的感觉
单纯形法定义
单纯形法,求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是:线性规划问题的可行域是 n维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是:先找出一个基本可行解,对它进行鉴别,看是否是最优解;若不是,则按照一定法则转换到另一改进的基本可行解,再鉴别;若仍不是,则再转换,按此重复进行。因基本可行解的个数有限,故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。
原问题与对偶问题定义:
现将单纯形表结构按照不同的目的分解,发现单纯表的奥秘;
1、按基与非基划分:
2、按原变量和松弛变量划分:
总结:
1、检验数,也可以理解为边际贡献,或者商业软件中的reduce cost,为对应X 对目标函数的边际贡献,针对最大化问题,最优解的判断条件为检验数为非正,及所有变量的增加对目标值的感觉没有正向的贡献;
2、 为决策变量的值,为单纯形乘子,也是该问题对偶问题的决策变量的取值该问题对偶问题的决策变量的取值,也称影子价格;
3、按照第二种结构划分可以更清晰表达影子价格和最优解的基变量的结构。同时将此结构结合对偶问题联系来看,更加发现原问题和对偶问题的巧妙关系:
1)、假设原问题为资源定产问题,则对偶问题即为资源定价问题,原问题的松弛变量的检验数为负的为该松弛变量对目标函数的边际贡献,
2)、松弛变量及是剩余资源的代表,松弛变量的对原问题的边际贡献,也就是该项资源在该系统内资源定价,这就是对偶问题所求的资源定价问题,由此可见此种单纯形结构将原问题和对偶问题紧紧的联系在一起。
单纯形算法与对偶论总结