运筹学电子教案-LP运输

《运筹学电子教案-LP运输》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、商店123需求量（件/周）506030工厂123供应量（件/周）507020运输问题的一般描述模型的一般形式引例这里有三家工厂，都将产品运往三个不同的商店（见下图）。每个工厂以产品件数表示出每周生产能力见下表1。每家商店平均需求量见下表2。线性规划LinearProgramming（LP）特殊线性规划——运输问题工厂1工厂3工厂2商店1商店3商店2表1表21但是，由于运货距离不同，各个工厂运往各商店的货物的运输费用是不同的。费用如下表，我们的问题是确定由哪家工厂运送多少件产品到哪家商店。能否列出线性最优化模型？决策存在什么样的约束条件？模型评价涉及什么样的准则？有那些决策变量？

2、线性规划LinearProgramming（LP）特殊线性规划——运输问题由工厂每件产品运往各商店的费用（元）123132321058313102模型建立决策变量——有待确定的是从每家工厂i（i=1，2，3）运输多少件产品到每家商店j（j=1，2，3）去。因此，方便的办法是用双下标来表示决策变量即Xij。目标函数——利用运输费用表中的数据，我们希望其值为最小的是：MinZ=由工厂1运出产品的总费用----3X11+2X12+3X13+由工厂2运出产品的总费用----10X21+5X22+8X23+由工厂3运出产品的总费用----X31+3X32+10X33即：MinZ=3X11

3、+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的供应约束）线性规划LinearProgramming（LP）特殊线性规划——运输问题3——对每家商店来说，也需要一个逻辑关系式来说明每个星期运到的产品总数应等于每周的需求量。对商店1必须有X11+X21+X31=50对商店2必须有X12+X22+X32=60对商店3必

4、须有X13+X23+X33=30于是，用于解此问题的线性最优化模型是：MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33X11+X12+X13≤50X21+X22+X23≤70X31+X32+X33≤20X11+X21+X31=50Xij≥0且为整数X12+X22+X32=60i=1，2，3X13+X23+X33=30j=1，2，3线性规划LinearProgramming（LP）特殊线性规划——运输问题s.t.4运输问题模型分析一般形式：某种物资有m个产地Ai，产量（供应量）是ai（i=1，2，…，m），有n个销地Bj，销量（

5、需求量）是bj（j=1，2，…，n）。从运到的单位运价为cij（i=1，2，…，m；j=1，2，…，n），如何安排运输可使总运费最小？线性规划LinearProgramming（LP）特殊线性规划——运输问题产大于销——ai≥bjMinZ=CijXijxij≤ai（i=1，2，…，m）xij=bj（j=1，2，…，n）xij≥0（i=1，2，…，m；j=1，2，…，n）销大于产——ai≤bjMinZ=CijXijxij=ai（i=1，2，…，m）xij≤bj（j=1，2，…，n）xij≥0（i=1，2，…，m；j=1，2，…，n）5产销平衡——ai=

6、bj注意！这种模型具有特殊的形式：所有决策变量的约束条件，其系数均等于1；而且，每个决策变量仅出现于两个约束条件之中。这些特性表明，解这类线性最优化模型的单纯形法中有一种特殊的方法可用来解这个问题——这是解这类模型的特别有效的一种方法。而且上述特性还表明，可以给这类线性最优化模型以一种象网络模型式的形象化的说明。线性规划LinearProgramming（LP）特殊线性规划——运输问题MinZ=CijXijxij=ai（i=1，2，…，m）xij=bj（j=1，2，…，n）xij≥0（i=1，2，…，m；j=1，2，…，n）jjii6运输问题的求解方法求解此问题的一个十

7、分有效的方法是表上作业法：（1）产销平衡问题——总产量等于总销量的运输问题a、建立作业表b、确定初始调运方案（最小元素法）c、现行方案的最优性检验（位势法）d、现行方案的调整（闭回路法）线性规划LinearProgramming（LP）特殊线性规划——运输问题7例1——甲（B1）、乙（B2）、丙（B3）、丁（B4）三城市所需煤炭由三个煤矿A1、A2、A3供应，有关数据如表，表中数字为单位运费（万元／万吨），请制订使总运费最小的调运计划。产地A1A2A3销量B1B2B3B4产量37645243