运输问题

如何以最低运输成本,将货物由来源地送至目的地。

问题建模

典型范例:各工厂应分别运送多少数量至各配销中心,才能获得最低的总运输成本?

tp-1

建立线性规划模型

lp-1

求得的最优解为

lp-solve-2

运输问题的一般LP数学模型

s.t.

上式中的两个限制条件:

  • (2-2)为供给限制条件,表示工厂i的供给量为
  • (2-3)为需求限制条件,表示配销中心j的需求量为

对于任何可以建模成以上数学模型的线性规划问题,都可以称之为运输问题。

模型假设及性质

  • 运输问题基于两个假设条件:

    • 供给等于需求:

      若不相等,则需要进行调整

  • 成本成比例性:

    运输成本=单位运输成本()x运送数量()

  • 整数解性质

    虽然运输问题是线性规划问题,但是当所有均为整数,不需要加上整数限制,该问题自动变成整数规划问题,从而得到整数解。

产销不平衡情况的处理

总供给大于总需求

加上一个虚拟目的地或虚列

总供给小于总需求

加上一个虚拟来源或虚行

限制分配

:即来源i至目的地j没有适当的路径,或来源i所供给的货物并不符合目的地j的需要。

(对min问题,M表示一个无限大的值),同时使

需求存在上限和下限(意味着总需求大或等于总供给)

需求经常分为两部分:

  • 一部分是必须满足的最低需求
  • 另一部分则是可额外多出的需求

做法:在所增加的虚列中,相应的需求下限的单位成本为M,而让额外需求的单位成本为0。

举例

示例1(总供给大于总需求)

未来一年第1至4季需求35、50、80、20艘游艇,公司本身产能38艘/季;可外包给两家代工厂,成本增加3万元/艘;两家代工厂的合计产能20艘/季。公司可利用存货调节旺季的需求,存货成本1.5万/季/艘。

问题分析

对于上述问题,由于总供给为(38+20)*4 = 232,总需求为35+50+80+20=185;这种特殊情况属于总供给大于总需求的情况,需要增加虚行来进行调整。

来源:

  • 公司本身第一季度的供给量->C1
  • 代工厂第一季度的供给量->T1

目的地:

  • 季度1->W1,以此类推,虚行->W5

单位运输成本:

  • C1行W1列对应的单位运输成本:表示第一季度公司生产的游艇供给给第一季度的成本为0;
  • C1行W2列对应的单位运输成本:表示第一季度公司生产的游艇供给给第二季度的成本为1.5,因为该存货存放1个季度的成本为1.5。

tp-3

示例2(需求存在上限和下限)

tp-2

图中对于W2的需求上限,可以根据上面的示例限制条件求的,当满足其他所有目的地的需求量之后,剩下的供给量即为W2的需求上限:285-65-60-0 = 160。

对应这个问题,相当于总需求大或等于总供给的情况,需要添加虚拟行来进行调整。

对于目的地的需求上限和需求下限均非0,且不想等的情况下,需要对应的目的地使用两列来表示,其中一列的需求量为需求下限,另外一列的需求量为(需求上限-需求下限)。

由于需求下限对应列的需求量可由正常的来源地供给,所以在虚拟列中它对应的单位运输成本为M(表示不需要),而另一列表示可额外多出的需求量对应的单位运输成本为0(表示不存在),该需求量有虚行对应的来源地供给。

运输问题中的解法

表上作业法(产销平衡)

表上作业法是单纯形法在求解运输问题时的一种简化方法。这一方法的计算步骤如下所示:

  1. 找出初始基可行解,即在产销平衡表上给出m+n-1个数字格

    求解方法有西北角法、最小元素法、伏格尔法

    • 西北角法(左上角法)

      每次选取的都是左上角的第一个元素,即有限安排运价表上编号最小的产地和销地之间的运输业务。该方法的特点是 选取方便,算法简单易实现。(具体方法看参考资料)

      缺点:完全没有考虑运价问题!

    • 最小元素法

      就近供应,从单价中最小运价确定供应量,逐步次小,直至得到m+n-1个数字格

      3-13

      3-14

      第1次:从表3-13中找出最小运价为1,表示先将A2的产品供应给B1,于是更新产销平衡表:

      3-15

      第2次:这时从除B1列之外的其他列中找出最小运价为2,则把A2剩下的货物供应给B3。于是更新产销平衡表:

      3-16

      不断重复以上过程,最后得到的产销平衡表如下:

      3-17

      缺点:为了节省局部的运输费用,造成其它地方的运费增加

    • 伏格尔法

      第一步:首先在表3-13中分别计算出各行、各列的最小运费和次最小运费的差额,并填入该表的最右列和最下行:

      3-18

      第二步:从行或列差额中选出最大者,选择它所在行或列中的最小元素。如上表所示,B2列是最大差额所在列,B2列中最小元素为4,因此可确定A3的产品应该优先供应B2的需要。因此产销供应表更新如下:

      3-19

      划去表3-13中的B2列,对未划去的元素重复第一、二步,直到给出初始基可行解为止。最终求的的初始基可行解为:

      3-20

  1. 求各非基变量的检验数,即在表上计算空格(非基变量)的检验数,判别是否达到最优解。如果已是最优解,则停止计算,否则转入下一步。

    求解方法有闭回路法、位势法

  2. 确定换入变量和换出变量,找出新的基可行解(即在表上用闭回路法进行调整)

  3. 重复2、3,直到求出最优解为止。

参考资料