所谓满足对偶可行性,即指其检验数满足最优性条件。只要保持检验数满足最优性条件前提下,一旦基解成为可行解时,对偶问题和原问题均可行,由强对偶性证明,二者均有最优解。
设原始问题的标准形式为max{cxAx=b,x≥0},则其对偶问题(Dual Problem)为 min{ybyA≤c}。当原问题的一个基解满足最优性条件时,其检验数小于等于0,当σ=cj-zj=cj-CBB-1A≤0时,既有或,即知单纯形算子y=CBB-1为对偶问题的可行解。换而言之,只要保证检验数σ≤0,则对偶问题一定存在可行基B。
在初始单纯形表中,一般此可行基B都为单位矩阵I,这时候只要能够保持检验数持续小于等于0迭代下去,通过变换到一个相邻的目标函数值较小的基可行解(因为对偶问题是求目标函数极小化),并循环进行,一到XB=B-1b≥0时,原问题也为可行解。这时,对偶问题和原问题均为可行解,而且两者的可行解就是最优解,这就是对偶单纯形法求解线性规划的基本思路。
一旦最终基变量XB≥0,原问题也满足最优解条件的原因是:对偶问题的最终单纯形表中的基变量XB=B-1b和原问题的最终单纯形表中的检验数的相反数CBB-1取值相等,不难观察到原问题的检验数σ=cj-zj-CBB-1=-B-1b≤0,其检验数满足最优性条件。(注:这里的B并不是同一个矩阵,它们是各自问题的初始可行基,但CB和b在本质上是同一个向量。)
虽然,本方法借鉴了对偶理论的思路,但是它是求解原问题而非对偶问题的一个方法。而且,一般用对偶单纯形法解决的是原始问题是极小化问题,min{cxAx=b,x≥0},但是只要先标准化为max{cxAx=b,x≥0}即于上面一致。
未经允许不得转载:五金工具_五金配件_五金建材_机械设备-森宝五金网 > 对偶单纯形法例题详细步骤?对偶单纯形法求解过程
热门信息
阅读 (18653)
1 数控车床,拉杆与液压卡盘行程的关系?液压卡盘拉杆调节行程阅读 (8149)
2 304不锈钢螺钉盐雾试验48小时不生锈是不是达到标准啊?阅读 (6140)
3 藏青色的上衣配什么颜色的裤子和鞋子好?阅读 (2743)
4 国家铁路职业技能证书查询入口?阅读 (2031)
5 电线字母ns是什么线?电线上的n是什么意思