运筹学2 对偶问题

运筹学教程

运筹学Operations Research Chapter 2 对偶问题Dual Problem

1. 线性规划的对偶模型 Dual Model of LP 2.对偶性质 对偶性质 3.对偶单纯形法 对偶单纯形法 4.灵敏度分析 灵敏度分析 Dual property Dual Simplex Method Sensitivity Analysis

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 2 of 19

在线性规划问题中，存在一个有趣的问题，即每一个线性规 划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。

【例2.1】 某企业用四种资源生产三种产品，工艺系数、 例 资源限量及价值系数如下表：产品 资源 Ⅰ Ⅱ Ⅲ Ⅳ 每件产品利润 9 5 8 7 100 8 4 3 6 80 6 7 2 4 70 500 450 300 550 A B C 资源限量

建立总收益最大的数学模型。

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 3 of 19

【解】设x1,x2,x3分别为产品A,B,C的产量，则线性规划数学模 解 型为： m Z = 100x + 80x + 70x ax1 2 3

9x1 + 8x2 + 6x3 ≤ 500 5x + 4x + 7x ≤ 450 2 3 1 8x1 + 3x2 + 2x3 ≤ 300 7x + 6x + 4x ≤ 550 2 3 1 x1, x2, x3 ≥ 0 现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产 品，而将现有的资源转让或出租给其它企业，那么资源的转让价格 是多少才合理？价格太高对方不愿意接受，价格太低本单位收益又 太少。合理的价格应是对方用最少的资金购买本企业的全部资源， 而本企业所获得的利润不应低于自己用于生产时所获得的利润。这 一决策问题可用下列线性规划数学模型来表示。

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 4 of 19

设y1,y2,y3及y4分别表示四种资源的单位增殖价格(售价 =成本+增殖),总增殖最低可用 min w=500y1+450y2+300y3+550y4 表示。企业生产一件产品A用了四种资源的数量分别是9, 5,8和7个单位，利润是100,企业出售这些数量的资源所 得的利润不能少于100,即

9y1 + 5y2 + 8y3 + 7y4 ≥ 100同理，对产品B和C有

8y1 + 4y2 + 3y3 + 6y4 ≥ 80 6y1 + 7y2 + 2y3 + 4y4 ≥ 70

价格不可能小于零，即有yi≥0,i=1, …,4.从而企业的资源价 格模型为

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 5 of 19

m w = 500y1 + 450y2 + 300y3 + 550y4 in 9y1 + 5y2 +8y3 + 7y4 ≥100 8y + 4y + 3y + 6y ≥ 80 1 2 3 4 6y1 + 7y2 + 2y3 + 4y4 ≥ 70 yi ≥ 0, i =1, ,4 这是一个线性规划数学模型，称这一线性规划问题是前面 生产计划问题的对偶线性规划问题或对偶问题。生产计划 的线性规划问题称为原始线性规划问题或原问题。

运筹学教程

§2.1线

性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 6 of 19

【例2.2】某人根据医嘱，每天需补充A、B、C三种营养， 例 A不少于80单位，B不少于150 单位，C不少于180单位。此人准备每天从六种食物中摄 取这三种营养成分。已知六种食物每百克的营养成分含量 及食物价格如下表，试建立此人在满足健康需要的基础上 花费最少的数学模型。含量 营养成分 食物

A B C食物单价(元/100g)

一 13 24 18 0.5

二 25 9 7 0.4

三 14 30 21 0.8

四 40 25 34 0.9

五 8 12 10 0.3

六 11 15 0 0.2

需要量 ≥80 ≥150 ≥180

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 7 of 19

【解】设xj为每天第j种食物的用量，数学模型为 解13 x1 + 25x2 +14x3 + 40x4 + 8x5 +11x6 ≥ 80 24x + 9x + 30x + 25x +12x +15x ≥ 150 1 2 3 4 5 6 18 x1 + 7x2 + 21x3 + 34x4 +10x5 ≥ 180 x1、 2、x3、x4、 5、x6 ≥ 0 x x

m Z = 0.5x1 + 0.4x2 + 0.8x3 + 0.9x4 + 0.3x5 + 0.2x6 in

现有一制药厂要生产一种包含A、B、C三种营养成分的合 成药，如何制定价格，使得此药既要畅销又要产值最大。 设yi(i=1,2,3)为第i种营养成分的单价，则

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 8 of 19

m w = 80y1 +150y2 +180y3 ax 13 y1 + 24y2 +18y3 ≤ 0.5 25y + 9y + 7y ≤ 0.4 2 3 1 y1 + 30y2 + 21y3 ≤ 0.8 14 40y1 + 25y2 + 34y3 ≤ 0.9 8y +12y +10y ≤ 0.3 2 3 1 y1 +15y2 ≤ 0.2 11 y1、y2、y3 ≥ 0

影子价格( 影子价格 Shadow price): 上面两个线性规划有着重要的经 济含义。原始线性规划问题考虑的是充分利用现有资源，以产品的 数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价 格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同， 它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格 影子价格， 影子价格 即对偶问题中的决策变量yi的值。

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 9 of 19

由后面的对偶性质可知：原问题和对偶问题的最 优值相等，故有

Z = CB X B = CB B 1b = Yb = ∑bi yii=1 m

Z = yi i = 1, , m bi 即yi是第i种资源的变化率，说明当其它资源供应量bk(k≠i) 不变时，bi增加一个单位时目标值Z增加yi个单位。

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 10 of 19

例如，第一种资源的影子价格为y1=2,第二种资源的影子 价格为y2=2,即当第一种资源增加一个单位时，Z增加2个 单位

,当第二种资源增加一个单位时，Z增加2个单位。 企业可利用影子价格调节生产规模。例如，目标函数 Z表示利润(或产值 ),当第i种资源的影子价格大于零 (或高于市场价格)时，表示有利可图，企业应购进该资 源扩大生产规模，当影子价格等于零(或低于市场价格), 企业不能增加收益，这时应将资源卖掉或出让，缩小生产 规模。应当注意， Z 是在最优基B不变的条件下有上述 yi= bi 经济含义，当某种资源增加或减少后，最优基B可能发生

了变化，这时yi的值也随之变化。

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 11 of 19

在例2.1中，原问题的最优解X=(24.24,0,46.96) 对偶问题的最优解Y=(10.6,0.91,0,0) 最优值z=w=5712.12 分析： 分析 1. y1=10.6说明在现有的资源限量的条件下，增加 一个单位第一种资源可以给企业带来10.6元的利润； 如果要出售该资源，其价格至少在成本价上加10.6元。 2. y3=0说明增加第三种资源不会增加利润，因为第 三种资源还有 没有用完。 问题：1.第三、四种资源的售价是多少，是否不值钱？ 问题 2. 如果要增加利润，企业应增加哪几种资源，各 增加多少后再进行调整？

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 12 of 19

以上是依据经济问题推导出对偶问题，还可以用 代数方法推导出对偶问题。 原问题和对偶问题是互为对偶的两个线性规划问题，已知 一个问题就可写出另一个问题。 上面两种形式的线性规划称为对称形式。 对称形式的定义是：目标函数求极大值时，所有约束条件 对称形式 为≤号，变量非负； 目标函数求极小值时，所有约束条件为≥号，变量非 负。 对称形式的线性规划的对偶问题亦是对称形式。

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 13 of 19

【例2.3】写出下列线性规划的对偶问题 例m Z = 5x1 2x2 + 3x3 in 4x1 + x2 x3 ≥ 4 x1 7x2 + 5x3 ≥ 1 x , x , x ≥ 0 1 2 3

【解】这是一个对称形式的线性规划，设Y=(y1,y2), 解 则有 4 m w = Yb = ( y1, y2 ) = 4y1 + y2 ax 1 1 4 1 - YA = ( y1, y2 ) 1 - 5 7 = (4y1 + y2 , y1 7y2, y1 + 5y2 ) ≤ (5, 2,3)

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 14 of 19

从而对偶问题为m Z = 4y1 + 3y2 ax 4y1 + y2 ≤ 5 y1 7y2 ≤ 2 y1 + 5y2 ≤ 3 y1 ≥ 0, y2 ≥ 0

对偶变量yi也可写成xi的形式。

运筹学教程

§2.1线性规划的

对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 15 of 19

【例2.4】 写出下列线性规划的对偶问题 例m Z = 4x1 + 3x2 ax 5x1 x2 ≤ 6 7x1 + 5x2 ≤ 8 x1 + 3x2 ≤ 10 x1 ≥ 0, x2 ≥ 0

【解】这是一个对称形式的线性规划，它的对偶问题求最 解 小值，有三个变量且非负，有两个“ ≥”约束，即m w = 6y1 + 8y2 +10y3 in 5y1 + 7y2 + y3 ≥ 4 y1 + 2y2 + 3y3 ≥ 3 y ≥ 0, i = 1,2,3 i

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 16 of 19

若给出的线性规划不是对称形式，可以先化成对称形式再 写对偶问题。也可直接按表2-1中的对应关系写出非对称 形式的对偶问题。 例如，原问题是求最小值，按表2-1有下列关系： 1. 第i个约束是“ ≤”约束时，第i个对偶变量yj≤0 i ≤ i y 2.第i个约束是“ = ”约束时，第i个对偶变量yi无约束； 3.当xj≤0时，第j个对偶约束为“ ≥”约束，当xj无约束 时 ，第j个对偶约束为“ = ”约束。 将上述原问题与对偶问题的对应关系列于表2-1

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 17 of 19

表2-1 原问题(或对偶问题) 目标函数(max) 目标函数系数(资源限量) 约束条件系数矩阵A(AT) 变 n个变量 第j个变量≥0 第j 个变量≤0 第j个变量无约束 m个约束 第i个约束≤ 第i个约束≥ 第i个约束为= 约

对偶问题(或原问题) 目标函数(min) 资源限量(目标函数系数) 约束条件系数矩阵ATA) n个约束 第j个约束为≥ 第j 个约束为≤ 第j个约束为= m个变量 第i个变量≥0 第i个变量≤0 第i个变量无约束

量 约

束 变

束

量

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 18 of 19

【例2.5】写出下列线性规划的对偶问题 例

m Z = x1 + 5x2 4x3 + 9x4 in 7x1 2x2 + 8x3 x4 ≤18 6x2 5x4 ≥10 2x1 + 8x2 x3 = 14 x1无 约束 x2 ≤ 0, x3, x4 ≥ 0 , 【解】目标函数求最小值，应将表2-1 解 的右边看作原问题，左边是对偶问题， 原问题有3个约束4个变量，则对偶问题 有3 个变量4个约束，对照表2-1的对 应关系，对偶问题为：m w =18y1 +10y2 14y3 ax 7y1 + 2y3 =1 2y1 + 6y2 +8y3 ≥ 5 8y1 y3 ≤ 4 y 5y ≤ 9 2 1 约 y1 ≤ 0, y2 ≥ 0, y3无 束

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 19 of 19

本节以实例引出对偶问题; 介绍了如何写对称与非对称问题的对偶问题; 1.您应该会写任意线性规

划的对偶问题； 2.深刻领会影子价格的含义，学会用影子价格 作经济活动分析。 作业：教材P74 T2.3(1)(2)

The End of Section 2.1返回首页 对偶性质Exit

本文来源：https://www.bwwdw.com/article/vapi.html