第二章 运筹学运输问题PPT讲稿.ppt

《第二章 运筹学运输问题PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第二章 运筹学运输问题PPT讲稿.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 运筹学运输问题第1页，共36页，编辑于2022年，星期二n教学目的与要求：使学生学会建模方法能用表上作业法及WinQSB求解运输问题。n重点与难点：重点是产销平衡运输问题的表上作业法，难点是基变量个数为m+n-1的理论及操作方法.n教学方法:课堂讲授并辅以课件及软件.n思考题,讨论题,作业:教材中第三章作业.n参考资料:见前言n学时分配:4学时.第2页，共36页，编辑于2022年，星期二第二章 运输问题(Transportation problems)物资调运是一个典型的线性规划问题.1939年前苏联经济学家康托洛维奇提出这一问题,1941年美国数学家F.L.Hitchcock提出运输

2、问题数学模型,1951年Dantzig将此类问题的解法系统化,完善化,改为用表上作业法求解.第3页，共36页，编辑于2022年，星期二第一节 运输问题数学模型一.平衡运输问题的数学模型平衡表第4页，共36页，编辑于2022年，星期二建立数学模型第5页，共36页，编辑于2022年，星期二平衡运输问题数学模型的矩阵表示法第6页，共36页，编辑于2022年，星期二定理1 在产销平衡的运输问题中,其约束方程组的系数矩阵和增广矩阵的秩相等,且等于m+n-1.定理2 方程组 有解的充要条件是证明:必要性第7页，共36页，编辑于2022年，星期二充分性定理3 平衡的运输问题一定有最优解.证明:第8页，共36

3、页，编辑于2022年，星期二1.编制初始调运方案方法一:最小元素法(Minimal elements method)在平衡表中,按运价最小者优先满足的原则,找出m+n-1个有数字的格为基变量,空格为非基变量.方法二:西北角法(Northwest corner method)注意:一般来说用最小元素法得到的初始调运方案更接近于最优方案.第9页，共36页，编辑于2022年，星期二二.运输问题的表上作业法 发发量7 3113124 19289 74105收量3656 20例1 见下表:第10页，共36页，编辑于2022年，星期二2.最优方案的判别方法一:闭回路法闭回路:从非基变量格出发,沿水平或垂直

4、方向前进,碰到适当的基变量格转向,再回到原来的空格,称为一个闭回路.在闭回路上的基变量格称为转角点.可以证明,如果不考虑方向,则每一个空格的闭回路唯一存在.第11页，共36页，编辑于2022年，星期二找出上例中各空格的闭回路发发量437 311312314 1928639 74105收量3656 20收第12页，共36页，编辑于2022年，星期二每个空格即非基变量的检验数的求法:注意:1.空格为第0次转角.2.当第一次出现正检验数时,可停止以下检验数的计算.第13页，共36页，编辑于2022年，星期二调运方案的判优准则:对调运方案表中的每一空格作一条闭回路,并求出检验数,如果检验数全部小于等于

5、零,则该调运方案最优.否则要调整调运方案.3.方案的调整 选取入基变量:第一个正检验数的空格对应的非基变量为入基变量.本例中 为入基变量.入基变量的取值为,=min奇转角点运量.即该非基变量的运量为,同时变为基变量.第14页，共36页，编辑于2022年，星期二 出基变量的选择:在此闭回路上和奇转角点上最小运量对应的基变量变为零,该变量是出基变量,在新方案中它的位置是空格.在该闭回路中按奇,偶点进行运量的平衡调整,得一新的调运方案.对新方案判优,调整,直到求出最优方案.第15页，共36页，编辑于2022年，星期二发发量437 311312314 1928639 74105收量3656 20收第1

6、6页，共36页，编辑于2022年，星期二发发量527 311312314 1928549 74105收量3656 20收第一次调整后的新方案第17页，共36页，编辑于2022年，星期二经过四次迭代得到最优方案如下,总运费为85.发发量257 311312134 1928639 74105收量3656 20收第18页，共36页，编辑于2022年，星期二方法二:乘数法(位势法)发发量437 311 312314 1928639 7410 5收量3656 20收第19页，共36页，编辑于2022年，星期二令第一,二,三行的乘数分别为令第一,二,三,四列的乘数分别为且有写出基变量的乘数方程:第20页，

7、共36页，编辑于2022年，星期二该乘数方程有六个方程,七个未知数,一定有解,且有无穷多解.可令 得出一组解.由这组解按下面的公式求空格(非基变量的检验数:第21页，共36页，编辑于2022年，星期二与闭回路法求得的检验数完全相同.第22页，共36页，编辑于2022年，星期二注意:要保证调运平衡表中填有数字的格数为 m+n-1,且不构成闭回路。若 填上调运量后,第i行发量及第j列销量都已满足,则在运价表中只允许划去第i行与第j列中的一个,而不允许将它们全划去.此后,当运价 或 最小时,要在 或 的格子上填写0,它表示一个基变量,这属于LP中退化的情形.第23页，共36页，编辑于2022年，星期

8、二发发量25 164832 8951013 7243收量22131718 70收请看下面的例子:第三行,第二列任选一个第24页，共36页，编辑于2022年，星期二2.对于有的运输问题,最优调运方案不止一个.23521432232713521516143212254518第25页，共36页，编辑于2022年，星期二二.产销不平衡的运输问题第26页，共36页，编辑于2022年，星期二解决方法:增加一个虚拟(Dummy)库存点(销地),其库存量为第27页，共36页，编辑于2022年，星期二再增加m个松弛变量表示产地 在 处的库存量.在运价表中,相应的运价 ,但这个运价不按最小元素处理.经过以上的处理

9、,可将产大于销的运输问题变为产销平衡的运输问题.第28页，共36页，编辑于2022年，星期二例3 收发发量7 211345 103597 7812收量2346 1915第29页，共36页，编辑于2022年，星期二 收发 库存发量库存7 2113405 103590778120收量2346 419将其改为产销平衡的运输问题,并求出初始调运方案第30页，共36页，编辑于2022年，星期二对于产销不平衡的运输问题中产小于销的情况，可在产销平衡表中虚设一个产地，其产量为 ，到各地的运价是0，变为产销平衡的运输问题。第31页，共36页，编辑于2022年，星期二产销不平衡（需求量不固定）的运输问题实例:某

10、研究院有 三个区。每年取暖分别需要用煤3500吨，1100吨，2400吨，这些煤都要由 煤矿 供应，价格，质量均相同。煤矿的供应能力分别为1500吨，4000吨，运价如下表所示。由于需求大于供应，经研究决定：区供应量可减少0900吨，区必须满足需求量，区供应量不少于1600吨，试求总费用最低的调运方案。第32页，共36页，编辑于2022年，星期二 需求地煤矿产量17519520815001601822154000需求量350011002400第33页，共36页，编辑于2022年，星期二解：这是一个产销不平衡的运输问题，需求量大于供应量。处理办法是，将 区和 区分别设为两个区：一个是必须满足需求

11、量的区，另一个是可以调整供应量的区。同时增加一个虚设的产地 ，其供应量为1500吨，同时在运价表中，取M表示一个很大的正数，使必须满足需求量的区域的运价取值为M，可调整需求量的区域的运价取值为0。（为什么？）这样，原问题变为有五个需求点，三个供应点的产销平衡的运输问题。新平衡表如下：第34页，共36页，编辑于2022年，星期二 需求地煤矿产量17517519520820815001601601822152154000M0MM01500需求量260090011001600800 70007000第35页，共36页，编辑于2022年，星期二用WinQSB解运输问题。第36页，共36页，编辑于2022年，星期二