第二章 运筹学运输问题

第二章运筹学运输问题第1页，课件共36页，创作于2023年2月教学目的与要求：使学生学会建模方法能用表上作业法及WinQSB求解运输问题。重点与难点：重点是产销平衡运输问题的表上作业法，难点是基变量个数为m+n-1的理论及操作方法.教学方法:课堂讲授并辅以课件及软件.思考题,讨论题,作业:教材中第三章作业.参考资料:见前言学时分配:4学时. 第2页，课件共36页，创作于2023年2月第二章运输问题(Transportationproblems)物资调运是一个典型的线性规划问题.1939年前苏联经济学家康托洛维奇提出这一问题,1941年美国数学家F.L.Hitchcock提出运输问题数学模型,1951年Dantzig将此类问题的解法系统化,完善化,改为用表上作业法求解.第3页，课件共36页，创作于2023年2月第一节运输问题数学模型一.平衡运输问题的数学模型平衡表第4页，课件共36页，创作于2023年2月建立数学模型第5页，课件共36页，创作于2023年2月平衡运输问题数学模型的矩阵表示法第6页，课件共36页，创作于2023年2月定理1在产销平衡的运输问题中,其约束方程组的系数矩阵和增广矩阵的秩相等,且等于m+n-1.定理2方程组有解的充要条件是证明:必要性第7页，课件共36页，创作于2023年2月充分性定理3平衡的运输问题一定有最优解.证明:第8页，课件共36页，创作于2023年2月1.编制初始调运方案方法一:最小元素法(Minimalelementsmethod)在平衡表中,按运价最小者优先满足的原则,找出m+n-1个有数字的格为基变量,空格为非基变量.方法二:西北角法(Northwestcornermethod)注意:一般来说用最小元素法得到的初始调运方案更接近于最优方案.第9页，课件共36页，创作于2023年2月二.运输问题的表上作业法

发发量731131241928974105收量365620例1见下表:第10页，课件共36页，创作于2023年2月2.最优方案的判别方法一:闭回路法闭回路:从非基变量格出发,沿水平或垂直方向前进,碰到适当的基变量格转向,再回到原来的空格,称为一个闭回路.在闭回路上的基变量格称为转角点.可以证明,如果不考虑方向,则每一个空格的闭回路唯一存在.第11页，课件共36页，创作于2023年2月找出上例中各空格的闭回路发发量437311312314192863974105收量365620收第12页，课件共36页，创作于2023年2月每个空格即非基变量的检验数的求法:注意:1.空格为第0次转角.2.当第一次出现正检验数时,可停止以下检验数的计算.第13页，课件共36页，创作于2023年2月调运方案的判优准则:对调运方案表中的每一空格作一条闭回路,并求出检验数,如果检验数全部小于等于零,则该调运方案最优.否则要调整调运方案.3.方案的调整⑴选取入基变量:第一个正检验数的空格对应的非基变量为入基变量.本例中为入基变量.⑵入基变量的取值为θ,θ=min{奇转角点运量}.即该非基变量的运量为θ,同时变为基变量.第14页，课件共36页，创作于2023年2月⑶出基变量的选择:在此闭回路上和奇转角点上最小运量对应的基变量变为零,该变量是出基变量,在新方案中它的位置是空格.⑷在该闭回路中按奇,偶点进行运量的平衡调整,得一新的调运方案.⑸对新方案判优,调整,直到求出最优方案.第15页，课件共36页，创作于2023年2月发发量437311312314192863974105收量365620收第16页，课件共36页，创作于2023年2月发发量527311312314192854974105收量365620收第一次调整后的新方案第17页，课件共36页，创作于2023年2月经过四次迭代得到最优方案如下,总运费为85.发发量257311312134192863974105收量365620收第18页，课件共36页，创作于2023年2月方法二:乘数法(位势法)发发量437311312314192863974105收量365620收第19页，课件共36页，创作于2023年2月令第一,二,三行的乘数分别为令第一,二,三,四列的乘数分别为且有写出基变量的乘数方程:第20页，课件共36页，创作于2023年2月该乘数方程有六个方程,七个未知数,一定有解,且有无穷多解.可令得出一组解.由这组解按下面的公式求空格(非基变量的检验数:第21页，课件共36页，创作于2023年2月与闭回路法求得的检验数完全相同.第22页，课件共36页，创作于2023年2月注意:⒈要保证调运平衡表中填有数字的格数为m+n-1,且不构成闭回路。若填上调运量后,第i行发量及第j列销量都已满足,则在运价表中只允许划去第i行与第j列中的一个,而不允许将它们全划去.此后,当运价或最小时,要在或的格子上填写0,它表示一个基变量,这属于LP中退化的情形.第23页，课件共36页，创作于2023年2月发发量2516483289510137243收量2213171870收请看下面的例子:第三行,第二列任选一个第24页，课件共36页，创作于2023年2月2.对于有的运输问题,最优调运方案不止一个.

23521432232713521516143212254518第25页，课件共36页，创作于2023年2月二.产销不平衡的运输问题第26页，课件共36页，创作于2023年2月解决方法:增加一个虚拟(Dummy)库存点(销地),其库存量为第27页，课件共36页，创作于2023年2月再增加m个松弛变量表示产地在处的库存量.在运价表中,相应的运价,但这个运价不按最小元素处理.经过以上的处理,可将产大于销的运输问题变为产销平衡的运输问题.第28页，课件共36页，创作于2023年2月例3收发发量72113451035977812收量23461915第29页，课件共36页，创作于2023年2月收发库存发量库存72113405103590778120收量2346419将其改为产销平衡的运输问题,并求出初始调运方案第30页，课件共36页，创作于2023年2月对于产销不平衡的运输问题中产小于销的情况，可在产销平衡表中虚设一个产地，其产量为，到各地的运价是0，变为产销平衡的运输问题。第31页，课件共36页，创作于2023年2月产销不平衡（需求量不固定）的运输问题实例:某研究院有三个区。每年取暖分别需要用煤3500吨，1100吨，2400吨，这些煤都要由煤矿供应，价格，质量均相同。煤矿的供应能力分别为1500吨，4000吨，运价如下表所示。由于需求大于供应，经研究决定：区供应量可减少0—900吨，区必须满足需求量，区供应量不少于1600吨，试求总费用最低的调运方案。

第32页，课件共36页，创作于2023年2月需求地煤矿产量17519520815001601822154000需求量350011002400第33页，课件共36页，创作于2023年2月解：这是一个产销不平衡的运输问题，需求量大于供应量。处理办法是，将区和区分别设为两个区：一个是必须满足需求量的区，另一个是可以调整供应量的区。同时增加一个虚设的产地，其供应量为1500吨，同时在运价表中，取M表示一个很大的正数，使必须满足需求量的区域的运价取值为M，可调整需求量的区域的运价取值为0。（为什么？）这样，原问题变为有五个需求点，三个供应点的产销平衡的运输问题。新平衡表如下：