运筹学中运输问题求解算法
在线性规划问题中，运输问题属于线性规划问题，但它不同于一般的线性规划问题，有其本身所特有的性质，这也使得它在运筹学领域中有着不可或缺的地位。在标准运输问题[1]的求解里，唯一的约束条件只有在物资生产地和物资销售地之间因运输而产生的费用，要使得总运费最小，对于其他因素如产地的物资运输最大能力、物资的运输效率等不加以考虑。在标准运输问题的基础上，会更多地联系实际，提出更多的限制条件。本文将首先讨论标准运输问题的基本模型，简单总结标准运输问题的求解算法，然后就运输问题进行更适用于现实情况的扩展，主要会对带运输容量限制和时间约束的运输问题进行研究。
目录
摘要1
关键词1
Abstract1
Key words1
引言1
1 运输问题模型与算法2
1.1 运输问题的数学模型 2
1.2 运输问题求解 2
1.2.1 初始基本可行解的确定2
1.2.2 基本可行解的最优性检验2
1.2.3 方案的调整3
2 带时间约束的运输问题3
2.1 问题的简介及描述3
2.2 问题的求解4
3 带容量限制的运输问题 5
3.1 问题的简介及描述5
3.2 问题的求解6
4 总结10
致谢10
参考文献11
运筹学中运输问题求解算法
引言
引言
运输问题，是人们在现代社会中常常能遇到也常常需要运用到的优化问题，例如在经济活动和军事活动中，它都有一定的应用。运输问题不只是线性规划问题这一大问题中一小类具备特殊性的问题，它也是我们在研究线性网络的优化相关问题时，早期常常出现用作举例的问题，在现实的生产活动中也有普遍的运用。对于运输问题的研究，不仅是要解决如怎样调配运输物资、如何有效调度交通工具等实际的运输类问题，一些表面上看起来和运输类问题没有关系的问题通过合理的变换也能够转化为运输问题的求解。
由于现实情况的复杂与不确定性，与之对应的求解运输问题的模型也是多种多样的。求解经典的运输问题时，限制最后结果的约束条件只有在物资生产地和销售地 *好棒文|www.hbsrm.com +Q: ^351916072#
之间运输过程所要花费的费用这一条[2]，而我们实际生活中遇到的运输问题，除了运费这一基本条件，还需要考虑道路的运输能力、各销地适用的交通运输工具等其他约束因素。本文分别讨论了带时间约束和运输容量限制的运输问题，作为现实生活中常见相关问题的参考。
1 运输问题模型与算法
1．1 运输问题的数学模型
在利用算法求解标准运输问题[3]中，我们要求解的问题一般是，有若干生产地与若干销售地，为了使得最终的运输费用最小，应当制定怎样的运输方案。用数学语言描述为：
设有个产地生产某物资，生产量分别为个单位，联合为个销地提供供应，其销售量分别为个单位。又假设由产地向销地运送物资时，运送单位物资所花费的金额（单价）为，试问该如何制定方案来科学合理地运输物资才能使最终花费的运输费用最小？
产地到销地的最终运输数量用来表示（；），在存在产销平衡时，可将上述数字排列在表1中。
表 1
到销地的运量
产量
到销地的运价
产地
销量
由此可得数学模型如下：
以上问题称为TP（Transportation Problem），即标准运输问题的模型，之后为其他运输问题建立数学模型时，都是以TP模型为基础，在其中或加入新的约束条件，或改变当前的目标函数来达到目的。
1．2 运输问题求解
标准运输问题在求解时仍然能够用一般线性规划中最基本求解方法如单纯形法的求解思路，即先通过算法确定一个初始的基本可行解，然后检验其是否已经为最优解，若还不是最优解，则通过换基迭代的方式来求最优解。但是，由于运输问题与普通的线性规划问题相比具有更多特殊的性质，采用线性规划单纯形法求解这些有利条件就不能获得充分的利用从而获得更简便的算法。于是，前人们在对运输问题的基本特征进行了研究分析之后，建立了表上作业法。表上作业法也是专门求解运输问题的求解算法，它仍然像单纯形法一样需要基本可行解、检验数以及方案调整等[4]。
1．2．1 初始基本可行解的确定
一般有如下两种求解方法来对初始基本可行解进行确定：
最小元素法
最小元素法是比较简单的求基本可行解的方法，它的基本求解思想就是要求各产销地之间就近供应。即先分配运价表中运价最小的运输路线的运输量，然后给次小运价的路线分配运输量，一直重复这一过程直到得出一个初始基本可行解。
元素差额法（又称Vogel法）
由于最小元素法求得的解往往不够准确，所以又在最小元素法基础上加以改进而得到了元素差额法。元素差额法的基本思想是：当某一产地的产品无法走运费最小的那条运输路线时，就得考虑运输费用次小的运输路线，在此之间就有一个单位费用的差值，这个差值越大，不能走运费最小的运输路线时，能算出来总运费的增加就越多，因而应当首先在差值最大的路径上考虑以运费最小的运输路线来调运。
目录
摘要1
关键词1
Abstract1
Key words1
引言1
1 运输问题模型与算法2
1.1 运输问题的数学模型 2
1.2 运输问题求解 2
1.2.1 初始基本可行解的确定2
1.2.2 基本可行解的最优性检验2
1.2.3 方案的调整3
2 带时间约束的运输问题3
2.1 问题的简介及描述3
2.2 问题的求解4
3 带容量限制的运输问题 5
3.1 问题的简介及描述5
3.2 问题的求解6
4 总结10
致谢10
参考文献11
运筹学中运输问题求解算法
引言
引言
运输问题，是人们在现代社会中常常能遇到也常常需要运用到的优化问题，例如在经济活动和军事活动中，它都有一定的应用。运输问题不只是线性规划问题这一大问题中一小类具备特殊性的问题，它也是我们在研究线性网络的优化相关问题时，早期常常出现用作举例的问题，在现实的生产活动中也有普遍的运用。对于运输问题的研究，不仅是要解决如怎样调配运输物资、如何有效调度交通工具等实际的运输类问题，一些表面上看起来和运输类问题没有关系的问题通过合理的变换也能够转化为运输问题的求解。
由于现实情况的复杂与不确定性，与之对应的求解运输问题的模型也是多种多样的。求解经典的运输问题时，限制最后结果的约束条件只有在物资生产地和销售地 *好棒文|www.hbsrm.com +Q: ^351916072#
之间运输过程所要花费的费用这一条[2]，而我们实际生活中遇到的运输问题，除了运费这一基本条件，还需要考虑道路的运输能力、各销地适用的交通运输工具等其他约束因素。本文分别讨论了带时间约束和运输容量限制的运输问题，作为现实生活中常见相关问题的参考。
1 运输问题模型与算法
1．1 运输问题的数学模型
在利用算法求解标准运输问题[3]中，我们要求解的问题一般是，有若干生产地与若干销售地，为了使得最终的运输费用最小，应当制定怎样的运输方案。用数学语言描述为：
设有个产地生产某物资，生产量分别为个单位，联合为个销地提供供应，其销售量分别为个单位。又假设由产地向销地运送物资时，运送单位物资所花费的金额（单价）为，试问该如何制定方案来科学合理地运输物资才能使最终花费的运输费用最小？
产地到销地的最终运输数量用来表示（；），在存在产销平衡时，可将上述数字排列在表1中。
表 1
到销地的运量
产量
到销地的运价
产地
销量
由此可得数学模型如下：
以上问题称为TP（Transportation Problem），即标准运输问题的模型，之后为其他运输问题建立数学模型时，都是以TP模型为基础，在其中或加入新的约束条件，或改变当前的目标函数来达到目的。
1．2 运输问题求解
标准运输问题在求解时仍然能够用一般线性规划中最基本求解方法如单纯形法的求解思路，即先通过算法确定一个初始的基本可行解，然后检验其是否已经为最优解，若还不是最优解，则通过换基迭代的方式来求最优解。但是，由于运输问题与普通的线性规划问题相比具有更多特殊的性质，采用线性规划单纯形法求解这些有利条件就不能获得充分的利用从而获得更简便的算法。于是，前人们在对运输问题的基本特征进行了研究分析之后，建立了表上作业法。表上作业法也是专门求解运输问题的求解算法，它仍然像单纯形法一样需要基本可行解、检验数以及方案调整等[4]。
1．2．1 初始基本可行解的确定
一般有如下两种求解方法来对初始基本可行解进行确定：
最小元素法
最小元素法是比较简单的求基本可行解的方法，它的基本求解思想就是要求各产销地之间就近供应。即先分配运价表中运价最小的运输路线的运输量，然后给次小运价的路线分配运输量，一直重复这一过程直到得出一个初始基本可行解。
元素差额法（又称Vogel法）
由于最小元素法求得的解往往不够准确，所以又在最小元素法基础上加以改进而得到了元素差额法。元素差额法的基本思想是：当某一产地的产品无法走运费最小的那条运输路线时，就得考虑运输费用次小的运输路线，在此之间就有一个单位费用的差值，这个差值越大，不能走运费最小的运输路线时，能算出来总运费的增加就越多，因而应当首先在差值最大的路径上考虑以运费最小的运输路线来调运。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/jsjkxyjs/1691.html
