运筹学课件第5章 运输问题.ppt

1、第五章运输问题，重庆三峡学院关文忠，运营计划学课件的管理，2020年7月11日星期六，教育目标和要求，在本章学习，了解运输问题的特点，制作运输问题数学模型，可以把产销不平衡的运输问题转换成产销平衡的运输问题，至少掌握一个软件，以达到运输问题的最佳【知识构造】、运筹学课件的管理，2020年7月11日星期六，案例分析的发送问题，把xij从配送中心Ai发送给城市Bj的货物数量，z作为总运输费，可以看出这个问题的数学模型是：运筹学课件的管理，2020年7月11日星期六本章主要内容5.1运输问题的数学模型5.1.1产销平衡的数学模型5.1.2产销平衡的数学模型5.1.3非标准形式数学模型的标准化5.2表

2、作业法5.2.1初期基本可行解5.2.2解的最优性检验5.2.3改进运输方案5.2.4如何改进多个解决运输问题或题目(各节的实验演示) 5.4应用例本章总结，管理运营计划的授课资料，2020年7月11日星期六，5.1.1的产销平衡的数学模型，一般状况： m产地，产量为Ai n据点，销售量为bj=ai=bj时，产销平衡ai吗生产大头针平衡运送模型包含(1)mn个变量，有Mn个制约条件(2)，因此容易可知，系数矩阵中的线性独立列向量的最大个数是(mn1 )个，即生产大头针平衡运输问题的解中枢变量的个数是(mn1 )个。运营计划学课件管理、2020年7月11日星期六、5.1.2产销不平衡数学模型、运

3、营计划学课件管理、2020年7月11日星期六、5.1.3非标准形式数学模型标准化、运营计划学课件管理、2020年7月11日星期六、 5.1.3非标准形式数学模型的标准化，【例5.1】运输问题标准化运营计划学课件的管理，2020年7月11日星期六，5.1.3非标准形式数学模型的标准化，运营计划学课件的管理，2020年7月11日星期六，5.1.3非标准形式数学模型的标准化，运营计划学课件的(1)找到初期的基本可行解。 也就是说，(mn )产销平衡表赋予(m n-1 )个数字的格，与此对应的运输量是基本变量，填入格中的值是基本变量的解。 (2)求出各非基底变量的检测常数，即表中除了(m n-1 )个

4、数字以外的空格的检测常数，判别是否得到了最佳解。 如果是最佳解则中止计算，否则进入下一步。 (3)决定基础变量和输出基础变量，找到新的基本可能的解，用表调整闭合回路。 (4)重复2、3直到得到最佳解。 初期解是怎样给出的？ 如何求出检验数，如何调整普拉姆？三个重要环节：管理运筹学教材，2020年7月11日星期六，2.3.1初步方案确定，初步基本可行解确定方法有西北方法、最小元素法、Vogel法等。 Vogel法给出的初期方案最好，最小元素体法其次，西北方法最差，在此只介绍后者的两种方法。 无论采用哪种方法，输入数字都应遵循以下原则。 初始方案的数值填充原则： (1)满足需求时，删除其销售目的地

5、列，填充产地行的可用数量=原来的可用数量-数值；(2)如果生产量已经供给完毕，则删除其产地行，销售目的地列的需求量=原需求量-填充数字；(3)需求量和可供给量正好相等，则任意未删除的ai或bj的馀量为0，该0视为可填充的数字，保证原则(4)的满脚丫子(4)计划的有数字的格子数=行数列数-1。管理运营计划教材，2020年7月11日星期六，1 .最小元素法、最小元素法的基本思想提供到附近，从单位价目表中最小的运输价格确定销售关系，依次类推，直到所有方案都被提出为止。例如，在最小元素体2中，A2和B- 1的供应关系，B1对8、a-2的产量10所需要的8个，B1被满足，界定该列，a-2是2。 剩馀的最

6、小元素体3由于A2和B3的供应关系，B3=10，a2=剩馀2，a2=已供应，除了该行，B3仍为10。 剩下的最小元素体4由于a-1和B- 3的供应关系，B- 3进一步需要10、a-1的产量16来供应10个，B- 3充满脚丫子，界定该列，a-1是6个多馀的。 剩下的最小元素体5由于a-3和B- 2的供应关系，B- 2需要14、a-3的产量22，供应14个，B- 2充满脚丫子，界定该列，a-3有8个多馀。 剩下的最小元素体6与a3-B4的供应关系，其中B4完成了对14个、a3-8个、8个和A3个的供应，b 4仍为6。 剩下的元素体只有11个，由于A1和B4的委托关系，B4仍为6，A1多6，供给6个

7、，A3供给完成，B4满脚丫子，选择1列或列。 数字网格数(6)=行数(3)的列数(4)-1得到初始方案，为8，2，10，6，14，8，14，12，| 10，14，| 6，16，22，|8，10，|2，管理运营学课件，2020年7月11日Vogel法的步骤是从运费价目表中分别找出各行和各列的最小元素和子要素，求出它们的差，从差最大的行或列中找出最小运费价格，确定供求关系和供给数量。 求8、2、12、4、14、8、14、12、14、| 6、16、|4、22、|8、10、|2、(1)最小元素体的差额，其中最大的是5，对应的是(A3，B2) 差最大的是3，位于第4列，最小元素是6，对应的是(A3，B4

8、 )的B4为14-8=6，|2，(3)第4列的最小元素体的差为2，其馀不变由于B1=min 10，8=8，所以满足了用数字8，B1填充(a2，B1 )的需求，删除某列A1馀16-12=4， 222222222222卡卡西卡卡西卡卡西卡卡西卡卡西卡卡西卡卡西卡6 5.2.2解的最优性检验电势法，例5.4最小元素体法给出方案的检验常数，单位价目表，初期方案，电势法检验常数表，0，4，11，-1，-5 10，6，存在负检验常数，存在非最佳解，管理运营计划学课件，2020年7月11日星期六，5.2.3方案的改进闭路法例5.4最小元素体法给出方案的检验数，单位价目表，方案调整，电位法检验表，0，4，11

9、，-2，- 5，4 2，10，6，12，4，优化方案，运营计划学课件的管理，2020年7月11日星期六，5.2.4如何查找优化方案，运营计划学课件的管理，2020年7月11日星期六，5.4应用实例，运输问题模式简单案例5-1生产排程问题案例5-2空车规划问题案例5-3运输问题，运营计划课件的管理，2020年7月11日星期六，案例5-1生产排程问题，存储成本： 10万元/万吨*季度，250，280，300，250，260，270，280，250 m (1)本季度生产当季销售，单位运费=生产成本，(2)前期生产后季度销售，单位运费=生产成本的积累成本，(3)后期生产前季度销售不可能，运费为m，解：

10、生产能力被视为产地，需求被视为销售地，生产销售平衡表和单位运费价格表被制作运输计划学课件的管理，2020年7月11日星期六，运输任务案例5-2空车调配问题，行驶日程，空缺表，以空缺为供求的运输问题，最佳安排方案，行驶距离：23.9公里，3，0，6，4，3，0，8，8，0，-3，-2 工厂生产的产品可以运送到直销模式，也可以经由其他工厂和仓库运送到销售地，也可以在销售地之间运送。 工厂1的产量是7t，工厂2的产量是3t，销售地1和销售地2的需求都是5t。 工厂、仓库、销售地之间的单位运价如表5-30所示，试着确定运输费最小的运输计划，将15、15、10、10、10、10、10、13、17、10、13、17、17、解：产地、仓库、销售地作为产地和销售地双方。 两工厂的生产量之和为10，也就是最大运输量，作为运输点的生产量和销售量的产地的工厂，除了作为运输据点之外，还承担着生产任务，那个生产量是最大运输量加上各自的生产量，作为销售点的卖场，除了作为运输据点，还有销售需要寻求最佳方案：管理运营计划教材，2020年7月11日星期六，总结本章，本章介绍了特殊类型的线性规划运输问题。 建立运输问题LP模型的关键是建立产销平衡表和单位运输价目表。 利用表作业法解决运输问题时，目标min、产量=销量和需要标准化的表作业法有给出初期方案、求出检验数、调整方案三个重要环节。 西