运筹学电子教案-LP运输

1商店123需求量（件/周）506030工厂123供应量（件/周）507020运输问题的一般描述模型的一般形式引例这里有三家工厂，都将产品运往三个不同的商店（见下图）。每个工厂以产品件数表示出每周生产能力见下表1。每家商店平均需求量见下表2。线性规划LinearProgramming（LP）特殊线性规划——运输问题工厂1工厂3工厂2商店1商店3商店2表1表22但是，由于运货距离不同，各个工厂运往各商店的货物的运输费用是不同的。费用如下表，我们的问题是确定由哪家工厂运送多少件产品到哪家商店。能否列出线性最优化模型？决策存在什么样的约束条件？模型评价涉及什么样的准则？有那些决策变量？线性规划LinearProgramming（LP）特殊线性规划——运输问题由工厂每件产品运往各商店的费用（元）123132321058313103模型建立决策变量——有待确定的是从每家工厂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+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）特殊线性规划——运输问题4——对每家商店来说，也需要一个逻辑关系式来说明每个星期运到的产品总数应等于每周的需求量。对商店1必须有X11+X21+X31=50对商店2必须有X12+X22+X32=60对商店3必须有X13+X23+X33=30于是，用于解此问题的线性最优化模型是：MinZ=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33X11+X12+X13≤50X21+X22+X23≤70X31+X32+X33≤20X11+X21+X31=50Xij≥0且为整数X12+X22+X32=60i=1，2，3X13+X23+X33=30j=1，2，3线性规划LinearProgramming（LP）特殊线性规划——运输问题s.t.5运输问题模型分析一般形式：某种物资有m个产地Ai，产量（供应量）是ai（i=1，2，…，m），有n个销地Bj，销量（需求量）是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）6产销平衡——ai=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）jjii7运输问题的求解方法求解此问题的一个十分有效的方法是表上作业法：（1）产销平衡问题——总产量等于总销量的运输问题a、建立作业表b、确定初始调运方案（最小元素法）c、现行方案的最优性检验（位势法）d、现行方案的调整（闭回路法）线性规划LinearProgramming（LP）特殊线性规划——运输问题8例1——甲（B1）、乙（B2）、丙（B3）、丁（B4）三城市所需煤炭由三个煤矿A1、A2、A3供应，有关数据如表，表中数字为单位运费（万元／万吨），请制订使总运费最小的调运计划。产地A1A2A3销量B1B2B3B4产量3764524322438533322线性规划LinearProgramming（LP）特殊线性规划——运输问题9a、建立平衡调运作业表376424324385A1A2A3B1B2B3B4产量销量33225233运价Xij调运量，当其为非基变量时不予填写ij检验数，当其为基变量的检验数时不予填写线性规划LinearProgramming（LP）特殊线性规划——运输问题10b、确定初始调运方案（最小元素法）376424324385A1A2A3B1B2B3B4产量销量33225233运价Xij调运量，当其为非基变量时不予填写ij检验数，当其为基变量的检验数时不予填写211430222线性规划LinearProgramming（LP）特殊线性规划——运输问题11c、现行方案的最优性检验（位势法）102223376424324385A1A2A3B1B2B3B4UiVj由ij=Cij-（Ui+Vj）计算位势Ui，Vj，因对基变量而言有ij=0，即Cij-（Ui+Vj）=0令U1=003764-1-4再由ij=Cij-（Ui+Vj）计算非基变量的检验数ij-2-2-1565当存在非基变量的检验数kl0且kl=min{ij}时，令Xkl进基。从表中知可选X23进基。线性规划LinearProgramming（LP）特殊线性规划——运输问题12d、现行方案的调整（闭回路法）102223376424324385A1A2A3B1B2B3B4UiVj03764-1-4-2-2-1565调整量={从进基变量X23出发的闭回路中偶拐点上基变量的最小值}=2。调整步骤为闭回路上奇拐点变量的值+偶拐点变量的值-230线性规划LinearProgramming（LP）特殊线性规划——运输问题13d、现行方案的调整（闭回路法）1022223376424324385A1A2A3B1B2B3B4UiVj重复步骤C、检验当前调运方案（基可行解）的最优性如非最优方案，则擦去Ui、Vj和ij然后重新计算。30037-144-42-2-15850线性规划LinearProgramming（LP）特殊线性规划——运输问题14d、现行方案的调整（闭回路法）1022023376424324385A1A2A3B1B2B3B4UiVj重复步骤C、检验当前调运方案（基可行解）的最优性如非最优方案，则擦去Ui、Vj和ij然后重新计算。30374-3-46021565当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费minZ=9+0+8+0+6+9=32线性规划LinearProgramming（LP）特殊线性规划——运输问题15（2）产销不平衡问题——总产量小于总销量的运输问题例2—有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。A1A2A3最低需求（万吨）最高需求（万吨）B1B2B3B4产量（万吨）16132217501413191560192023---503070010507030不限线性规划LinearProgramming（LP）特殊线性规划——运输问题化肥厂需求地区运价：万元/万吨16分析：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，地区B4每年最多能分配到60万吨，这样最高总需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂D，其年产量为50万吨。由于各个地区的需要量包含两部分，如地区B1，其中30万吨是最低需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为M（任意大正数），而另一部分20万吨满足或不满足均可，因此可以由虚拟的化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表——线性规划LinearProgramming（LP）特殊线性规划——运输问题17例2产销平衡表线性规划LinearProgramming（LP）特殊线性规划——运输问题A1A2A3DB'1B''1B2B3B'4B''4产量销量171714141319151519192023MMM0M0M050605050302070301050161622132030203050202040301010030202018产销平衡表线性规划LinearProgramming（LP）特殊线性规划——运输问题A1A2A3DB'1B''1B2B3B'4B''4UiVj13501430132019015102330M2002003001301419154-4+M4-M-4+M220-M3221-M18-M19-M119-M3M-192M-182M-17M-232M-19162217171415191920MMM0M1603020203019产销平衡表线性规划LinearProgramming（LP）特殊线性规划——运输问题A1A2A3DB'1B''1B2B3B'4B''4UiVj501430140132015102330M2002003000-14+M-1414141337-M151422-15+M23-18+M119-M19-M21-M-1M1+M-23+M-1+M10200502016132217171915191920MMM0M1620产销平衡表线性规划LinearProgramming（LP）特殊线性规划——运输问题A1A2A3DB'1B''1B2B3B'4B''4UiVj16135022171714101420132019151015192019202330MM0M0M0M050160055-M1414131815-5+M224222-M120-M02-20+M-19+2M-19+M-18+M-23+M-20+2M1020021产销平衡表线性规划LinearProgramming（LP）特殊线性规划——运输问题A1A2A3DB'1B''1B2B3B'4B''4UiVj161350221717141014201320191510150192019202330MMM0M0M050160060141413171515225222-11-21+M-21+M-14+M-14-13+M-17-15+M101030204022产销平衡表线性规划LinearProgramming（LP）特殊线性规划——运输问题A1A2A3DB'1B''1B2B3B'4B''4UiVj1350142013201510151019302320010040008-151114131515155272234-3-1M-23M-23M+41M+2M3003020201622171714191920MMM0MM1623产销平衡表线性规划LinearProgramming（LP）特殊线性规划——运输问题A1A2A3DB'1B''1B2B3B'4B''4UiVj16135022171714141320