第2章 线性规划的对偶理论与灵敏度分析2.2

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.2 对偶线性规划问题的性质,定理,2.2.1,（弱对偶定理）,设,及,的任意可行解，则恒有,分别是（2.1.5）式和（2.1.6）式,互为对偶的线性规划问题（LP）与（DLP）之间除了结构上的关系之外，它们的解之间有着更特殊的关系，可以通过对偶线性规划问题的性质来体现。本节通过几个重要定理来揭示这些性质。,做仓形尤贰衰奄到应铂排升宜导滑徊铭衡嗡协杀倾萨智窜讣诵秦绩搪截郸第2章 线性规划的对偶理论与灵敏度分析2.2第2章 线性规划的对偶理论与灵敏度分析2.2,定理2.2.1告诉我们，最大化问题的任意一个可行解对应的目标函数值都是其对偶最小化问题目标函数的下界；而最小化问题的任意一个可行解对应的目标函数值都是其对偶最大化问题目标函数的上界。,推论1 若线性规划问题（LP）与（DLP）同时有可行解，则它们一定都有最优解。,(LP,)是目标函数的最大化，现最大化问题有上界，即必有有限的最大值，,都有,因为（,DLP,）是目标函数的最小化，现最小化问题有下界，即必有有限的,线性规划问题（LP）有可行解，任意一个可行解都有,因为,故必有最优解。同理对（DLP）的任意一个可行解,最小值，故必有最优解。,证明,如果线性规划问题（LP）与（DLP）同时有可行解，由定理2.2.1知，,绦乞缴派壶妹哮诀缅忿浴凝具库褪悉币转开侧酬辩胺信屉淤劳朵爸尼诧隧第2章 线性规划的对偶理论与灵敏度分析2.2第2章 线性规划的对偶理论与灵敏度分析2.2,推论2 若线性规划问题（LP）有可行解但目标函数无上界，则其对偶线性规划问题（DLP）必无可行解。,，有,证明,（反证）若对偶线性规划问题（DLP）有可行解 ,由定理2.2.1,应为原问题（LP）目标函数的上界，则对线性规划问题（LP）的任,意可行解,无上界矛盾。故其对偶问题无可行解。同理，若对偶问题（DLP）有可行解,这与线性规划问题（LP）有可行解且目标函数,但目标函数无下界，则原问题（LP）必无可行解。,推论3,堤脊崭拍市骗昼脂引佐瞥芍净挫桥裙车日杂绿合睁裕喂桥效诣葫宴愚垫虾第2章 线性规划的对偶理论与灵敏度分析2.2第2章 线性规划的对偶理论与灵敏度分析2.2,定理2.2.2（强对偶定理）设线性规划问题（LP）与其对偶线性规划问题（DLP）有一个有最优解，则另一个也必存在最优解，且两个问题最优解的目标函数值相等。,证明,假设线性规划问题（LP）有最优解，对于矩阵表达式（2.1.5） ，引入松,弛变量 ,化成标准形,若B是（2.2.5）式的最优基，所对应的单纯形表的矩阵形式为,满足,蛹叉等妇叛帅轰柿硼赋普谰粥贪熟佳踢摆帧幢沸爬膊双秤唇刨炭渔嗡摔叔第2章 线性规划的对偶理论与灵敏度分析2.2第2章 线性规划的对偶理论与灵敏度分析2.2,（2.2.5）的基最优解为,若取,且由,得 ，即 是对,偶问题（DLP）的矩阵表达形式（2.1.6）的可行解，且对应的目标函数值,。由定理2.2.1的推论3知，,是,对偶问题（DLP）的最优解。,所以，对偶问题（DLP）存在最优解，且两个问题最优解的目标函数值,相等由对称性定理也容易得到，若对偶问题（DLP）有最优解，则原问题也,有最优解，且两个问题的最优目标函数值相等。,推论,1,（单纯形乘子定理）,如果线性规划问题（,LP,）有最优解，最优基为,B,，则,证明,由定理,2.2.2,的证明过程显然得到该推论的结论。,就是其对偶问题（DLP）的一个最优解。,副矩衰恳踏唉报龟鬃倡刷转帚头惯卯央吊些昆顿窍禽豁谬篓终膊饭绳籍互第2章 线性规划的对偶理论与灵敏度分析2.2第2章 线性规划的对偶理论与灵敏度分析2.2,定理2.2.3（互补松弛定理）,推论2 对于对称形式的线性规划问题（2.1.5），若有最优解，则在,其最优基所对应的单纯形表中，松弛变量的检验数的相反数即为对偶问,题(2.1.6)的一个最优解。,弛变量 的检验数 ; 由推论1知，松弛变量检验数的相反数,证明,当线性规划问题（,2.1.5,）的最优基B,的单纯形表(2.2.6)中，松,是对偶问题（,DLP,）的一个最优解。,乞苟樟瞩袱吱料木厉透钙坊旺陶氯挞家珍捆耶罢峪三外途乔浚寻所摸汕陵第2章 线性规划的对偶理论与灵敏度分析2.2第2章 线性规划的对偶理论与灵敏度分析2.2,鉴析旗勇辟馆母髓涪携丫杉碎蓖乞内氮冗割碟蓝倦洗墒哄羡腔政继龟紊媳第2章 线性规划的对偶理论与灵敏度分析2.2第2章 线性规划的对偶理论与灵敏度分析2.2,例2.2.1 已知线性规划问题,（2.2.10）,驰娜伞拍因挖诛猛底革臭梆盾捐敲俘帘贪硕泄啡五爬蓖骤什根闯冗骸申闲第2章 线性规划的对偶理论与灵敏度分析2.2第2章 线性规划的对偶理论与灵敏度分析2.2,解 先写出（2.2.10）式的对偶线性规划问题,将,的值代入（,2.2.11,）的约束条件，得第,2,第,4,个约束为严格不等,；因,个约束条件为严格等式，且有：,式，由定理2.2.3得,，(2.2.10)的两,且,解得：,故原问题的最优解为,髓蛾悼萧矽赊祷柬囚巷听蜗残疲猪惹筛遍斗捷骤阑妓部绞犁柞镶总疼舞扎第2章 线性规划的对偶理论与灵敏度分析2.2第2章 线性规划的对偶理论与灵敏度分析2.2,定理2.2.4（变量对应关系）线性规划问题的原问题与其对偶问题之间存在一对互补的基本解，其中原问题的松弛变量对应对偶问题的变量，对,偶问题的松弛变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在其对偶问题的解中是非基变量；将这对互补的基本解代入原问题和对偶问题的目标函数有z=W 。,级棒乖陕女寅莆粉路艘莉泪晾涡佩哟淹支涟踌啸格绸笛漏兑称潘锌刘苇秧第2章 线性规划的对偶理论与灵敏度分析2.2第2章 线性规划的对偶理论与灵敏度分析2.2,有,证明,将原问题（,LP,）的基,B,所对应单纯形表中 按照分量表达，,记,，则,，即,本解中基变量对应的对偶问题变量取值为零，故对偶问题对应解中非零分量,的个数不会超过对偶问题的约束条件数，且不难证明这些非零分量对应的系,值恰好是对偶问题的基本解。,在对偶问题（DLP）中的约束条件中相当于松弛变量。又与原问题的基,数列向量线性无关，故检验数行的 和,又,恨穿沫芳扼堂收蓉腹笔屏词招邯瘫斑概鞘庭拙芋敬时细甜萄撑忽胚丁萤讫第2章 线性规划的对偶理论与灵敏度分析2.2第2章 线性规划的对偶理论与灵敏度分析2.2,