线性规划综合案例.ppt

线性规划综合案例 总结 例1 某工厂用甲 乙两种原料生产A B C D四种产品 每种产品的利润 现有的原料数及每种产品消耗原料定量如表 问题1 怎样组织生产 才能使总利润最大 解 设生产A B C D产品各X1 X2 X3 X4万件 数学模型为 maxS 9x1 8x2 50 x3 19x43x1 2x2 10 x3 4x4 182x3 1 2 x4 3x1 x2 x3 x4 0 问题2 写出该线性规划的标准形式 化成标准型maxS 9x1 8x2 50 x3 19x43x1 2x2 10 x3 4x4 x5 182x3 1 2 x4 x6 3x1 x2 x3 x4 x5 x6 0 问题三 应用单纯形法解算该线性规划问题 列出初始单纯形表 初始基B1 P5 P6 第二行除以2 第一行加上第二行的 10 B3 P1 P3 第一行除以3 B3 P1 P3 B4 P2 P3 第一行乘以 3 2 第一行乘以 4 3 B5 P4 P3 第二行减去第一行1 4倍 最优基B5 P4 P3 最优解 0 0 1 2 S 88 问题4 对比初始单纯形表和最终单纯形表 找出基矩阵B 非基矩阵N B的逆矩阵B 1 初始基B1 P5 P6 最优解 X 0 0 1 2 最优值 S 88 最优基B5 P4 P3 对应原松驶变量的位置即为B 1 初始表 最优表 A I 32104100021 201 B 10421 232N 0010I 01 B 1 A I 24 3012 3 10 3 1 2 1 310 1 64 3B 1 N B I 24 3012 3 10 3 1 2 1 310 1 64 3 B 1N 24 3 1 2 1 310B 1B 012 3 10 3B 1I 1 64 3 B 1 问题5 写出该线性规划的对偶问题 解 原问题 MaxS 9x1 8x2 50 x3 19x43x1 2x2 10 x3 4x4 182x3 1 2 x4 3x1 x2 x3 x4 0对偶问题 MinW 18y1 3y23y1 92y2 810y1 2y2 504y1 0 5y2 19y1 y2 0 问题6 已知原问题的最优解为X 0 0 1 2 试应用松紧定理求对偶问题的最优解 要求写出计算步骤 并进行必要说明 解 1 因为原问题有最优解 因此其对偶问题也一定有最优解 2 因为X3 1 X4 2均不为0 因此根据松紧定理可知其对偶问题要达到最优解的充要条件是其第3 第4个约束条件中的松弛变量Y3 Y4均0 因此有 10y1 2y2 504y1 0 5y2 19解方程组得到 Y1 13 3 Y2 10 3对偶问题最优解为Y 13 3 10 3 问题7 若A C产品的利润产生波动 波动范围多大 最优基不变 1 目标函数中C1 9在多大范围内变化 原问题最优解不变 2 目标函数中C3 50在多大范围内变化 原问题最优解不变 B 410B 1 2 3 10 31 22 1 64 3 B 1A 24 3012 3 10 3 1 2 1 310 1 64 3 CB C4 C3 19 50 C 9 8 50 19 0 0 当目标函数的C1 9有波动 设波动为C1 9 a CB CB C 9 a 8 50 19 0 0 得到检验数的变化为 4 a 2 3 0 0 13 3 10 3 4 a 2 3 0 0 13 3 10 3 仅当 4 a4时 即每万件A产品的利润超过13万元时 B已经不是最优基 继续进行最优化 当a 4时 4 a 0 第一行除以2 第二行加上第一行 1 2 重新计算检验数 为了保证B为最优 必须满足6 2a 0 4 a 0 9 a 0 5a 30 0得到4 a 6 当4 a 6时 即每万件A产品的利润在13 15万元之间 得到新的最优基 P1 P3 最优决策方案 1 0 3 2 0 最优利润 84 a 最大利润在88 90之间 当目标函数的C3 50有波动 设波动为C3 50 a CB CB 原最优表如下 当目标函数的C3 50有波动 设波动为C3 50 a CB CB 重新计算检验数如下 为保证最优 满足a 8 0 a 2 0 a 26 0 10 4a 0 得到 5 2 a 2 即产品C的利润在47 5 52万元之间 原最优决策方案不变 最优利润在85 5 90万元之间 同理可以讨论 a2时 只要X2进基变量 问题8 若想增加甲种原料 增加多少时 原最优基不变 设b1发生变化 问b1在多大范围内变化 原问题最优解不变 解 设b1发生了变化a 故b1 18 a b 18 a 3 2 3 10 318 a2 2 3 aB 1b 1 64 33 1 1 6 a 解 2 2 3 a 0 1 1 6 a 0得到 3 a 6即15 b1 24原最优基不变 但最优解与目标函数最优值都是a的函数 X 0 0 1 a 6 2 2 3 a S 88 13 3 a 万元 当a 6 a6情形 原问题最优基 2 2 3 a用B 1b 1 1 6 a代替常数项因为a 6 则1 1 6 a 0 原始不可行 但是对偶可行 用对偶单纯形法求解 用对偶单纯形法求解 第二行乘以 3 用对偶单纯形法求解 第一行加上第二行 4 3 当 3 1 2 a 0 即a 6新的最优基 B P4 P2 最优解 0 3 1 2 a 0 6 最大利润 90 4a 万元 问题9 若考虑要生产产品E 且生产1万件E产品要消耗甲原料3公斤 消耗乙原料1公斤 那么 E产品的每万件利润是多少时有利于投产 解 增加变量 设生产E产品X7万件 每万件利润是C7万元 则模型为 maxS 9x1 8x2 50 x3 19x4 C7x73x1 2x2 10 x3 4x4 x5 3x7 182x3 1 2 x4 x6 x7 3x1 x2 x3 x4 x5 x6 x7 0 A P1 P2 P3 P4 P5 P6 P7 P7 3 1 t原最优解 0 0 1 2 0 0 则X 0 0 1 2 0 0 0 一定是原问题的可行解 但不一定是原问题的最优解 若要生产E 在原最优表中增加非基变量X7 其中P7 B 1P7 2 3 10 33 4 3 1 104 315 6相应的检验数 49 3 C7 0时 才有利生产 令C7 17 相应的检验数 2 3 插入原最优表 继续求解 第二行乘以6 5 第一行加上第二行乘以4 3 得到新的最优解 0 0 0 18 5 0 0 6 5 最优值 88 4 5 最优方案生产D产品18 5 万件 E产品6 5 万件 利润达到88 8 万元 问题10 假设该工厂又增加了用电不超过8千瓦的限制 而生产A B C D四种产品各1万件分别消耗电4 3 5 2千瓦 此约束是否改变了原最优决策方案 只需在模型中增加新的约束条件 4x1 3x2 5x3 2x4 8标准化后有4x1 3x2 5x3 2x4 x7 8加入模型中 X4 X3 X7是基变量 使增加一行元素 5 2 为零 第三行加上第一行的 2 倍 第三行加上第二行的 5 倍 第三行不可行 第三行乘以 2 第一行加上第三行乘以 2 3 第二行加上第三行乘以 1 6 计算检验数得最优表 增加用电约束后 最优生产方案 生产4 3万件C产品 2 3万件D产品 总利润为79 5万元 问题11 对偶解的经济含义是什么 如果把线性规划的约束看成广义资源约束 右边项则代表某种资源的可用量 约束条件右端某一常数项增加一个单位而引起目标函数最优值的变化量 通常称为影子价格 对偶解对应于影子价格 证明 在最优解情况下有 z CX 0 CBXB 0 CBB 1b Y 0 b因为Y 0 是对偶问题的最优解 而且表示随资源量b增加1个单位 目标函数值的变化量 因此 影子价格就是该约束条件相对应的对偶变量的最优值 当yi 0时 当bi增加后 z将增加 当yi 0时 当bi增加后 z不会增加 所以可见 影子价格是与原始问题约束条件相联系 而不是与决策变量相联系 影子价格的特征 1 影子价格是一种虚拟的价格而不是真实价格 是对系统内部资源的客观估计 2 影子价格是对系统资源的最优估计 只有系统达到最优状态时才可以赋与资源这种价值 3 影子价格的取值受系统状态变化的影响 系统内部资源数量和价格的变化都会引起影子价格的变化 它是一种动态的价格体系 影子价格的特征 4 影子价格的大小客观反映了资源在系统内的稀缺程度 如果某资源在系统内供大于求 尽管它有市场价格 但它的影子价格等于零 增加这种资源的供应不会引起系统目标的任何变化 如果某资源是稀缺资源 其影子价格必然大于零 影子价格越高 这种资源在系统中越稀缺 5 影子价格是一种边际价值 它与经济学中边际成本