运输单纯形法VIP免费

§3.3运输单纯形法TransportationSimplexMethodCh3TransportationProblem2025年1月5日Page1of31njijijmixcz11minnjmixnjbxmiaxijjmiijnjiij,,1;,,1,0,,1,,111设平衡运输问题的数学模型为：§3.3运输单纯形法TransportationSimplexMethodCh3TransportationProblem2025年1月5日Page2of31运输单纯形法也称为表上作业法，是直接在运价表上求最优解的一种方法，它的步骤是：第一步：求初始基行可行解（初始调运方案），常用的方法有最小元素法、元素差额法（Vogel近似法）、左上角法。第二步：求检验数并判断是否得到最优解，常用求检验的方法有闭回路法和位势法，当非基变量的检验数λij全都非负时得到最优解，若存在检验数λlk<0，说明还没有达到最优，转第三步。第三步：调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。§3.3运输单纯形法TransportationSimplexMethodCh3TransportationProblem2025年1月5日Page3of313.3.1初始基可行解1.最小元素法最小元素法的思想是就近优先运送，即最小运价Cij对应的变量xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。jiijbax,min§3.3运输单纯形法TransportationSimplexMethodCh3TransportationProblem2025年1月5日Page4of31【例3.3】求表3－6所示的运输问题的初始基可行解。表3－6销地产地B1B2B3产量A186730A243545A374825销量603010100§3.3运输单纯形法TransportationSimplexMethodCh3TransportationProblem2025年1月5日Page5of31销地产地B1B2B3产量A186730A243545A374825销量603010100【解】30××15×10×2520§3.3运输单纯形法TransportationSimplexMethodCh3TransportationProblem2025年1月5日Page6of31【例3.4】求表3－7给出的运输问题的初始基本可行解。B1B2B3B4aiA1311447A277384A3121069bj365620表3－7§3.3运输单纯形法TransportationSimplexMethodCh3TransportationProblem2025年1月5日Page7of31【解】B1B2B3B4aiA1311447A277384A3121069bj3656203××60×××4×16在x12、x22、x33、x34中任选一个变量作为基变量，例如选x12表3－8§3.3运输单纯形法TransportationSimplexMethodCh3TransportationProblem2025年1月5日Page8of31初始基本可行解可用下列矩阵表示634610表3－8中，标有符号的变量恰好是3+4－1=6个且不包含闭回路，是一组基变量，其余标有符号×的变量是非基变量，323123141312,,,,,xxxxxx§3.3运输单纯形法TransportationSimplexMethodCh3TransportationProblem2025年1月5日Page9of312．元素差额法（Vogel近似法）最小元素法只考虑了局部运输费用最小，对整个产销系统的总运输费用来说可能离最优值较远。有时为了节省某一处的运费，而在其它处可能运费很大。元素差额法对最小元素法进行了改进，考虑到产地到销地的最小运价和次小运价之间的差额，如果差额很大，就选最小运价先调运，否则会增加总运费。例如下面两种运输方案，2010125815510C2010125851510C15151515前一种按最小元素法求得，总运费是Z1=10×8+5×2+15×1=105，后一种方案考虑到C11与C21之间的差额是8－2=6，如果不先调运x21，到后来就有可能x11≠0，这样会使总运费增加较大，从而先调运x21，再是x22，其次是x12这时总运费Z2=10×5+15×2+5×1=85