对偶性与对偶算法

对偶性与对偶算法内容摘要：

同样道理可得 设 Xˆ 是原问题的最优解， Yˆ 是对偶问题的最优解 ib0ˆ  XabTii iyˆ  njYPcx Tjjj  1,0ˆˆ物理意义为生产单位 产品的利润减去按影子价 格计算的资源的总成本，如果差值大于零，应继 续生产，所以最优解必须满足所有检验数非正 如果原问题为标准型 njxbxPtsxc jnjjjnjjj 1,0,..m a x11 是最优基矩阵，在推导强对偶性时已说明其对 偶问题的最优解为 ，于是，非基变量 的检验数可写成 B miiijjjTjjTBj yacPYcPBCc11 ˆˆBT CBY ˆjxj影子价格只能在局部范围内反映资源增长（即 增加约束的右边常数）可以产生的目标函数的 增值，一旦资源增长导致最优基矩阵改变，原 来的最优对偶变量值一般情况下不等于单位资 源增长带来的目标函数的增值，从而失去影子 价格的意义 注意 BT CBY ˆb 改变，但 不变，影子价格 不变 BBT CBY ˆb 改变导致 改变，影子价格 改变 B1x2x621  xx1x2x ,z621  xx影子价格不变，最优目标值增量等于 )56( 例如：例 1中第三个约束的常数项加 1 521  xx521  xx  3,39z  xx521  xx如果 最优基改变，最优目标值增量不等于 )( 对偶单纯型法 例 1 如果取 ，用 左乘等式约束两边，可 将其变换成以下等价的标准线性规划模型 5,2,1,052415100010001125160s .t . 0002m a x5432154321jxxxxxxxxxxxj 215,B P P P 1B5,2,1,01331006161015215151001010s .t . 0002m a x5432154321jxxxxxxxxxxxj5,2,1,01331006161015215151001010s .t . 0002m a x5432154321jxxxxxxxxxxxj将 的表示式代入目标函数，原问题等价为 512 , xxx5,2,1,01331006161015215151001010s .t . 311519m a x5432143jxxxxxxxxj变换后的等价问题对应的单纯型表为 9031151001161152003061151013005110R H SBV51254321zxxxxxxxx该单纯型表的检验数均为非正数，如果右边常数没 有负数，已经得到原问题的最优解 能否在保持检验数非正的前提下消除负的右边数。 9031151001161152003061151013005110R H SBV51254321zxxxxxxxx93115116115243543zxxxxx9621521615243543zxxxxx② ① ① () + ② ① (2) + ② 或 合格 不合格 选比值小的进基。  6131,152151m i n2, i 出基变量行非基变。