运筹学-第二章-对偶理论与灵敏度分析课件.pptx

1、运筹学运筹学第二章第二章 对偶理论与对偶理论与灵敏度分析灵敏度分析学习目标学习目标v对偶问题对偶问题v对偶定理对偶定理v对偶单纯形法对偶单纯形法v灵敏度分析灵敏度分析3开篇案例开篇案例某工厂在计划期内要安排生产甲、乙两种产品，已某工厂在计划期内要安排生产甲、乙两种产品，已知生产单位产品所需要的设备台时及知生产单位产品所需要的设备台时及A、B两种原两种原材料的消耗，该工厂每生产一件产品甲可获利材料的消耗，该工厂每生产一件产品甲可获利2元，元，每生产一件产品乙可获利每生产一件产品乙可获利3元。假设该工厂决定不元。假设该工厂决定不再生产甲、乙产品，而将其出租或出售，这时该如再生产甲、乙产品，而将其出

2、租或出售，这时该如何考虑每种资源的定价？何考虑每种资源的定价？45 设 分别为出租单位设备台时的租金和出让单位原材料A、B的附加额。试考虑，若用一个单位台时和4个单位原材料A生产一件产品甲，可获利2元，那么生产每件产品甲的设备台时和原材料出租和出让的收入应不低于生产一件甲产品的利润，即 。同理，将生产每件乙产品的设备台时和原材料出租和出让的收入应不低于生产一件乙产品的利润，即 。将工厂所有设备台时和资源都出租和出让，其收入为 。对工厂来说，越大越好，但对接受者来说，支付的愈少愈好，所以工厂只能在满足大于等于所有产品的利润前提下，使其总收入尽可能小，才能实现其愿望。为此，得到如下模型：通过该模型

3、的求解，即可得到工厂出租和出让3种资源的收入不低于生产产品的定价策略。123,yyy1242yy13243yy12381612yyy1231213min81612422430,1,2,3jyyyyyyyyj2.1 线性规划问题的对偶及其变换线性规划问题的对偶及其变换 对偶理论是线性规划中的重要内容之一，每个线对偶理论是线性规划中的重要内容之一，每个线性规划问题都伴随一个与之相对应的线性规划问题，性规划问题都伴随一个与之相对应的线性规划问题，一个问题称为原问题，则另一个则称为其对偶问题。一个问题称为原问题，则另一个则称为其对偶问题。原问题与对偶问题有着非常密切的关系，对偶理论原问题与对偶问题有着

4、非常密切的关系，对偶理论深刻地揭示了原问题和对偶问题的内在联系，为进深刻地揭示了原问题和对偶问题的内在联系，为进一步深入研究线性规划理论提供了依据。一步深入研究线性规划理论提供了依据。62.1.1 对偶问题的提出对偶问题的提出例例2-1 已知资料如表已知资料如表2-1所示，问怎样安排生产计划所示，问怎样安排生产计划使得既能充分利用现有资源又使得总利润最大？使得既能充分利用现有资源又使得总利润最大？7根据线性规划理论，可假设甲、乙两种产品的产量根据线性规划理论，可假设甲、乙两种产品的产量分别为分别为x1、x2件，使得总利润最大件，使得总利润最大 8 如果从另一个角度来讨论这个问题，现假设：该如果

5、从另一个角度来讨论这个问题，现假设：该厂的决策者不是考虑自己生产甲、乙两种产品，而厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外来加工任务，只收是将厂里的现有资源用于接受外来加工任务，只收取加工费。试问该决策者应如何制定合理的收费标取加工费。试问该决策者应如何制定合理的收费标准（接受外来加工任务利润至少不比生产产品获利准（接受外来加工任务利润至少不比生产产品获利少）？少）？这个问题可以从两个方面来思考：（这个问题可以从两个方面来思考：（1）要求每）要求每种资源收回的费用不能低于自己生产时的可获利润；种资源收回的费用不能低于自己生产时的可获利润；（2）定价又不能太高，因

6、为要使对方能够接受。）定价又不能太高，因为要使对方能够接受。9 假设假设y1,y2,y3分别为三种资源的收费定价，每种分别为三种资源的收费定价，每种资源收回的费用不能低于自己生产时的可获利润，资源收回的费用不能低于自己生产时的可获利润，所以有所以有 1011从承租方来看，是使租金 ，最少，则对承租方应有如下模型：对以上模型进行求解，得出的结果就是租赁双方决策者认为的最优方案。123200100150yyy123123123123min2001001505210 23518,0 yyyyyyyyyy yy12把生产模型（原问题）与租赁模型（对偶问题）进行对比：站在生产者的立场上建立起来的数学模型

7、同站站在生产者的立场上建立起来的数学模型同站在承租方立场上所建立的数学模型加以对比，可以在承租方立场上所建立的数学模型加以对比，可以发现它们的参数是一一对应的。即建立后一个模型发现它们的参数是一一对应的。即建立后一个模型并不需要在前一个模型的基础上增加任何补充信息。并不需要在前一个模型的基础上增加任何补充信息。亦即后一个线性规划问题是前一个线性规划问题从亦即后一个线性规划问题是前一个线性规划问题从相反角度所作的阐述；如果前者称为线性规划的原相反角度所作的阐述；如果前者称为线性规划的原问题，那么后者就称为其对偶问题。问题，那么后者就称为其对偶问题。132.1.2 对偶问题的一般形式对偶问题的一般

8、形式线性规划原问题的标准形式为：线性规划原问题的标准形式为：1415用 代表第i种资源的估价，则其对偶问题的形式为:1,2,iy im11221112121112122222112201,2,mmmmmmnnmnmniMinb yb yb ya ya yayca ya yayca yayaycyim用矩阵形式表示，对称形式的线形规划问题的原问用矩阵形式表示，对称形式的线形规划问题的原问题为：题为：其对偶问题为：其对偶问题为：16 如果将目标函数求极大值、约束条件取小于等于如果将目标函数求极大值、约束条件取小于等于号、决策变量非负的线性规划问题称为对称形式的号、决策变量非负的线性规划问题称为对称

9、形式的原问题。原问题。对称形式的原问题与其对偶问题的对应关系可概对称形式的原问题与其对偶问题的对应关系可概括为：括为：v1若原问题目标函数求极大值，那么对偶问题若原问题目标函数求极大值，那么对偶问题目标函数求极小值；目标函数求极小值；v2原问题决策变量的数目等于对偶问题约束条原问题决策变量的数目等于对偶问题约束条件的数目；件的数目；17v3原问题约束条件的数目等于对偶问题决策变原问题约束条件的数目等于对偶问题决策变量的数目；量的数目；v4原问题的价值系数原问题的价值系数 成为对偶问题的资源系数成为对偶问题的资源系数；v5原问题的资源系数原问题的资源系数 成为对偶问题的价值系数成为对偶问题的价值

10、系数；v6原问题的技术系数矩阵与对偶问题的技术系原问题的技术系数矩阵与对偶问题的技术系数矩阵互为转置；数矩阵互为转置；v7原问题约束条件为原问题约束条件为“”，对偶问题约束条，对偶问题约束条件为件为“”；v8原问题决策变量大于等于零，对偶问题决策原问题决策变量大于等于零，对偶问题决策变量大于等于零。变量大于等于零。18 一般地一般地v（1）如果原问题是）如果原问题是MAX问题，则其对偶问题是问题，则其对偶问题是MIN问题，按下表可将其对偶问题写出。问题，按下表可将其对偶问题写出。1920（2）如果原问题是）如果原问题是MIN问题，则其对偶问题是问题，则其对偶问题是MAX问题，按下表可将其对偶问

11、题写出。问题，按下表可将其对偶问题写出。2122例例2-2 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题 23解：其对偶问题为解：其对偶问题为 2425例例2-3 写出下列线性规划问题的对偶问题26解：其对偶问题为：2.2 线性规划对偶问题的基本性质线性规划对偶问题的基本性质 假定原问题为：假定原问题为：27性质性质1(1(对称性对称性)对偶问题的对偶问题是原问题对偶问题的对偶问题是原问题 证明：证明：设原问题为对偶问题为对偶问题的对偶问题为比较模型(2-7)和式(2-9),显然二者是等价的,命题得证。2829证明：根据模型(2-7),由于 ,又由于 ,从而必有：根据模型(2-

12、8),由于 ，又由于 ，从而必有结合式(2-11)和式(2-12),立即可得 ，命题得证性质性质2(2(弱对偶性弱对偶性)设原问题为模型设原问题为模型(2-7)(2-7)，对偶问，对偶问题为模型题为模型(2-8),(2-8),是原问题的任意一个可行解是原问题的任意一个可行解,是是对偶问题的任意一个可行解对偶问题的任意一个可行解,那么总有那么总有YXAXb0Y YAc0X CXYb30性质性质3(3(最优性最优性)：设 原问题模型(2-7)的可行解,是对偶问题题模型(2-8)的可行解,当是 时，是原问题模型(2-7)的最优解，是对偶问题模型(2-8)的最优解。*Y*C XY b*Y证明:设 是模

13、型(2-7)的最优解,那么有由于 ，那么根据弱对偶性质，又有从而 ，也就是 是原问题模型(2-7)的最优解。同理可证明 是对偶问题模型(2-8)的最优解。X*CXY b*(2 15)CX Yb*CXCX*X*Y31 性质性质4(无界性无界性)设原问题为无界解，则对偶问题无解设原问题为无界解，则对偶问题无解证明：用反证法证明。设原问题为模型(2-7)，对偶问题为模型(2-8)。假定对偶问题有解，那么存在一个可行解为 ，这时对偶问题的目标函数值为 。由于原问题为无界解，那么一定存在一个可行解 满足 ，因此 。而根据弱对偶性，又有 ，发生矛盾。从而对偶问题没有可行解。YYbTXCXTCXYbCXYb

14、32证明：设B为原问题模型(2-7)的最优基，那么当基为B时的检验数为 ，其中 为由基变量的价值系数组成的价值向量。既然B为原问题模型(2-7)的最优基，那么有 。令：，那么有 ，从而 是对偶问题模型(2-8)的可行解。这样一来，是对偶问题的可行解，是原问题的最优基可行解。由于 ，而 ，从而有 。根据性质（3），命题得证性质5(强对偶性、对偶性定理)若原问题有最优解，那么对偶问题也有最优解，且最优目标函数值相等1BCC B ABC10BCC B A0CYAYAC33证明：设原问题和对偶问题的标准型是原问题对偶问题将原问题目标函数中的系数向量C用 代替后，得到：将对偶问题的目标函数中系数列向量，

15、用 代替得到：若 则 ，由最优性可知 分别是原问题和对偶问题的最优解性质6(对偶松弛定理、松弛性)若 分别是原问题和对偶问题的可行解，那么 和 ，当且仅当 为最优解34又若 分别是原问题和对偶问题的可行解，再根据最优性，则有由式(2-16)和(2-17)，必有2.3 对偶单纯形法对偶单纯形法2.3.1对偶单纯形法的基本思路对偶单纯形法的基本思路v前面介绍的单纯形法可以解决一切线性规划问题，前面介绍的单纯形法可以解决一切线性规划问题，但它对于某些特殊问题，虽然也可解决，但计算但它对于某些特殊问题，虽然也可解决，但计算量较大。对偶单纯形法是根据对偶原理和单纯形量较大。对偶单纯形法是根据对偶原理和单

16、纯形法的原理而设计出来求解线性规划问题的一种方法的原理而设计出来求解线性规划问题的一种方法（而不能简单的将它理解为是求解对偶问题的法（而不能简单的将它理解为是求解对偶问题的方法）。方法）。35例如线性规划问题例如线性规划问题3637在约束方程中出现了一个负单位矩阵，若将剩余变量 取作初始基变量，则初始基 ，初始解 不满足可行性，因此不能将 取作初始基，为了求得初始基本可行解，需在约束方程左边增加一组人工变量，通过大M法或两阶段法进行计算，这就显得很不方便，且 也没能利用上。考察一般的标准形式的线性规划问题及其对偶问题：38设B为原问题(P)的一个基，不妨设则 为原问题的（P）的一个基本解；且当

17、时，则 为一个基可行解，B为可行基；进一步若检验数满足则 为原问题（P）的一个最优解，这时B称为最优基。以上概念都是对原问题（以上概念都是对原问题（P）而言的，因此，我）而言的，因此，我们更将条件们更将条件(2-19)称为可行性条件；条件称为可行性条件；条件(2-20)称称为最优性条件。为最优性条件。3940原始单纯形法的基本思路是：从满足可行性条件(2-19)的一个基可行解出发，经过换基运算迭代到另一个基可行解，即总是保持解的可行性不变（满足条件(2-19)），变化的只是检验数向量 ，它从不满足 ，逐步迭代到 成立，一旦达到 ，也就得到了原问题的最优解。41再从对偶的观点来解释这个问题，令

18、代入式2-20，得：即y是对偶问题（D）的一个可行解。条件(2-21)称为对偶可行性条件，即最优性条件(2-20)与对偶可行性条件(2-21)是等价的，因此，如果一个原始可行基B是原问题（P）的最优基，则 就是对偶问题（D）的一个可行解，此时对应的目标函数值 等于原问题（P）的目标函数值，可知 也是对偶问题（D）的最优解。若原问题（若原问题（P）的一个基本解）的一个基本解 对应的对应的检验数向量满足条件检验数向量满足条件(2-20)，即，即则称则称X为（为（P）的一个正则解。）的一个正则解。于是可知，原问题（于是可知，原问题（P）的正则解）的正则解x与对偶问题与对偶问题（D）的可行解）的可行解

19、y是一一对应的，它们由同一个基是一一对应的，它们由同一个基B所决定，我们称这一基为正则基。所决定，我们称这一基为正则基。42 因此，我们可以设想另一条求解思路，即在迭代因此，我们可以设想另一条求解思路，即在迭代过程中，始终保持对偶问题解的可行性，而原问题过程中，始终保持对偶问题解的可行性，而原问题的解由不可行逐渐向可行性转化，一旦原问题的解的解由不可行逐渐向可行性转化，一旦原问题的解也满足了可行性条件，也就达到了最优解。也即在也满足了可行性条件，也就达到了最优解。也即在保持正则解的正则性不变条件下，在迭代过程中，保持正则解的正则性不变条件下，在迭代过程中，使原问题解的不可行性逐步消失，一旦迭代

20、到可行使原问题解的不可行性逐步消失，一旦迭代到可行解时，即达到了最优解。这正是对偶单纯形法的思解时，即达到了最优解。这正是对偶单纯形法的思路，这个方法并不需要把原问题化为对偶问题，利路，这个方法并不需要把原问题化为对偶问题，利用原问题与对偶问题的数据相同（只是所处位置不用原问题与对偶问题的数据相同（只是所处位置不同）这一特点，直接在反映原问题的单纯形表上进同）这一特点，直接在反映原问题的单纯形表上进行运算。行运算。432.3.2对偶单纯形法的计算步骤对偶单纯形法的计算步骤求解如下标准形式线性规划问题求解如下标准形式线性规划问题:对偶单纯形法的计算步骤：对偶单纯形法的计算步骤：4445（1）找一

21、个正则基B和初始正则解 ，将原问题化为关于基B（不妨设 ）的典式，列初始对偶单纯形表，见表2-5。表2-5对偶单纯形表jc1c2cmc1mc2mcncBcBx b1x2xmx1mx2mxnx1c1x 1b11ma21mana12c2x 2b12ma22mana2 mcmxmb1mma2mmamna1m2mn462.若 ，则停止计算，当前的正则解 ，即为原问题的最优解；否则转下一步。3.确定换出（出基）变量：令 ，（显然 ），则取相应的变量，为换出（出基）变量。4.若 ，（j=1,2,n），则停止计算，原问题无可行解。否则转下一步。5.确定进（换入）基变量：若则取相应的变量 为进（换入）基变量。

22、6.以 为主元进行换基运算，得到新的正则解，转（2）。例例2-4 用对偶单纯形法求解用对偶单纯形法求解 47解：解：将问题化为将问题化为其中其中 松弛变量，取初始正则基松弛变量，取初始正则基则问题已化为关于基则问题已化为关于基B的典式，初始正则解为：的典式，初始正则解为：及目标函数值及目标函数值48建立对偶单纯形表并进行迭代见表2-5，由表2-6（）可知，因为49表2-6 对偶单纯形法求解例2-4的单纯形表过程50故应取 为换出基变量，又因为 故应取 为换入基变量，以 为主元作换基运算，得由表2-6（），又该表可知，因为故应取 为换出基变量，又因为故应取 为换入基变量，以 为主元作换基运算，得

23、表2-6()，至此，基变量的取值已全部非负，检验已全部非正，故已求得最优解 及相应的目标函数最优值，原问题的目标函数最优值 由表2-6()还可以看出，其对偶问题的最优解为 及目标函数最优值例例2-5 用对偶单纯形法求解用对偶单纯形法求解 51解：将问题化为解：将问题化为:其中 为松弛变量，取初始正则基 则问题已代为关于基B的典式，初始正则解为：及目标函数值用对偶单纯形法求解、迭代过程如表2-6。5253表表2-62-6续表续表54 由表由表2-6（）可知，基变量的取值已全部非负，）可知，基变量的取值已全部非负，检验数已全部非正，故已求得最优解检验数已全部非正，故已求得最优解:x*=(6,2,0

24、,0,2,0)T及原问题目标函数最优值及原问题目标函数最优值Z*=20。55v 从以上求解过程可以看到，对偶单纯形法与原从以上求解过程可以看到，对偶单纯形法与原始单纯形法的计算步骤类似，但又有所不同，对始单纯形法的计算步骤类似，但又有所不同，对偶单纯形法有以下优点：偶单纯形法有以下优点：v（1）初始解可以是非可行解，当检验数都为负）初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人数时，就可以进行基的变换，这时不需要加入人工变量，因此，可以简化计算；工变量，因此，可以简化计算；v（2）变量多于约束条件的线性规划问题，用对）变量多于约束条件的线性规划问题，用对偶单纯形

25、法计算可以减少计算工作量，因此，对偶单纯形法计算可以减少计算工作量，因此，对变量较少，而约束条件很多的线性规划问题，可变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求先将它变换成对偶问题，然后用对偶单纯形法求解。解。562.4 对偶问题的经济解释对偶问题的经济解释影子价格影子价格2.4.1 影子价格的概念影子价格的概念考虑一对对称的对偶问题从对偶问题的基本性质可知，当（P）问题求得最优解 其（D）问题也得到最优解 ，且有57 对偶变量对偶变量yi*的意义代表在资源最优利用条件下对的意义代表在资源最优利用条件下对单位第单位第i种资源的估价，这种估价不是资源的市

26、场种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而得到的价格，而是根据资源在生产中作出的贡献而得到的估价，称之为影子价格。估价，称之为影子价格。资源的影子价格有赖于资源的利用情况，不同企资源的影子价格有赖于资源的利用情况，不同企业，即使是相同的资源，其影子价格也不一定相同，业，即使是相同的资源，其影子价格也不一定相同，就是同一个企业，由于企业生产任务、产品结构等就是同一个企业，由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。情况发生变化，资源的影子价格也随之改变。5859在在(2-22)式中对式中对z求求 的偏导数，得的偏导数，得 ，这说，这说明明

27、 的值相当于在资源得到最优利用的生产条件下，的值相当于在资源得到最优利用的生产条件下，每增加一个单位时目标函数每增加一个单位时目标函数z的增量，所以，影的增量，所以，影子价格是一种边际价格。子价格是一种边际价格。例例2.6 某企业产品的单位产值，对三种资源的单位某企业产品的单位产值，对三种资源的单位消耗及资源的现有数量如表消耗及资源的现有数量如表2-7，经理对其生产的，经理对其生产的甲、乙两种产品，用线性规划来确定最优的产量方甲、乙两种产品，用线性规划来确定最优的产量方案。案。60用单纯形法解这个线性规划问题，得初始及最优单用单纯形法解这个线性规划问题，得初始及最优单纯形表（表纯形表（表2-8

28、2-8）。）。61 求解结果说明最优生产方案为甲产品生产求解结果说明最优生产方案为甲产品生产35件，件，乙产品生产乙产品生产10件，总产值达到最大为件，总产值达到最大为215。同时在最优单纯形表中，得到对偶解，即影子价同时在最优单纯形表中，得到对偶解，即影子价格：资源格：资源A的影子价格的影子价格y1=0；资源；资源B的影子价格的影子价格y2=1；资源；资源C的影子价格的影子价格y3=3。资源资源A的影子价格为零，说明增加这种资源不会的影子价格为零，说明增加这种资源不会增加总的产值，如在表增加总的产值，如在表2-8的初始表中的的初始表中的90改为改为91，则最优单纯形表为表则最优单纯形表为表2

29、-9，这说明资源，这说明资源A的增加不改的增加不改变产品生产方案，也不增加总的产值。变产品生产方案，也不增加总的产值。6263如果资源如果资源C增加一个单位从增加一个单位从45改为改为46，最优单纯形，最优单纯形表为表表为表2-10。64 这说明增加一个单位的资源这说明增加一个单位的资源C以后，最优生产方以后，最优生产方案为甲产品生产案为甲产品生产34件，乙产品生产件，乙产品生产12件，总产值由件，总产值由原来原来215件增加到件增加到218，增加了，增加了3个单位，即为该资个单位，即为该资源的影子价格格或边际价格。源的影子价格格或边际价格。6566由对偶问题的互补松弛定理中有 时，；当 时，

30、有 ，这表明生产过程中，如果某种资源，未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。2.4.2 影子价格在企业经营管理中的应用影子价格在企业经营管理中的应用 影子价格在企业经营管理中的用处很多，可从以影子价格在企业经营管理中的用处很多，可从以下方面来理解。下方面来理解。v1影子价格说明增加哪一种资源对增加经济效影子价格说明增加哪一种资源对增加经济效益最有利。如例益最有利。如例2.6中的三种资源的影子价格为中的三种资源的影子价格为（0,1,3），说明首先应考虑增加资源），说明首先应考虑增加资源C，因为相，因为相比之下它能给收益带来的增加最大

31、。比之下它能给收益带来的增加最大。v2.影子价格又是一种机会成本，企业经营决策者影子价格又是一种机会成本，企业经营决策者可以把本企业资源的影子价格与当时的市场价格可以把本企业资源的影子价格与当时的市场价格进行比较，当年进行比较，当年i种资源的影子价格高于市场价格种资源的影子价格高于市场价格时，则企业可以买进该种资源；而当某种资源的时，则企业可以买进该种资源；而当某种资源的67影子价格低于市场价格时（特别是当影子价格为零影子价格低于市场价格时（特别是当影子价格为零时），则企业可以卖出该种资源，以获得较大的利时），则企业可以卖出该种资源，以获得较大的利润。润。682.5 线性规划的灵敏度分析线性规

32、划的灵敏度分析 在前面讨论线性规划问题时，总是假定在前面讨论线性规划问题时，总是假定aij,bi,cj都都是常数，但在实际问题中，这些数据往往是估计值是常数，但在实际问题中，这些数据往往是估计值或预测值，因此会有一定的误差。而且随着情况的或预测值，因此会有一定的误差。而且随着情况的变化，这些数据也会经常发生改变。例如，市场行变化，这些数据也会经常发生改变。例如，市场行情的变化会引起价值系数情的变化会引起价值系数cj的变化；工艺条件的改的变化；工艺条件的改变会引起消耗系数变会引起消耗系数aij的变化；资源数量的变化；资源数量bi也会视经也会视经济效益而进行调整；增加新产品会引起决策变量的济效益而

33、进行调整；增加新产品会引起决策变量的增加；增加新的资源限制会引起约束条件的增加等增加；增加新的资源限制会引起约束条件的增加等等。因此很自然会提出这样的问题，当这些参数中等。因此很自然会提出这样的问题，当这些参数中的一个或几个发生变化时，问题的最优解会有什的一个或几个发生变化时，问题的最优解会有什69么么变化，或者这些参数在一个多大范围内变化时，变化，或者这些参数在一个多大范围内变化时，问题的最优基不变。这就是灵敏度分析所需研究解问题的最优基不变。这就是灵敏度分析所需研究解决的问题。决的问题。灵敏度分析就是分析、研究线性规划模型参数灵敏度分析就是分析、研究线性规划模型参数aij,bi,cj 的取

34、值变化时，最优解或最优基的影响，它的取值变化时，最优解或最优基的影响，它在应用线性规划解决实际问题的过程中是非常有用在应用线性规划解决实际问题的过程中是非常有用的。的。当然，当线性规划问题中的一个或几个参数变化当然，当线性规划问题中的一个或几个参数变化时，可以用单纯形法重新计算，确定最优解有无变时，可以用单纯形法重新计算，确定最优解有无变化，但这样做既麻烦又没有必要。由单纯形法的化，但这样做既麻烦又没有必要。由单纯形法的70迭代过程知，只需在最终单纯形表中，看这些数据迭代过程知，只需在最终单纯形表中，看这些数据变化后，是否仍满足可行性、最优性的条件，如果变化后，是否仍满足可行性、最优性的条件，

35、如果不满足的话，再从该表开始进行迭代计算，使之可不满足的话，再从该表开始进行迭代计算，使之可行并求得最优解。同样，讨论在保持现有最优基不行并求得最优解。同样，讨论在保持现有最优基不变，找出这些数据变化的范围，即所谓数据的稳定变，找出这些数据变化的范围，即所谓数据的稳定区间，也可通过最终单纯形表中对可行性条件区间，也可通过最终单纯形表中对可行性条件 和最优性条件和最优性条件 的讨论得到。的讨论得到。712.5.1 目标函数中价值系数目标函数中价值系数cj的变化分析的变化分析 目标函数中价值系数目标函数中价值系数cj的变化会引起的变化会引起 的的变化，变化，从而影响最优性条件能否成立，可以分别就从

36、而影响最优性条件能否成立，可以分别就cj是对是对应的非基变量和基变量两种情况来讨论。应的非基变量和基变量两种情况来讨论。72731.若 是非基变量 的系数，则 改变为 ，时，则变化后的检验数为：要保持原最优基不变，必须满足由此可以确定 的变化范围了。当超出这个范围时，原最优基将不再是最优解了。为了求新的最优解，可在原最优单纯形表的基础上，继续往下迭代，以求得新的最优解。2.若 是基变量 的系数，则 改变为 将影响到所有非基变量的检验数，这时其中 是矩阵 的第r行，于是变化后的检验数为：74要求原最优基不变，则必须满足于是得到：当 时，有 ；当 时，有 ，因此 允许变化范围是例例2-7 已知线性

37、规划的标准形式为已知线性规划的标准形式为 其最优单纯形表如下其最优单纯形表如下 75问：问：(1)当当C1由由1变为变为4时，求新问题的最优解时，求新问题的最优解 (2)讨论讨论C2在什么范围内变化时，原有的最优解在什么范围内变化时，原有的最优解仍是最优解仍是最优解 7677解：由表可知，解：由表可知，C1是非基变量的价值系数，因此是非基变量的价值系数，因此C1的改变只影响的改变只影响1：见最优性准则已不满足，继续迭代见最优性准则已不满足，继续迭代7879要使原最优解仍为最优解，只要在新的条件下满足0成立，因为x2是基变量，所以所有的检验数值都将发生变化即 ，则 c2+c21 c2-1所以当

38、的系数c2-1时，原最优解仍能保持为最优解。的系数c2-1时，原最优解仍能保持为最优解。2.5.2 约束条件中资源数量约束条件中资源数量bi的变化分析的变化分析80由于 ，所以资源数量 变化为 ，并假设原问题的其它系数不变，则使最终单纯形表中原问题的解相应地变化为：其中这时rmrmririrrrmrrirrrmibabbabbabbabababbb111181其中 为 中的第r列，若要求最优基B不变，则必须 ，即由此可导出：当 时，有 当 时，有因此 的允许变化范围是：当b改变为 以后，若解的可行性不变，则目标函数变为12(,)Trrmraaa1B0Bx0 1,2,iirribabm（）0ir

39、airirbba 0irairirbba rbmax|0min|0iiirriririrbbabaaabb1*1()BBzc Bbbzc Bb例例2-8 已知线性规划问题及其最优单纯形表已知线性规划问题及其最优单纯形表 821231231231231,2,3max429240zxxxxxxxxxxxxx 83若右端列向量解：解：因为因为1小于小于0，因此继续迭代，因此继续迭代 841110231/3 02/331()1112011251 0131/3 01/332BXBbb 根据对偶单纯形法，计算得到根据对偶单纯形法，计算得到85所以新问题的最优解为所以新问题的最优解为X*=(0,0,3/2,

40、0,7/2,3/2)，Z*=6。862.5.3 增加一个变量增加一个变量xj的分析的分析87增加一个变量在实际问题中反映为增加一种新的产品。若增加一个新的变量 ，它对应的价值系数为 ，在约束系数矩阵中的对应列向量 ，则把 看成非基变量，在原来的最优单纯形表中增加一列 及检验数就得到了新问题的单纯形表，若 ，则原问题最优解不变；若 ，则按单纯形法继续迭代计算找出最优。11,12,1,1(,)Tnnnn nPaaa1nx1111,12,1,1(,)Tnnnnn nPB Paaa111111nnnnnncc B PcyP10n10n例例2-9 已知线性规划问题及其最优单纯形表已知线性规划问题及其最优

41、单纯形表 88123123123123123max42924,0zxxxxxxxxxxxxx xx 现增加一个新变量现增加一个新变量x7，且，且c7=3，p7=(3,1,-3)T，求，求新问题的最优解新问题的最优解 8990解：由表知：所以所以继续迭代177331/302/3011121/301/330pB p 177733(1,0,4)2600BcC B p 所以，得到最优解所以，得到最优解 X*=(0,0,13/3,0,56/9,0,1/9)T，Z*=53/3。912.5.4 约束条件中技术系数约束条件中技术系数aij的变化的变化92根据变动的系数 处于矩阵A中的哪一列又可分为两种情况来考

42、虑。1非基变量 的系数列向量 的变化分析 对于最优基B而言，非基变量 的系数列向量 改变为 ，则变化后的检验数为：其中 为原问题的对偶可行解，要使原最优基B保持不变，则必须 ，即2基变量 的系数列向量 的变化分析。对于最优基B而言，当基变量 的系数列向量 发生变化时，将使相应的B、都发生变化，因此，它不仅影响现行最优解的可行性，也影响到它的最优性。jxjPjjjPPP11()jjBjjBjjjjcc B Pcc BPPy P1Byc B0jjjy Pjx1B例例2-10 已知线性规划问题及其最优单纯形表已知线性规划问题及其最优单纯形表 最优单纯形表如下：最优单纯形表如下：93123134235

43、1,2,3,4,5max2311121333147133330zxxxxxxxxxxxx94若p3由原来的 变为 ，最优解将如何变化？1/37/31/101/395解：计算所以继续迭代133411/101/15111/37/30pB p1/1512,31/607/30 所以得到最优解所以得到最优解X*=(3/7,0,60/7,0,0)T，Z*=66/7。962.5.5增加新的约束条件增加新的约束条件97增加一个约束工具在实际问题中相当增添一道工序，设在原线性规划问题中，增加一个新的约束条件。则首先把已求得的原问题的最优解代入新增加的约束条件，如果条件满足，则原问题的最优解仍为新问题的最优解，结

44、束，如果条件不满足，则将新增加的约束条件直接添加到最终单纯形表中重新求解。1,1 11,221,1mmmnnmaxaxaxb*12(,)Tmxx xx例例2-11 2-11 已知线性规划问题及其最优单纯形表已知线性规划问题及其最优单纯形表 98现增加新约束 ，求新问题的最优解。1233617xxx99解：将原问题的最优解代入新增约束不满足新增加的约束条件，因此引入松弛变量x7后，新增约束变为加进最优表得：12373617xxxx规格化，继续运用对偶单纯形法求解规格化，继续运用对偶单纯形法求解 100所以得到最优解为：所以得到最优解为：X*=(5/3,0,11/3,0,4,2,0)T，Z*=13

45、。101本章小结本章小结 对偶理论与灵敏度分析是研究线性规划中原问题对偶理论与灵敏度分析是研究线性规划中原问题与对偶问题之间关系的理论。在线性规划早期发展与对偶问题之间关系的理论。在线性规划早期发展中最重要的发现是对偶问题，即每一个线性规划问中最重要的发现是对偶问题，即每一个线性规划问题有一个与它对应的对偶线性规划问题（称为对偶题有一个与它对应的对偶线性规划问题（称为对偶问题）。对偶问题与原问题之间存在着多方面的对问题）。对偶问题与原问题之间存在着多方面的对应关系。对偶问题能提供原问题最优解的许多重要应关系。对偶问题能提供原问题最优解的许多重要信息，有助于对原问题的求解和分析。信息，有助于对原

46、问题的求解和分析。102思考题思考题v1.对偶问题和对偶变量的经济意义是什么？对偶问题和对偶变量的经济意义是什么？v2简述对偶单纯形法的计算步骤。它与单纯形简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？法的异同之处是什么？v3什么是资源的影子价格？它和相应的市场价什么是资源的影子价格？它和相应的市场价格之间有什么区别？格之间有什么区别？v4如何根据原问题和对偶问题之间的对应关系，如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？找出两个问题变量之间、解及检验数之间的关系？1035.写出下列线性规划的对偶问题写出下列线性规划的对偶问题104(1)ma

47、x z=2x1+2x24x3x1+3x2+3x3 304x1+2x2+4x380 x1、x2，x30(2)min z=2x1+8x24x3x1+3x23x3 30 x1+5x2+4x3=804x1+2x24x350 x10、x20，x3无限制6.用对偶单纯形法求解线性规划问题用对偶单纯形法求解线性规划问题1057.已知线性规划问题已知线性规划问题其对偶问题的最优解为其对偶问题的最优解为y1*=6/5，y2*=1/5。试用对。试用对偶定理求该线性规划问题的最优解。偶定理求该线性规划问题的最优解。1068.某厂利用原料、生产甲、乙、丙三种产品，某厂利用原料、生产甲、乙、丙三种产品，已知生产单位产品

48、所需原料数、单件利润及有关数已知生产单位产品所需原料数、单件利润及有关数据如表据如表2-23所示，分别回答下列问题：所示，分别回答下列问题：107(1)建立线性规划模型，求该厂获利最大的生产计划；建立线性规划模型，求该厂获利最大的生产计划；(2)若产品乙、丙的单件利润不变，产品甲的利润在若产品乙、丙的单件利润不变，产品甲的利润在什么范围变化，上述最优解不变？什么范围变化，上述最优解不变？(3)若有一种新产品丁，其原料消耗定额：为单若有一种新产品丁，其原料消耗定额：为单位，为单位，单件利润为位，为单位，单件利润为2.5单位，问该种产单位，问该种产品是否值得安排生产，并求新的最优计划；品是否值得安

49、排生产，并求新的最优计划；(4)若原材料市场紧缺，除拥有量外一时无法购进，若原材料市场紧缺，除拥有量外一时无法购进，而原材料如数量不足可去市场购买，单价为而原材料如数量不足可去市场购买，单价为0.5，问该厂应否购买，以够劲多少为宜？问该厂应否购买，以够劲多少为宜？(5)由于某种原因该厂决定暂停甲产品的生产，试重由于某种原因该厂决定暂停甲产品的生产，试重新确定该厂的最优生产计划新确定该厂的最优生产计划1089.某厂生产甲、乙、丙三种产品，分别经过、某厂生产甲、乙、丙三种产品，分别经过、三种设备加工。已知生产单位产品所需的设备台三种设备加工。已知生产单位产品所需的设备台时数、设备的现有加工能力及每

50、件产品的利润见表时数、设备的现有加工能力及每件产品的利润见表2-24。109110(1)建立线性规划模型，求该厂获利最大的生产计划；(2)产品丙每件的利润增加到多大时才值得安排生产？如产品丙每件的利润增加到50/6，求最优生产计划。(3)产品甲的利润在多大范围内变化时，原最优计划保持不变？(4)设备A的能力如为100+10，确定保持原最优基不变的的变化范围。(5)如有一种新产品丁，加工一件需设备A、B、C的台时各为1、4、3小时，预期每件的利润为8元，是否值得安排生产？(6)如合同规定该厂至少生产10件产品丙，试确定最优计划的变化。10.表表2-25是某一约束条件用是某一约束条件用“”连接的线