运筹学对偶理论与灵敏度分析

nullnull第二章 对偶理论与灵敏度分析 要求： 了解LP对偶问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP的灵敏度分析 null2.1 对偶问题的提出 某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：null问题：如何安排生产 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 ，使得获利最多？ 解：设生产A产品x1 (kg）,B产品x2（kg）， 数学模型为： maxZ=70X1+120X2 9X1+4X2≤360 4X1+5X2≤200 3X1+10X2 ≤300 X1≥0 X2≥0null 现在A、B两产品销路不畅，可以将所有资源出租或外卖，现在要谈判，我们的价格底线是什么？ 设每个工时收费y1 元，设备台时费用y2元，原材料附加费y3元。 出租收入不低于生产收入： 9y1+4y2+3y3 ≥70 4y1+5y2+10y3 ≥120 目标：ω=360y1+200y2+300y3 出租收入越多越好？至少不低于某数，并且保证出租出去，目标 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 取最小化。 null原问题与对偶问题之比较 原问题： 对偶问题： maxZ=70X1+120X2 minω=360y1+200y2+300y3 y1 9X1+4X2≤360 9y1+4y2+3y3 ≥70 y2 4X1+5X2 ≤200 (3.1) 4y1+5y2+10y3 ≥120 （3.2) y3 3X1+10X2 ≤300 y1 ≥0, y2 ≥0, y3 ≥0 X1≥0 X2≥0null 2.2 对偶规则 原问题一般模型： 对偶问题一般模型： maxZ=CX min ω=Yb AX ≤b (1) YA ≥C (2) X ≥0 Y ≥0null例 线性规划问题 maxz=3x1+5x2 st x1+3x2  10 7x1+4x2  20 xj0;j=1,2. 对偶问题为： ming=10y1+20y2 st y1+7y2  3 3y1+4y2  5 yi 0;i=1,2。null 对偶规划的一般概念 例：给定 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 形的线性规划 maxz=CX 　（LP） ＡＸ=b （3） xj0, j=1,2,…,n 求其对偶规划。 解：约束方程组（3）等价于：AX b 且AXb。 因此（3）化（1）的形式为： nullmaxz=CX 　 ＡＸ≤ b （-Ａ）Ｘ≤- b X≥0 设对偶变量为Y1,Y2,对偶问题为： Minw= Y1b-Y2b Minw= （Y1-Y2）b (Y1,Y2) A ≥C 即： （Y1-Y2）A ≥C, -A Y1,Y2 ≥0 Y1,Y2 ≥0 令：Y= Y1-Y2 为无约束，对偶问题为： Minw= Yb YA ≥C Y为无约束原规划与对偶规划的线性关系原规划与对偶规划的线性关系null对偶规则：原问题有m个约束条件，对偶问题有m个变量 原问题有n个变量，对偶问题有n个约束条件 原问题的价值系数对应对偶问题的右端项 原问题的右端项对应对偶问题的价值系数 原问题的技术系数矩阵转置后为对偶问题系数矩阵 原问题的约束条件与对偶问题方向相反 原问题与对偶问题优化方向相反null对偶规则由max min对偶约束与原问题变量一致，变量与约束相反； 由min max对偶约束与原问题变量相反，变量与约束一致； 原问题一般模型： 对偶问题一般模型： maxZ=CX min ω=Yb AX ≤b (1) YA ≥C (2) X ≥0 Y ≥0null 例2 max ω=7y1+4y2-2y3 minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 ≤3 2x1+x2-4x3+x4+3x5 ≥7 y1 +3y3 ≤2 x1+ 2x3 -x4 ≤ 4 -4y1+ 2y2 ≤-6 -x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 ≥ 0 x1，x2，x3 ≥0; 3y1 +y3=1 x4 ≤ 0;x5无限制 y1 ≥ 0，y2 ≤ 0，y3无约束 由max min对偶约束与原问题变量一致，变量与约束相反； 由min max对偶约束与原问题变量相反，变量与约束一致；null例：写出线性规划的对偶问题null解：对应对偶问题为：null 对偶规则 原问题一般模型： 对偶问题一般模型： maxZ=CX min ω=Yb AX ≤b (1) YA ≥C (2) X ≥0 Y ≥0 约束“=” 变量为“无约束”null2.3对偶问题的基本性质对称性：对偶问题的对偶问题是原问题 证明：原问题为： maxZ=CX AX ≤b X ≥0 对偶问题为： min ω=Yb YA ≥C Y ≥0 ， 取负号，变为： max(- ω)=-Yb -YA ≤-C Y ≥0 , 则上述对偶问题为： min(- ω*)=-CX -AX ≥-b X ≥0 即： maxZ=CX AX ≤b X ≥0null2 弱对偶性：极大化原问题的任一可行解的目标函数值大于其对偶问题任意可行解的目标函数值。即： CX1 ≤ Y1b 证明：设原问题为maxZ=CX， AX ≤b ，X ≥0. X1为原问题的可行解，有AX1 ≤b， Y1为对偶问题的可行解，则 Y1AX1 ≤Y1b . 对偶问题为： min ω=Yb， YA ≥C ，Y ≥0 . Y1为对偶问题的可行解，所以， Y1A ≥C，有 Y1AX1 ≥CX1 .于是 CX1 ≤ Y1AX1 ≤Y1b . null3 无界性：原问题（对偶问题）为无界解，对偶问题（原问题）无可行解 证明：若对偶问题有可行解Y1，则CX1 ≤ Y1b ， 与原问题有无界解矛盾。逆不成立。 即：一个为无可行解，则另一个必为无界解或无可行解。 例如： 原问题（对偶问题） 原问题（对偶问题） minw=-X1-X2 maxz=y1+y2 X1-X2≥1 y1-y2≤-1 -X1+X2 ≥1 -y1+y2≤-1 X1≥0 X2≥0 y1≥0 y2≥0null4 可行解是最优解的性质 ：设X*是原问题的可行解， Y*是对偶问题的可行解，当CX*=Y*b时，X*,Y*是最优解。 证明：若CX*=Y*b，由性质2，对偶问题的所有可行解Y1，因CX*=Y*b，所以Y*b =CX* ≤ Y1b，故Y*是对偶问题的最优解；对原问题的可行解X1，有CX1 ≤Y*b= CX*,故X*是原问题的最优解。5 对偶定理：若一个问题有最优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1null证明： 设X*是原问题的最优解，则其对应的基为B，有C-CBB-1 A ≤ 0，设Y*= CBB-1 ，则Y*A ≥C.又对偶问题目标函数值w=Y*b= CBB-1 b；原问题目标函数值z=CX*= CBB-1 b=w.由性质4， Y*是对偶问题的最优解。6 对偶松弛性1：若X*， Y*是原问题和对偶问题的可行解，那么Y*Xs= YsX *=0,当且仅当X*， Y*是最优解。证明：原问题 对偶问题 maxZ=CX min ω=Yb AX + Xs =b YA- Ys =C X ， Xs ≥0 Y ，Ys ≥0 null则：z=(YA- Ys )X= YAX- Ys X w=Y(AX + Xs )= YAX + YXs 必要性：若Y*Xs= YsX *=0，则z= YAX= w，由性质4， X*， Y*是最优解。 充分性： 若X*， Y*分别是原问题和对偶问题的最优解，因 CX* ≤ Y*AX* ≤Y*b， CX*=Y*b， 故Y*Xs= YsX *=0。7 对偶松弛性2：若原问题有最优解，则最终表中松弛变量检验数的相反数为对偶问题的最优解；其它变量检验数的相反数为对偶松弛变量的值。 证明：因为Y*= CBB-1 ，σs = 0- CBB-1 Is =- Y*. -σs = Y*. σ= C-CBB-1 A=C-YA,YA+ σ=C,YA-(- σ)=C,故 - σ=Ys null例4：已知线性规划问题：试用对偶理论证明此线性规划问题无最优解。 解：对偶问题为： 因为（0，0，0）为线性规划问题的可行解。而对偶问题无可行解，则原问题为无界解或无可行解，故原问题无最优解。 null例5：线性规划问题最优解为 用对偶问题求原问题的最优解。解：标准型为：null对偶问题为：标准型为：null代入原问题标准型有：null2.4对偶最优解的经济解释—影子价格 影子价格表示最优目标值随相应资源数量变化的变化率。 若x*,y* 分别为（LP）和（DP）的最优解， 那么， cx* = y* b 。 根据 w = y*b=b1y1*+b2y2*++bmym* 可知 w/ bi = yi* yi* 表示 bi 变化1个单位对目标 w 产生的影响，称 yi* 为 bi的影子价格。 注意：若 B 是最优基， y* = CBB-1 为影子价格向量。null1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）剩余的资源（吨）消耗的资源（吨）单位产品消耗的资源（吨/件）null2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、...、wm称为m种资源的影子价格（Shadow Price）null3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0(因为Y*XS=0) 影子价格代表 对这种资源的一个估价。当某种资源的市场价低于影子价格时，应买进这种资源；否则，应卖出这种资源。null 2.6对偶单纯形法 单纯形法：始终保持原问题的可行性，b ≥0, σ =C-CBB- A(C-YA)由正变负，得到原问题和对偶问题的最优解。 对偶单纯形法：始终保持对偶问题的可行性，YA ≥C（C-YA=C- CBB-1 A ≤0）即 σ =C-CBB-1 A ≤0，原问题可以从非可行解开始，逐步迭代到基可行解。 无须加人工变量 nullLP: MAXZ=CX AX =b XB = B-1 b X ≥0 对偶单纯形法步骤: (1)找一个基，列出初始单纯形表，检验b列，若b ≥0， σ =C-CBB-1 A ≤0，则得到最优解，stop nor next. (2) 确定换出变量：按min{(B-1 b) i| (B-1 b) i ＜ 0}= B-1 b l .xl为换出变量。 (3)确定换入变量：检验（4）以xlk为主元素进行行的初等变换，重复（1）---（4）。null例：用对偶单纯形法求解变标准型为：null对偶单纯形法法如下： nullnull得原问题最优解为： 得对偶问题最优解为： null解：变标准型例：用对偶单纯形法求解nullnull无最优解。nullmaxZ=CX AX =b X ≥02.6灵敏度分析为什么进行灵敏度分析？ （1）研究A,C,b变化时，最优解的变化； （2）研究A,C,b在什么范围变化，最优解不变。 灵敏度分析的两把尺子： σj =Cj-CBB-1pj≤ 0；  xB= B-1b ≥0null一.资源变化的灵敏度分析 例1: 线性规划问题： max S = 2x1 + 3x2 s.t. x1+2x2 <= 8 4x1 <= 16 4x2 <= 12 x1,x2>=0 null初始单纯性表TAB(1)为：null最终单纯性表TAB(1)为：null 例1中,若该厂又从别处抽出4台时用于生产这两种产品产品,求这时的最优 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 . null 代入最终表得TAB(2)null 最优生产方案改为:x1=4,x2=3,z*=4×2+3 ×3=17(元).null二.目标函数中价值系数变化的灵敏度分析 例：基变量x2的系数c2变化为△c2 ，在最优解不变条件下确定△c2变化范围。null从上表中知:三.技术系数变化的灵敏度分析 例:null 分析在原计划中是否应该安排一种新产品Ⅲ,已知数据如上表,问该厂是否应该生产,生产多少? 解（1）设生产产品Ⅲ 台，其技术系数向 量 ， 的检验数为说明安排生产Ⅲ是有利的。null（2）计算产品Ⅲ在最终表中对应 的列向量将（1）、（2）结果加入P31页最终表中得：null（3） 换入， 换出，得下表： 例：原工艺发生变化时，例如：产品Ⅰ的工艺有了改进，其技术系数 ，每件利润 为4元，试分析对原最优计划有何影响。null将以上结果添入P32页最终表 的列向量位置。null变为正规表为：最优解为：null 若遇到原问题与对偶问题都为非可行解时，则需要引入人工变量重新求解。 例：上例中产品Ⅰ的技术系数向量变为 ， 而每件获利仍为4元，问该厂应如何安排最优生产方案。 解：将以上结果添入P32页最终表 的列向量位置。null变为正规表为：null原问题与对偶问题都为非可行解，引入人工变量 ，第三行用方程表示为：null 换入， 换出，得下表： =x1 换入， 换出，得下表： null例：某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见下表。 要求： （1）    确定获利最大的产品计划； （2）    写出其对偶问题的最优解; （3）产品A的利润在什么范围内变动时,上述最优计划不变. 产品 A B C 可用量（单位） 劳动力 6 3 5 45   材 料 3 4 5 30 产品利润 3 1 4 null解:其数学模型为 变标准型为:null 3 1 4 0 0 CB XB b 0 45 6 3 5 1 0 0 30 3 4 [5] 0 1 3 1 4 0 0 0 15 [3] -1 0 1 -1 4 6 3/5 4/5 1 0 1/5 3/5 -11/5 0 0 -4/5 3 5 1 -1/3 0 1/3 -1/3 4 3 0 0 1 -1/5 2/5 0 -2 0 -1/5 -3/5 最优解X*=(5,0,3,0,0)T, Z*=27 null(2)对偶问题最优解为Y*=(-1/5, 3/5) (3)产品A利润改变为 ,则