运输问题_表上作业法VIP免费

4.2表上作业法表上作业法表上作业法与单纯形法的关系表上作业法的基本步骤确定初始基可行解最小元素法的基本步骤伏格尔法三、运输问题的求解三、运输问题的求解运输问题的求解采用表上作业法，即用列表的方法求解线性规划问题中的运输模型的计算方法，实质上是单纯形法。表上作业法是一种特定形式的单纯形法，它与单纯形法有着完全相同的解题步骤，所不同的只是完成各步采用的具体形式。1.表上作业法2.表上作业法与单纯形法的关系表上作业法中的最小元素法和伏格尔法实质上是在求单纯形表中的初始基可行解；表上作业法中的“位势法”实质上是在求单纯形表中的检验数；调运方案表中数字格的数实质上就是单纯形法中基变量的值；调运方案表上的“闭回路法”实质上是在做单纯形表上的换基迭代。（1）找出初始基可行解：m+n-1个数字格（基变量）；（2）求各非基变量（空格）的检验数。,那么选取xij为入基变量；（3）确定入基变量，若min{|0}ijijlk3.表上作业法的基本步骤（4）确定出基变量，找出入基变量的闭合回路；（5）在表上用闭合回路法调整运输方案；（6）重复2、3、4、5步骤，直到得到最优解。4、确定初始基可行解与一般的线性规划不同，产销平衡的运输问题一定具有可行解（同时也一定存在最优解）。最小元素法（theleastcostrule）和伏格尔法（Vogel’sapproximationmethod）。最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止.最小元素法找出最小运价，确定供求关系，最大量的供应；划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；在剩余的运价表中重复1、2两步，直到得到初始基可行解。5、最小元素法的基本步骤最小元素法最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止。表4-1甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656最小元素法的应用（以引例4-1为例）第一步：从表第一步：从表4-14-1中找出最小运价“中找出最小运价“1”1”，最，最小运价所确定的供应关系为（小运价所确定的供应关系为（BB，甲），在（，甲），在（BB，，甲）的交叉格处填上“甲）的交叉格处填上“3”3”，形成表，形成表4-24-2；将运；将运价表的甲列运价划去得表价表的甲列运价划去得表4-3.4-3.甲乙丙丁产量（ai）A7B4C9销量（bj）3656甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656表4-2表4-33第二步：在表第二步：在表4-34-3的未被划掉的元素中再找出最小的未被划掉的元素中再找出最小运价“运价“2”2”，最小运价所确定的供应关系为（，最小运价所确定的供应关系为（BB，，丙），即将丙），即将BB余下的余下的11个单位产品供应给丙，表个单位产品供应给丙，表4-4-22转换成表转换成表4-44-4。划去。划去BB行的运价，划去行的运价，划去BB行表明行表明BB所生产的产品已全部运出，表所生产的产品已全部运出，表4-34-3转换成表转换成表4-54-5。。甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656表4-3甲乙丙丁产量（ai）A7B4C9销量（bj）3656甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656表4-4表4-531甲乙丙丁产量（ai）A3113107B19284C741059销量（bj）3656表4-5第三步：在表4-5中再找出最小运价“3”，这样一步步地进行下去，直到单位运价表上的所有元素均被划去为止。表4-7甲乙丙丁产量（ai）A7B4C9销量（bj）3656表4-6甲乙丙丁产量（ai）A311107B1984C7109销量（bj）36563213446533最后在产销平衡表上得到一个调运方案，见表4-6。这一方案的总运费为86个单位。最小元素法各步在运价表中划掉的行或列是需求得到满足的列或产品被调空的行。一般情况下，每填入一个数相应地划掉一行或一列，这样最终将得到一个具有m+n-1个数字格（基变量）的初始基可行解。在供需关系格（在供需关系格（ii，，jj）处填入一数字，刚）处填入一数字，刚好使第好使第ii个产地的产品调空，同时也使第个产地的产品调空，同时也使第jj个销个销...