运筹学对偶理论线性规划的对偶模型对偶性质PPT学习教案

1、会计学1 运筹学对偶理论线性规划的对偶模型对运筹学对偶理论线性规划的对偶模型对 偶性质偶性质 例例3.1 (原例原例1.1)某工厂生产甲、乙两种产品。这些产某工厂生产甲、乙两种产品。这些产 品分别要在品分别要在A、B、C三种不同的设备上加工。企业决三种不同的设备上加工。企业决 策者应如何安排生产计划，使企业总的利润最大？策者应如何安排生产计划，使企业总的利润最大？ 3.1 线性规划的对偶模型 Dual model of LP 第1页/共31页 3.1 线性规划的对偶模型 Dual model of LP 12 12 12 12 12,3 max3230 3436 5440 9876 ,0 Zx

2、x xx xx xx x x x 现在从另一个角度来考虑企业的决策问题。假如企业不考虑自己生产产品，而将现有的资源标价出售， 问题：决策者应怎样给定资源一个合理的价格？ 第2页/共31页 设y1，y2，y3分别表示三种资源的单位增值价格(售价成本 增值)，总增值最低可用 min w=36y1+40y2+76y3 表示。企业生产一件产品甲用了四种资源的数量分别是3，5和9个单位，利润是32, 企业出售这些数量的资源所得的利润不能少于32，即 123 35932yyy 同理，对产品 乙有 123 44830yyy 3.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP 第3

3、页/共31页 123 123 123 min364076 35932 44830 0,1,3 i wyyy yyy yyy yi 这是一个线性规划数学模型，称这一线性规划模型是前面生产计划模型的对偶线性规划模型, 这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。 3.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP 价格不可能小于零，即有yi0(i=1, ,4), 从而企业的资源价格 模型为 第4页/共31页 注：注：以上两问题是同一组数据参以上两问题是同一组数据参 数，只是位置有所不同，所描述数，只是位置有所不同，所描述 的问题实际上是从两

4、个不同的角的问题实际上是从两个不同的角 度去描述。原始线性规划问题考度去描述。原始线性规划问题考 虑的是充分利用现有资源，以产虑的是充分利用现有资源，以产 品数量和单位产品的利润来决定品数量和单位产品的利润来决定 企业的总利润，没有考虑资源的企业的总利润，没有考虑资源的 价格，实际上在构成产品的利润价格，实际上在构成产品的利润 中，不同的资源对利润的贡献也中，不同的资源对利润的贡献也 不同，它是企业生产过程中一种不同，它是企业生产过程中一种 隐含的潜在价值，经济学中称为隐含的潜在价值，经济学中称为 影子价格影子价格。 12 12 12 12 12,3 max3230 3436 5440 987

5、6 ,0 Zxx xx xx xx x x x 123 123 123 min364076 35932 44830 0,1,3 i wyyy yyy yyy yi 3.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP 第5页/共31页 12 1 2 3 12 max(32,30)(,) 3436 5440 9876 (,)0 T T Zx x x x x x x 123 123 123 min( ,)(36,40,76) 359 ( ,)(32,30) 448 ( ,)0 T wy yy y yy y yy max 0 ZCX AXb X min 0 wYb YAC

6、Y 第6页/共31页 线性规划问题(3.2)就是原线性规划问题(3.1)的对偶线性规划问题，反之，(3.2)的对偶问题就是(3.1) 3.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP max (3.1) 0 ZCX AXb X min (3.2) 0 wYb YAC Y 原问题与对偶问题有如下原问题与对偶问题有如下关系关系(假设原问题假设原问题 (3.1)： (1)原问题的原问题的约束个数约束个数(不含非负约束不含非负约束)等于等于对偶变量的个数对偶变量的个数 (2)原问题的原问题的目标函数系数目标函数系数对应于对偶问题的对应于对偶问题的右端项右端项 (3)原问题

7、的原问题的右端项右端项对应于对偶问题的对应于对偶问题的目标函数系数目标函数系数 (4)原问题的原问题的约束矩阵转置约束矩阵转置就是对偶问题就是对偶问题系数矩阵系数矩阵 (5)原问题求原问题求最大最大，对偶问题是求，对偶问题是求最小最小 (6)原问题不等式约束符号为原问题不等式约束符号为“”,对偶问题不等式约束符号为对偶问题不等式约束符号为“” 第7页/共31页 【例3.2】写出下列线性规划的对偶问题 123 123 123 123 max523 44 751 ,0 Zxxx xxx xxx x x x 【解】设Y=(y1，y2 )， 则有 1212 12 121212 4 min(,)4 1

8、411 (,) 175 (4,75)(5,2,3) wYby yyy YAyy yyyyyy ， 3.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP 123 1 2 3 123 max(5, 2,3)( ,) 4114 1751 ( ,)0 T T Zx x x x x x x x x 从而对偶问题为 12 12 12 12 12 min4 45 72 53 0,0 Zyy yy yy yy yy 第8页/共31页 【例3.3】 写出下列线性规划的对偶问题 12 12 12 12 12 max43 56 758 310 0,0 Zxx xx xx xx xx 【解】

9、该线性规划的对偶问题是求最小值，有三个变量 且非负, 有两个“ ” 约束, 即 3 , 2 , 1, 0 335 475 1086min 321 321 321 iy yyy yyy yyyw i 3.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP 第9页/共31页 线性规划问题的规范形式(Canonical Form 或叫对称形式) ： 定义： 目标函数求极大值时，所有约束条件为号，变量非负； 目标函数求极小值时，所有约束条件为号，变量非负。 3.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP 0 ) 1 . 2( max X bAX

10、CXZ 0 )2 . 2( min X bAX CXZ 注：注： (1)(1)线性规划规范形式与标准型是两种不同形式，但可以线性规划规范形式与标准型是两种不同形式，但可以 相互转换。相互转换。 (2)规范形式的线性规划问题的对偶仍然是规范形式 第10页/共31页 原问题原问题(或对偶问题或对偶问题)对偶问题对偶问题(或原问题或原问题) 目标函数目标函数max 目标函数系数目标函数系数(资源限量资源限量) 约束条件系数矩阵约束条件系数矩阵A(AT) 目标函数目标函数min 资源限量资源限量(目标函数系数目标函数系数) 约束条件系数矩阵约束条件系数矩阵AT(A) 变变 量量 n个变量个变量 第第j

11、个变量个变量0 第第j 个变量个变量0 第第j个变量无约束个变量无约束 约约 束束 n个约束个约束 第第j个约束为个约束为 第第j个约束为个约束为 第第j个约束为个约束为= 约约 束束 m个约束个约束 第第i个约束个约束 第第i个约束个约束 第第i个约束为个约束为= 变变 量量 m个变量个变量 第第i个变量个变量0 第第i个变量个变量0 第第i个变量无约束个变量无约束 3.1 线性规划的对偶模型线性规划的对偶模型 Dual model of LP 问题问题：讨论一般形式的线性规划问题的对偶问题？：讨论一般形式的线性规划问题的对偶问题？ 方法：方法：先将其转化为规范形式的线性规划问题，然后写出其

12、对先将其转化为规范形式的线性规划问题，然后写出其对 偶问题，适当将其进行化简。偶问题，适当将其进行化简。 第11页/共31页 3.2 对偶性质(了解) Dual property 第12页/共31页 0 max X bAX CXZ 对偶问题是(记为DP)： 0 min Y CYA Ybw 这里A是mn矩阵, X是n1列向量, Y是1m行向量 。 【性质1】 对称性: 对偶问题的对偶是原问题。 设原问题是(记为LP)： 3.2 对偶性质 Dual property 3.2.1 对偶性质 【性质2】 弱对偶性: 设X*、Y*分别为LP(max)与 DP(min)的可行解，则 bYCX * 第13页

13、/共31页 3.2 对偶性质 Dual property 由这个性质可得到下面几个结论： (1)(LP) 的任一可行解的目标值是 (DP) 的最优值 下 界；(DP)的任一可行解的目标是(LP)的最优值的上界； (2) 在互为对偶的两个问题中，若一个问题可行且 具有无界解，则另一个问题无可行解； (3) 若原问题可行且另一个问题不可行，则原问题具 有无界解。 注意: 上述结论(2)及(3)的条件不能少。一个问题无可 行解时，另一个问题可能有可行解(此时具有无界解) 也可能无可行解。 * (max)(min)LPDPCXY b 第14页/共31页 例如：例如： 0, 2 2 2 1 2min 2

14、1 21 21 21 xx xx xx xxz 无可行解，而对偶问题 0, 2 2 1 1 22max 21 21 21 21 yy yy yy yyw 有可行解，由结论(3)知必有无界解。 3.2 对偶性质 Dual property 第15页/共31页 【性质3】最优准则定理: 设X*与Y*分别是(LP)与(DP) 的可行解，则X*、Y*是(LP)与(DP)的最优解当且仅当 C X*= Y*b . 3.2 对偶性质 Dual property 【性质4】对偶性：若互为对偶的两个问题其中一个 有最优解，则另一个也有最优解，且最优值相同。 另一结论：若(LP)与(DP)都有可行解，则两者都有最

15、优 解，若一个问题无最优解，则另一问题也无最优解。 【性质5】互补松弛定理: 设X*、Y*分别为 (LP) 与 (DP) 的可行解，XS和YS分别是它们的松弛变量的可行 解，则X*和Y*是最优解当且仅当 YSX*=0 和 Y*XS=0 第16页/共31页 性质5告诉我们已知一个问题的最优解时求另一个问题 的最优解的方法，即已知Y*求X*或已知X*求Y*。 Y * XS = 0 和 YS X * = 0 两式称为互补松弛条件。将互补松弛条件写成下式 * 1 * 1 0 0 i j m iS i n Sj j y x y x 由于变量都非负，要使求和式等于零，则必定每一分 量为零，因而有下列关系：

16、 3.2 对偶性质 Dual property 第17页/共31页 (1)当yi*0时， , 反之当 , 时yi*=0； 0 i S x0 i S x * (2)00,00 jj SjjS yxxy时反之当时 利用上述关系，建立对偶问题(或原问题)的约束线性 方程组，方程组的解即为最优解。 【例3.5】 已知线性规划 3 , 2 , 1, 0 1622 102 43max 321 321 321 jx xxx xxx xxxz j 的最优解是 , 求对偶问题的最优解 。 (6, 2, 0)TX 3.2 对偶性质 Dual property 第18页/共31页 【解】对偶问题是 0, 1 422

17、 32 1610min 21 21 21 21 21 yy yy yy yy yyw 因为x10，x20，所以对偶问题的第一、二个约束 的松弛变量等于零，即 422 32 21 21 yy yy 解此线性方程组得y1=1, y2=1, 从而对偶问题的最优 解为Y=(1，1)，最优值w =26。 3.2 对偶性质 Dual property 第19页/共31页 【例3.6】 已知线性规划 无约束 321 321 321 321 , 0, 0 6 4 22min xxx xxx xxx xxxz 的对偶问题的最优解为Y=(0，2)，求原问题的最优 解。 【解】对偶问题是 12 12 12 12 1

18、2 max46 2 1 2 0 wyy yy yy yy yy 无约束， 3.2 对偶性质 Dual property 第20页/共31页 解方程组得：x 1=5, x 3=1, 所以原问题的最优解 为 X=(5，0，1)T，最优值 Z= 12。 6 4 31 31 xx xx 因为y20，所以原问题第二个松弛变量 =0，由 y1=0、y2=-2知，松弛变量 故 x2=0，则原问题的约束条件为线性方程组： , 1, 0 21 SS yy 2 S x 3.2 对偶性质 Dual property 第21页/共31页 【例3.7】 证明该线性规划无最优解： 3 , 2 , 1, 0 32 4 mi

19、n 321 31 321 jx xxx xx xxxZ j 【证】容易看出X=(4，0，0) 是一可行解。对偶问题 0, 0 12 1 1 34max 21 21 2 21 21 yy yy y yy yyw 将三个约束的两端分别相加得 , 而第二个约束有 y21,矛盾，故对偶问题无可行解，因而原问题具有 无界解，即无最优解。 2 1 2 y 3.2 对偶性质 Dual property 第22页/共31页 【性质6】LP(max)的检验数的相反数对应于 DP(min)的一组基本解。 其中第j个决策变量xj的 检验数的相反数对应于(DP)中第j个松弛变量 的解，第i个松弛变量 的检验数的相反数

20、对应 于第i个对偶变量yi的解。反之，(DP)的检验数(注 意：不乘负号)对应于(LP)的一组基本解。 j S y i S x 3.2 对偶性质 Dual property 注：注：应用性质应用性质6 6 的前提是线性规划为规范形式，而的前提是线性规划为规范形式，而 性质性质1-51-5则对所有形式线性规划有效。则对所有形式线性规划有效。 第23页/共31页 【例3.8】 线性规划 123 123 13 123 max62 22 44 ,0 zxxx xxx xx x x x (1) 用单纯形法求最优解； (2) 写出每步迭代对应对偶问题的基本解； (3) 从最优表中写出对偶问题的最优解； (

21、4) 用公式Y=CBB-1求对偶问题的最优解。 【解】(1) 加入松弛变量x4、x5后，单纯形迭代 如表3-5所示。 3.2 对偶性质 Dual property 第24页/共31页 XBx1x2x3x4x5b 表表 （1） x4 x5 2 1 1 0 2 4 1 0 0 1 2 4 j62100 表表 （2） x1 x5 1 0 1/2 1/2 1 3 1/2 1/2 0 1 1 3 j01530 表表 （3） x1 x2 1 0 0 1 4 6 0 1 1 2 4 6 j001122 表3-5 3.2 对偶性质 Dual property 最优解X=(4，6，0)T，最优值Z=6426=1

22、2； 第25页/共31页 (2) 设对偶变量为y1、y2, 松弛变量为y3、y4、y5 , Y=(y1、y2、y3、y4、y5)，由性质6得到对偶问题的基本 解 (y1、y2、 y3、y4、y5) =(4,5,1,2,3)，即 表25(1)中=(6，2，1，0，0)， 则Y(1)=(0，0，-6，2，1) 表25(2)中=(0，1，5，3，0)， 则Y(2)=(3，0，0，1，5) 表35(3)中=(0，0，11，2，2)， 则Y（3）=(2，2，0，0，11) 3.2 对偶性质 Dual property 第26页/共31页 (3) 因为表32(3)为最优解，故Y（3）=(2，2，0，0 ，11)为对偶问题最优解； CB=(6，2)，因而 (4) 表32(3)中的最优基 B-1 为表32(3)中x4，x 5两列的系数，即 21 10 B 21 10 1 B )2 , 2( 21