依据模型很容易求得：k=5
所以根据我们所设计的算法很快找到一组合理的运输路线是： 车号 行车路线 一号车 V1?V5?V7?V6?V3?V4?V1 二号车 V1?V5?V8?V9?V10?V2?V1 （2）模型优化 由上知，两辆车都经过了客户5，根据算法二号车必经过客户5，因此将一号车进行优化可得如下所示； 车号 行车路线 线路的长该车负责的客度 户 一号车 140公里 3,4,6,7 V1?V7?V6?V3?V4?V1 二号车 V1?V5?V8?V9?V10?V2?V1 155公里 2,5,8,9,10 两辆车全程总和为295公里。 5.3.2模型建立与求解
用两辆容容量相等的货车为这10个客户分配货物，要求使行驶的路线尽量最短，因此本文运用问题二所求得的最短行驶路线，进行假设分析；同样本文建立线性规划模型对运输方案进一步优化，并且将问题简化为单目标，首先确定第一辆车的最优行驶路线，再将模型进行简化定义和说明；
1．Dj为每个客户的需货量,它是在向量?8,13,6,9,7,15,10,5,12,9?的每j个分量,据上分析知:36???Xij?Dj?50(不考虑客户1的需求量,因为它在提货点)。
i?1j?110102．由于这里是分两条路线分别给10个客户送货,就没有必要设计每条路线都能够访问每个客户点,但要保证送货员能回提货点,且均从提货点出发回到提货点，则送货员进入一个客户同时也必须出来。故我们用以下条件来分别保证我们的假设：
?Xi?110ij?1?j?1,2,?,10? ?Xij?1?i?1,2,?,10?
j?110i?210?Xj?2101,j?1与?Xi,1?1 ?X??Xijj?1j?11010ij?0
到此我们得到了一个模型，它是一个指派问题的整数规划模型。其目标是使式子：
??Ci?1j?11010ij?Xij
在约束条件下取得最小值。
其余变量的假设与问题二的假设一致。
故可建立模型（3）如下：
目标函数:minZ???Ci?1j?11010ij?Xij?10??Xij?1?i?1,2,?,10?j?1?10?Xij?1?j?1,2,?,10???i?1?X?0或1?0,1变量?ij??Xij?N?整型变量??u?u?n?Xi?n?1jj?i??2?i?j?n??条件:?ui?0i?1,2,?,101010??36???Xij?Dj?50i?1j?1?1010?Xij??Xij?0??j?1j?1?1010?Xij?K???i?1j?1?1010 ?X?1,X?1?1,j?i,1?i?2?j?2在36?Dj?50约束下，参加附录[3]的代码，在lingo中求解可得以下结果： K的值 <=5 6 >=7 以上可视为确定首先确定的第一辆车的行车方案；则这两条路线所对的第二辆车最优路线的选择，（以长度为95公里的路线为例）只需将模型（3）中的条件：
满足条件的较短路径（1-1） V1?V5?V7?V8?V9?V1 V1?V4?V8?V9?V10?V5?V1 路径长度（单位：公里） 95 135 …… 不存在符合条件的路径 ?X??Xijj?1j?11010ij?0与??Xij?K改为条件Xij?1i?1j?11010?j?2,3,4,6,10且j?i?
即要保证第二辆访问到所有第一辆车未访问过的客户，允许其访问第一辆车访问过的客户，故模型基本上不用改动。同样参照参加附录[3]的代码，可求得上述路线对应的另一条路线为： K的值 满足条件的较短路径（2-1） 路径长度 （单位：公里）
<=5 6 >=7 V1?V5?V2?V3?V4?V6?V9?V10?V1 V1?V5?V2?V3?V6?V7?V1 205 155 …… 不存在符合条件的路径 此时我们可以为公司提供一种更好的二号运输方案： 车号 行车路线 线路的长度 该车负责的客户 一号车 135公里 4，5，8，9，10 V1?V4?V8?V9?V10?V5?V1 二号车 V1?V5?V2?V3?V6?V7?V1 155公里 2，3，6，7 两辆车全程总和为290公里。 5.3.3模型检验
从以上产生的结果中很容易，往往第一辆车通过的线路，有些第二辆车也要经过，并不能保证两条线路完全独立，显然这样话，我们可以确定第一辆车的线路的时候让其线路上的货物承受量大一点，两车都经过的让第二辆车去送货，这样模型（3）很可能就存在缺陷了，这是由于对条件：36???Xij?Dj?50的上界进行约束引起的，因此
i?1j?11010们可以这个条件的上界放大，给模型有更大的自由选择空间，可将它改为：
36???Xij?Dj?86
i?1j?11010，再用上述方法可以求解，但此最后形成运输方案的时候应该多考虑另一个因素，即哪些客户的货物由走哪条线路的货车负责运送，同样地可以得到以下的运输方案： K的值 满足条件的较短路径（1-2） 路径长度 （单位：公里） <=5 95 V1?V5?V7?V8?V9?V1 6 7 8 9 V1?V5?V2?V3?V8?V9?V1 V1?V5?V2?V3?V4?V8?V9?V1 V1?V7?V5?V2?V3?V4?V8?V9?V1 V1?V7?V5?V2?V3?V4?V8?V9?V10?V1 125 135 150 185 10 不存在符合条件的路径 …… 而计算第二辆车的路径，与模型（3）的计算方法完全一样，其结果如下： K的值 满足条件的较短路径（2-2） 路径长度
<=5 6 7 8 9 V1?V5?V2?V3?V4?V6?V9?V10?V1 V1?V7?V6?V4?V8?V9?V10?V1 V1?V7?V6?V9?V10?V1 V1?V7?V6?V9?V10?V1 V1?V7?V6?V9?V1 （单位：公里） 205 170 145 145 110 10 不存在符合条件的路径 …… 根据两个表中的路径，进行对比很容易得出一个最优的三号运输方案那就是：
车号 行车路线 线路的长度 该车负责的客户 一号车 135公里 2，3，4，5，8 V1?V5?V2?V3?V4?V8?V9?V1 二号车 V1?V7?V6?V9?V10?V1 145公里 6，7，9，10 两辆车全程总和为280公里。
5.4问题四的模型建立与求解
5.4.1模型的假设
由于出车费100一辆,相当于100公里的行程费用,当行程超200公里时是否以多出车来换取小行程呢?我们认为没必要:其一从题中给出的数据阵可以看出行程超过200公里该车至少经过4个客户点,其总货物需求量超过小车的容量,是不可取的;其二即使可行,但要保证加车后,两辆车总行程要控制在100公里以内也不是一件容易的事。从此两个原因可以看出我们不必考虑加车的方案，即根据客户总需求量与货车的容量可决定只派4辆车为客户送货即可。
（1）假设派四辆车运送货物；
分析，首先将10个地点分成4条路线去完成，即每条线路行驶的路程最短，货物量不得超过25 各单位，每辆车的出车费为100元，每公里的路程为1元，（不考虑空车返回时的费用），计算费用最优； 5.4.2模型建立
由问题可知，十个客户总的货物需求量为94个单位，每辆货车最多承载25个单位，假设每辆货车只是送一趟货，而且尽量使每辆车在运输过程中经过的站
4点不重复，那么至少需要的货车数为[94/25]?（辆）。因此本文首先以四辆车进
行送货尝试，除去固定的出车费用外要求总的运输成本最小，则该问题可以转化为寻求每辆车所行驶的最短路径问题。
设Li(i?1,2,3,4)为每辆车行驶的路线，每条路线经过的站点
Li?[PjQjWjRj](j?1,,,10)且有[PjQjWjRj]?[Zj]其中Z（为所jj=1,,,10）有的客户站点，aij为第i条路线前一个站点到第j站点距离，bi为每条路线的最短距离。
MinC?400?Li(u)
s.t?U(k)?25,k?1,2,3,4?4 ?minL(?)?b?ii?i?1?引入0—1变量，建立bi的最优化模型：
?10??Pjaij(j?1,,,10)?j?1?10??Qjaij(j?1,,,10)?j?1?10? bi(i?1,2,3,4)???Wjaij(j?1,,,10)?j?1?10??Rjaij(j?1,,,10)?j?1?0表示在第i条路线上不经过该j点?P,Q,W,R???jjjj?表示在第i条路线上经过该j点?1?根据Lingo软件可以得出运输公司所派出的4辆车所走的路线及每
路线总长度 40 80 55 70 货物需求量 20 20 25 21 条线上的货物总需求量如下表： 车号 行车路线 一号车 二号车 三号车 四号车 V1?V5?V2 V1?V4?V3?V8 V1?V7?V6 V1?V9?V10 显然每条发车路线上的货物总需求量均不会超过货车的容量25，故方案可行；则公司运货的总费用：