论文部分内容阅读
摘 要：生产救灾物资生产厂家分布在全国各地。除了捐赠以外，其余的救灾物资由国家救灾指挥部统一购买。政府需要支付救灾物资的购买费用以及物资运输费用。根据发生灾害的具体情况，初步有一个总费用计划，再根据灾害的情况不断进行调整。由于政府的预算资金有限，希望以最小的费用代价，最优的完成救灾物资的订购和运输要求。
问题一：针对以最小费用最优的完成物资订购与运输问题，建立费用优化模型。根据题目中具体的限制条件，由于部分物资的使用是可以相互替代的，供应商的供应能力有限，有生产的最大值，对每个地区而言，有最低需求量和额外需求量，确立出可以解决实际自然灾害的费用优化模型。
问题二：针对供应厂家S到物资需求方D最优运输路线的解法，使用Dijkstra算法，使用MATLAB编写程序，得出满足费用最小的条件下的最优路径，得出从10个供应厂家到18个物资需求方的运输五种不同物资的最优路线，共有900个结果。针对最小费用的解法，根据第一问所建立的优化模型，带入附表中的具体数据，使用lingo编写程序，得到满足供应商和物资需求方的最优化的费用为0.9224303×1012元。
关键词：优化模型 Dijkstra算法 最短路径
一、问题重述
救灾物资生产厂家分布在全国各地。 除了生产厂家的捐赠以外，另外的物资由国家救灾指挥部统一购买，各个地区的民政部门负责本地区的物资集中和运送。需要付出物资的购买费用以及运输费用。
现在已知：产品的生产厂家有10家，用 Si，i=1，2…10表示，能够提供的物资有5种，分别是：M1，M2 ，M3 ，M4 ，M5 。需要物资供应的地区有18个，用 Dj，j=1，2…18 表示。各个厂家的生产能力，以及需求地区的需求数量已知。根据物资实际生产状况要求，部分供应物资生产量有最低要求：如果订单量低于此线，则不开工生产。由于部分物资的使用可以相互替代，对于需求地区Dj，j=1，2，3，7，12 ，如果要订购的话，M1 和M2 仅需订购一种，M3 和M5 仅需订购一种，其它需求没有特别的要求。根据各种物资的实际作用，对每个需求地区而言，有最低需求量和额外需求量。
产品的订购价格按照一定的数量实施分段定价原则。
问题一：请建立一般的数学模型，来确定生产订单以及物资运送路线，希望以最小的费用代价，完成救灾物资的订购和运输要求。
问题二：根据问题中提供的有关具体数据，求出最小费用和运输路线。
二、问题分析
（一）问题一的分析
问题一属于模型优化问题，对于解决此类问题我们一般是根据题目中的要求建立目标函数，再根据题目中的已知信息列出约束条件。
在综合考虑影响运输费用的各个因素之后，建立优化模型，寻求在满足运输费用最小的条件下，生产订单方案和物资运输路线，更好的完成政府的物资订购和运输要求。
根据题目中的信息发现此优化模型有限制条件：第一，物资实际生产状况要求，部分供应物资生产量有最低要求，如果订单量低于此线，那么那些供应商会选择不开工生产。第二，由于部分物资是相互替代品，对于需求地区Dj，j=1，2，3，7，12 ，如果要订购的话，M1 和M2 只需要订购其中一种，M3 和M5 只需要订购其中一种。第三，根据各种物资的实际作用，对每个需求地区而言，有最低需求量和额外需求量。
（二）问题二的分析
根据题目中所提供的有关供应物资生产厂家的供应量、物资需求地区的需求量以及二者之间的距离等具体数据，求出最小费用和运输路线。
针对供应厂家S到物资需求方D最优运输路线的解法，使用MATLAB编写程序，得出满足费用最小的条件下的最优路径。
因为题目给了一个无向路径图，标记出了出了各个节点间的距离权重，且无负权重。因为没给出每个节点在某坐标系下的坐标，所以不妨用邻接矩阵来表示该无向路径图。然后使用解决无负权重最优路径问题中，较为可靠的Dijkstra算法进行距离的求解。针对最小费用的解法，根据第一问所建立的优化模型，带入附表中的具体数据，使用lingo编写程序，得到满足供应商和物资需求方的最优化的费用。
三、模型假设
1、假设题目中所给的数据真实可靠；
2、运输速度只与路程有关，不考虑与其他如天气、交通情况等因素；
3、所有的货物由国家宏观统一计划，不受供求关系影响，货物价格稳定；
4、不考虑车辆行驶过程中的非正常燃油消耗；
5、物资在运输途中不会发生丢失或损耗；
四、定义与符号说明
五、模型的建立与求解
第一部分、问题一的优化模型
根据题目信息建立优化模型，以确定生产订单以及物资运送路线。希望以最小的费用代价，制定最好的完成救灾物资的订购和运输方案。
建立优化函数： （1）
其中，S（i，j，k） 表示第i种物资从第j供应商运到k地的数量；J（j，k） 表示从第j供应商到目的地k的距离；Y（i） 表示物资i的单位运价；P（i） 表示物资i的单位价格；G（I，j） 表示第j个供应商供应物资的最大值。s（I，j，k）.P（i） 表示物资i的从供应商j运到k地的总价格；J（j，k）·Y（i） ·s（i，j，k） 表示物资i的从供应商j运到k地的运价。
限制条件：
由于部分物资的使用可以相互替代，对于需求地区Dj，j=1，2，3，7，12 ，如果要订购的话，M1 和M2 仅需订购一种，M3 和 M5仅需订购一种。
一、求供应廠家S到物资需求方D的最小运输路线问题
因为题目给了一个无方向路径图，标记出了出了各个节点间的距离权重，且无负权重。因为没给出每个节点在某坐标系下的坐标，所以不妨用邻接矩阵来表示该无向图。然后使用解决无负权重最优路径问题中，较为可靠的Dijkstra算法进行距离的求解。 1.算法进行前的辅助矩阵
1.1邻接矩阵a
1.1.1邻接矩阵的定义
不妨记邻接矩阵a（i，j）为当前所找到的从起始点（si（i=1-10））到其它每个目的地端点的长度。为了程序编写方便，将供应厂家S1-S10和物资需求方D1-D18，这一共28个点一起构造矩阵SDj（j=1-28），这个矩阵就是邻接矩阵。
1.1.2邻接矩阵的各项数值
因为此题是无方向路径图，在当求最短路径，即a（i，j）时，分为三种情况：
1）当i=j时，其为0；
2）当i与j之间无法直接或者通过中间节点相连时，其为无穷大，在MATLAB中可以用自带常变量inf表示；
3）当i与j之间可以相连时其值为其所有连线方法中总权值之和最小值；
1.2距离辅助矩阵d
d是个10*28的数组，其用来储存每一次si到全部28个端点的初始路程，此时的d数组成为最短路径估计值。
2.确定28个点到某一个物资需求方的最短路径
2.1标记端点
将28个端点点分成两类：最短路程确定的端点矩阵P 和最短路径不确定的端点矩阵Q。开始时确定的端点矩阵P中只有源点一个端点。不妨用一个0-1数组保存在P中的点。若某个点在这个数组中为1，则代表其在矩阵P中；相反若某个点在数组中为0，则代表其并不在矩阵P中，而是在不确定的端点矩阵Q中。
2.2设置路径长度
设置供应商源点s到自己本身点的最短路径为0，即d[i]=0。若存在源点有能直接到达的端点i，则把初始距离d[i]设为e[s][i]。同时把所有其它供应商源点s不能直接到达的端点的最短路径为设为无穷大∞。
2.3松弛操作
在最短路径不确定的端点矩阵Q的所有端点中选择一个离供应商源点s最近的端点u（即d[u]最小）加入到集合P。并观察题目所有以点u为起点的路线。
假如存在一条从离供应商最近的点u到目的地v的路线，那么可以通过将路线uv添加到路线su的后面，来拓展一条从供应商s到目的地v的路径，这条路径的长度是d[u]+e[u][v]。如果这个值比原始的d[v]的小，即用新值d[u]+e[u][v]来替代当前值d[v]。
2.4循环运行
循环运行第3步，当最短路径不确定的端点矩阵Q为空，算法结束。最终距离辅助矩阵d数组中的值就是源点到所有端点的最短路径。
3.重复以上步骤10次，即求的s1-s10的所有结果，求得的矩阵是10行28列的。由题意只需要供应厂商s到物资需求方d的距离，所以只需取该矩阵11列到28列。
4.供应厂家S到物资需求方D的最小运输路线结果。
5.一共有5种不同的物资，从10个物资供应商运输到18个物资需求方的运输方案有900中。
二、最小费用问题
根据问题一的优化模型，希望以最小的费用代价，最好的完成救灾物资的订购和运输要求。
使用lingo编写程序，带入具体数值，求得满足条件的最小费用为0.9224303×1012元。
六、模型評价与改进
模型较好的解决了题目给出的问题。建立了优化数学模型确定生产订单以及物资运送路线，以最小的费用代价，完成救灾物资的订购和运输要求。
问题一：充分考虑题目中的具体信息，建立了使物资购买费用和运输费用最小化的优化模型。但是在现实生活中，影响实际的费用花费有很多的因素，例如物资运输过程中的损耗或丢失，由于车辆行驶中的非正常行驶导致的燃油费用的增加等等。在模型中并未考虑，却在实际生活中要综合考虑这些不可控的因素所造成的影响。
问题二：针对最短路径问题，运用Dijkstra算法，使用MATLAB编写程序得出，从供应厂商到物资需求方的的最短运输路线共有180种；在考虑五种不同的物资，最优的运输路线有900种不同的结果。运算出数量太多，没有再找到方法使结果更加简单。针对最小费用问题，是在第一问的优化模型基础上，使用lingo编写程序，代入数据，得出最优化结果下的运输费用。
参考文献：
[1]基于Dijkstra算法的大型停车场最优泊车路径规划[J]. 吴若伟，楼佩煌. 工业控制计算机. 2013（05）
[2]改进Dijkstra算法在GIS导航应用中最短路径搜索研究[J]. 董俊，黄传河. 计算机科学. 2012（10）
[3]改进的Dijkstra最短路径算法及其应用研究[J]. 王树西，吴政学. 计算机科学. 2012（05）
[4]求解震后最优路径的改进Dijkstra算法[J]. 李敬贤，厉小润. 计算机工程. 2012（06）
[5]基于改进的Dijkstra算法的动态最短路计算方法[J]. 刘建美，马寿峰，马帅奇. 系统工程理论与实践. 2011（06）
[6]复杂路网下多客户间最短路径的扇面Dijkstra算法[J]. 郑四发，曹剑东，连小珉. 清华大学学报（自然科学版）. 2009（11）
[7]基于Dijkstra距离剪枝的测地线求解算法[J]. 周竞文，程志全，金士尧. 系统仿真学报. 2009（S1）
作者简介：
吴施，男 （1997-），籍贯：四川省广安市人，民族（汉），职称（无），学历（高中）.
问题一：针对以最小费用最优的完成物资订购与运输问题，建立费用优化模型。根据题目中具体的限制条件，由于部分物资的使用是可以相互替代的，供应商的供应能力有限，有生产的最大值，对每个地区而言，有最低需求量和额外需求量，确立出可以解决实际自然灾害的费用优化模型。
问题二：针对供应厂家S到物资需求方D最优运输路线的解法，使用Dijkstra算法，使用MATLAB编写程序，得出满足费用最小的条件下的最优路径，得出从10个供应厂家到18个物资需求方的运输五种不同物资的最优路线，共有900个结果。针对最小费用的解法，根据第一问所建立的优化模型，带入附表中的具体数据，使用lingo编写程序，得到满足供应商和物资需求方的最优化的费用为0.9224303×1012元。
关键词：优化模型 Dijkstra算法 最短路径
一、问题重述
救灾物资生产厂家分布在全国各地。 除了生产厂家的捐赠以外，另外的物资由国家救灾指挥部统一购买，各个地区的民政部门负责本地区的物资集中和运送。需要付出物资的购买费用以及运输费用。
现在已知：产品的生产厂家有10家，用 Si，i=1，2…10表示，能够提供的物资有5种，分别是：M1，M2 ，M3 ，M4 ，M5 。需要物资供应的地区有18个，用 Dj，j=1，2…18 表示。各个厂家的生产能力，以及需求地区的需求数量已知。根据物资实际生产状况要求，部分供应物资生产量有最低要求：如果订单量低于此线，则不开工生产。由于部分物资的使用可以相互替代，对于需求地区Dj，j=1，2，3，7，12 ，如果要订购的话，M1 和M2 仅需订购一种，M3 和M5 仅需订购一种，其它需求没有特别的要求。根据各种物资的实际作用，对每个需求地区而言，有最低需求量和额外需求量。
产品的订购价格按照一定的数量实施分段定价原则。
问题一：请建立一般的数学模型，来确定生产订单以及物资运送路线，希望以最小的费用代价，完成救灾物资的订购和运输要求。
问题二：根据问题中提供的有关具体数据，求出最小费用和运输路线。
二、问题分析
（一）问题一的分析
问题一属于模型优化问题，对于解决此类问题我们一般是根据题目中的要求建立目标函数，再根据题目中的已知信息列出约束条件。
在综合考虑影响运输费用的各个因素之后，建立优化模型，寻求在满足运输费用最小的条件下，生产订单方案和物资运输路线，更好的完成政府的物资订购和运输要求。
根据题目中的信息发现此优化模型有限制条件：第一，物资实际生产状况要求，部分供应物资生产量有最低要求，如果订单量低于此线，那么那些供应商会选择不开工生产。第二，由于部分物资是相互替代品，对于需求地区Dj，j=1，2，3，7，12 ，如果要订购的话，M1 和M2 只需要订购其中一种，M3 和M5 只需要订购其中一种。第三，根据各种物资的实际作用，对每个需求地区而言，有最低需求量和额外需求量。
（二）问题二的分析
根据题目中所提供的有关供应物资生产厂家的供应量、物资需求地区的需求量以及二者之间的距离等具体数据，求出最小费用和运输路线。
针对供应厂家S到物资需求方D最优运输路线的解法，使用MATLAB编写程序，得出满足费用最小的条件下的最优路径。
因为题目给了一个无向路径图，标记出了出了各个节点间的距离权重，且无负权重。因为没给出每个节点在某坐标系下的坐标，所以不妨用邻接矩阵来表示该无向路径图。然后使用解决无负权重最优路径问题中，较为可靠的Dijkstra算法进行距离的求解。针对最小费用的解法，根据第一问所建立的优化模型，带入附表中的具体数据，使用lingo编写程序，得到满足供应商和物资需求方的最优化的费用。
三、模型假设
1、假设题目中所给的数据真实可靠；
2、运输速度只与路程有关，不考虑与其他如天气、交通情况等因素；
3、所有的货物由国家宏观统一计划，不受供求关系影响，货物价格稳定；
4、不考虑车辆行驶过程中的非正常燃油消耗；
5、物资在运输途中不会发生丢失或损耗；
四、定义与符号说明
五、模型的建立与求解
第一部分、问题一的优化模型
根据题目信息建立优化模型，以确定生产订单以及物资运送路线。希望以最小的费用代价，制定最好的完成救灾物资的订购和运输方案。
建立优化函数： （1）
其中，S（i，j，k） 表示第i种物资从第j供应商运到k地的数量；J（j，k） 表示从第j供应商到目的地k的距离；Y（i） 表示物资i的单位运价；P（i） 表示物资i的单位价格；G（I，j） 表示第j个供应商供应物资的最大值。s（I，j，k）.P（i） 表示物资i的从供应商j运到k地的总价格；J（j，k）·Y（i） ·s（i，j，k） 表示物资i的从供应商j运到k地的运价。
限制条件：
由于部分物资的使用可以相互替代，对于需求地区Dj，j=1，2，3，7，12 ，如果要订购的话，M1 和M2 仅需订购一种，M3 和 M5仅需订购一种。
一、求供应廠家S到物资需求方D的最小运输路线问题
因为题目给了一个无方向路径图，标记出了出了各个节点间的距离权重，且无负权重。因为没给出每个节点在某坐标系下的坐标，所以不妨用邻接矩阵来表示该无向图。然后使用解决无负权重最优路径问题中，较为可靠的Dijkstra算法进行距离的求解。 1.算法进行前的辅助矩阵
1.1邻接矩阵a
1.1.1邻接矩阵的定义
不妨记邻接矩阵a（i，j）为当前所找到的从起始点（si（i=1-10））到其它每个目的地端点的长度。为了程序编写方便，将供应厂家S1-S10和物资需求方D1-D18，这一共28个点一起构造矩阵SDj（j=1-28），这个矩阵就是邻接矩阵。
1.1.2邻接矩阵的各项数值
因为此题是无方向路径图，在当求最短路径，即a（i，j）时，分为三种情况：
1）当i=j时，其为0；
2）当i与j之间无法直接或者通过中间节点相连时，其为无穷大，在MATLAB中可以用自带常变量inf表示；
3）当i与j之间可以相连时其值为其所有连线方法中总权值之和最小值；
1.2距离辅助矩阵d
d是个10*28的数组，其用来储存每一次si到全部28个端点的初始路程，此时的d数组成为最短路径估计值。
2.确定28个点到某一个物资需求方的最短路径
2.1标记端点
将28个端点点分成两类：最短路程确定的端点矩阵P 和最短路径不确定的端点矩阵Q。开始时确定的端点矩阵P中只有源点一个端点。不妨用一个0-1数组保存在P中的点。若某个点在这个数组中为1，则代表其在矩阵P中；相反若某个点在数组中为0，则代表其并不在矩阵P中，而是在不确定的端点矩阵Q中。
2.2设置路径长度
设置供应商源点s到自己本身点的最短路径为0，即d[i]=0。若存在源点有能直接到达的端点i，则把初始距离d[i]设为e[s][i]。同时把所有其它供应商源点s不能直接到达的端点的最短路径为设为无穷大∞。
2.3松弛操作
在最短路径不确定的端点矩阵Q的所有端点中选择一个离供应商源点s最近的端点u（即d[u]最小）加入到集合P。并观察题目所有以点u为起点的路线。
假如存在一条从离供应商最近的点u到目的地v的路线，那么可以通过将路线uv添加到路线su的后面，来拓展一条从供应商s到目的地v的路径，这条路径的长度是d[u]+e[u][v]。如果这个值比原始的d[v]的小，即用新值d[u]+e[u][v]来替代当前值d[v]。
2.4循环运行
循环运行第3步，当最短路径不确定的端点矩阵Q为空，算法结束。最终距离辅助矩阵d数组中的值就是源点到所有端点的最短路径。
3.重复以上步骤10次，即求的s1-s10的所有结果，求得的矩阵是10行28列的。由题意只需要供应厂商s到物资需求方d的距离，所以只需取该矩阵11列到28列。
4.供应厂家S到物资需求方D的最小运输路线结果。
5.一共有5种不同的物资，从10个物资供应商运输到18个物资需求方的运输方案有900中。
二、最小费用问题
根据问题一的优化模型，希望以最小的费用代价，最好的完成救灾物资的订购和运输要求。
使用lingo编写程序，带入具体数值，求得满足条件的最小费用为0.9224303×1012元。
六、模型評价与改进
模型较好的解决了题目给出的问题。建立了优化数学模型确定生产订单以及物资运送路线，以最小的费用代价，完成救灾物资的订购和运输要求。
问题一：充分考虑题目中的具体信息，建立了使物资购买费用和运输费用最小化的优化模型。但是在现实生活中，影响实际的费用花费有很多的因素，例如物资运输过程中的损耗或丢失，由于车辆行驶中的非正常行驶导致的燃油费用的增加等等。在模型中并未考虑，却在实际生活中要综合考虑这些不可控的因素所造成的影响。
问题二：针对最短路径问题，运用Dijkstra算法，使用MATLAB编写程序得出，从供应厂商到物资需求方的的最短运输路线共有180种；在考虑五种不同的物资，最优的运输路线有900种不同的结果。运算出数量太多，没有再找到方法使结果更加简单。针对最小费用问题，是在第一问的优化模型基础上，使用lingo编写程序，代入数据，得出最优化结果下的运输费用。
参考文献：
[1]基于Dijkstra算法的大型停车场最优泊车路径规划[J]. 吴若伟，楼佩煌. 工业控制计算机. 2013（05）
[2]改进Dijkstra算法在GIS导航应用中最短路径搜索研究[J]. 董俊，黄传河. 计算机科学. 2012（10）
[3]改进的Dijkstra最短路径算法及其应用研究[J]. 王树西，吴政学. 计算机科学. 2012（05）
[4]求解震后最优路径的改进Dijkstra算法[J]. 李敬贤，厉小润. 计算机工程. 2012（06）
[5]基于改进的Dijkstra算法的动态最短路计算方法[J]. 刘建美，马寿峰，马帅奇. 系统工程理论与实践. 2011（06）
[6]复杂路网下多客户间最短路径的扇面Dijkstra算法[J]. 郑四发，曹剑东，连小珉. 清华大学学报（自然科学版）. 2009（11）
[7]基于Dijkstra距离剪枝的测地线求解算法[J]. 周竞文，程志全，金士尧. 系统仿真学报. 2009（S1）
作者简介：
吴施，男 （1997-），籍贯：四川省广安市人，民族（汉），职称（无），学历（高中）.