目标函数为极大化型的运输问题的直接解法--王雨雷施泉.doc

目标函数为极大化型的运输问题的直接解法-王雨雷.施泉生 摘要 从传统的产销平衡的运输问题出发，本文提出了目标函数为极大化型的运输问题的直接解法修改的表上作业法，直接求解此类问题，减少运算量，降低应用难度，并在求解过程中明确了求解方法对应的实际问题的经济意义。AbstractBased from the traditional transportation problem with the balance of produce and sale, this paper puts forward a direct method to solve the transportation problem whose objective is to maximize the problem-the modified tabular method, so as to diminish the quantity of calculation, reduce the problems difficulty, and explain the economic meaning in the calculating process at the same time.主题词 运输问题 极大化型 修改的表上作业法Key Words Transportation Problem Maximum Revised Tabular Method引言 传统的运输问题给出了产销平衡时运输成本最小的物资调运方案。随着供应链管理理论的发展，物流已经成为企业继降低材料成本和提高劳动生产率之后的第三利润源泉，在企业运营尤其是第三方物流发展的实践中，经常要考虑如何调运产品，使收益最大，从而成为一类新的运输问题。本文基于运输问题的理论，用修改的表上作业法解决了此问题，并在实际运用中取得了较好的效果。一、模型的建立 传统的产销平衡的运输问题可以用数学语言描述为：已知有m个产地Ai，i1，2，m，可供应某种物资，其供应量（产量）分别为ai，i1，2，m，有n个销地Bj，j1，2，n，其需要量（销量）分别为bj，j1，2，n，从Ai到Bj运输单位物资的运价（单价）为cij，这些数据可汇总为表1产销平衡表和表2单位运价表，其中各产地和销地分别用对应的数字来表示：表1 产销平衡表销 地产 地1 2 n产 量12ma1a2am销 量b1 b2 bn表2 单位运价表 销 地产 地1 2 n12mc11 c12 c1nc21 c22 c2n cm1 cm2 cmn一般可将这两表合一。 若令xij表示从Ai到Bj的运量，那么使得总运费最小的调运方案的数学模型为： Min z St. bj j1，2，n （1） ai i1，2，m （2） xij 0此问题目标函数为极小化形式，并有产销平衡的等式 成立，所以模型最多只有mn1个独立约束方程。产销平衡的运输问题总是存在可行解，同时必存在最优解。求解此问题的方法为表上作业法。 与之相对应，若单位运价变为单位利润，则要求出总利润最大的调运方案，即成为目标函数为极大化型的运输问题。此时产销平衡表不变，而单位运价表变为单位利润表，cij表示从Ai到Bj运输单位物资的利润。其数学模型为： Max St. bj j1，2，n ai i1，2，m xij 0 由于运输问题同时又是线性规划问题，仿照线性规划中目标函数为极大化和极小化之间的关系，可将此问题转化为极小化型的运输问题。即令z，则求Max 就等价于求Min z，仍可用表上作业法来求解。 然而此时单位运价表中的数据成为负数，既增加了运算量，又破坏了运输问题表上作业法对应的实际问题的经济意义。为了降低应用难度，减少运算量，并在求解过程中明确该问题的经济意义，仿照表上作业法，本文提出了求解目标函数为极大化型的运输问题的直接解法，即修改的表上作业法。二、修改的表上作业法表上作业法的实质是单纯形法，其步骤为：（1） 找出初始基可行解，即在（mn）产销平衡表上给出mn1个数字格；（2） 求各非基变量的检验数ij，i，jN，即在表上计算空格的检验数，判别是否达到最优解：如已达到，则停止计算，否则转到下一步；（3） 确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法调整；（4） 重复（2）、（3）直到得出最优解为止。由此可见，表上作业法的关键在于找出初始基可行解，以及求出空格（非基变量）的检验数ij，i，jN，从而判别是否达到最优。确定初始基可行解的方法一般为最小元素法，西北角法和伏格尔（Vogel）法，求ij则用闭回路法或位势法，判别的方法是计算ij，当所有的ij 0时为最优解。仿此，修改的表上作业法实质也是单纯形法，步骤同上，关键也在于找出初始基可行解，以及求出空格（非基变量）的检验数ij，i，jN，从而判别是否达到最优。相应地，确定初始基可行解的方法一般为最大元素法，西北角法和修改的伏格尔（Vogel）法，求ij亦用闭回路法或位势法，但判别的方法是计算ij，当所有的ij 0时为最优解。1. 确定初始基可行解（一） 最大元素法：此方法的基本思想是根据最大利润来直接供应，即从单位利润表中最大的利润开始确定供销关系，然后次大，一直到给出初始基可行解为止；（二） 西北角法：同表上作业法，每次都选择单位利润表上位于西北角的空格来确定供销关系，一直到给出初始基可行解为止；（三） 修改的伏格尔法：考虑到一产地的产品假若不能按最大利润供应，就考虑次大利润，此时就有一个差额，差额越大，说明不能按最大利润调运时，利润减少越多，因而对差额最大处，就应当采用最大利润调运。反复此过程，一直到给出初始基可行解为止。 以上三种方法均给出了mn1个基变量的初始值，它们对应的系数列向量线性独立，都是运输问题的基可行解。2. 最优解的判别求空格的检验数ij的方法同表上作业法的闭回路法或位势法，当所有的ij 0时为最优解。3. 改进的方法同表上作业法的闭回路调整法。若有两个和两个以上的正检验数时，一般选其中最大的正检验数，以它对应的非基变量为换入变量。4. 修改的表上作业法计算中的问题（一） 无穷多最优解当某个非基变量（空格）的检验数为0时，该问题有无穷多最优解。（二） 退化当出现退化时，在相应的格中一定要填一个0，以表示此格为数字格。三、示例中国最大的光电元器件基地佛山市国星光电公司将采购R1、R2、R3、R4四种类型的材料元件，数量分别为15万件、20万件、30万件和35万件。有三个公司A、B、C可供应上述元件，数量分别为25万件、25万件和50万件。预计单位利润如下表所示，对此产销平衡的运输问题，请确定利润最大的采购方案。表3 单位利润表（单位：千元/万件）R1R2R3R4ABC1089523674768求解中仍沿用产地和销地的概念，分别用最大元素法、西北角法和修改的伏格尔法求解。解法一、用最大元素法求解：第一步：用最大元素法给出初始基可行解，如下表4：表4 用最大元素法给出的初始基可行解（单位：万件）R1R2R3R4产 量 A B C15 515 52535 25 25 50销 量15203035第二步：用位势法计算非基变量（空格）的检验数，如下表5，其中ui和vj为对偶变量：表5 用位势法计算的表4中非基变量（空格）的检验数R1R2R3R4ui A B C314035 0 1 2vj105610在表5中还有正检验数，说明未得最优解，需要改进；第三步：以表5中空格（31）为调入格，用闭回路调整法进行改进，找到闭回路（31）（11）（12）（32）（31），调整后可行基解如下表6：表6 以表5中空格（31）为调入格进行调整后得到的新的基可行解（单位：万件）R1R2R3R4产 量 A B C01520 52535 25 25 50销 量15203035第四步：用位势法计算非基变量（空格）的检验数，如下表7：表7 用位势法计算的表6中非基变量（空格）的检验数R1R2R3R4ui A B C341124 0 11vj10 569表7中所有空格的检验数均小于0，说明表6已为最优解。最优值为20556257159358720千元，问题得到解决；解法二、用西北角法求解： 用西北角法给出的初始基可行解如下表8：表8 用西北角法给出的初始基可行解（单位：万件）R1R2R3R4产 量 A B C151010151535 25 25 50销 量15203035以下求解过程同解法一；解法三、用修改的伏格尔法求解： 用修改的伏格尔法给出的初始基可行解如下表9：表9 用修改的伏格尔法给出的初始基可行解（单位：万件）R1R2R3R4产 量 A B C15515 52535 25 25 50销 量15203035以下求解过程同解法一。四、结论 本文基于企业运营和第三方物流发展的实际，参照传统的产销平衡的运输问题，提出了目标函数为极大化型的运输问题的直接解法修改的表上作业法，直接求解此类问题，避免了传统方法要进行转换的困难，减少运算量，降低应用难度，并在求解过程中明确了求解方法对应的实际问题的经济意义，在实际运用中取得了较好的效果。五、进一步说明 上例亦可转化为目标函数为极小化型的运输问题，用表上作业法来求解。详细的求解过程可以发现，除了单位利润表中数字符号相反，求检验数时对偶变量值和检验数的值符号相反，从而最优解判别的规则相反外，其它都类同。可见修改的表上作业法实质就是表上作业法，是表上作业法的推广应用。由于产销不平衡的运输问题均可以转化为产销平衡的运输问题来处理，所以本文不再讨论产销不平衡的运输问题的求解。 处理运输问题时，同时考虑成本最小和利润最大并结合其它限制条件来考虑，得到的解将更具有现实意义。参考文献1 运筹学教材编写组，运筹学（修订版）， 北京，清华大学出版社，1990，p79-p982 胡运权 运筹学教程 北京 清华大学出版社 1998 p70-p943 Alexander S.Belenky, Operations Research in Transportation Systems, The Netherlands, Kluwer Academic Publishers, 1998, p125-p2204 Wayne L. Winston, Operations Research-Applications and Algorithms, California, Duxbury Press, 1994, p338-p3935 陈宝林、何坚勇，运输问题的表上作业法的一个解释，清华大学学报（自然科学版），1998，第38卷 第12期，p40-p436 卢厚清、黄劳生，运输问题的研究，系统工程理论与实践，1997年，第10期，p120-p1267 臧运华，运输问题的一种图上解法，运筹与管理，2002年，第11卷 第4期，p81-p858 蒋宏峰，运输问题表上作业法的改进，长沙大学学报，2002年，第11卷 第2期， p47-p499李时椿，运输问题表上作业法的改进研究，南京航空航天大学学报，2000年，第32卷 第3期， p324-p329目标函数为极大化型的运输问题的直接解法 A Direct Algorithm for the Transportation Problem with the Maxmized Objective Function王雨雷1（Wang Yulei） 施泉生2（Shi Quansheng） （1. 复旦大学管理学院 上海 200433；2. 上海电力学院经济管理系 上海 200090）摘要 从传统的产销平衡的运输问题出发，本文提出了目标函数为极大化型的运输问题的直接解法修改的表上作业法，直接求解此类问题，减少运算量，降低应用难度，并在求解过程中明确了求解方法对应的实际问题的经济意义。AbstractBased from the traditional transportation problem with the balance of produce and sale, this paper puts forward a direct method to solve the transportation problem whose objective is to maximize the problem-th