线规划的对偶模型DualModelofLP对偶质.ppt

《线规划的对偶模型DualModelofLP对偶质.ppt》由会员分享，可在线阅读，更多相关《线规划的对偶模型DualModelofLP对偶质.ppt（106页珍藏版）》请在三一办公上搜索。

1、2.1 线性规划的对偶模型 Dual Model of LP 2.2 对偶性质 Dual property 2.3 对偶单纯形法 Dual Simplex Method 2.4 灵敏度与参数分析 Sensitivity and Parametric Analysis,2.1.1 引例,【例21】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：,建立总利润最大的数学模型。,2.1 线性规划的对偶模型,3,第2章 对偶理论,【解】设x1，x2，x3分别为产品A，B，C的产量，则,现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，要将现有的资源转让或出租给其它企业，那么

2、资源的转让价格应是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。,2.1.1 引 例,（LP）,4,第2章 对偶理论,设y1，y2，y3，y4分别表示四种资源的单位增值价格 售价成本增值 总增值最低可表示为,min w=500y1+450y2+300y3+550y4,企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100，企业出售这些数量的资源所得的利润（增值）不能少于100，即,同理，对产品B和C有,另有,2.1.1 引 例,yi0,i=1,4,5,第2章 对偶理论,这是一个线性规划数学模型，称这

3、一线性规划问题是前面生产计划模型()的对偶线性规划问题或对偶问题（Dual Poblem,DP）。生产计划的线性规划问题称为原始线性规划问题或原始问题。,2.1.1 引 例,（）,（DP）,6,第2章 对偶理论,观察以上两个线性规划模型的对应关系 原始问题 对偶问题,2.1.1 引 例,原始问题的C,A,b分别转置后就是对偶问题的资源限量(b)，消耗系数(A)及利益系数(C),原始问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可以写出另一个问题。,7,第2章 对偶理论,对 偶 表,2.1.1 引 例,8,第2章 对偶理论,规范形式（Canonical Form）的定义：目标函数求极

4、大值时，所有约束条件为号，变量非负；目标函数求极小值时，所有约束条件为号，变量非负。,2.1.2 线性规划的规范形式,9,第2章 对偶理论,表22,表23,2.1.2 线性规划的规范形式,10,第2章 对偶理论,2.1.3 对偶模型,每个线性规划问题都有一个与之相伴的对偶问题。已知一个问题就可写出另一个问题。当原始问题是规范形式，其对偶问题很容易写出；如果给出的问题不是规范形式，可以先化成规范形式再写对偶问题。也可直接按表2-4中的对应关系写出非规范形式的对偶问题。,11,第2章 对偶理论,设线性规划模型是式（2.1）的规范形式由表2-3知，当检验数,时得到最优解,在 两边右乘b,则有,又因Y

5、0无上界,从而只存在最小值，得到另一个线性规划问题,2.1.3 对偶模型,12,第2章 对偶理论,（2.3）是原始线性规划问题（2.1）的对偶问题，反之，（2.3）的对偶问题是（2.1）。原始问题和对偶问题是互为对偶的两个线性规划问题。规范形式的线性规划的对偶仍然是规范形式。已知一个规范形式问题就可写出另一个对偶问题,2.1.3 对偶模型,其中 Y=(y1,y2，,ym),原始问题,对偶问题,对偶问题,原始问题,13,第2章 对偶理论,【例22】写出下列线性规划的对偶问题,【解】这是一个规范形式的线性规划,2.1.3 对偶模型,14,第2章 对偶理论,【补充例】写出下列线性规划问题的对偶问题,

6、2.1.3 对偶模型,15,第2章 对偶理论,2.1.3 对偶模型,设原始问题是求最小值的非规范形式，则有下列关系,1.第i个约束是“”约束时，第i个对偶变量yi0,2第i个约束是“=”约束时，第i个对偶变量yi无约束；,3当xj无约束时，第j个对偶约束为“=”约束。当xj0时，第j个对偶约束为“”约束。,16,第2章 对偶理论,表2-4,2.1.3 对偶模型,17,第2章 对偶理论,【例2-3】写出下列线性规划的对偶问题,【解】目标函数求最小值，应将表2-4的右边看作原始问题，左边是对偶问题，原始问题有3个约束4个变量，则对偶问题有3个变量4个约束，对照表2-4的对应关系，写出对偶问题。,=

7、,y10，,y20，,y3无约束,2.1.3 对偶模型,y1y2y3,18,第2章 对偶理论,1.本节以实例引出对偶问题;,2.介绍了如何写规范与非规范问题的对偶问题;,2.1.3 对偶模型,下一节：对偶性质,19,第2章 对偶理论,对偶问题,假设Xs与Ys分别是（LP）与（DP）的松驰变量。,原始问题,2.2 对偶问题的性质,2.2.1 对偶性质,20,第2章 对偶理论,【性质2】（弱对偶性）设X、Y分别为LP(max)与 DP(min)的可行解，则,这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值。,【性质1】（对称性）对偶问题的

8、对偶是原问题。,2.2.1 对偶性质,21,第2章 对偶理论,由性质2可得到下面几个推论：推论1:(LP)的任一可行解的目标值是(DP)的最优值下界；(DP)任一可行解的目标是(LP)的最优值的上界；推论2:在互为对偶的两个问题中，若一个问题具有无 界解，则另一个问题无可行解；推论3:若原问题可行且另一个问题不可行，则原问题具 有无界解。注意上述后两个推论的条件不能少。,2.2.1 对偶性质,22,第2章 对偶理论,思考：一个问题无可行解时，另一个问题解的情况怎样？【结论】一个问题无可行解时，另一个问题可能有可行 解（此时具有无界解）也可能无可行解。,2.2.1 对偶性质,23,第2章 对偶理

9、论,例：,无可行解其对偶问题有可行解,由推论3知对偶问题必有无界解。,2.2.1 对偶性质,24,第2章 对偶理论,【性质3】（最优性）设X0与Y0分别是（LP）与（DP）的可行解，则X0、Y0是（LP）与（DP）的最优解 当且仅当C X 0=Y 0b【性质4】（对偶性）若互为对偶的两个问题其中一个 有优解，则另一个也有最优解，且最优值相同。由性质4还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解；若一个问题无最优解，则另一问题也无最优解。,2.2.1 对偶性质,25,第2章 对偶理论,2.2.1 对偶性质,【性质5】（互补松弛定理）X 0、Y 0分别为（LP）与（DP）的可

10、行解，XS 和YS是它的松弛变量的可行 解，则X 0和Y 0是最优解当且仅当YS X 0=0 和 Y 0 XS=0性质5表明：在线性规划的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零。,Y=(1,1),26,第2章 对偶理论,【解】对偶问题是,因为x10，x20，所以对偶问题的第一、二个约束取严格等式，即,解此线性方程组得 y1=1,y2=1 对偶问题的最优解为 Y=(1,1)，最优值w=26。,2.2.1 对偶性质,的最优解是 求对偶问题的最优解。,【例2-4】已知线性规划,因为y20，所以原问题第二个约

11、束取严格等式 x1+x2-x3=6 将y1=0、y2=-2代人对偶问题，得-y1-y2=2y1+y2=-2-1y1-y2=2则原问题的约束条件为线性方程组,【例2-5】已知线性规划 的对偶问题的最优解为Y=(0,-2),求原问题的最优解。,【解】对偶问题为,原问题的最优解为 X=(-5,0,-1)T,最优值 Z=12。,28,第2章 对偶理论,【例2-6】证明下列线性规划无最优解,【证】对偶问题,将三个约束的两端分别相加得而第二个约束有y21，矛盾，故对偶问题无可行解，因而原问题无最优解。,2.2.1 对偶性质,问题：证明【例2-6】具有无界解,29,第2章 对偶理论,【例2-6】证明下列线性

12、规划具有无界解,【证】容易看出X=(4,0,0)是一可行解，故问题可行。对偶问题,将三个约束的两端分别相加得而第二个约束有y21，矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解（性质2.2的推论2）。,2.2.1 对偶性质,30,第2章 对偶理论,【性质6】LP(max)的检验数的相反数对应于DP(min)的一组基本解。其中第 j 个决策变量 xj 的检验数的相反数对应于（DP）中第 j 个松弛变量 的解，第 i 个松弛变量 检验数的相反数对应于第 i 个对偶变量 yi 的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。,性质6给出了原问题与对偶问题解的对应

13、关系。这一规律对于减少单纯形法的计算颇有好处。一般来说，在两个互为对偶的线性规划问题中，可选约束条件少的求解，这样运算量可能减少。注意：应用性质6的前提条件是线性规划为规范形式，性质1-性质5则对所有线性规划都有效。,2.2.1 对偶性质,31,第2章 对偶理论,【例2-7】已知 线性规划,1、用单纯形法求最优解；2、写出每步迭代对应对偶问题的基本解；3、从最优表中写出对偶问题的最优解；4、用公式Y=CBB-1求对偶问题的最优解。,【解】1、加入松弛变量x4、x5后，单纯形迭代如表2-2所示,2.2.1 对偶性质,32,第2章 对偶理论,表2-2,2.2.1 对偶性质,原始问题的最优解 X=(

14、4,6,0)T，最优值 Z=6426=12,-y1-y2,-y3-y4-y5,表（1）对应DP的基本解是：Y（1）=（0，0，-6，2，1）,表（2）对应DP的基本解是：Y（2）=（3，0，0，1，5）,表（3）对应DP的基本解是：Y（3）=（2，2，0，0，11）,3、Y=（2，2）（或Y（3）=（2,2,0,0,11）是DP的最优解 最优值 W=12,33,第2章 对偶理论,2.2.1 对偶性质,表2-2,34,第2章 对偶理论,4、先求B-1，有两种方法【方法1】最优基为 对B求逆矩阵【方法2】B-1 为表22（3）中x4，x 5两列的系数，即,CB=（6，2）,2.2.1 对偶性质,3

15、5,第2章 对偶理论,表26,2.2.1 对偶性质,36,第2章 对偶理论,例2-1 原始问题 对偶问题,2.2.2 影子价格,X=(24.24,0,46.97,0,0,12.12,192.42)T Z=W=5712.12 y1=10.6，y2=0.9，y3=0，y4=0分别称为资源、的影子价格。,Y=(10.6,0.9,0,0),37,第2章 对偶理论,2.2.2 影子价格,X=(24.24，0，46.97，0，0，12.12，192.42)T Y=(10.6，0.9，0，0)经济意义：y1=10.6表示在资源达到最优利用时，每单位资源 给工厂带来的增值是10.6元；y2=0.9表示每单位资

16、源给工厂带来的增值是0.9元；y3=0，y4=0表示资源、过剩，分别剩余12.12，192.42单位。,38,第2章 对偶理论,影子价格(Shadow price):原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格。影子价格是对偶问题最优解中决策变量 yi 的值。,2.2.2 影子价格,39,第2章 对偶理论,由性质4互为对偶的两个线性规划原始问题和对偶问题的最优值相等，故有,即 yi 是第 i 种资源的变化率，说明当

17、其它资源供应量 bk(ki)不变时，bi 增加一个单位时目标值 Z 增加 yi 个单位,2.2.2 影子价格,40,第2章 对偶理论,2.2.2 影子价格,影子价格的经济意义 在最优利用条件下，每单位资源对目标函数的贡献。是对单位资源所带来的经济效益的一种估计。影子价格不是资源的实际价格，而是资源配置结构的反映，是根据资源在生产中作出的贡献而作出的估价，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。,41,第2章 对偶理论,例2-1影子价格的经济意义也可解释为：y1=10.6说明在现有的资源限量的条件下，增加一个单位第一种资源可以给企业带来10.6元的利润；如果要

18、出售该资源，其价格至少在成本价上加10.6元。y2=0.9说明在现有的资源限量的条件下，增加一个单位第二种资源可以给企业带来0.9元的利润；如果要出售该资源，其价格至少在成本价上加0.9元。y3=0，y4=0说明增加第三、第四种资源不会增加利润，因为第三、第四种资源还没有用完，分别剩余12.12，192.42单位。,问题：1.第三、四种资源的售价应是多少，是否不值钱？2.如果要增加利润，企业应增加哪几种资源，各增加多 少后再进行调整？,2.2.2 影子价格,42,第2章 对偶理论,2.2.2 影子价格,注意：影子价格是针对约束条件而言，并不是所有的约束都代表资源的约束。因此影子价格的经济意义应

19、根据原问题的经济背景作出不同的解释。,43,第2章 对偶理论,2.2.2 影子价格,影子价格与市场价格的区别：资源的市场价格是资源作为商品时其价值的货币表现，是已知数，相对比较稳定。而资源的影子价格是依据企业所生产的产品、利润计算出来的帐面价格，即同一种资源在不同的条件下影子价格不同。例如，某种钢板市场价格是每吨8000元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板给企业带来的效益是不一样的。故影子价格是一种动态的价格体系。,44,第2章 对偶理论,资源的影子价格定量地反映资源在系统内的短缺程度及供求矛盾，影子价格越高，资源越稀缺，当某一资源发生剩余时，该资源的影子价格为零。而

20、商品的市场价格一般是不会为零的。,2.2.2 影子价格,影子价格是一个变量。由 的含义知影子价格是一 种边际价格（或机会成本），与bi 的基数有关，在最优基B不变的条件下yi 不变，当某种资源增加或减少时，最优基B可能发生变化，这时yi的值也随之发生变化。,45,第2章 对偶理论,利用影子价格可作下列经济活动分析：（1）调节生产规模。例如,目标函数Z表示利润（或产值）,当第i种资源的影子价格大于零（或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业无利可言，这时应将资源卖掉或出让，缩小生产规模。（2）生产要素对产出贡献的分解。通过影子价格分

21、析每种资源获得多少产出。例如，企业获得100万元的利润，生产过程中产品直接消耗的资源有材料A、材料B、设备和劳动力，这些资源各产生多少利润，由影子价格可以大致估计出来。影子价格为决策者提供原材料转让及设备出租（或租借）的基价。,2.2.2 影子价格,46,第2章 对偶理论,2.2.2 影子价格,（3）用影子价格进行内部核算，对新产品是否值得引进进行可行性分析或对新产品定价。注意：第 i 种资源的影子价格等于零，并不能说明第 i 种资源在生产过程中没有作出贡献，只能表明第 i 种资源有剩余，此时再增加该资源量不会给企业带来利润或产值的增加。,【补充例】某煤机厂生产甲、乙两种产品，受到A、B、C三

22、种资源的约束。产品对三种资源的消耗及资源限量如下表：,（1）问甲、乙两种产品的产量应为多少，才能使该厂获最大利润？（2）求资源的剩余量。（3）求资源的影子价格，并解释其经济意义。（4）以1千元的单价购买A资源，这种投资是否合理，为什么？（5）现有新产品丙，每件需消耗资源A、B、C分别为1，1，2，预计利润为3.2千元，问该产品是否值得生产？,48,第2章 对偶理论,2.2.2 影子价格,【解】（1）设甲、乙两种产品分别生产x1,x2件,最优解 X*=(2,6,2,0,0)T，Z=36即甲、乙产品各生产2，6件，可使该厂获最大利润，最大利润为36千元,用单纯形法求解，得最优单纯形表,49,第2章

23、 对偶理论,（2）因松弛变量x3=2,x4=0,x5=0,故A资源剩余2，B、C资源均无剩余。（3）由单纯形表知，DP的最优解为 y1=0,y2=3/2,y3=1 即A、B、C三种资源的影子价格分别为0,3/2,1千元。经济解释（略）（4）因A资源的影子价格为0（A资源剩余2）,再购买该资源（其它资源不增加），不会使总利润增加，故以任何价格购买该资源都不合理。（5）丙产品的机会成本为 10+12/3+21=7/23.2 所以丙产品不值得生产,只有当利润超过7/2千元时才值得生产。,2.2.2 影子价格,50,第2章 对偶理论,1.本节介绍的6个性质都是原问题与对偶问题的有关解的对应关系；2.性

24、质5和性质6可用来已知一个问题的最优解求另一个问题的最优解；3.第2章的大部分概念都集中在这一节。,下一节：对偶单纯形法,2.2.2 影子价格,4.深刻领会影子价格的含义，学会用影子价格作经济活动分析。,51,第2章 对偶理论,根据对偶性质6，可以构造一个求解线性规划的另一种方法，即对偶单纯形法。,对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题时j0，极小化问题时j0。,2.3 对偶单纯形法,原始问题,对偶问题,52,第2章 对偶理论,【例2-8】用对偶单纯形法求解,【解】先将约束不等式化为等式，再两边同乘以（1），得到,取x4、x5 为基变量，建立初始单纯形表,2.3 对偶单纯形法

25、,53,第2章 对偶理论,表2-7,最优解 X(4，1，0)T；最优值 Z=17,2.3 对偶单纯形法,54,第2章 对偶理论,对偶单纯形法的计算步骤：（1）将线性规划的约束化为等式，取对偶可行基B（全部检验数j0（max）或j0（min），模型为典式）建立初始单纯形表；（2）检验：当基本解可行时，即常数项列B-1b0,达到最优解；若基本解不可行，即B-1b中有负数，则要进行换基迭代；,（3）换基迭代：先确定出基变量。l 行对应的变量xl出基，l 行称为主行；,再选进基变量。求最小比值，k所在列对应的变量xk出基，第k列称为主列。,2.3 对偶单纯形法,55,第2章 对偶理论,若第 l 行所有

26、元素aij 0,说明线性规划无可行解；用初等变换将主元素alk化为 l，主列的其它元素化为零，得到新的单纯形表；重复（2）、（3），直到得出最优解或判断无可行解。,2.3 对偶单纯形法,56,第2章 对偶理论,2.3 对偶单纯形法,【例2-9】用对偶单纯形法求解,【解】取x3、x4为初始基变量,57,第2章 对偶理论,表28,第二张表中x 4=60且第二行的元素全部大于等于零，说明原问题无可行解。,2.3 对偶单纯形法,58,第2章 对偶理论,2.3 对偶单纯形法,注意：,（1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；,（2）最小比值中 的绝对值是使得比值非负；,

27、（3）对偶单纯形法与普通单纯形法换基时主元素的选取不一样，对偶单纯形法的主元素始终为负数，普通单纯形法的主元素始终为正数。,2.3 对偶单纯形法,60,第2章 对偶理论,其目的是保证下一个对偶问题的基本解可行；,（4）普通单纯形法的最小比值是其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是,（5）对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的bi 对应的基变量出基，不影响计算结果，只是迭代次数可能不一样,2.3 对偶单纯形法,61,第2章 对偶理论,本节介绍了一种特殊线性规划的求解方法对偶单纯形法。,1.对偶单纯形法的应用条件；,2.出基与进基的顺序；,3.如何求

28、最小比值；,4.最优解、无可行解的判断。,下一节：灵敏度分析与参数分析,2.3 对偶单纯形法,62,第2章 对偶理论,线性规划的灵敏度分析也称为敏感性分析，它是研究和分析参数（cj，bi，aij）的波动对最优解的影响程度，主要研究下面几个方面的问题：（1）参数在什么范围内变化时，原最优解或最优基不变；（2）当参数已经变化时，最优解或最优基有何变化。当模型的参数发生变化后，可以不必对线性规划问题重新求解，而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解。,2.4 灵敏度分析,63,第2章 对偶理论,【例2-10】某企业用三种资源生产三种产品，消耗系数、资源限量及价值系数如下

29、表：,求总利润最大的生产方案。,2.4 灵敏度分析,64,第2章 对偶理论,【解】建立模型，加入松弛变量x4,x5,x6，用单纯形法求解得最优表,表29,最优解 X=(5，0，15，5，0，0)T;最优值Z=50。对偶问题最优解 Y=(0,1,2),2.4 灵敏度分析,65,第2章 对偶理论,设线性规划,其中Amn，线性规划存在最优解，单纯形表为 最优基B的逆矩阵为,检验数为,2.4.1 价值系数cj的变化分析,2.4 灵敏度与参数分析,66,第2章 对偶理论,（1）cj 是非基变量 xj 的系数,即cj 的增量 不超过xj 的检验数的相反数时，最优解不变，否则最优解就要改变。,所以,当cj变

30、化为 要使最优解不变，则检验数应仍然是小于等于零，即,这时分cj是非基变量和基变量的系数两种情况讨论。,2.4.1 价值系数 cj 的变化分析,67,第2章 对偶理论,（2）ci 是基变量 xi 的系数,令,因ciCB，所以每个检验数j中含有c i,当c i变化为c ici 时，所有非基变量的检验数j同时变化,2.4.1 价值系数 cj 的变化分析,68,第2章 对偶理论,要使得所有，则有,只要求出上限2及下限1就可以求出ci的变化区间。即ci 的增量 ci 在此区间内变化时，最优解不变，否则最优解就要改变。,2.4.1 价值系数 cj 的变化分析,69,第2章 对偶理论,【例】对例2-10分

31、别求c1,c2,c3的变化范围，使得最优解不变。,2.4.1 价值系数 cj 的变化分析,70,第2章 对偶理论,【解】,表29,最优解X=(5，0，15)T;最优值Z=50。,2.4.1 价值系数 cj 的变化分析,71,第2章 对偶理论,c1对应的变量x1为基变量：最优表中x 1对应行的系数只有一个负数,有两个正数,c1的变化范围是：,2.4.1 价值系数 cj 的变化分析,x2为非基变量，则,c2变化范围是：,72,第2章 对偶理论,c3无上界，即有c32，c3的变化范围是,对于c3：最优表中x3对应行,2.4.1 价值系数 cj 的变化分析,73,第2章 对偶理论,对c3的变化范围，也

32、可直接从最优表推出。将c3=3写成,分别计算非基变量的检验数并令其小于等于零。,2.4.1 价值系数 cj 的变化分析,74,第2章 对偶理论,得c32，即同理，用此方法可求出c2和c1的变化区间。,要使 同时小于等于零，解不等式组,2.4.1 价值系数 cj 的变化分析,75,第2章 对偶理论,常数项b的变化与检验数C-CBB-1A无关，但会导致基变量XB=B-1b的变化，若变化后的B满足 则B仍为最优基。,设br的增量为br，b的增量为 要使最优基B不变，即要使,2.4.2 资源限量bi 的灵敏度分析,因为,所以,77,第2章 对偶理论,令,2.4.2 资源限量bi 的灵敏度分析,因而要使

33、得所有 必须满足,即br的增量br 在此区间内变化时，最优基不变，否则最优基就要改变。注意：最优基不变不等于最优解不变。br在允许范围内变化只能说明产品结构不变，但生产量 有可能改变。,【解】由表29知，最优基B、B1及XB分别为,对于b1：比值的分母取B1的第一列，则,b1无上界，即b15，因而b1在35,+)内变化时最优基不变。,【例2-11】求例2-10的b1、b2、b3分别在什么范围内变化时，原最优基不变。求b2由20变为24时的最优解。,对于b2：比值的分母取B1的第二列，120，220，则,即b215，25 时最优基不变,此时，最优解为 X=(9,0,15)T，最优值Z=54,80

34、,第2章 对偶理论,对于b3：比值的分母取B1的第三列，有,故有15b35，b3 0，20 时最优基不变。,若线性规划模型是一个生产计划模型，当求出cj或bi的最大允许变化范围时，就可随时根据市场的变化来掌握生产计划的调整。,2.4.2 资源限量bi 的灵敏度分析,81,第2章 对偶理论,2.4.2 资源限量bi 的灵敏度分析,【补充例】求例2-10的b2由20变为30时的最优解。,【解】由例2-11知b2的变化范围是15，25 即b2=30时，在范围之外,XB不可行，原方案不再是最优方案在原最优表的基础上用对偶单纯形法求解,82,第2章 对偶理论,2.4.2 资源限量bi 的灵敏度分析,表2

35、9,最优解X=(10，0，15，0，5，0)T，最优值Z=55。,83,第2章 对偶理论,说明：上述cj及bi的最大允许变化范围是假定其它参数不变的前提下，单个参数的变化范围，当几个参数同时在各自范围内变化时，最优解或最优基有可能改变。,灵敏度分析的关键在于线性规划某些参数或条件发生变化时，需要判断最优表中哪些数据发生了变化，如何求这些数据，如果不是最优解再用什么方法计算等问题。前两个问题可以直接用1.5的矩阵公式判断和计算。将这些问题简要综合在表2-15中。,2.4.2 资源限量bi 的灵敏度分析,84,第2章 对偶理论,2.4.3 综合分析,灵敏度分析方法还可以分析工艺系数aij的变化对最

36、优解的影响，对增加约束、变量或减少约束、变量等情形的分析。,85,第2章 对偶理论,【例2-12】考虑下列线性规划,求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。,（1）改变右端常数为:,2.4.3 综合分析,86,第2章 对偶理论,（2）改变目标函数x3的系数为c3=1;,（3）改变目标函数中x2的系数为c2=2；,（4）改变x2的系数为,（5）改变约束（1）为,（6）增加新约束,（7）增加新约束,2.4.3 综合分析,87,第2章 对偶理论,【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如下,表210,最优解X=（1，0，2，0，0，1）T，最优值Z=10

37、,2.4.3 综合分析,88,第2章 对偶理论,最优基矩阵及其逆矩阵为,（1）基变量的值为,基本解不可行，将求得的XB代替表210中的常数项，用对偶单纯形法求解，其结果见表211所示。,2.4.3 综合分析,89,第2章 对偶理论,表211,2.4.3 综合分析,90,第2章 对偶理论,（2）由表210容易得到基变量x3的系数c3的增量变化范围是,而c3=1在允许的变化范围之外，故表210的解不是最优解。计算非基变量的检验数,x4进基，用单纯形法计算，得到表212,2.4.3 综合分析,91,第2章 对偶理论,表212,最优解为X=（3，0，0，14，0，1)T，最优值z=6。,2.4.3 综

38、合分析,92,第2章 对偶理论,2.4.3 综合分析,方法2：直接求出x2的检验数,（3）c2是非基变量x2的系数，由表27知，由 1变为2时，从而最优解不变。,方法2：直接求出x2的检验数,（3）c2是非基变量x2的系数，由表27知，由 1变为2时，从而最优解不变。,方法2：直接求出x2的检验数,（3）c2是非基变量x2的系数，由表27知，由 1变为2时，从而最优解不变。,93,第2章 对偶理论,(4)这时目标函数的系数和约束条件的系数都变化了，同样求出2判别最优解是否改变。,x2进基，计算结果如表213所示,2.4.3 综合分析,94,第2章 对偶理论,表213,最优解,2.4.3 综合分

39、析,95,第2章 对偶理论,（5）第一个约束变为 实际上是改变了a12及b1，这时要求2及XB，判断解的情况。,因为 可行，所以最优基不变，最优解为,2.4.3 综合分析,96,第2章 对偶理论,。,（6）先验证最优解X=(1,0,2)是否满足该约束，若满足，最优解不变。（不满足）引入松弛变量x7得,x1、x3是基变量，利用表210消去x1、x3，得,x7为新的基变量，将上式加入表210中用对偶单纯形法迭代得到表2-14。,2.4.3 综合分析,97,第2章 对偶理论,表214,最优解,2.4.3 综合分析,98,第2章 对偶理论,（7）将原最优解代入约束 的左边有 5122=110，满足新约

40、束，故最优解不变。,2.4.3 综合分析,当 且 时用单纯形法继续迭代；当 且 不可行时用对偶单纯形法继续迭代；当 且 不可行时，需加入人工变量另找可行基。,注意：,99,第2章 对偶理论,说明：上述cj及bi的最大允许变化范围是假定其它参数不变的前提下，单个参数的变化范围，当几个参数同时在各自范围内变化时，最优解或最优基有可能改变。,灵敏度分析的关键在于线性规划某些参数或条件发生变化时，需要判断最优表中哪些数据发生了变化，如何求这些数据，如果不是最优解再用什么方法计算等问题。前两个问题可以直接用1.5的矩阵公式判断和计算。将这些问题简要综合在表2-15中。,2.4.3 综合分析,表2-15,

41、101,第2章 对偶理论,参数分析是研究线性规划的价值系数与资源限量中附加了一个参数：,分析参数在不同取值区间内最优解的变化分析，是研究最优解对于参数摄动的一种灵敏度分析方法,【例2-13】线性规划,(1)求参数0时的最优解(2)讨论在区间(，)内的变化,2.4.4 参数分析,102,第2章 对偶理论,【解】（1）0时就是普通线性规划，加入松弛变量x4、x5，最终单纯形表见表2-16 最优解X（8，9，0），目标值Z67,表2-16,2.4.4 参数分析,103,第2章 对偶理论,(2)将约束条件右端分解成下列成的线性式,则带参数的单纯形表见表2-17,2.4.4 参数分析,表2-17,(1)

42、当18时表2-17(1)仍然是最优表,最优解是参数的函数 X（8，9+0.5，0）,目标值Z67+1.5(2)当18时最优解X（8，0，0），目标值Z40(3)当18时不可行，用对偶单纯形法，x2出基x5进基得到表2-17(2)，当3018时最优解X=（20+2/3，0，0），最优值Z100+10/3(4)当30时无可行解目标函数与参数的关系如图2.1所示,105,第2章 对偶理论,同理，当目标函数中含有参数时，先令参数等于零，再用公式求出检验数，分析参数在不同区间解的关系,图2.1,2.4.4 参数分析,106,第2章 对偶理论,The End of Chapter 2,1.注意最优解与最优基不变的区别；2.掌握某个参数变化后，最优表中哪些数据会发生变化，如何变化；3.模型发生变化后不是重新求解，而是在原模型的最优表中求出变化后的数据，根据变化条件，选择合适的方法继续计算。4.了解参数分析的思路。,5.利用WinQSB软件中的修改（Modify problem）和Perform Parametric Analysis功能，进行灵敏度分析和参数分析。,2.4.4 参数分析,