运筹学第七讲运输问题.ppt

该【运筹学第七讲运输问题 】是由【小屁孩】上传分享，文档一共【19】页，该文档可以免费在线阅读，需要了解更多关于【运筹学第七讲运输问题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。绍兴文理学院工学院计算机系运筹学2021/10/102运筹学第七讲运输问题第七章运输问题一类特殊类型的LP问题——运输问题;模型、表上作业法应用、用Excel求解讨论2021/10/103运筹学第七讲运输问题运输问题某种产品从若干个产地(产量已知)运往若干个销地(销量已知),已知各地间运输单价,求总运费最小的运输方案。此问题是我国科学家(王元,越民义等)在1959年前率先研究讨论的,并获得了:表上作业法和图上作业法等重要结果。2021/10/104运筹学第七讲运输问题运输问题产地数m=2,销地数n=3,产销平衡,决策变量个数m*n,等式约束数m+n,不等式约束数0,目标函数是总运价,要求最小。2021/10/105运筹学第七讲运输问题运输问题目标函数:,但若用单纯形法,[等式约束数m+n(但当产销平衡的时候其中有一个是多余的,),不等式约束数0]初始基可行解就显得很难求,决策变量个数也较大,我国科学家在上世纪五十年代提出了解运输问题的图上作业法和表上作业法。2021/10/107运筹学第七讲运输问题表上作业法运输问题的表上作业法:平衡产销;找出初始基可行解(西北角法、最小元素法、Vogel法);基可行解是否最优的判别(闭回路法、位势法*);非最优的基可行解的改进(闭回路调整法).2021/10/108运筹学第七讲运输问题平衡产销运输问题中产销不平衡时:产>销:增加一个假想的仓库,运费为0,当新销地。产<销:增加一个假想的产地,运费为0。总可以调整为产销平衡。2021/10/109运筹学第七讲运输问题找出初始基可行解运输问题的独立的等式约束数=系数矩阵的秩=基变量个数=m+n-1,非基变量个数=m*n-m-n+1。找出初始基可行解(m+n-1格):西北角法;最小元素法;伏格尔(Vogel)法*。344222233662021/10/1011运筹学第七讲运输问题