
运筹课件灵敏度分析123讲解.ppt
64页第六节 线性规划应用举例 例1:某工厂生产A,B两种产品,均需经过两道工 序, 每种产品需各工序加工的时间及各工序可 提供的时间如下表生产产品B同时生产出副 产品C,每生产一吨产品B可同时得到2吨产品 C,无需费用 出售一顿A盈利400元,B盈利1000元,C盈利 300元,而生产要报废的C每吨损失200元,经 预测C最大销量为5吨,列模型决定A,B产量, 使工厂总盈利最大 A B C工时限量 一工序 二工序 2 3 3 4 12 24 盈利 损失 400 1000 300 -200 可控变量:设X1为A产量,X2为B产量, X3为C销售量,X4为C报废量 目标为总盈利,约束为资源限制等 • maxZ=4X1+10X2+3X3-2X4 2X1+3X2≤12 3X1+4X2≤24 X3+X4=2X2 X3≤5 X1,X2,X3,X4≥0 例2:某工厂生产的一种产品由四个零件一和 三个零件二组成,这两种零件好用两种原 材料,由于三个车间拥有的设备和工艺不 同,每个工班原材料耗用量和零件产量不 同,问三个车间应各开多少工班,才能使 该产品的配套数达到最大。
分析:可控变量是什么,目标和约束是什 么 每班用料数( 公斤) 每班产量(件数) A材料B材料零件一零件二 一车间 二车间 三车间 8 5 3 6 9 8 7 6 8 5 9 4 资源限量300500 可控变量:三个车间工班数, 目标:产品配套数,约束资源约束 目标为两目标取小,要转化为一个目标时 的方法 Z=min( (7x1+6x2+8x3)/4 ,(5x1+9x2+4x3)/3) 可令y= min( (7x1+6x2+8x3)/4 ,(5x1+9x2+4x3)/3) 则上目标转化为maxZ=y (7x1+6x2+8x3)/4≥y (5x1+9x2+4x3)/3≥y maxZ=y (7x1+6x2+8x3)/4≥y (5x1+9x2+4x3)/3≥y 8x1+5x2+3x3≤300 6x1+9x2+8x3≤500 x1,x2,x3,y≥0 解 先看有多少种裁料方案,再进行组合和选择方案 : 例3 合理利用线材问题 现要做一百套钢管, 每套要长为2.9m、2.1m和1.5m的 钢管各一根。
已知原料长7.4m,问应如何下料,使用的 原料最省 设用方案 Ⅰ,Ⅱ,…,Ⅷ 分别裁原料 钢管x1,x2, …,x8根, 则 : Min z= x1+ x2+ x3+x4+ x5+x6+x7+x8 2x1+ x2+x3 + x4 ≥ 100 2x2+x3+ 3x5 +2x6+ x7 ≥ 100 x1+ x3 +3x4 +2x6+3x7+4x8≥ 100 x1, x2, x3, x4, x5 ,x6, x7, x8 ≥0 例4 某工厂要用三种原材料C,P,H混合调配出 三种不同规格的产品A,B,D已知产品的规格要 求、单价和原料的供应量、单价如下表该厂应 如何安排生产,能使利润最大? 根据产品要求有: AC≥0.5A, AP≤0.25A BC≥0.25B, BP≤0.5B AC+AP+AH=A BC+BP+BH=B 根据原料供应量有: AC+BC+DC≤100 AP+BP+DP≤100 AH+BH+DH≤60 设AC,AP,,DH分别为x1,x2,,x9,有 Max z=50(x1+x2+x3)+35(x4+x5+x6) +25(x7+x8+x9) - 65(x1+x4+x7) - 25(x2+x5+x8) - 35(x3 +x6 +x9) x1≥0.5(x1+ x2+ x3) x2 ≤0.25(x1+ x2+ x3) x4 ≥0.25(x4+ x5+ x6) x5 ≤0.5(x4+ x5+ x6) x1+ x4+ x7≤100 x2+ x5+ x8≤100 x3+ x6+ x9≤60 xj≥0, j=1,2,3,4,5,6,7,8,9 解:记产品A,B,D中C,P,H的含量分 别为AC,AP,AH,BC,BP,BH,DC,DP,DH。
例5 连续投资问题某单位有资金10万元,在今 后5年内可考虑下列投资项目,已知: 项目A:从第1到第4年每年初可投资,并于次 年末回收本利115%; 项目B:第3年初需要投资,到第5年末回收本 利125%,但最大投资额不超过4万元; 项目C:第2年初需要投资,到第5年末能回收 本利140%,但最大投资额不超过3万元; 项目D:5年内每年初可购买公債,当年末回 收本利106% 问它应该如何安排每年的投资,使到5年末拥 有的资金最多? 年份 项目 一 二 三 四 五 A X1AX2AX3AX4A B X3B CX2C D X1DX2DX3DX4DX5D x2A+x2C+x2D=1.06x1D 解:每年的投资额 应不超过手中的资 金由于项目D每 年都可投资,且当 年末就可收回所 以该单位每年必然 把资金全部投出去 ,即投资额等于手 中的资金数 设第i年投资各项目的资金 为xiA,xib,xiC,xiD 数学模型为: x1A+x1D=10 x3A+x3B+x3D=1.15x1A+1.06x2D x4A+x4D=1.15x2A+1.06x3D x5D=1.15x3A+1.06x4D xiA,xib,xiC,xiD≥0 Max z=1.15x4A+1.4x2C+1.25x3B+1.06x5D 第二章 线性规划的对偶理论 与灵敏度分析 改进单纯型法 对偶问题 对偶理论 目标函数值之间的关系 最优解之间的互补松弛关系 对偶单纯形法 对偶的经济解释 灵敏度分析 DUAL 第一节 改进单纯型法 需要求的几个重要指标 ,不需要完全的矩阵 变换就可求得。
需要求的:基可行解,θ,非基变量σ, XBB-1b B-1B-1Pk 初始表为单位 阵(初始基) 确定 主元 素 -Y=-CBB-1 σk 求σ,确定换入变 量xk ,计算B-1Pk ,计 算θ,确定主元素, 对简化单纯型表作 旋转变换 简化单纯形表 Cj C CB XB B-1b X b A B-1b B-1A σC-CB B-1A Cj CB CS CN1 CB XB B-1b XB XS XN1 CS XS b B E N1 CB XB B-1b E B-1 B-1N1 σ 0 CS-CB B-1 CN1-CB B-1N1 初始表 以B为基的 单纯形表 当XS为松弛变量时CS=0,松弛变量检验数为--C CB B B B -1-1 ,, C CB B B B -1-1称为 称为单纯形乘子单纯形乘子 Cj CB CN CB XB B-1b XB XN b B N B-1b E B-1N σ 0 CN-CB B-1N 第二节 对偶问题 产品 资源 I II 总 量 原料 工时 2 3 4 6 100 120 利润 6 4 原问题:确定获利最大的生产方案 对偶问题:确定资源最低可接受 出让价格 建立两问题的模型,对比其最优解,最优目标函数 值的关系。
两规划最优目标函数值相等 为 Z=ω=CB B-1b 此时 最优解XB= B-1b, Y= CB B-1(为原规划松弛变量在最 终表 中的检验数,即单纯形乘子) 原始问题 max z=C X s.t.AX≤b X ≥0 对偶问题 min ω=Yb s.t. YA≥C Y ≥0 ≤ max bA C CTAT bT ≥ min m n m n 第三节 对偶理论 一、对偶问题的性质 1、对偶的对偶就是原始问题 对偶的定义 max z=CXmax z=CX s.t. AX≤bs.t. AX≤b X ≥0 X ≥0 minω=Yb s.t. YA≥C Y ≥0 对偶的定义 max ω=-Yb s.t. -YA≤-C Y ≥0 min z’=-Cmin z’=-C X X s.t. -AX≥-bs.t. -AX≥-b X ≥0 X ≥0 2、其他形式问题的对偶 原始问题约束条件的性质,影响对偶问题变量的性质 原始问题变量的性质,影响对偶问题约束条件的性质 max z=Cmax z=C X X s.t. AXs.t. AX≤ ≤b b X ≥0 X ≥0 min ω=Yb s.t. YA≥C Y ≥0 maxz=Cmaxz=C X X s.t. AXs.t. AX= =b b X ≥0 X ≥0 min ω=Yb s.t. YA≥C Y :unr max z=Cmax z=C X X s.t. AXs.t. AX≥ ≥b b X ≥0 X ≥0 min ω=Yb s.t. YA≥C Y ≤ ≤ 0 原问题(或对偶问题)对偶问题(或原问题 ) 目标maxZ目标minω 变量 (n个) ≥0 ≤0 无约束 约束 (n个) ≥ ≤ = 约束 (m个) ≤ ≥ = 变量 (m个) ≥0 ≤0 无约束 min z= 2x1+4x2-x3 s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15 max ω=6y1+12y2+8y3+15y4 s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1- 3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0 ≤ ≥ = ≥unr≤≥ ≥ = ≤ ≥ x1≥0 x2≤0 x3: unr q原始问题变量的个数(3)等于对偶问题约束条件的个数(3); 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。
q原始问题变量的性质影响对偶问题约束条件的性质 原始问题约束条件的性质影响对偶问题变量的性质 二、原始对偶关系 1、可行解的目标函数值之间的关系 设XF、YF分别是原始问题和对偶问题的可行解 z=C XF ≤YF AXF ≤YF b=ω 2、最优解的目标函数值之间的关系 设Xo、Yo分别是原始问题和对偶问题的最优解 z=C Xo=Yo AXo=Yo b=Y max z=CX s.t.AX+XS=b X, XS ≥0 min ω=Yb s.t. YA-YS=C Y, YS ≥0 YSX=0 Y XS=0 AT Y -E Ys C T T mn =n X A E Xs b= nm m 3、基解与检验数之间的关系 单纯形表和对偶 max z=C X s.t. AX+XS=b X, XS≥0 min ω=Yb s.t. YA -YS=C Y, YS≥0 min ω=Yb s.t. YA ≥ C Y≥0 对偶问题 max z=C X s.t. AX ≤ b X ≥0 原始问题 引。
