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

目标函数为极大化型的运输问题的直接解法--王雨雷.施泉生 ??? 摘要 ??? 从传统的产销平衡的运输问题出发，本文提出了目标函数为极大化型的运输问题的直接解法――修改的表上作业法，直接求解此类问题，减少运算量，降低应用难度，并在求解过程中明确了求解方法对应的实际问题的经济意义。 [Abstract] Based 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 problem’s difficulty, and explain the economic meaning in the calculating process at the same time. ? 主题词????? ?运输问题? ?极大化型? ?修改的表上作业法 Key Words ???Transportation Problem?? ?Maximum?? ?Revised Tabular Method ? 引言 ??? 传统的运输问题给出了产销平衡时运输成本最小的物资调运方案。随着供应链管理理论的发展，物流已经成为企业继降低材料成本和提高劳动生产率之后的第三利润源泉，在企业运营尤其是第三方物流发展的实践中，经常要考虑如何调运产品，使收益最大，从而成为一类新的运输问题。本文基于运输问题的理论，用修改的表上作业法解决了此问题，并在实际运用中取得了较好的效果。 一、模型的建立 ???? 传统的产销平衡的运输问题可以用数学语言描述为：已知有m个产地Ai，i＝1，2，…，m，可供应某种物资，其供应量（产量）分别为ai，i＝1，2，…，m，有n个销地Bj，j＝1，2，…，n，其需要量（销量）分别为bj，j＝1，2，…，n，从Ai到Bj运输单位物资的运价（单价）为cij，这些数据可汇总为表1－产销平衡表和表2－单位运价表，其中各产地和销地分别用对应的数字来表示： 表1 产销平衡表 ??销 地 产 地 1 ??2 ??… ??n 产 量 1 2 m ? a1 a2 am 销? 量 b1? ?b2? … ?bn ? 表2 单位运价表 ????? 销 地 产 地 1 ??2 ??… ??n 1 2 m c11?? c12? …?? c1n c21?? c22? …?? c2n cm1?? cm2? …? cmn 一般可将这两表合一。 ???? 若令xij表示从Ai到Bj的运量，那么使得总运费最小的调运方案的数学模型为： ??????? Min z ＝ ??? St.? ?＝ bj??? j＝1，2，…，n???????????????????????? （1） ??????? ?＝ ai??? i＝1，2，…，m???????????????????????? （2） ????????????? xij ≥ 0 此问题目标函数为极小化形式，并有产销平衡的等式 ＝ 成立，所以模型最多只有m＋n－1个独立约束方程。产销平衡的运输问题总是存在可行解，同时必存在最优解。 求解此问题的方法为表上作业法。 ??? 与之相对应，若单位运价变为单位利润，则要求出总利润最大的调运方案，即成为目标函数为极大化型的运输问题。此时产销平衡表不变，而单位运价表变为单位利润表，cij表示从Ai到Bj运输单位物资的利润。其数学模型为： ??????? Max ω ＝ ??? St.? ?＝ bj??? j＝1，2，…，n???????????????????????? ??????? ?＝ ai??? i＝1，2，…，m???????????????????????? ????????????? xij ≥ 0 ?????? 由于运输问题同时又是线性规划问题，仿照线性规划中目标函数为极大化和极小化之间的关系，可将此问题转化为极小化型的运输问题。即令z＝－ω，则求Max ω就等价于求Min z，仍可用表上作业法来求解。 ????? 然而此时单位运价表中的数据成为负数，既增加了运算量，又破坏了运输问题表上作业法对应的实际问题的经济意义。为了降低应用难度，减少运算量，并在求解过程中明确该问题的经济意义，仿照表上作业法，本文提出了求解目标函数为极大化型的运输问题的直接解法，即修改