管理运筹学04运输问题课件

管理运筹学04运输问题课件1管理运筹学04运输问题课件2第46页例4-12022/10/30第46页例4-12022/10/233例4-1的数学模型2022/10/30例4-1的数学模型2022/10/2343.运输问题的求解1.求解方法：表上作业法2.表上作业法的基本步骤:(1)找出初始基可行解；(2)求检验数并判断最优性；(3)确定入基变量和出基变量；(4)调整运输方案；(5)重复2~4，直至最优。2022/10/303.运输问题的求解1.求解方法：表上作业法2022/10/5找出初始基可行解1.最小元素法(1)基本思想：就近供应(2)基本步骤(3)例4-12.伏格尔法(1)基本思想：机会成本(2)基本步骤(3)例4-12022/10/30找出初始基可行解1.最小元素法2022/10/236最小元素法的基本步骤1.找出最小运价，确定供求关系，最大量的供应；2.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；3.在剩余的运价表中重复1、2两步，直到得到初始基可行解。2022/10/30最小元素法的基本步骤1.找出最小运价，确定供求关系，最大量的7例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/238例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/239例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2310例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2311例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2312例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2313伏格尔法的基本步骤1.计算每行、列两个最小运价的差；2.找出最大差所在的行或列；3.找出该行或列的最小运价，确定供求关系，最大量的供应；4.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；5.在剩余的运价表中重复1~4步，直到得到初始基可行解。2022/10/30伏格尔法的基本步骤1.计算每行、列两个最小运价的差；202214例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2315例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2316例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2317例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2318例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2319例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2320求检验数并判断最优性1.闭合回路法：从任意一个空格（非基变量）出发，沿着行或列寻找的一条除此空格之外其余顶点均为有数字格（基变量）的回路。空格的闭合回路有且唯一，有数字格不存在闭合回路。2.位势法：行因子i，列因子j，使每一个基变量有cij

=

i

+j。3.判断最优性：若所有的检验数均大于等于零，已得最优方案；否则，进行方案调整。2022/10/30求检验数并判断最优性1.闭合回路法：从任意一个空格（非基变21闭合回路法的基本步骤1.找出某一空格的闭合回路；2.从该空格开始在闭合回路上给各个顶点进行”+“、”-“间隔标号；3.计算空格的检验数空格检验数=cij(+)-cij(-)

4.重复1~3，直至求得全部的检验数。

2022/10/30闭合回路法的基本步骤1.找出某一空格的闭合回路；202222例4-1(最小元素法)

2022/10/30例4-1(最小元素法)2022/10/2323闭合回路法求检验数

2022/10/30闭合回路法求检验数2022/10/2324闭合回路法求检验数

2022/10/30闭合回路法求检验数2022/10/2325闭合回路法求检验数

2022/10/30闭合回路法求检验数2022/10/2326例4-1(伏格尔法)

2022/10/30例4-1(伏格尔法)2022/10/2327闭合回路法求检验数2022/10/30闭合回路法求检验数2022/10/2328位势法的基本步骤1.把基变量对应的运价拿来；2.任意取一个位势因子并赋予一个任意值；3.余下的所有因子可根据基变量的运价cij

=

i

+j来唯一确定；4.计算空格检验数ij=cij-(

i

+j)。

2022/10/30位势法的基本步骤1.把基变量对应的运价拿来；2022/129例4-1(最小元素法)

2022/10/30例4-1(最小元素法)2022/10/2330位势法求检验数

2022/10/30位势法求检验数2022/10/2331位势法求检验数

2022/10/30位势法求检验数2022/10/2332例1(伏格尔法)

2022/10/30例1(伏格尔法)2022/10/2333位势法求检验数

2022/10/30位势法求检验数2022/10/2334位势法求检验数2022/10/30位势法求检验数2022/10/2335确定入基变量和出基变量1.确定入基变量：具有最大绝对值的负检验数所对应的变量即为入基变量。2.确定出基变量：在入基变量所处的闭合回路上，让入基变量增加，由于供求平衡关系，带“+”标号的基变量将随之增加；而带“-”标号的基变量将随之减少，最先减少为零的基变量即为出基变量。2022/10/30确定入基变量和出基变量1.确定入基变量：具有最大绝对值的负检36确定入基变量2022/10/30确定入基变量2022/10/2337确定出基变量2022/10/30确定出基变量2022/10/2338调整运输方案1.在入基变量所在的闭合回路上，带“+”标号的格增加x出，带“-”标号的格减少x出。注意：出基变量减少后的“0”不要保留在表格中，如果同时有多个而带“-”标号的格减少为零，可人为确定之一为出基变量，在表格中保留其它“0”。2.对调整后的方案求检验数并判断其最优性。3.重复1~2两步，直至得到最优方案。2022/10/30调整运输方案1.在入基变量所在的闭合回路上，带“+”标号39运输方案2022/10/30运输方案2022/10/2340调整后的运输方案2022/10/30调整后的运输方案2022/10/2341最优运输方案2022/10/30最优运输方案2022/10/23424.运输问题的拓展及应用1.产销不平衡的运输问题(1)产大于销(2)销大于产2.运输问题的应用(1)第59页例4-4(2)第60页例4-5(3)第62页习题6(4)第60页例4-62022/10/304.运输问题的拓展及应用1.产销不平衡的运输问题2022/43产大于销的运输问题2022/10/30产大于销的运输问题2022/10/2344产大于销的运输问题2022/10/30产大于销的运输问题2022/10/2345销大于产的运输问题2022/10/30销大于产的运输问题2022/10/2346销大于产的运输问题2022/10/30销大于产的运输问题2022/10/2347第59页例4-42022/10/30第59页例4-42022/10/2348第59页例4-42022/10/30第59页例4-42022/10/2349第59页例4-42022/10/30第59页例4-42022/10/2350第60页例4-52022/10/30第60页例4-52022/10/2351第60页例4-52022/10/30第60页例4-52022/10/2352第62页习题6已知某厂每月可生产甲产品270吨，先运至A1、A2、A3三个仓库，然后在分别供应B1、B2、B3、B4、B5五个用户。已知仓库容量分别为50、100、150吨，各用户的需要量分别为25、105、60、30、70吨。已知从该厂经各仓库然后供应各用户的运费如下表所示，试确定一个使总运费最少的调运方案。2022/10/30第62页习题6已知某厂每月可生产甲产品270吨，先运至A1、53第62页习题62022/10/30第62页习题62022/10/2354第62页习题62022/10/30第62页习题62022/10/2355第60页例4-62022/10/30第60页例4-62022/10/2356第60页例4-62022/10/30第60页例4-62022/10/2357第60页例4-62022/10/30第60页例4-62022/10/2358第60页例4-62022/10/30第60页例4-62022/10/2359文档名THEEND!THANKYOU!文档名THEEND!THANKYOU!60管理运筹学04运输问题课件61管理运筹学04运输问题课件62第46页例4-12022/10/30第46页例4-12022/10/2363例4-1的数学模型2022/10/30例4-1的数学模型2022/10/23643.运输问题的求解1.求解方法：表上作业法2.表上作业法的基本步骤:(1)找出初始基可行解；(2)求检验数并判断最优性；(3)确定入基变量和出基变量；(4)调整运输方案；(5)重复2~4，直至最优。2022/10/303.运输问题的求解1.求解方法：表上作业法2022/10/65找出初始基可行解1.最小元素法(1)基本思想：就近供应(2)基本步骤(3)例4-12.伏格尔法(1)基本思想：机会成本(2)基本步骤(3)例4-12022/10/30找出初始基可行解1.最小元素法2022/10/2366最小元素法的基本步骤1.找出最小运价，确定供求关系，最大量的供应；2.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；3.在剩余的运价表中重复1、2两步，直到得到初始基可行解。2022/10/30最小元素法的基本步骤1.找出最小运价，确定供求关系，最大量的67例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2368例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2369例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2370例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2371例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2372例4-1的最小元素法2022/10/30例4-1的最小元素法2022/10/2373伏格尔法的基本步骤1.计算每行、列两个最小运价的差；2.找出最大差所在的行或列；3.找出该行或列的最小运价，确定供求关系，最大量的供应；4.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；5.在剩余的运价表中重复1~4步，直到得到初始基可行解。2022/10/30伏格尔法的基本步骤1.计算每行、列两个最小运价的差；202274例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2375例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2376例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2377例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2378例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2379例4-1的伏格尔法2022/10/30例4-1的伏格尔法2022/10/2380求检验数并判断最优性1.闭合回路法：从任意一个空格（非基变量）出发，沿着行或列寻找的一条除此空格之外其余顶点均为有数字格（基变量）的回路。空格的闭合回路有且唯一，有数字格不存在闭合回路。2.位势法：行因子i，列因子j，使每一个基变量有cij

=

i

+j。3.判断最优性：若所有的检验数均大于等于零，已得最优方案；否则，进行方案调整。2022/10/30求检验数并判断最优性1.闭合回路法：从任意一个空格（非基变81闭合回路法的基本步骤1.找出某一空格的闭合回路；2.从该空格开始在闭合回路上给各个顶点进行”+“、”-“间隔标号；3.计算空格的检验数空格检验数=cij(+)-cij(-)

4.重复1~3，直至求得全部的检验数。

2022/10/30闭合回路法的基本步骤1.找出某一空格的闭合回路；202282例4-1(最小元素法)

2022/10/30例4-1(最小元素法)2022/10/2383闭合回路法求检验数

2022/10/30闭合回路法求检验数2022/10/2384闭合回路法求检验数

2022/10/30闭合回路法求检验数2022/10/2385闭合回路法求检验数

2022/10/30闭合回路法求检验数2022/10/2386例4-1(伏格尔法)

2022/10/30例4-1(伏格尔法)2022/10/2387闭合回路法求检验数2022/10/30闭合回路法求检验数2022/10/2388位势法的基本步骤1.把基变量对应的运价拿来；2.任意取一个位势因子并赋予一个任意值；3.余下的所有因子可根据基变量的运价cij

=

i

+j来唯一确定；4.计算空格检验数ij=cij-(

i

+j)。

2022/10/30位势法的基本步骤1.把基变量对应的运价拿来；2022/189例4-1(最小元素法)

2022/10/30例4-1(最小元素法)2022/10/2390位势法求检验数

2022/10/30位势法求检验数2022/10/2391位势法求检验数

2022/10/30位势法求检验数2022/10/2392例1(伏格尔法)

2022/10/30例1(伏格尔法)2022/10/2393位势法求检验数

2022/10/30位势法求检验数2022/10/2394位势法求检验数2022/10/30位势法求检验数2022/10/2395确定入基变量和出基变量1.确定入基变量：具有最大绝对值的负检验数所对应的变量即为入基变量。2.确定出基变量：在入基变量所处的闭合回路上，让入基变量增加，由于供求平衡关系，带“+”标号的基变量将随之增加；而带“-”标号的基变量将随之减少，最先减少为零的基变量即为出基变量。2022/10/30确定入基变量和出基变量1.确定入基变量：具有最大绝对值的负检96确定入基变量2022/10/30确定入基变量2022/10/2397确定出基变量2022/10/30确定出基变量2022/10/2398调整运输方案1.在入基变量所在的闭合回路上，带“+”标号的格增加x出，带“-”标号的格减少x出。注意：出基变量减少后的“0”不要保留在表格中，如果同时有多个而带“-”标号的格减少为零，可人为确定之一为出基变量，在表格中保留其它“0”。2.对调整后的方案求检验数并判断其最优性。3.重复1~2两步，直至得到最优方案。2022/10/30调整运输方案1.在入基变量所在的闭合回路上，带“+”标号99运输方案2022/10/30运输方案2022/10/23100调整后的运输方案2022/10/30调整后的运输方案2022/10/23101最优运输方案2022/10/30最优运输方案2022/10/231024.运输问题的拓展及应用1.产销不平衡的运输问题(1)产大于销(2)销大于产2.运输问题的应用(1)第59页例4-4(2)第60页例4-5(3)第62页习题6(4)第60页例4-62022/10/304.运输问题的拓展及应用1.产销不平衡的运输问题2022/103产大于销的运输问题2022/10/30产大于销的运输问题2022/10/23104产大于销的运输问题2022/10/30产大于销的运输问题2022/1