《运筹学之线性规划的对偶问题与灵敏度分析.ppt》由会员分享，可在线阅读，更多相关《运筹学之线性规划的对偶问题与灵敏度分析.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1对偶问题与灵敏度分析w 要求：了解LP 对偶问题的实际背景 了解对偶问题的建立规则与基本性质 掌握对偶最优解的计算及其经济解释 掌握LP 的灵敏度分析 理解计算机输出的影子价格与灵敏度分 析的内容21 对偶问题w 1.1 对偶问题的提出 回顾例题1：某工厂安排生产A、B 两种产品（假设产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台式及原材料的消耗。问如何安排生产使工厂获利最大？产品A 产品B资源限制劳动力设备原材料 9 4 3 4 5 10 360 200 300单位利润 70 12031 对偶问题w 1.1 对偶问题的提出现在A、B 两产品销路不畅，可以将所有资源出租或外卖，现在
2、要谈判，我们的价格底线是什么？4对偶模型w 设每个工时收费Y1 元，设备台时费用Y2 元，原材料附加费Y3 元。出租收入不低于生产收入：9y1+4y2+3y3 70 4y1+5y2+10y3 120目标：min=360y1+200y2+300y3出租收入越多越好？定价太高会失去竞争能力，使竞争力最大。5原问题与对偶问题之比较原问题：对偶问题：maxZ=70X1+120X2 min=360y1+200y2+300y3 9X1+4X2360 9y1+4y2+3y3 70 4X1+5X2 200(3.1)4y1+5y2+10y3 120(3.2)3X1+10X2 300 y1 0,y2 0,y3 0
3、X10 X2061.2对偶规则原问题一般模型：对偶问题一般模型：maxZ=CX min=Yb AX b YA C X 0 Y 07对偶规则w 原问题有m 个约束条件，对偶问题有m 个变量w 原问题有n 个变量，对偶问题有n 个约束条件w 原问题的价值系数对应对偶问题的右端项w 原问题的右端项对应对偶问题的价值系数w 原问题的技术系数矩阵转置后为对偶问题系数矩阵w 原问题的约束条件与对偶问题方向相反w 原问题与对偶问题优化方向相反8对偶规则.原问题 对偶问题目标函数 max min 目标函数约束条件=变量无约束 变量符号 无约束 约束条件=9对偶规则简捷记法w 原问题标准则对偶问题标准w 原问题
4、不标准则对偶问题不标准w 例题2 max=7y1+4y2-2y3minZ=3x1+2x2-6x3+x5 2y1+y2-y3 32x1+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;x4 0;x5无限制 3y1+y3=1 y1 0，y2 0，y3 无约束101.3对偶问题的基本性质w 对称性：对偶问题的对偶问题是原问题w 弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值w 无界性：原问题无界，对偶问题无可行解w 对偶定理：若一个问题有最
5、优解，则另一问题也有最优解，且目标函数值相等。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1111.4对偶最优解的经济解释影子价格w 资源i 的影子价格等于Z 对bi 的变化率。w 即在Y 确定的前提下，每增加一个单位的i 种资源，对目标函数的贡献。w 影子价格：y1=0:第一种资源过剩 y2=13.6：设备台时最紧张，每增加一个台时，利润增加13.6元。y3=2w 影子价格所含有的信息：1、资源紧缺状况 2、确定资源转让基价 3、取得紧缺资源的代价122灵敏度分析w 为什么进行灵敏度分析？w 灵敏度分析的两把尺子：j=Cj-CBB-1pj 0；xB=B-1b 03.2.1 价值系数的
6、灵敏度分析 Cj 变化到什么程度可以保持最优基不变？用 87.5 C2 233.33；36 C1 9613灵敏度分析w 右端项的灵敏度分析：bi 变化到什么程度可以保持最优基不变？用尺度 xB=B-1b 0例题5：1-3.12 1.16 360 B-1b=0 0.4-0.2 200 0 0-0.12 0.16 b3 b3的变化范围：227.586 b3 40014其它形式的灵敏度分析w 新产品的分析：在资源结构没有变化的条件下，是否生产这种新产品，就看它的竞争力如何。例题6：新增一种C 产品，单位利润110 元，使用劳动力6工时，设备5台时，原材料7公斤，问要否调整产品结构？先算检验数j=Cj
7、-CBB-1pj 6=C6-YP6=110-（0，13.6，2）（6，5，7）T=110-104.4=6 大于零，有利可图，将P6左乘B-1，加入到末表之中，继续迭代，直到求得最优解。153用计算机进行灵敏度分析w 五种产品P1、P2、P 3、P 4、P5 利润550、600、350、400、200w 所花费的工时P1 P2 P3 P4 P5研磨12 20 25 15转孔10 8 16 装配20 20 20 20 20w 九台磨床，六台转床，每周工作六天，每天两班，每班八小时，24名工人装配16需求约束：w P2 的最低需求10个单位w P2 的最高需求100个单位w P4 的最低需求20个单
8、位w P4 的最高需求150个单位17灵敏度分析作业一（供巩固）w 一、某厂生产甲、乙、丙三种产品，各产品都需要经过A、B、C 三种设备加工。已知生产单位各种产品所需要的设备台时、设备的现有加工能力及每单位产品的利润如下表：18灵敏度分析作业一甲 乙 丙 设备能力（台时）A 8 2 10 300B 10 5 8 400C 2 13 10 420单位产品利润3000 2000 290019灵敏度分析作业一1.建模2.求获利最大的产品生产计划。3.产品丙的单位利润在那个范围变化，最优生产方案保持不变？4.产品乙的单位利润从2000元增加到2200元，最优生产计划有什么变化？总利润会有什么变化？如果
9、设备A 的加工能力增加到400台时，当前基是否仍保持最优？6.如果设备C 的加工能力减少到180台时，最优生产计划会发生什么变化？20灵敏度分析作业一7.若为了增加产量，可租借别的工厂的设备B，单位台时的租金是多少才是合算的？应租借多少台时？8.如果合同规定产品丙至少要生产10个单位，那么生产计划应如何修改？9.若另外有两种新产品丁、戊，其中每生产单位产品丁需要A12 台时，B5 台时，C10 台时，可获利21百元，产品戊需要设备 A4 台时，B4 台时，C12台时，可获利18.7百元，如果A、B、C 设备台时不增加，分别回答这两种新产品投产在经济上是否合算？10.对产品工艺重新设计，改进结构
10、。改进后生产每单位产品甲，需要设备 A9 台时，B12 台时，C4 台时，单位产品盈利45百元，问这对原计划有何影响？21灵敏度分析作业二w 二、下面是某生产计划问题的线性规划模型，其中目标函数Z 为不考虑固定费用的总利润（单位：元），变量Xj 是第j 种产品的产量，约束条件是各资源的限额以及产品产量的需求与限制。w Maxz=80 x1+95x2+90 x3+60 x4+100 x5w s.t.x1+x2+2x3+x4+2x51000（劳动力）w 5x1+3x2+4x3+2x4+3x52450（设备台时）w 2x1+4x2+3x3+5x51950（原材料A）w 6x2+5x3+4x4+7x5
11、2130（原材料B）22灵敏度分析作业二w 写出最优生产计划和最大利润，并回答下列问题（请简单说明理由）w(a)按计划生产后哪种资源有剩余？w(b)产品5的单位利润在哪个范围变动，现行生产计划保持最优？总利润会改变吗？w(c)厂方想通过租借设备来提高利润，每台时的租金是多少才合算？应租借多少台时？w(d)能否通过买进原材料A 来提高总利润？w(e)若产品3的最低需求变为50，最优总利润又是多少？23灵敏度分析作业三w 三、一家工厂把从四个不同地点运来的铁矿石混合起来，产生一种合适的配料。这种配料对三种基本元素A、B、C 要有一个最低需求量，下表给出从各个地点运来的每吨矿石所含个基本元素的千克数
12、，每吨最终配料中个基本元素的最低需要量和各个地点来的矿石每吨的成本。24 地点基本元素1 2 3 4每吨配料最低需要量（千克）A 10 3 8 2 5B 90 150 75 175 100C 45 25 20 37 30每吨矿石成本（元）800 400 600 50025w 1.求成本最低的混料配比。w 2.每吨最优混合料中各种基本元素的含量是多少？w 3.若把每吨配料中基本元素A 的最低需要量降低到4.75千克或者提高到8千克，最优混料中的成本各有什么变化？w 4.降低配料基本元素B 的最低需要量能否降低成本？26结论w 在灵敏度范围内：w C 变化，不改变最优解，不改变最优基，只改变最优值，Z=CiXiw b变化，Z=bi*yi(相应的对偶价格)，最优解会变化，最优基不变