(运筹学课件运输问题 ).ppt

《(运筹学课件运输问题 ).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学运输问题第七章运输问题赵玮主要内容：7.1运输模型7.2运输问题的计算机求解7.3运输问题的应用一、产销不平衡的运输问题二、生产与储存问题三、转运问题7.4运输问题的表上作业法一、确定初始基本可行解二、最优解的判别三、改进运输方案的办法——闭回路调整法四、如何找多个最优方案一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。§7.1运输模型例1.某公司从两个产地A1

2、,A2将物品运往三个销地B1，B2，B3,各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：问应如何调运，使得总运输费最小？解：我们知道A1、A2两个产地的总产量为：200+300=500（件）；B1，B2，B3三个销地的总销量为：150+150+200=500（件）,总产量等于总销量这是一个产销平衡的运输问题。把A1，A2的产量全部分配给B1，B2，B3，正好满足这三个销地的需要。设xij表示从产地Ai调运到Bj的运输量（i=1，2；j=1，2，3），例如，x12表示从A1

3、调运到B2的物品数量，现将安排的运输量列表如下：从上表可写出此问题的数学模型。满足产地产量的约束条件为：x11+x12+x13=200，x21+x22+x23=300.满足销地销量的约束条件为：x11+x21=200，x12+x22=300，x13+x23=200.所以此运输问题的线性规划的模型如下：目标函数：minf=6x11+4x12+6x13+6x21+5x22+5x23约束条件：x11+x12+x13=200，x21+x22+x23=300，x11+x21=150，x12+x22=150，

4、x13+x23=200.xij≥0.(i=1，2；j=1，2，3)为了给出一般运输问题的线性规划的模型，我们将使用以下的一些符号：A1，A2，…，Am表示某种物资的m个产地；B1，B2，…，Bn表示某种物资的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运到销地Bj的单位运价。§7.1运输模型同样设xij表示从产地Ai运到销地Bj的运输量，则产销平衡的运输问题的线性规划模型如下所示：目标函数：§7.1运输模型约束条件：Xij≥0，对所有的i和j.有时上述的运输

5、问题的一般模型会发生一些如下变化：1.求目标函数的最大值而不是最小值有些运输问题中，它的目标是要找出利润最大或营业额最大的调运方案，这时要求目标函数的最大值了。2.当某些运输线路的运输能力有一定限制时，这时要在线性规划的模型的约束条件上要加上运输能力限制的约束条件。例如从A3运到B4的物品的数量受到运输能力的限制，最多运送1000单位，这时只要在原来的模型上加上约束条件x34≤1000即可。3.当生产总量不等于销售总量，即产销不平衡时，这时将通过增加一个假想仓库或假想生产地来化成产销平衡的问题，具

6、体做法将在下面阐述。§7.2运输问题的计算机求解在上一节中我们讨论的是产销平衡的运输问题，对于产销不平衡的运输问题，我们可以先化为产销平衡的运输问题然后再求解。例2．某公司从两个产地A1，A2将物品运往三个销地B1，B2，B3，各产地产量和各销地销量以及各产地运往各销地的每件物品的运输费列表如下：应如何组织运输，使总运输费用为最小？例2的产销平衡表例3．某公司从两个产地A1，A2将物品运往三个销地B1，B2，B3，各销地的销量以及从产地到销地的每件物品的运输单价列表如下：§7.3运输问题的应用主要

7、内容：一、产销不平衡的运输问题二、生产与储存问题三、转运问题一、产销不平衡的运输问题例4．石家庄北方研究院有三个区，即一区、二区、三区，每年分别需要生活用煤和取暖用煤3000、1000、2000吨，由河北临城，山西盂县两处煤矿负责供应，这两处煤矿的价格相同，煤的质量也基本相同，两处煤矿能供应北方研究院的单位运价（百元/吨）见下表：由于需大于供，经院研究平衡决定一区供应量可减少0～200吨，二区需要量应全部满足，三区供应量不少于1700吨。试求总运费为最低的调运方案。运价百元/吨解：根据题意，作出产

8、销平衡与运价表如下：例5．设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量、各地区年需求量及从各化肥厂到各地区运送单位化肥的运价如下表，试求出总的运费最节省的化肥调拨方案。输入“管理运筹学软件”即可得到最优调运方案如下（注：表中的M我们只要输入一个足够大的正数如10000即可）最小总运费为2460万元。二、生产与储存问题例6.某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台