多商品配送问题的数学模型及快速算法.doc

多商品配送问题的数学模型及快速算法

摘要:
多商品的配送问题日益成为现实社会的热点。本文描述了商品价格，需求以及销售网络已定的前提下，一个多货栈多商品多客户的供货商如何制定商品配送计划，以实现供应成本的最小化。在考虑了运输成本与时间的关系以及提前/推迟供货带来的惩罚之后，以实现运输成本与惩罚之和最小为目标，进行了系统建模。首先建立了原始模型，分析模型结构后，讨论了几种可行的算法。然后在运输时间小于一个订货时段，惩罚与误期的时段成正比的假定下，将模型转化为可求解的线性规划模型，并由最简单的情况开始逐级深化讨论模型。对各个简化模型，给出相应的具体算例，用lingo进行求解，结果分析表明了模型的正确性和有效性。当深化为多货栈多商品多零售商模型时，通过深入分析模型，提出一种快速算法，并由lingo编程实现，极大地减少了线性规划的变量个数（由O（）减少为O（）），降低了线性规划的复杂度。通过两种算法对带有个变量的大规模销售网络的计算比较，验证了快速算法的优越性。最后根据一种更符合实际情况的假设，进一步优化，建立了更加有效，更加节省成本的供销模型。
关键词：多商品配送 提前/推迟供货惩罚 运输成本 二次规划 线性规划 快速算法 优化模型

一、问题的重述：
考虑供货商的多种商品配送问题．假设该供货商在某地区有多个仓储的货栈，它们位于该地区的不同地点．供货商的目标是按照不同零售商的需求将商品及时发送给零售商，使总成本尽可能小．这里的总成本主要由以下几部分组成．（1）运输成本，它与运输的时间和运输的商品相关．（2）由于货栈可以以不同价格将同一种商品供给不同的零售商，且同一种商品在不同货栈的售价也可以不同，这样零售商会按照价格优先的原则选择发货的货栈．另一方面，每一时段每个商品在货栈中的存储量有一个上限．当一个货栈被指派为一个特定的零售商提供规定数量的商品的时候，可能会出现零售商的需求和货栈储量不平衡的情况．当某时段容量不足的时候，货栈通过提前或推迟供货给零售商的方式来补偿需求．如果提前供应，将会导致零售商的商品持有成本上升, 因此零售商会向供货商索要赔偿；若推迟, 则会降低货栈的信誉，且零售商也会向供货商索要赔偿．所以，提前和推迟所带来的赔偿都是供应成本的一部分，而赔偿费用与商品的价格和提前、推迟的时间有关．
现假设在一个周期（例如一年）开始时，每个零售商对所有商品在不同时间(时段)的需求已知，以及商品的价格已知，问题是供货商如何安排不同时间(时段)的供货，使得一个周期的总成本尽可能小．
1．对此问题，并针对你所理解的实际中的多商品配送问题，建立数学模型, 讨论求解算法的设计．
2．分析当运输成本和运输的时间是什么关系, 提前、推迟惩罚与商品的价格以及提前、推迟的时间是什么关系时，或在其他你认为合理的假设下，该问题可以有快速算法求解．这里，你对这些关系的假设应与实际背景较吻合．
3．举一个和几个实际算例来说明你的算法或模型．

二、问题的分析
考虑某地区的一个供货商，有J个货栈，分布在该地区的不同地方。该供货商可提供K种商品，每一个货栈可拥有全部的商品也可以是其中的一部分，每一个货栈又给多个零售商供货。假设供货商给I个零售商供货。在一个周期T（例如一年，并分为T个时段）开始时，每个零售商对所有商品在不同时段的需求已知，每种商品的价格已知，且这一价格在一个周期内保持不变。零售商选择价格最低的一个货栈给它供货（如果存在多个最低价格时，由零售商任意选择其中的一个），因此一个周期内货栈与零售商间的销售网络已经确定。我们认为根据所给价格既定的销售网络是健康的，不存在极度不平衡的供需关系。
该问题考虑的供应成本由两部分组成：运输成本和由于提前或延误供货造成的赔偿：
（1）、运输成本。该供货商在不同的地方设有多个货栈，而该地区的零售商也位于不同的地方，因此存在运输问题，即运输时间、运输费用。设运输成本为G，它与运输时间，运输商品的种类k及运输量有关。
（2）、由于提前或延误供货造成的赔偿，，称为惩罚函数，表示x单位价格的商品提前或延误时段对零售商的赔偿。当＝0或x＝0时，F＝0；当<0时，表示提前供货；当>0时表示推迟供货。

三、基本假设
1、零售商以时段为时间间隔向零售商订货，且每一时段至多订一次货。
2、 货栈以时段为时间间隔给零售商发货，且每一时段至多发一次货。
3、 当某货栈某时段容量不足时，供货商只通过由零售商按价格最低原则选定的 货栈提前或推迟供货的方式来补偿需求，而不考虑货栈之间的相互调货，或者由其它货栈给该零售商供货。
4、 供货商有充足的运输能力，运输成本只与时间与运输商品以及运输量有关， 而不考虑具体的运输细节。
5、 当配送区域比较大的时候，运输的时间可能比较长，货物经过几个时段才能送到零售商处。这时，供货商为了协调供货以达到总成本的最小，可以选择不同的方式，改变运输时间，从而改变运输成本。[1]
当配送区域比较小的时候，运输时间比较短，与一个时段相比可忽略，即当期发货当期可到。
6、 每一时段每个商品在货栈中的存储量有一个上限。供货商货源充足，且每一时段初给货栈补一次货，每次补货都可达到货栈的存储上限。不考虑补货的运输成本。
7、 不考虑商品在货栈中的存储成本。

四、变量及符号的说明
j : 表示第j个货栈
i：表示第i个零售商
k：表示第k种商品
：j货栈给i零售商提供k商品的价格
：对i零售商t时段的订货，j货栈在t’时段的发货量
：j货栈在t’时段运输k商品到i零售商的运输时间
：i零售商t时段对商品k的需求量
：j货栈存储量的上限
：单位的k商品运输时间产生的运输成本。
：惩罚函数，表示单位价格的商品提前或延误时段对零售商的赔偿。当＝0或＝0时，F＝0；当<0时，表示提前供货；当>0时表示推迟供货。

五、模型的建立
1、 目标函数的建立
根据题目要求，将模型的目标值考虑为两部分：运输成本和供货提前/延期的惩罚费用。由假设条件（4），在一个周期内，一个零售商对一种商品的需求只由一个货栈满足，不存在货栈之间的相互调整，各个货栈的供货是独立的，因此，在下面的最优化讨论中，我们只讨论一个货栈供货的最优化情况，整个供货商的最优化供货可通过J个货栈的线性叠加得到。为了不失一般性，我们考虑第j个货栈供货情况（j＝1，2，… ，J）。
（1） 、运输成本
前面已经假设第k种商品的运输成本与运输时间、商品数量的关系，很容易写出j货栈在一个周期之内所承担的所有运输成本：

（2） 、提前/推迟供货的惩罚费用
由前面假设的提前/延迟供货与惩罚费用的函数关系，且＝t’＋－t，代入惩罚函数，通过线性叠加易得j货栈在一个周期内的所有惩罚费用：

因此，一个周期内，j货栈的供应成本之和可表示为：

2、 约束条件：
（1）、货栈应当满足零售商在不同时段t的需求量，表达式如下：
t＝1，2，… ，T；i ＝1，2，…， I； k＝1，2，… ，K

其中表示i货栈t时段对k商品的需求量，为已知。
（2）、根据实际情况，j货栈所有商品的储存量之和有上限，列出表达式为：
j＝1，2，… ，J
其中为j货栈的最大存储量，为已知量。
原始模型如下：

s.t.
i ＝1，2，… ，I; k＝1，2，… ，K；
t＝1，2，… ，T;
j＝1，2，… ，J
t＝1，2，… ，T; t’＝1，2，… ，T ;
i ＝1，2，… ，I;j＝1，2，… ，J; k＝1，2，… ，K

3. 模型的初步分析及算法设计：
在上述数量决策的的数学规划模型中，已知条件为各个零售商的需求，各个货栈的容量上限以及供货价格。
在目标函数中我们假设某种商品的惩罚函数与延误时间成正比，与延误货品的数量成正比，而其运输费用与运输时间成正比，与运输的货量成正比。由于实际发货量与实际发货采用的运输时间均是待求解的未知量，从而它们的乘积将使目标函数的维数达到二维，该决策模型转化为二次规划问题。
对二次规划问题，传统的算法有直接消去法、广义消去法、有效集法等。这些算法虽然能算得问题的精确解，但其计算的复杂性随着求解规模的增大而迅速增大，所以这些算法对于大规模问题都不具有实际可行性。Mcarthy和Liu[102]认为经典的生产规划理论及其最优算法只具有学术价值，在实际应用中运用很少。为使算法更加使用，我们建议采用以下几种近似算法：
1、 规则方法： 这是一种在生产计划和调度问题研究中，运用最广泛的启发式方法。其优点在于，计算时间较少，便与生产中的实时生产与调度。
2、 仿真方法： 其主要是通过计算机模拟现实生产环境，对可能的生产计划和调度方案进行计算机上虚拟实施，比较计算结果，寻求最优方案[]。这种利用近似枚举的方法在缺乏有效的理论支持的情况下是一种最直观也最有效的方法。
3、 智能化方法： 智能化生产计划的方法主要有：遗传算法（GA）、设禁搜索（TS）、模拟退火（SA）和人工智能网络等智能化算法。这些智能算法的优点是能跳出局部最优，搜索全局最优解，但解的准确性还有待考证。
所列算法各有优缺点，具体实施中我们可以根据问题的规模及限制条件的复杂程度选择合适的算法。比如我们可以采用遗传算法（CP-GA）与模糊逻辑（CP-HA）相结合的智能混合算法（CP-FL），由于过程过于繁杂，此处不做详细说明，具体过程可参见文献[116，124，125]。
事实上，现实生活当中运输函数和成本函数有一些特殊的性质，这样便可以大大简化模型和算法。
为此，下一部分，我们将根据实际情况以及生产实践，对运输函数和惩罚函数做进一步的假设，再根据这些假设，从易到难，从单货栈单商品单零售商模型，到多货栈多商品多零售商模型，一步一步接近实际情况，给出快速的算法，并对各种模型举出具体算例，以验证模型的合理性。

六、模型的简化：
（一） 假设：
1、运输函数：。考虑商品k的运输费用为运输时间，商品数量的线性函数。假设为从j货栈到i零售商的平均运输时间，我们假设小于一个时段，即当期发货当期即可到达。它与时段和商品种类无关，只与货栈与零售商的距离有关，我们大胆地做假设，为了达到最低成本的目的，商家必定会选择一种最优的运输方式以及相应的最佳运输时间。设为单位商品k从货栈运输到零售商的单位时间的运费成本因子，则可以得到所有商品的运输费用：

在一个周期开始时，零售商的需求已知，因此已经确定，
所以一个周期内内的总运输成本也是一个定值，不能通过供货安排来改变，因此在下列简化模型中，要实现供应成本的最小化，只考虑惩罚的最小即可，
2、惩罚函数 ：
如果因为核算方式的不同而算出不同的延误赔偿额，供货商与零售商必将产生争议。为了避免在清算时发生争议，我们大胆假设惩罚函数对与延误时间应该是线性形的，以下我们给出简单的数学证明：
考虑某货栈只有一个零售商购买一种货品的情况，假设货栈上限不随时间变化。设惩罚函数可简单表示为F（x , Δt）,x为延误货量，Δt为延误时间。设货栈上限为C。
现只考虑推迟的情况。设某期的定单为货栈上限的两倍，则当期只能发出定单一半的货量，然后设之后连续N期的定单都为货栈的上限，第N+1期无定单，则拖欠的货物只能在第N+1期发出，可认为应赔F（ C ，N ）。但也可以认为是当期拖欠的货物在第一期发出，而第一期的货物在第二期发出，以次类推，直到第N期的货物在第N+1期发出从而补完拖欠。在这种情况下，其赔偿额为N*F（ C ，1 ）。
如果F（ C ，N ）≠ N*F（ C ，1 ）则零售商会要求按照二者中赔偿额高的那项索取赔偿，而供货商则会认为其调整方式是按二者中赔偿额低的那项实施的，从而双方产生争议。为使不产生争议，必须使
F（ C ，N ）= N*F（ C ，1 ）
提前的情况可同样证明。
所以惩罚函数是延误时间的线性函数，证毕。
从现有的有关生产计划与调度问题文献[6]来看，产品的交货期的描述方式有三种：精确交货期、交货期窗口和模糊交货期。通常，提前与推迟的惩罚与订单的价值成正比，且与提前、推迟时间成正比，设单位时间单位价值的提前与推迟供货的惩罚因子为，一般来说,推迟供货会引起信誉度的降低，因此假定，以使供货商在供货不足的情况下尽量采用提前供货代替推迟供货，则商品k的单位时间的提前与推迟供货惩罚因子为，（k＝1，2，… ，K）。设应交货时间为t，供货时间为t’。
精确交货期：交货时间为固定的时间点，如图4-1所示.
图4-1
精确交货期地隶属函数（用来描述客户的满意程度）可以表示为
（式6.1）

精确交货期的提前/推迟供货的惩罚函数可以描述为：

（式6.2）
交货期窗口：交货时间为一段时间，例如零售商要求在[，]这一区间内交货都可。为最早交货期，为最晚交货期。如图6-2所示。
图6-2
交货期窗口的隶属函数可以表示为：
（式6.3）
交货期窗口的提前/推迟供货的惩罚函数可以描述为：
(式6.4)

模糊交货期：交货时间为一段时间，并且反映了客户对偏离这一时间的不同主观满意程度。如图6-3所示，[，，， ]，其中，分别是商品k的最早交货期和最晚交货期，，分别是客户的最满意交货期的上限和下限，且满足<<< .
图6-3
模糊交货期的隶属函数可以表示为：
（式6.5）

模糊交货期的提前/推迟供货惩罚函数为：
（式6.6）

在我们的模型当中，交货的时间是离散的，因此精确交货期和交货期窗口的描述是等价的，为了简化起见，我们不考虑客户对误期长短的主观满意程度，即要么满意要么不满意。我们采用函数关系式（6.2）,其中t，t’都表示时段，为离散的量。
图6-4

3、线性规划 因为货品的单位都必须是整数，所以这道题应该用整数规划来求解。然而，考虑到每次的发货量都是较大的整数，且别的约束条件也全部由整数组成，所以用线性规划求解时得到非整数的概率并不大，即便出现非整数，四舍五入后得到的最优值也与实际整数规划的最优解相差不多，所以我们将整数规划简化为线性规划求解。
（二）、简化模型
1．单货栈单商品单零售商模型（简化模型1）
只考虑一个货栈给一个零售商提供一种商品，由上述假设,可列出简化模型1：

s.t.
( t =1,2,…T)
( t’ = 1,2,..T )
变量说明：：对零售商t时段的订单，该货栈在t’时段的发货量。
：该商品的价格
：零售商t时段对商品的需求量。
：该商品的体积因子。
：货栈的最大储存容量
实例应用：例1：假设一个周期分为5个时段，=0.2，=0.6，=1，=7，设有如下订单：
Di
D1
D2
D3
D4
D5
Di
4
3
9
8
6

表6.1.1

代入上述模型， 由Lingo解得最优解，各时段送货量如
X（i，j）
X(1,1)
X(2,2)
X(3,3)
X(3,2)
X(4,4)
X(4,2)
X(5)
X（i，j）
4
3
7
2
7
1
6
表6.1.2
其具体运行程序见附录[1]：
结果分析：
根据实验结果，在该种情况下，供货商实行的策略应该是尽量先满足当期的供货，当某期供货不足时，在附近时段搜索货栈有无余量，并选择其中赔偿额最小的时段发货。如此循环直至补足欠货。符合实际情况。
2、 单货栈单商品多零售商模型（简化模型2）
假设有单货栈给I个零售商供单种商品，同简化模型1，运输成本不可调，由惩罚的最小化建立单货栈单商品多零售商的最优化模型：

s.t.
t＝1，2，… ，T; i ＝1，2，… ，I;

t＝1，2，… ，T; t’＝1，2，… ，T ; i ＝1，2，… ，I;
变量说明：：对i零售商t时段的订单，该货栈在t’时段的发货量。
：第i个零售商的进价
：i零售商t时段对该商品的需求量
：货栈的最大存储容量
实例应用：例2：假设一个周期分为5个时段，有3个零售商，=0.2，=0.6，＝1.5, =1, =2，V＝21，假设有如下订单：

D1
D2
D3
D4
D5

8
5
13
6
8

3
7
9
5
8

2
11
2
4
8

表6.2.1
代入上述模型，用lingo解得最优解，如表6.2.2。。
X1(1,1)
X1(2,2)
X1(3,3)
X1(4,4)
X1(5,5)
X2(1,1)
8
5
13
6
8
3
X2(2,1)
X2(2,2)
X2(3,1)
X2(3,3)
X2(4,4)
X2(5,4)
2
5
3
6
5
3
X2(5,5)
X3(1,1)
X3(2,2)
X3(3,3)
X3(4,4)
X3(5,5)
3
2
11
2
4
8
表6.2.2
具体运行程序见附录[2]：
结果分析：
该模型除了保留简化模型1的特征之外，还对客户产生了不同的分级，购买价高的客户，级别也越高，如上例中，第5时段3个客户同时要8单位货物，但客户2的价格最低，（从而级别最低），被提前发了3单位货。这与实际情况相符。

3、 单货栈多商品多零售商模型（简化模型3）
假设该货栈提供K种商品，其余假设和条件同简化模型2，由于是单货栈供货，所以由假设，还是没有运输成本的变化，因此也只要考虑惩罚费用的最小化，由此建立单货栈多商品多零售商的最优化供货模型，即简化模型3。

s.t.
t＝1，2，… ，T;
i ＝1，2，… ，I;k＝1，2，… ，K

变量说明：：对i零售商t时段对k商品的订单，该货栈在t’时段的发货量
：该货栈给i零售商提供k商品时的价格，已知
：i零售商t时段对k商品的需求量，已知
：k商品的体积因子，已知
例3：：假设一个周期分为5个时段，该货栈有4种商品，给3个零售商供货，=0.2，=0.6， V＝21，价格如表6.3.1,＝订单如表6.3.2，6.3.3，6.3.4：
Cik
Ci1
Ci2
Ci3
Ci4
C1k
18
8
25
40
C2k
24
10
30
50
C3k
20
12
35
45
表6.3.1
Dik(t)
D1k(1)
D1k(2)
D1k(3)
D1k(4)
D1k(5)
D11(t)
0
0
0
0
0
D12(t)
15
20
25
30
20
D13(t)
0
0
0
0
0
D14(t)
6
5
4
3
8
表6.3.2
Dik(t)
D2k(1)
D2k(2)
D2k(3)
D2k(4)
D2k(5)
D21(t)
10
12
14
12
10
D22(t)
25
35
40
45
20
D23(t)
50
60
30
40
20
D24(t)
5
7
6
8
4
表6.3.3
Dik(t)
D3k(1)
D3k(2)
D3k(3)
D3k(4)
D3k(5)
D31(t)
14
12
10
10
10
D32(t)
35
40
50
25
35
D33(t)
0
0
0
0
0
D34(t)
6
5
4
3
2
表6.3.4
代入上述模型， 由Lingo解得最优解，各时段送货量如表6.3.5
X12(1,1)
X12(2,1)
X12(2,2)
X12(3,3)
X12(4,4)
X12(5,5)
X14(1,1)
X14(2,2)
15
8
12
25
30
25
6
5
X14(3,3)
X14(4,4)
X14(5,5)
X21(1,1)
X21(2,2)
X21(3,3)
X21(4,4)
X21(5,5)
4
3
8
10
12
14
12
10
X22(1,1)
X22(2,2)
X22(3,3)
X22(4,4)
X22(5,5)
X23(1,1)
X23(2,2)
X23(3,3)
25
35
40
45
20
50
60
30
X23(4,4)
X23(5,5)
X24(1,1)
X24(2,2)
X24(3,3)
X24(4,4)
X24(5,5)
X31(1,1)
40
20
5
7
6
8
4
14
X31(2,2)
X31(3,3)
X31(4,4)
X31(5,5)
X32(1,1)
X32(2,2)
X32(3,3)
X32(4,4)
12
10
10
10
35
40
50
25
X32(5,5)
X34(1,1)
X34(2,2)
X34(3,3)
X34(4,4)
X34(5,5)

35
6
5
4
3
2

表6.3.5
其具体程序见附录[3]：
结果分析：
在简化模型2的基础上，还对不同的产品产生了不同的分级，总体来看，价格越高，供货的优先级越高，其发货期越要求接近订货期。符合实际情况。

4、 多货栈多商品多零售商模型（简化模型4）
根据本文开始的问题分析，该模型退化为J个独立的简化模型3的线性组合。由此列出简化模型4：

s.t.
t＝1，2，… ，T; ;
i ＝1，2，… ，I; k＝1，2，… ，K
j＝1，2，… ，J;
变量说明： ：j货栈给i零售商提供第k种商品的价格
：对i零售商第t时段对第k种商品的订单，j零售商在第t’时段的供货
：i零售商t时段对k商品的需求
：j货栈的存储上限
这就是原始模型的线性化模型，也是我们的最终模型。

实例应用：例4：设有2个货栈，一个周期分为5个时段，货栈有5种商品，给4个零售商供货，=0.2，=0.6， V＝700 500，价格如表6.4.1,订单如表6.4.2，6.4.3，6.4.4, s6.4.5：
Cijk
Cij1
Cij2
Cij3
Cij4
Cij5
C11k
30
5
50
10
25
C12k
35
4
50
12
30
C13k
30
3
40
14
10
C14k
25
6
45
16
25
C21k
25
3
40
16
30
C22k
40
5
60
14
25
C23k
20
8
45
12
20
C24k
20
7
50
10
30
表6.4.1,
D1k(t)
D1k(1)
D1k(2)
D1k(3)
D1k(4)
D1k(5)
D11(t)
20
25
30
45
10
D12(t)
30
35
60
0
45
D13(t)
0
0
80
80
80
D14(t)
35
10
10
45
25
D15(t)
10
30
30
25
10
表6.4.2
D1k(t)
D2k(1)
D2k(2)
D2k(3)
D2k(4)
D2k(5)
D21(t)
30
45
10
0
50
D22(t)
40
75
50
50
85
D23(t)
40
30
20
30
0
D24(t)
25
25
0
35
10
D25(t)
40
10
20
5
30
表6.4.3
D1k(t)
D3k(1)
D3k(2)
D3k(3)
D3k(4)
D3k(5)
D31(t)
10
20
30
40
20
D32(t)
20
40
60
80
20
D33(t)
5
10
15
20
25
D34(t)
8
16
24
32
8
D35(t)
10
20
30
40
10
表6.4.4
D1k(t)
D4k(1)
D4k(2)
D4k(3)
D4k(4)
D4k(5)
D41(t)
25
10
35
20
5
D42(t)
80
60
10
70
40
D43(t)
0
0
0
0
0
D44(t)
0
0
40
40
40
D45(t)
40
20
10
5
40
表6.4.5
得到结果如下表：程序见附录[4]
X114(1,1)
X114(2,2)
X114(3,3)
X114(4,4)
X114(5,5)
X115(1,1)
X115(2,2)
X115(3,3)
35
10
10
45
25
10
30
30
X115(4,4)
X115(5,5)
X121(1,1)
X121(2,2)
X121(3,3)
X121(5,5)
X121(1,1)
X122(2,2)
25
10
30
45
10
50
40
75
X122(3,3)
X122(4,4)
X122(5,5)
X123(1,1)
X123(2,2)
X123(3,3)
X123(4,4)
X124(1,1)
50
50
85
40
30
20
30
25
X124(2,2)
X124(4,4)
X124(5,5)
X132(1,1)
X132(2,1)
X132(2,2)
X132(2,3)
X132(3,3)
25
35
10
20
8
28
5
60
X132(4,3)
X132(4,4)
X132(5,5)
X133(1,1)
X133(2,2)
X133(3,3)
X133(4,4)
X133(5,5)
75
5
20
5
10
15
20
25
X135(1,1)
X135(2,2)
X135(3,3)
X135(4,4)
X135(5,5)
X142(1,1)
X142(2,2)
X142(3,3)
10
20
30
40
10
80
60
10
X142(4,4)
X142(5,5)
X145(1,1)
X145(2,2)
X145(3,3)
X145(4,4)
X145(5,5)
X211(1,1)
70
40
40
20
10
5
40
20
X211(2,2)
X211(3,3)
X211(4,4)
X211(5,5)
X212(1,1)
X212(2,2)
X212(3,2)
X212(5,2)
25
30
45
10
30
35
60
5
X212(5,5)
X213(3,3)
X213(4,4)
X213(5,5)
X225(1,1)
X225(2,2)
X225(3,3)
X225(4,4)
40
80
80
80
40
10
20
5
X225(5,5)
X231(1,1)
X231(2,2)
X231(3,3)
X231(4,4)
X231(5,5)
X234(1,1)
X234(2,2)
30
10
20
30
40
10
8
16
X234(3,3)
X234(4,4)
X234(5,5)
X241(1,1)
X241(2,2)
X241(3,3)
X241(4,4)
X241(5,5)
24
32
8
25
10
35
20
5
X44(3,2)
X244(3,3)
X244(4,4)
X244(5,5)

2
38
40
40

表6.4.6;
5、.算法的优化
显而易见以上线性规划含I * J * K * T * T个变量。但考虑到每个零售商对某一具体商品都将选择唯一的货栈为其供货，则他在其他货栈对该商品的需求为零，进而可推知其他货栈对该零售商需要的这种商品的各期供应都为零。现将
按 i j k t t’递增的顺序排成一行矩阵，则此为一占空比达的稀疏矩阵。实际上，我们已知道其中有的变量为零，且可由人工目测的方式一一进行辨认，但不便于计算机求解。因此我们计划采用降维的办法将J下标消去，将变量数缩小为原来的。定义二元关系（i,k）表示i货商购买k商品所选择的货栈号，则（i,k）=j,若i商对k货无需求，则令（i,k）=0.从而我们写出一m*l矩阵，里面的第i行第k列元素表示i商对k货所选定的货栈号，从而将i,k与j对应，达到降维的目的，并且使变量和需求约束项数目都减为，大大简化运算。
在lingo上的具体实现，我们为了略掉上述的变量，增加了一部对矩阵的过滤，为此要先引入一个新的need(i,j,k)矩阵，当i商从j货栈购买k商品时，need（i，j，k）=1，否则为0。可知need（i，j，k）可由C（i，j，k）生成，再由need（i，j，k）来过滤X（i，j，k，t，t’）。具体编程请见附录[5]。

6、算法的比较，我们将两种算法在lingo上进行了比较，数据选的是10*10*10*10*10的，数据及程序见附录[6]。两个程序都给出了相同最优解，现将结果比较如下：

变量数
最优值
消耗内存值
用时（s）
常规线性规划
101000
1157.6
14104 K
0.08
优化算法
10000
1157.6
1773 K
0.01
可见，第二种显著提高了速度。

7、进一步改进设想。考虑到第1次为第t次提前供货不是很现实，我们可以简单的认为一切提前和推迟供应都应在当时段的前两个时段和后两个时段之内解决，如果这样，又将减少一半以上变量，提高运算速度，但同时，也可能会增加不可解的情况。
七、模型的评价及改进
模型的评价：
本文研究了供货商的多商品配送问题，充分考虑实际情况，不失一般性，讨论了多货栈给多零售商提供多商品的情况，建立了考虑货栈存储容量约束的供货商多商品配送的精确交货期的提前/推迟供货线性化模型CP4。该模型中有JKITT个变量，JT个约束项，是一个典型的一次线性化模型，利用lingo软件很容易求解。通过上述实例，从模型优化计算结果可以看出：各商品供应在满足存储容量上限的前提下，各货栈的存储商品都得到了充分的利用，并且合理安排了供货时间以及供货渠道，使得惩罚和运输成本之和达到最小值。由表格也可以看出各商品的供货期都尽可能地靠近要求地供货时段。
上述例子的计算结果充分表明了该模型的有效性。但是上述例子当中的J，K，I，T都比较小，计算起来非常快。但当这些量稍微大时，例如K,I,J,T>10时，变量超过100000，计算量非常庞大，但考虑到这些变量当中大部分都是0，为此，我们设计了快速算法，由程序实现。

模型的改进：
根据题意，每个零售商都根据价格最优的原则选定发货货栈。实际上我们可以认为，零售商选定的只是最低的那个价格而不是货栈。如果在具体配送的过程中，供货商愿意在商品出售价格保持不变的基础上选择从其他货栈发货，供应商自己补足差价，则收货的零售商应该没有异议，因以为这么做对零售商的利益丝毫没有影响，在惩罚因子较大的情况下甚至可以避免不必要的延误。
此时我们将各个货栈对某零售商提供某种商品所提供的价格减去其中的最低价格，从而产生差价，将这些差价加到相应的运费中去，产生虚拟运费（不低于原运费）或是折合成虚拟的运输时间（不少于原运输时间），在这种模型下各个货栈对某个零售商提供某种商品的价格均是最低价格，零售商对供货商指定的任何货栈均无异议。此时，在定单不超过当期货栈上限的情况下（即不需推迟或提前），供货商只要选择虚拟运费最低的那个货栈发货即可实现成本最低。
基于这种假设下建立的深化模型如下：

s.t.
t＝1，2，… ，T; ; i ＝1，2，… ，I;
k＝1，2，… ，K
j＝1，2，… ，J;
其中 是虚拟运输时间
采用这种可根据具体定单情况以及客户对象选派货栈供货的配送方式，比起自始至终由指派的货栈对确定的客户供货的配送方式，要更加灵活，也更节省成本。

八、参考文献
[1].张曙，分布式网络化的全球制造，中国机械工程，1998
[2].McCarthy B L and Liu J,Addressing the gap in scheduling research:a review of optimization and heuristic methods in production schedualing.International Joural Production Research 1994,32(4),903-915.
[3].D,Wang,S-C. Fang and H.L.Nuttle, Fussy rule quantification and its application in fussy due-date bargaining,Proceeding of IFSA Congress 1999
[4].Wang, Dingwei, Fang, S.C. and T.J. Hodgson,A fussy due-date bargainer for make-to-order manufacturing systems, IEEE Trans. on SMC Part-C,1999,29,566-575.
[5].