第二章 对偶理论与灵敏度分析---课件.ppt

《第二章 对偶理论与灵敏度分析---课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、Chapter2线性规划的对偶理论和灵敏度分析上海工程技术大学——管理学院本章重点1、掌握写出对偶问题的方法，原问题与其对偶问题的对应关系2、掌握对偶问题的基本理论和性质3、理解影子价格的定义和意义4、理解并掌握对偶单纯形方法的思想和步骤5、掌握线性规划灵敏度分析(1)资源数量bi发生变化的分析(2)目标函数中价值系数cj发生变化的分析难点难点XBXNXSbXBBNIbCCBCN00了解----单纯形的矩阵描述XS为松弛变量XBXNXSbXBIB－1NB－1B－1bN0CN－CBB－1N－CBB－1－CBB

2、－1b单纯性法计算时，总选取单位矩阵I为初始基，对应基变量为XS,设迭代若干步后，基变量变为XB,XB在初始单纯性表中的系数矩阵为B。则该步的单纯性表中由XB系数组成的矩阵为单位矩阵I，对应XS的系数矩阵在新表中应为B-1Y=CBB-1称为单纯性乘子（对偶变量）2.3对偶问题提出例2.2：某公司在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及AB两种原材料的消耗如表所示，该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排计划使该工厂获利最多？举例2Chapte

3、r2灵敏度分析先根据图表来列出模型MaxZ=2X1+3X2X1+2X2≤84X1≤164X2≤12X1,X2≥0举例设用y1,y2,y3分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额.现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。他在做定价决策时,作如下比较:若用

4、一个单位设备台时和4个单位原材料A可以生产一件产品I,可获利2元,那么生产每件产品I的设备台时和原材料出租和出让的所有收入应不低于生产一件产品I的利润,这就有y1+4y2≥2同理将生产每件产品II的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品II的利润,这就有2y1+4y3≥3把工厂所有设备台时和资源都出租和出让,其收入为f=8y1+16y2+12y3从工厂决策者的角度来看，f当然是越大越好,但从接受者眼光来说f是越少越好,所以工厂决策者只可以在满足≥所有产品的利润条件下,使其总收入尽可能的小.

5、因此我们称这个线性规划问题为线性规划问题（这称为原问题）的对偶问题。各模型中有关数据的“位置”示意图如下。矩阵A矩阵AT对偶问题提出例2.3某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。表2.3不难得出下面一对对偶问题。原问题对偶问题不少于甲产品的利润不少于乙产品的利润例2.4：资源利用问题考虑：资源拥有者为了实现一定的收入目标，将其所拥有的资源出售，给每一种资源如何定价？解：表示出售

6、单位数量的第i种资源的价格。资源拥有者在做出售资源的决策时，考虑出售资源的收入不应该低于生产所获得的收入，则有：如果资源拥有者将所有资源出售，则他得到的总收入f=资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而得到。对同一个资源利用问题，从不同的角度考虑，可以得到两个相互联系的线性规划模型，这就是线性规划的对偶问题。由上面的例子我们可以知道原问题与对偶问题的关系1．线性规划问题是对称形式Maxz=CXMinf=Ybs.t.Ax≤bs.t.YA≥cx≥0y≥0“Max--≤”“Min--≥”原问题与

7、对偶问题的关系互为转置列向量行向量n个变量n个约束例2.5写出下述问题的对偶问题解：上述问题的对偶问题为(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。如上面例题所示一对对称形式的对偶规划之间具有下面的对应关系(2)从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换

8、。(4)两个规划模型中的变量皆非负。补充例子原问题：对偶问题：Chapter2灵敏度分析2.线性规划问题是非对称形式对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，≤”或“min，≥”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个