[理学]第一章_线性规划.ppt

三、对偶问题最优解的经济解释——影子价格 设DP其最优值为Z *(注：与LP最优值同），则根据 Z * = bT y* = b1y1* + b2y2* + ?? + bmym* ?Z / ?bi = yi* 简单推导： Y*=(y1* , y2* ,……， ym* ）为DP的最优解，则yi* 表示 LP某资源bi 变化1个单位对目标 产生的影响，称 yi* 为 bi的影子价格。 例、煤电油例的对偶问题的最优解为Y* =(0 1.36 0.52), 则煤电油三种资源的影子价格分别为0 、 1.36 、 0.52 Max Z=7 x1 +12x2 9 x1 +4x2≤360 （煤） 4x1 +5x2 ≤200 （电） 3 x1 +10x2 ≤300 （油） x1 , x2≥0 LP Min W=360y1+200y2+300y3 DP 9y1+4y2+3y3≥7 4y1+5y2+10y3≥12 y1, y2, y3 ≥0 影子价格在管理决策中的作用： （1）影子价格≠市场价格 若 影子价格＞市场价格，则应 影子价格＜市场价格，则应 买进该资源 卖出该资源 （2）影子价格反映了资源的稀缺性， 影子价格越高，则越稀缺 例如：煤的影子价格为0，则表明有剩余 §4 灵敏度分析 任务：当LP的系数A、b、c变化时，是否影响最优解或最优基？ 或：若不影响最优解或最优基， A、b、c的变化范围？ 对解的影响 可行性：B-1b≥0 最优性： 一、b变 （只影响解的可行性） 问题：br在何范围变化时，不影响最优基？ 设第 r 种资源br→br+△ （b→ ） 方法： （保证可行性） 即 ，解出△即可 例：煤电油例，讨论b2的变化 解得-50≤△≤27或150≤b2≤227 二、C 变 （只影响解的最优性） 问题： cj在何范围变化时，不影响最优基（解）？ 设第 j 种资源cj→cj+△ （c → ） 方法： （讨论检验数） （1） cj为非基价格系数 ，解出 （2） cj为基价格系数 此时需考虑所有非基变量的检验数： 解出 例：煤电油例，为使最优解不变，求c1的变化范围。 解：考虑所有非基检验数 同理， 令 基变量的检验数仍全为0，故无需考虑。 三、A 变 （1） 增加新变量xn+1 8 10 单价 4 8 油 3 6 电 12 3 煤 丁 丙 例如，煤电油例又增加产品丙或丁，相关数据如右表。 问题：增加后是否影响最优基（解），从而判断是否 有利？（使目标改善） 方法：是否有利取决于是否进基。 故只需计算 ，则有利 ，则不利 例: ∴丙不应投产。 同理可得 丁应投产。 （2） 某列Pj→ Pj′（只考虑非基向量情形） 问题：改变后是否影响最优基（解）、有利？ 方法： 只需计算 ，则有利 ，则不利 §4 整数规划 Integer Programming(简称IP) 一、　整数规划的一般模型 LP: max z=CX AX=b X≥0 IP: max z=CX AX=b X≥0 X为整数 整数规划的解法：分枝定界法或割平面法 基本思想是把一个整数规划问题化为一系列的线性规划问题来求解 整数规划的分类： 纯整数规划：所有变量都限制为整数 混合整数规划：仅部分变量限制为整数 0-1整数规划：变量的取值仅限于0或1 [例] 人力资源分配的问题 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员? 30 2：00 —— 6：00 6 20 22：00 —— 2：00 5 50 18：00 —— 22：00 4 60 14：00 —— 18：00 3 70 10：00 —— 14：00 2 60 6：00 —— 10：00 1 所需人数 时间 班次 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,于是LP模型为: x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0且为整数 min z=x1 + x2 + x3 + x4 + x5 + x6 最优解：X* =(60 ，10，50 ，0 ，