第4章 对偶模型 4.1 对偶模型的提出 4.2 原模型与对偶模型的线性规划模型之 间的关系 4.3 对偶模型的基本性质

Presentation on theme: "第4章 对偶模型 4.1 对偶模型的提出 4.2 原模型与对偶模型的线性规划模型之 间的关系 4.3 对偶模型的基本性质"— Presentation transcript:

1 第4章 对偶模型 4.1 对偶模型的提出 4.2 原模型与对偶模型的线性规划模型之 间的关系 4.3 对偶模型的基本性质
第4章 对偶模型 4.1 对偶模型的提出 4.2 原模型与对偶模型的线性规划模型之 间的关系 4.3 对偶模型的基本性质 4.4 对偶模型的经济意义——影子价格 4.5 对偶模型最优解和影子价格 4.6 对偶单纯形法

2 4.1 对偶模型的提出 实际角度对偶模型的提出 【例4-1】某厂用甲、乙、丙三种原料生产A和B两种产品，每种产品耗用的各种原料、利润以及原料库存如表4-1所示，如何安排生产使得在现有条件下获得利润最多? 产品 资源 A B 资源限制 甲 1 90 乙 5 2 490 丙 6 240 利润/元 8

3 设生产A、B产品数分别为x1、x2，则数学模型为
现在从另一个角度讨论这一问题，假设该企业决策者决定不生产这两种产品，而将其资源出租，问题是对每种资源如何定价？ 出让代价应不低于 用同等数量的资源 自己生产的利润。

4 设用y1,y2,y3分别表示出让甲、乙、丙三种资源的附加额。做定价策略时，应比较：
产品 资源 A B 资源限制 甲 1 90 乙 5 2 490 丙 6 240 利润/元 8 y y y3 生产一单位A产品所用的甲、乙、丙资源出让所得的净收入（售价扣除资源的买入价）应不低于生产一单位A产品的利润，有

5 同理，生产一单位B产品所用的甲、乙、丙资源出让所得的净收入应不低于生产一单位B产品的利润，
A B 资源限制 甲 1 90 乙 5 2 490 丙 6 240 利润/元 8 y y y3 同理，生产一单位B产品所用的甲、乙、丙资源出让所得的净收入应不低于生产一单位B产品的利润，

6 只能在满足≥所有产品的利润的条件下, 其总收入尽可能少,才能成交. 企业能接受的条件： 把企业甲、乙、丙资源都出让，其收入为：
从支付者看,越少越好 支付方的意愿： 只能在满足≥所有产品的利润的条件下, 其总收入尽可能少,才能成交.

7 【例4-1】称为原问题。 称为【例4-1】的对偶问题。 原问题 对偶问题

8 理论角度对偶模型的提出 设原问题： 加入松弛变量： XB XN XS XB XN XS 当检验数 表示线性规划问题已得到最优解.

9 令 称它为单纯形乘子。 则由(4-4)有 由(4-2)和(4-3),有 故有

10 因为 而Y的上限无限大,所以只存在最小值。 由上讨论,可得另一个线性规划问题: 称为原线性规划问题 的对偶规划问题。

11 由式(4-1) 、(4-5)可看出，原线性规划模型和它的对偶模型的系数矩阵A、C、b就之间有紧密的联系。
一对对偶问题 对偶问题： 原问题：

12 4.2 原模型与对偶模型的线性规划模型 之间的关系
4.2 原模型与对偶模型的线性规划模型 之间的关系 对称形式线性规划模型的对偶模型 定义1 具有下列特点的线性规划模型称为对称形式的线性规划模型，变量均具有非负约束，其约束条件为当目标函数求最大时取“≤”、目标函数求最小时取“≥”。

13 对称形式的线性规划模型: 其对偶模型： 线性规划 对偶规划

14 标准型为：

15 n个变量 列向量 互为转置 n个约束 行向量

16 前例，原问题中各系数矩阵为 它的对偶问题是： 这里

17

18 4.2.2 一般形式的线性规划模型与对偶模型之间的关系
对于非对称形式的线性规划模型如何写出其对偶模型？ 其思路是首先将非对称形式转换为对称形式，然后再按照对应关系写出其对偶模型。 原问题求极小------ 原问题约束方程有“≥”------两边同乘（-1），“≤” 原问题约束方程有“=”------对偶问题？

19 【例4-3】写出下列线性回归模型的对偶模型 原问题约束方程有“=”，如何转化？

20

21 对称形式线性规划模型的对偶模型 对偶问题： 原问题：

22

23 将条件2两端同乘-1，并将条件3、4合并为等式，得

24 原问题 目标函数 约束条件右端项 目标函数中变量的系数 约束矩阵A 对偶问题 目标函数 目标函数中变量的系数 约束条件右端项 A的转置为约束矩阵

25 原模型与对偶模型之间的关系 原问题(或对偶问题) 对偶问题(或原问题) 目标函数maxZ n个变量 变量≥0 变量≤0 变量无限制
目标函数minW n个约束 约束≥ 约束≤ 约束= 约束m个 约束右端项 目标函数系数 m个变量 变量≤ 0

26 【例4-4】写出下列线性规划模型的对偶模型 设对偶变量为y1,y2,y3,对偶问题模型为： Max w=5y1+4y2+6y3
-5 1 ≥ ≤ = y1≥0, y2≤0, y3无约束

27 ≥ 2 ≤

28 对偶模型的基本性质 对称性 弱对偶性 最优解性 强对偶性（对偶定理） 互补松弛性

29

30 由弱对偶性可得出以下推论： （1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 （2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。

31 （3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。
例 已知线性规划问题 试用对偶理论证明上述问题无最优解。

32 原问题 对偶问题 y1≥0， y2≥0， 不满足该约束条件 X（0）=（0，0，0）T是原问题的一个可行解 对偶问题不可行 若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。

33 性质3  最优性 设 是原问题的可行解， 是对偶问题的可行 解，当 时， 是最优解。 对任何可行解，均有 ，故 是目标函数取值最小的可行解，因而是最优解。 利用弱对偶定理 同理可知, 也是最优解.

34 性质4 强对偶性（对偶定理） 若原问题有最优解，则对偶问题也有最优解，且目标函数最优值相等。 证：设 是原问题的最优解 ，它对应的基矩阵必存 在 ，即得到 若这时 是对偶问题的可行解，它使 因原问题的最优解 使目标函数取值 由此得到 可见 是对偶问题的最优解。

35 原问题与对偶问题的解和目标函数值之间的关系
最优解 无界解 无可行解 Z * =W *

36 Y*（b-AX*)=0 (Y*A-C)X*=0
充分必要条件 性质5 互补松弛性 设X*和Y*分别原问题和对偶问题的可行解，那么 Y*XS*=0和 YS*X*=0 ，当且仅当X*，Y*是最优解。 Y*（b-AX*)= (Y*A-C)X*=0 AX*≤ b AX*+XS*= b XS* =b-AX* Y*（b-AX*)=0 Y*XS*=0

37 已知线性规划问题 最优解点 对偶变量不为0，原问题相应约束式是等式 原问题约束为不等式，相应对偶变量为0

38 【例4-5】 已知线性规划模型 （1）写出该模型的对偶模型 （2）已知原模型的最优解为：X=（2，2，4，0）T 根据对偶理论，直接求对偶模型的最优解。

39 （1）对偶模型是： （2）已知原模型的最优解为：X=（2，2，4，0）T 根据对偶理论，直接求对偶模型的最优解。

40 （2）根据原模型的最优解为X=（2，2，4，0）T
将其代入原问题的约束条件，得原模型的松弛变量： x5=0，x6=0，x7=1，x8=0 约束条件 (3) 为严格不等式，由互补松弛定理知：y3*=0

41 设对偶模型的剩余变量为y5，y6，y7，y8， 由原模型的最优解为X=（2，2，4，0）T ，根据互补松弛定理知： y5=0，y6=0，y7=0， 求解上面的方程组得：y1*=4/5 ， y2*=3/5 ， y3*=0, y4* =1

42 目标函数Z=CBB-1b和检验数CN-CBB-1N中都有乘子Y=CBB-1,Y的经济意义？
4.4 对偶模型的经济意义——影子价格 目标函数Z=CBB-1b和检验数CN-CBB-1N中都有乘子Y=CBB-1,Y的经济意义？ 设B是 的最优解，则该 基所对应最优解的目标函数值 Z*=CBB-1b=Y*b 由此 当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优值增加的数量。

43 第i 种资源的影子价格是第i个约束条件的右端常数增加一个单位时，目标函数增加的数量
当某个右端常数bi bi+1时 第i 种资源的影子价格是第i个约束条件的右端常数增加一个单位时，目标函数增加的数量

44 优解时，这一对线性规划对应的目标函数值相等， 即有：
在【例4-1】中，当原问题和对偶问题都取得最 优解时，这一对线性规划对应的目标函数值相等， 即有： 其中X*=（75，15）T，是原问题的最优解， y* =（5，0，0.5）T是对偶问题最优解。 若甲原料供应量能增加一个单位，即右端常数向量b=(90，490，240)T中的b1从90个单位增加到91个单位，则目标函数值的变化量为：

45 y1* =5描述了在生产最优安排下，原料甲的变动给总利润带来的影响。
对偶变量 的意义——代表在资源最优利用条件下对单位第 种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（shadow price)。

46 影子价格的经济意义 1．资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。 2．影子价格是一种边际价格。 在式中， 。 说明 的值相当于在资源得到最优利用的生产条件下， 每增加一个单位时目标函数 的增量。

47 3．资源的影子价格实际上又是一种机会成本. 在纯市场经济条件下,当资源的市场价格低于影子价格时，可以买进这种资源用于扩大生产；相反当市场价格高于影子价格时，就会卖出这种资源获利。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态，因此影子价格具有市场调节的作用。

48 4．在对偶问题的互补松弛性质中有 这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。

49 —第j种产品的产值或者利润 5．从影子价格的含义上考察单纯形表的检验数 的经济意义。 —生产第j中产品所消耗各项资源的
影子价格的总和。（即隐含成本） 可见，产品产值或者利润>隐含成本 可生产该产品；否则，不安排生产。——检验数的经济意义

50 6．一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。
经济学研究如何管理自己的稀缺资源 如何从单纯形表中找到影子价格？ 原问题的最终单纯形表中松弛变量的检验数对应对偶问题的最优解。

51 4.5 对偶模型最优解和影子价格 4.5.1 对偶模型的最优解 对偶模型与原模型单纯形表之间的关系 其相应的对偶问题为
4.5 对偶模型最优解和影子价格 对偶模型的最优解 对偶模型与原模型单纯形表之间的关系 其相应的对偶问题为 设B是原问题的一个基， A=(B,N),原问题可改写为

52 取YS1为对偶问题的非基变量,即有YS1=0,故可得对偶问题的一个基解. Y=CBB-1 YS2=CBB-1N-CN YS1=0
原问题的单纯形表 XB XN XS 取YS1为对偶问题的非基变量,即有YS1=0,故可得对偶问题的一个基解 Y=CBB-1 YS2=CBB-1N-CN YS1=0 对偶问题 与原问题的检验数比较-----原问题的检验数对应对偶问题的基解(差一负号)

53 原 问 题 变量性质 基变量 非基变量 XB XN XS 检验数 CN-CBB-1N -CBB-1 对偶 问题 基解 -YS1 -YS2 -Y 在用单纯形法求解原问题的过程中，每迭代一次，得到原问题的一个基本可行解，其对应一组检验数，这组检验数又对应对偶问题的一个解（只是符号相反）。

54 用单纯形法进行迭代求解得到最优单纯形表，那么对偶问题的最优解就是松弛变量和剩余变量对应的检验数的相反数。
例如，【例4-1】线性规划模型的单纯形解法迭代过程 原问题 对偶问题

55 原模型的最优解：x1=75，x2=15。松弛变量对应的检验数为（-5，0，-0. 5）。由此得对偶模型的最优解为：y1. =5，y2
原模型的最优解：x1=75，x2=15。松弛变量对应的检验数为（-5，0，-0.5）。由此得对偶模型的最优解为：y1*=5，y2*=0，y3*=0.5。 进一步求解【例4-1】线性规划模型的对偶模型

56 原模型的最优解：5，0，0.5。对偶模型的最优解为剩余变量对应的相反数75，15。

57 影子价格 1．在一般线性规划模型中，并非所有的约束都是资源约束（如产量约束,这样的约束也有影子价格即销售量对利润的贡献），但每个约束条件对应的对偶解分量yi﹡都可以解释为目标最优值z﹡对右端项bi的变化率，即bi增加一个单位时z﹡的改变量。由于yi﹡的符号可为正，也可为负，故随着bi的增加，z﹡可能增加，也可能减少。 2．大多数的计算机软件(包括本书所用到的QM)沿用如下的输出惯例：打印输出的影子价格是当右端项增加时目标最优值的改进率而不是变化率。改进的意思在最大化模型中是增加，在最小化模型中则是减少；正的改进率使前者的目标最优值增加，使后者的目标最优值减少；而负的改进率将使目标最优值受到“损害”，故它的作用正好相反。

58 表4-3 影子价格 约束种类 影子价格 ≤ 对偶最优解（yi*的值） ≥ 对偶最优解的相反数（ yi*值的相反数） 【例4-6】求解例2-2中MD公司生产问题的线性规划模型

59

60 对偶模型的最优解为：4，0，1。 三个约束条件的影子价格为： -4，0，1。

61 4.6 对偶单纯形法 4.6.1 对偶单纯形法的原理 对偶单纯形法是根据对偶问题求解的特点和对称性设计出的一种解法。
对偶单纯形法 对偶单纯形法的原理 对偶单纯形法是根据对偶问题求解的特点和对称性设计出的一种解法。 在单纯形法迭代时，在b 列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解，通过逐步迭代，当在检验数行得到的对偶问题的解也是基可行解时，已得到最优解，即原问题与对偶问题都是最优解。 根据对偶问题的对称性：若保持对偶问题的解是基可行解，即cj-CBB-1aj≤0,而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。 原问题的某个基解：称该基解为正则解。

62 原 保持对偶可行性，逐步改进主可行性，求解原问题。
X（0）为基本可行解的条件？ X（0）为最优解的条件？ 基本解 B-1b≥0 原始可行性条件 原始最优性条件 设B为一个基 令Y=CBB-1，代入原始最优性条件，→YA≥C 保持对偶可行性，逐步改进主可行性，求解原问题。 对偶可行性条件 当b有负分量，A中有一明显初始对偶可行基(检验数均非正)，此时为正则解。因而易得一初始解时，可用对偶单纯形法求解。

63 对偶单纯形法步骤： 列出该正则解的单纯形表，检查b 列的数字若都为非负，则已得到最优解，停止计算，若b列的数字中至少有一个负分量，转第二步。 2. 确定出基变量 按 ,对应的基变量xr为出基变量。 确定入基变量 在单纯形表中检查xr所在行的各系数arj(j=1,2, …,n),若所有arj ≥0，则无可行解，停止计算，若存在arj ＜0，计算

64 按 规则所对应的列的非基变量xk为入基变量，保证得到的新基解所对应的对偶问题的解仍为可行解。
以 ark为主元素，进行旋转变换，得到新基解的单 纯形表，重复1—4的步骤，直至b 列中所有元素均为非负数为止。 【例4-7】用对偶单纯形法求解下面线性规划模型

65 将模型化为满秩标准型：

66 以x3,x4,x5为基变量可得该问题的一基解(正则解),其单纯形表如下：
cj -2 -1 CB XB x1 x2 x3 x4 x5 b -3 1 -4 -6 σj

67 原问题：该基解不是可行解。 cj -2 -1 CB XB x1 x2 x3 x4 x5 b -3 1 -4 -6 σj 对偶问题的解是可行解 出基变量确定： 可任选一个对应的基变量为出基变量。 取-3对应的变量x3为出基变量。 入基变量确定： 计算 故x1为入基变量。

68 cj -2 -1 CB XB x1 x2 x3 x4 x5 b 1 1/3 -1/3 -5/3 -4/3 σj -2/3 2 -2 x1 1 -3/5 1/5 3/5 -1 x2 4/5 6/5 x5 σj -2/5 -1/5 12/5 最优解是X*=（3/5，6/5，0，0，1）T， 目标函数最优值为Wmin=-Zmax=12/5

69 单纯形法 从一个初始基可行解出发 检验数可正可负 保持右端常数非负（可行性） 检验数均≤0，即为最优解 对偶单纯形法 从一个初始正则解出发 右端常数可正可负 保持检验数非正（正则性） 右端常数均≥0，即为最优解 对偶单纯形法的实质就是对原问题的对偶问题运用单纯形法求解.

70 单纯形法 例 用对偶单纯形法求解 大M 法 剩余变量、人工变量 用（-1）乘不等式两边，再引入松弛变量。

71 cj x5 x6 原问题，符合原始最优性条件，但不可行 cj -1 x1 x6
先选出基变量 后选进基变量 cj CB XB x1 x2 x3 x4 x5 x6 b x5 x6 -3 -2 原问题，符合原始最优性条件，但不可行 cj CB XB x1 x2 x3 x4 x5 x6 b -1 x1 x6 3 -8

72 cj -1 -4 0 -3 0 0 CB XB x1 x2 x3 x4 x5 x6 b -1 x1 x6 1 2 - 1 1 -1 0
CB XB x1 x2 x3 x4 x5 x6 b -1 x1 x6 3 -8 最优解 X*=（7，0，4，0）T Z*=-7 -1 x1 x3 1 7/ / /2 0 3/ / /2 7 4 0 -1/ / /2