第二章线性规划的对偶理论与灵敏度分析 一、本章内容简要回顾 在这一章里，我们首先由第一章的实际问题引出了线性规划的对偶 问题，阐明了线性规划原问题与其对偶问题的关系；。 接着，论证了对偶问题的五个重要性质：在此基础上， 讲述了求解线 性规划的对偶单纯形法，其计算步骤如下： 步骤1确定原问题的初始基B,使所有检验数O;=C;-CBP;≤0 即Y=CB'是对偶可行解，建立初始单纯形表 步骤2检查基变量的取值，若XBb≥0，则已得最优解，计算停： 否则求 min{(Bb),|(Bb),<0}=(Bb) 确定单纯形表第L行对应的基变量为旋出变量。 步骤3若所有a,≥0，则原问题无可行解，计算停； 否则，计算 0=min (oilaul a<0)=ok/ak 确定对应的x为旋入变量。 步骤4以k为主元作(L,K)旋转变换，得新的单纯形表，转步骤2。 本章还介绍了对偶问题的经济意义一影子价格。 对偶最优解Y=CB=(y1,y2,,y),y表示在原问题已取得最优解的情 况下，第种资源增加一个单位时总收益的增加值，也可以说y是对第 种资源的一种价格估计。这种价格估计并不是第种资源的实际价值或 成本，而是由该企业在制产品的收益来估计所用资源的单位价值，它 是一种潜在的价格称为影子价格。 nULU第二章 线性规划的对偶理论与灵敏度分析  一、本章内容简要回顾 在这一章里，我们首先由第一章的实际问题引出了线性规划的对偶 问题,阐明了线性规划原问题与其对偶问题的关系;。 接着，论证了对偶问题的五个重要性质;在此基础上，讲述了求解线 性规划的对偶单纯形法,其计算步骤如下： 步骤1 确定原问题的初始基B，使所有检验数 ， 即Y=CBB-1是对偶可行解，建立初始单纯形表。 步骤2 检查基变量的取值，若XB=B-1b≥0，则已得最优解，计算停； 否则求 min{(B-1b)i│(B-1b)i＜0｝=(B-1b)ι 确定单纯形表第L行对应的基变量为旋出变量。 步骤3 若所有aιj≥0,则原问题无可行解，计算停；否则，计算 θ=min｛σj / aιj│ aιj ＜0 ｝=σk /aιk 确定对应的xk为旋入变量。 步骤4 以aιk为主元作（L，K）旋转变换，得新的单纯形表，转步骤2。 本章还介绍了对偶问题的经济意义——影子价格。 对偶最优解Y= CBB -1=(y1,y2,…,ym ), yi表示在原问题已取得最优解的情 况下，第i种资源增加一个单位时总收益的增加值，也可以说yi是对第i 种资源的一种价格估计。这种价格估计并不是第i种资源的实际价值或 成本，而是由该企业在制产品的收益来估计所用资源的单位价值，它 是一种潜在的价格,称为影子价格。 C - C B Pj 0 1 σj j B  − =