第一章_运筹学—线性规划1001上传.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 例1用伏格尔法得到的初始基可行解 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 4 8 14 8 12 2 目标函数值 用最小元素法 求出的目标函数z=246 一般说来，伏格尔法得出的初始解的质量最好，常用来作为运输问题最优解的近似解。 第二步：解的最优性检验 闭回路法 思路：计算空格（非基变量）的检验数 若令 则 如何求检验数？ 分析： ——运费的增量 即 增加1个单位 的检验数=相应的运费增量 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 从初始表分析： 要保证产销平衡，则 称为闭回路 +1 -1 +1 -1 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 2 1 检验数表 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 2 1 1 -1 10 12 表中的解不是最优解。 第三步：解的调整 调整位置（2，4）非空，回路角上的格至少为空，且保证数字的非负性。 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 10 14 6 8 -1 （-2） （-2） （+2） （+2） 调整后的解为： 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 8 2 12 14 4 8 2 2 0 9 1 12 此时的解为最优解。 有无穷多最优解 几点说明： 当检验数为的负的变量超过两个，选择最小者对应的变量换入； 在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解； 迭代过程中，若某一格填数时需同时划去一行和一列，此时出现退化。为保证m+n-1个非空格，需在上述的行或列中填入数字0。 讨论内容： 初始调运方案（初始基可行解） ——西北角法 解的最优性检验——对偶变量法（或称位势法） 还有其它的方法吗 ？ 根据第一节运输问题对偶问题与原问题的检验数的关系 第三节 运输问题的 进一步讨论 上节给出产销平衡运输问题的表上作业法，本节以下问题进一步讨论： 二、有转运的运输问题 一、产销不平衡的运输问题 并附有运输问题的思考题及练习题 一、产销不平衡的运输问题 （Ⅰ）若总产量大于总销量，即 令假象销地的销量为： 决策变量 表示由 到 的物品数量。 销地 产地 销量 产量 注意：用最小元素法求初始调运方案时，最后一列的零运价最后考虑。 原产大于销平衡问题的数学模型 修改后产大于销平衡问题的数学模型 （Ⅱ）若总产量小于总销量，即 令假象产地的销量为： 一、产销不平衡的运输问题 仿照上述类似处理。 举例说明 某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表： 4 12 2 8 5 4 3 9 6 11 11 10 销量 产量 销地 产地 二、有转运的运输问题 中间转运站——产地、销地、中转站。 建模思路：从发送及接受角度考虑。 产地 转运 销地 发送量 产地 转运 销地 接受量 应用问题举例 例1、水泥调运的产销不平衡情况及运价如下表，求最好的调运方案。 2 11 10 7 8 3 5 9 2 1 4 3 销量 产量 销地 产地 最优方案为： 2 11 10 7 8 3 5 9 2 1 4 3 销量 产量 销地 产地 0 0 0 例2、某农场有土地900亩，分为三类，计划种植三种作物，情况如下表，求使作物总产量最多的布局方案。 500 销量 产量 销地 产地 700 700 850 480 600 300 400 500 解：目标函数最大，可用最大元素法，即是按产量高的优先安排的原则。 500 销量 产量 销地 产地 700 700 850 480 600 300 400 500 100 300 100 400 0 50 调整： 500 销量 产量 销地 产地 700 700 850 480 600 300 400 500 100 200 200 400 0 可验证此时为最优解。 运