具有上下界主约束条件的运输问题的标准化方法

卢跃奇

(洛阳师范学院 数学科学学院,河南 洛阳 471934)

0 引言

针对产销平衡的标准形式的运输问题,可以使用表上作业法求最优解[1]。对于总产量大于总销量或总销量大于总产量形式的产销不平衡的运输问题,其主约束条件都是“≤”或“=”形式,其中对于主约束条件有上界约束的情况,可以通过添加松弛变量转换为产销平衡的运输问题,即对于总产量大于总销量的运输问题,可以添加一个虚拟的销地,设置每个产地到虚拟销地的单位运价为零,设置虚拟销地的销量为总产量与原总销量的差;对于总销量大于总产量的运输问题,可以添加一个虚拟的产地,设置虚拟产地到每个销地的单位运价为零,设置虚拟产地的产量为总销量与原总产量的差。对于其他形式的运输问题,诸多学者也进行了一系列深入的研究[2-7]。

对于主约束条件既有上界约束又有下界约束的运输问题,如何等价地转化为产销平衡的标准形式的运输问题呢?针对这类形式的运输问题,也有比较通用的处理方法。下面以销量约束有上下界要求的运输问题为例来说明。

1 销量约束有上下界要求的运输问题模型的一般形式

设第i个产地到第j个销地的单位运价为cij,运量为xij,第i个产地的产量为si,第j个销地的最低需求为aj、最高需求为bj,其中i=1,2,…,m,j=1,2,…,n,则在附加条件

下的运输问题的数学模型的一般形式为

2 销量约束有上下界要求的运输问题模型的标准化方法

注意到上述销量约束有上下界要求的运输问题模型的附加条件中,总产量既高于最低总需求,又低于最高总需求,即每个销地的需求中,最低需求部分必须满足,而介于最低需求和最高需求之间的需求可以全部满足,也可以部分满足。因此,可以把每个销地的需求量分为两部分:刚性需求,即最低需求;弹性需求,即最高需求与最低需求之差。

令xij=x′ij+x″ij,其中x′ij表示从第i个产地运往第j个销地的运量中,满足第j个销地需求量中的刚性需求部分,x″ij表示从第i个产地运往第j个销地的运量中,满足第j个销地需求量中的弹性需求部分,从而把原运输问题等价地转化为总销量大于总产量形式的运输问题

其中,只需在弹性需求约束

左侧添加非负松弛变量x″m+1,j化为等式

同时,在约束条件中添加

即可化为产销平衡的运输问题。

3 应用举例

例1已知从各产地到各销地的单位运价(元/kg)、各产地的产量、各销地的需求量,如表1。在各产地产量都运走的条件下,求总运费最小的运输方案。其中,“—”表示B4的需求量不能从A3运过来。

表1 产销量与单位运价

解注意到总产量有限,合计只有160 kg,故B4的最高需求量实质上不可能不受限制。考虑到只有当给其他每个销地运送最少的量时,B4才会得到最大可能的量,故B4的最高需求量为

160-(30+70+0)=60 kg。

为了使得B4的需求量不能从A3运过来,即x34=0,考虑到运输问题的目标函数求最小值,只需令相应的单位运价c34=M(一个足够大的正常数)即可。从而,原问题可转化为销量约束有上下界要求的运输问题。

根据上一节的分析,可把销量约束有上下界要求的运输问题转化为总销量大于总产量形式的运输问题,见表2,其中,销地B11、B2、B41为刚性需求,对应产量约束为等式约束,其他销地为弹性需求,对应销量约束为≤形式的不等式约束如表2所示。

表2 包含刚性需求和弹性需求的单位运价

为了使表2中总销量大于总产量形式的运输问题转化为产销平衡的运输问题,须增加一个虚拟的产地A4,其产量为(30+20+70+30+10+50)-(50+60+50)=50 kg。同时,考虑到每个销地的刚性需求部分B11、B2、B41不能由虚拟产地运过来,即从虚拟产地运到刚性需求的运量必须为零。为了做到这一点,考虑到目标函数求最小值,只需令相应的运价为M即可;而每个销地的弹性需求,若是从虚拟产地运过来的,因为实际上没有发生对应的运费,故相应的运价应取零,若是从实际产地运来的,则运价取原来相应运价。从而转化为表3所示产销平衡的运输问题。

表3 产销平衡的单位运价

利用表上作业法,求得上述运输问题的最优解(表4),其中空格对应的运量为零。

表4 最优解

可以看出,在最优调运方案中:B1满足了最高需求50 kg,都从A3运来;B2的需求70 kg也得到满足,其中从A1运过来50 kg,从A2运过来20 kg;B3表面上满足了最高需求30 kg,但都是从虚拟产地A4运来的,实际上没有得到任何满足;B4满足了最低需求10 kg,是从A2运过来的,还满足了部分弹性需求30 kg,也是从A2运过来的,而还有部分弹性需求20 kg,是从虚拟产地A4运过来的,这部分弹性需求实际上没得到满足,即B4实际上总共只得到了40 kg的需求。

4 总结

对于具有上下界主约束条件的运输问题,只需把需求量分为弹性需求和刚性需求、产量分为刚性产量和弹性产量,增加适当的虚拟销地或虚拟产地;对于不能从虚拟产地运过来的刚性需求量,不能把刚性产量运到虚拟销地的产量,只需令相应的单位运价取M;对于能从虚拟产地运过来的弹性需求量、能把弹性产量运到虚拟销地的产量,只需令相应的单位运价取零,就可以转化为标准形式的产销平衡运输问题,从而可以利用表上作业法等经典方法快速求出最优解。