运筹学电子教案_LP运输.ppt

商店 1 2 3 需求量（件/周） 50 60 30; 但是，由于运货距离不同，各个工厂运往各商店的货物的运输费用是不同的。费用如下表，我们的问题是确定由哪家工厂运送多少件产品到哪家商店。 能否列出线性最优化模型？ 决策存在什么样的约束条件？ 模型评价涉及什么样的准则？ 有那些决策变量？;模型建立 决策变量——有待确定的是从每家工厂i（i=1，2，3）运输多少件产品到每家商店j（j=1，2，3）去。因此，方便的办法是用双下标来表示决策变量即 Xij。 目标函数——利用运输费用表中的数据，我们希望其值为最小的是： Min Z =由工厂1运出产品的总费用---- 3X11+ 2X12+ 3X13 +由工厂2运出产品的总费用----10X21+ 5X22+ 8X23 +由工厂3运出产品的总费用---- X31+ 3X32+10X33 即：Min Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23 + X31+ 3X32+10X33 约束条件——需要把决策变量的约束条件当作方案生成源。 对工厂1必须有 X11+X12+X13 ≤50 （对工厂1的供应约束） 对工厂2必须有 X21+X22+X23 ≤70 （对工厂2的供应约束） 对工厂3必须有 X31+X32+X33 ≤20 （对工厂3的供应约束）;——对每家商店来说，也需要一个逻辑关系式来说明每个星期运到的产品总数应等于每周的需求量。 对商店1必须有 X11+X21+X31 =50 对商店2必须有 X12+X22+X32 =60 对商店3必须有 X13+X23+X33 =30 于是，用于解此问题的线性最优化模型是： Min Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23 + X31+ 3X32+10X33 X11+X12+X13 ≤50 X21+X22+X23 ≤70 X31+X32+X33 ≤20 X11+ X21+ X31 = 50 Xij≥0 且为整数 X12+ X22+ X32 = 60 i=1，2，3 X13+ X23+ X33 = 30 j=1，2，3 ;运输问题模型分析 一般形式： 某种物资有m个产地Ai，产量（供应量）是ai（i=1，2，…，m），有n个销地Bj，销量（需求量）是bj（j=1，2，…，n）。从运到的单位运价为cij（i=1，2，…，m；j=1，2，…，n），如何安排运输可使总运费最小？;产销平衡——? ai = ? bj 注意！这种模型具有特殊的形式：所有决策变量的约束条件，其系数均等于1；而且，每个决策变量仅出现于两个约束条件之中。这些特性表明，解这类线性最优化模型的单纯形法中有一种特殊的方法可用来解这个问题——这是解这类模型的特别有效的一种方法。而且上述特性还表明，可以给这类线性最优化模型以一种象网络模型式的形象化的说明。;运输问题的求解方法 求解此问题的一个十分有效的方法是表上作业法： （1）产销平衡问题——总产量等于总销量的运输问题 a、建立作业表 b、确定初始调运方案（最小元素法） c、现行方案的最优性检验（位势法） d、现行方案的调整（闭回路法）;例1—— 甲（B1）、乙（B2）、丙（B3）、丁（B4）三城市所需煤炭由三个煤矿A1、A2、A3供应，有关数据如表，表中数字为单位运费（万元／万吨），请制订使总运费最小的调运计划。;a、建立平衡调运作业表;b、确定初始调运方案（最小元素法）;c、现行方案的最优性检验（位势法）;d、现行方案的调整（闭回路法） ;d、现行方案的调整（闭回路法） ;d、现行方案的调整（闭回路法） ;（2）产销不平衡问题——总产量小于总销量的运输问题 例2—有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。 ;分析： 这是一个产销不平衡的运输问题，