3-2运输问题表上作业法.ppt

该【3-2运输问题表上作业法 】是由【小屁孩】上传分享，文档一共【42】页，该文档可以免费在线阅读，需要了解更多关于【3-2运输问题表上作业法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。运输问题的表上作业法1、单纯形法(为什麽?)2、表上作业法由于问题的特殊形式而采用的更简洁、更方便的方法2021/10/101一、表上作业法的基本思想先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进,直至求出最优方案,如图3-1所示。表上作业法和单纯形法的求解思想完全一致,但是具体作法更加简捷。2021/10/102确定初始方案(初始基本可行解)改进调整(换基迭代)否判定是否最优?是结束最优方案图1运输问题求解思路图2021/10/103二、初始方案的确定1、作业表(产销平衡表)初始方案就是初始基本可行解。将运输问题的有关信息表和决策变量——调运量结合在一起构成“作业表”(产销平衡表)。表2是两个产地、三个销地的运输问题作业表。2021/10/104调销地运量产地B1B2B3产量A1c11X11c12X12c13X13a1A2c21X21c22X22c23X23a2销量b1b2b3表2运输问题作业表(产销平衡表)2021/10/105其中xij是决策变量,表示待确定的从第i个产地到第j个销地的调运量,cij为从第i个产地到第j个销地的单位运价。2、确定初始方案的步骤:(1)选择一个xij,令xij=min{ai,bj}=将具体数值填入xij在表中的位置;2021/10/106(2)调整产销剩余数量:从ai和bj中分别减去xij的值,若ai-xij=0,则划去产地Ai所在的行,即该产地产量已全部运出无剩余,而销地Bj尚有需求缺口bj-ai;若bj-xij=0,则划去销地Bj所在的列,说明该销地需求已得到满足,而产地Ai尚有存余量ai-bj;(3)当作业表中所有的行或列均被划去,说明所有的产量均已运到各个销地,需求全部满足,xij的取值构成初始方案。否则,在作业表剩余的格子中选择下一个决策变量,返回步骤(2)。2021/10/107按照上述步骤产生的一组变量必定不构成闭回路,其取值非负,且总数是m+n-1个,因此构成运输问题的基本可行解。对xij的选择采用不同的规则就形成各种不同的方法,比如每次总是在作业表剩余的格子中选择运价(或运距)最小者对应的xij,则构成最小元素法,若每次都选择左上角格子对应的xij就形成西北角法(也称左上角法)。2021/10/1083、举例例3-2甲、乙两个煤矿供应A、B、C三个城市用煤,各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4,求使总运输量最少的调运方案。2021/10/109表3-4例3-2有关信息表450200150100日销量(需求量)250756580乙2001007090甲日产量(供应量)CBA运距城市煤矿2021/10/1010