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

Chapter3 对偶理论 Dual Theory Chapter 3 对偶理论 Dual Theory 3.1 线性规划的对偶模型 Dual Model of LP 3.2 对偶性质 Dual property 3.3 对偶单纯形法 Dual Simplex Method 3.4 灵敏度与参数分析 Sensitivity and Parametric Analysis 运筹学 Operations Research 3.1 线性规划的对偶模型 Dual Model of LP 【例3.1】 某企业用四种资源生产三种产品，工艺系数、资源 限量及价值系数如下表： 建立总收益最大的数学模型。 产品 资源 A B C 资源限量 Ⅰ 9 8 6 500 Ⅱ 5 4 7 450 Ⅲ 8 3 2 300 Ⅳ 7 6 4 550 单件产品利润 100 80 70 3.1 线性规划的对偶模型 Dual model of LP 【解】设x1，x2，x3分别为产品 A，B，C的产量，则线性规划数学模型为： 现在从另一个角度来考虑企业的决策问题。假如企业不考虑自己生产产品，而将现有的资源标价出售， 问题：决策者应怎样给定资源一个合理的价格？ 3.1 线性规划的对偶模型 Dual model of LP 产品 资源 A B C 资源 限量 Ⅰ 9 8 6 500 Ⅱ 5 4 7 450 Ⅲ 8 3 2 300 Ⅳ 7 6 4 550 单件产 品利润 100 80 70 设y1，y2，y3及y4分别表示四种资源的单位增值价格(售价＝成本 ＋增值)，总增值最低可用 min w=500y1+450y2+300y3+550y4 表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100, 企业出售这些数量的资源所得的利润不能少于100，即 同理，对产品 B 和 C 有 3.1 线性规划的对偶模型 Dual model of LP 这是一个线性规划数学模型，称这一线性规划模型是前面生产计划模型的对偶线性规划模型, 这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。 3.1 线性规划的对偶模型 Dual model of LP 价格不可能小于零，即有yi≥0(i=1, …,4), 从而企业的资源价格 模型为 注：以上两问题是同一组数据参数，只是位置有所不同，所描述的问题实际上是从两个不同的角度去描述。原始线性规划问题考虑的是充分利用现有资源，以产品数量和单位产品的利润来决定企业的总利润，没有考虑资源的价格，实际上在构成产品的利润中，不同的资源对利润的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格。 3.1 线性规划的对偶模型 Dual model of LP 线性规划问题(3.2)就是原线性规划问题(3.1)的对偶线性规划问题，反之，(3.2)的对偶问题就是(3.1)． 3.1 线性规划的对偶模型 Dual model of LP 原问题与对偶问题有如下关系(假设原问题 (3.1))： (1)原问题的约束个数(不含非负约束)等于对偶变量的个数 (2)原问题的目标函数系数对应于对偶问题的右端项 (3)原问题的右端项对应于对偶问题的目标函数系数 (4)原问题的约束矩阵转置就是对偶问题系数矩阵 (5)原问题求最大，对偶问题是求最小 (6)原问题不等式约束符号为“≤”,对偶问题不等式约束符号为“≥” 【例3.2】写出下列线性规划的对偶问题 【解】设Y=(y1，y2 )， 则有 3.1 线性规划的对偶模型 Dual model of LP 从而对偶问题为 【例3.3】 写出下列线性规划的对偶问题 【解】该线性规划的对偶问题是求最小值，有三个变量 且非负, 有两个“ ≥” 约束, 即 3.1 线性规划的对偶模型 Dual model of LP 线性规划问题的规范形式(Canonical Form 或叫对称形式) ： 定义： 目标函数求