运筹学胡运权第五版课件(第3章)分析ppt.ppt

《运筹学胡运权第五版课件(第3章)分析ppt.ppt》由会员分享，可在线阅读，更多相关《运筹学胡运权第五版课件(第3章)分析ppt.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第三章 运输问题Transportation Problem篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3.1 运输问题的典例和数学模型例例 某食品公司经营糖果业务，公司下设三个加工厂某食品公司经营糖果业务，公司下设三个加工厂A A1 1、A A2 2、A A3 3，四个销售门市部，四个销售门市部B B1 1、B B2 2、B B3 3、B B4 4。已知每天各自的生。已知每天各自的生产量、销售量及调运时的单位糖果的运输费用

2、等情况。产量、销售量及调运时的单位糖果的运输费用等情况。问：如何调运可使总费用最小？问：如何调运可使总费用最小？生产量：生产量：A A1 177吨，吨，A A2 244吨，吨，A A3 399吨吨销售量：销售量：B B1 133吨，吨，B B2 266吨，吨，B B3 355吨，吨，B B4 466吨吨加工厂加工厂单位运价单位运价门市部门市部B1 B2 B3 B4 A1A2A3 3 11 3 10 1 9 2 8 7 4 10 5单位：元单位：元/吨吨篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统解：用解：用cij表示从第表示从第i

3、个加工厂到第个加工厂到第j个门市部的单位糖果的运价，个门市部的单位糖果的运价，设设xij表示第表示第i个加工厂到第个加工厂到第j个门市部调运糖果的数量，个门市部调运糖果的数量，（i=1=1，2 2，3 3；j=1=1，2 2，3 3，4 4）则总费用为：则总费用为：min z=cijxij34i=1j=1x11+x12+x13+x14=7x11+x21+x31=3xij 0,(i=1,2,3；j=1,2,3,4)产产量量限限制制销销量量限限制制x21+x22+x23+x24=4x31+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6s.t

4、.篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1、运输问题 产地产地产地产地 提供物资的地点提供物资的地点提供物资的地点提供物资的地点 用用用用A A1 1,A,A2 2,A,Amm表示，或用表示，或用表示，或用表示，或用i i=1=1=1=1，2 2 2 2，,m m 表示；表示；表示；表示；销地销地销地销地 需要物资的地点需要物资的地点需要物资的地点需要物资的地点 用用用用B B1 1,B,B2 2,B,Bn n表示，或用表示，或用表示，或用表示，或用j j=1,2,=1,2,=1,2,=1,2,n n 表示；表示；表示；表示

5、；产量产量 每个产地提供物资的数量，用每个产地提供物资的数量，用a1,a2,am 表示；表示；销量销量 每个销地需要物资的数量，用每个销地需要物资的数量，用b1,b2,bn 表示；表示；单位物资运价单位物资运价 从产地从产地i到销地到销地j单位物资的运价为单位物资的运价为cij一般满足产销平衡：一般满足产销平衡：与物资调运有关的问题。与物资调运有关的问题。2、已知条件篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统已知条件的表格形式已知条件的表格形式单单 销销 价价 地地产地产地产产量量销销 量量平衡平衡产销平衡表产销平衡表单位运价表

6、单位运价表本例中：本例中：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统对于对于m m产产n n销运输问题，设销运输问题，设xij表示产地表示产地 i 运往销地运往销地 j 的物资的物资数量，则其数学模型如下：数量，则其数学模型如下：3、运输问题的数学模型注：运输问题是特殊的线性规划问题。注：运输问题是特殊的线性规划问题。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统4、模型的特点已知运输问题有已知运输问题有m m个产地、个产地、n n个销地，个销地，（1 1）决策变量的

7、个数：）决策变量的个数：m n（2 2）约束方程的个数：）约束方程的个数：m+n 其中线性独立方程的个数：其中线性独立方程的个数：m+n-1 基变量的个数：基变量的个数：m+n-1 非基变量的个数：非基变量的个数：mn-(m+n-1)篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5 5、运输问题解的情况、运输问题解的情况篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 3.2 表上作业法初始调运方案初始调运方案的确定的确定结束结束Y调整方案调整方案使目标函数值更小使目标函数

8、值更小N基本原理：基本原理：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2-12-1 初始方案的确定初始方案的确定1 1、最小元素法最小元素法 例例 用最小元素法确定初始方案。用最小元素法确定初始方案。就近供应就近供应“找便宜找便宜”有多少有多少要多少要多少运多少运多少篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 得到初始调运方案表：得到初始调运方案表：（1 1）有数字格（基格）有数字格（基格）填写了调运量的格子，对应填写了调运量的格子，对应解中的基变量。（用白圈表示

9、）解中的基变量。（用白圈表示）（2 2）空格空格 未填写调运量的格子，对应解中的非基变量，未填写调运量的格子，对应解中的非基变量，其对应变量在该方案中取值为其对应变量在该方案中取值为0。（用蓝圈表示）。（用蓝圈表示）在调运方案表中，在调运方案表中，12个格子分成两类：个格子分成两类：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例例 用最小元素法确定初始方案。用最小元素法确定初始方案。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统注意：注意：在调运方案表中，每次填入一个数

10、字，都在满在调运方案表中，每次填入一个数字，都在满足供需关系下划去相应的一列或一行。足供需关系下划去相应的一列或一行。若填入的一个数字既满足产量要求又满足销量若填入的一个数字既满足产量要求又满足销量要求，则应同时划去这一列和这一行，并在划去的要求，则应同时划去这一列和这一行，并在划去的所在列或行的任一个空格内填入一个所在列或行的任一个空格内填入一个0 0，以保持有数，以保持有数字格的总数不变（即基变量的个数不变）。字格的总数不变（即基变量的个数不变）。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2.2.沃格尔法（沃格尔法（Voge

11、l）01101225132-1301-2-1201-2-1-例例每行两个最每行两个最小元素之差小元素之差每列两个最每列两个最小元素之差小元素之差“找大差找大差”注意：由沃格尔法得出的解比最小元素注意：由沃格尔法得出的解比最小元素法得出的解更接近最优解。法得出的解更接近最优解。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2-2 最优性检验与方案的调整1 1、闭回路的概念、闭回路的概念在调运方案表中以一个空格和若干个有数字格作为顶点，以及在调运方案表中以一个空格和若干个有数字格作为顶点，以及水平、垂直连线围成的封闭回路，称为该空格对应

12、的闭回路。水平、垂直连线围成的封闭回路，称为该空格对应的闭回路。例如例如 分别找出下列空格的闭回路。分别找出下列空格的闭回路。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A1 1,B,B1 1）的闭回路）的闭回路篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A2 2,B,B2 2）的闭回路）的闭回路篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A1 1,B

13、,B2 2）的闭回路）的闭回路篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A2 2,B,B4 4）的闭回路）的闭回路篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A3 3,B,B1 1）的闭回路）的闭回路篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A3 3,B,B3 3）的闭回路）的闭回路注意：调运表中每个空格有且只有一个闭回路。注意：调运表中每个空格有

14、且只有一个闭回路。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2、利用闭回路计算检验数 令空格令空格（Ai,Bj）对应的非基变量的值对应的非基变量的值为为1 1，沿着闭沿着闭回路，相应顶点的基变量的回路，相应顶点的基变量的值依次值依次-1-1，+1+1，-1-1，+1+1，得到新可行解。，得到新可行解。将新可行解与原可行解相比，得到的将新可行解与原可行解相比，得到的运费变化量运费变化量称为该空格处的检验数，记做称为该空格处的检验数，记做ij。即即篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系

15、统是一种得分类型的系统例例 求下列调运方案表中各个空格的检验数。求下列调运方案表中各个空格的检验数。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A1 1,B,B1 1）的闭回路）的闭回路表示新方案的费用要增加表示新方案的费用要增加1 1元元篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A2 2,B,B2 2）的闭回路）的闭回路表示新方案的费用要增加表示新方案的费用要增加1 1元元篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负

16、的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A1 1,B,B2 2）的闭回路）的闭回路表示新方案的费用要增加表示新方案的费用要增加2 2元元篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A3 3,B,B1 1）的闭回路）的闭回路表示新方案的费用要增加表示新方案的费用要增加1010元元篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A3 3,B,B3 3）的闭回路）的闭回路表示新方案的费用要增加表示新方案的费用要增

17、加1212元元篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 空格（空格（A A2 2,B,B4 4）的闭回路）的闭回路表示新方案的费用要减少表示新方案的费用要减少1 1元元篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统综上，得到检验数表如下：综上，得到检验数表如下：B1B2B3B4A11200A20101A3100120注意：有数字格（基变量）的检验数为注意：有数字格（基变量）的检验数为0 0。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的

18、计时计分系统是一种得分类型的系统B1B2B3B4A10200A20210A390120例例 已知运输问题的调运方案如下，已知运输问题的调运方案如下，用闭回路法求检验数表用闭回路法求检验数表。解：检验数表为解：检验数表为篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3、利用检验数表判断最优性（1 1）若有负检验数，则该方案需要改进；）若有负检验数，则该方案需要改进；（2 2）若空格的检验数全为正数，则该问题有唯）若空格的检验数全为正数，则该问题有唯一最优方案；一最优方案；（3 3）若检验数全非负，且有空格的检验数为）若检验数全非负，且

19、有空格的检验数为0 0，则该问题有无穷多最优解。则该问题有无穷多最优解。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 在检验数表中，确定绝对值最大的负检验在检验数表中，确定绝对值最大的负检验数对应的空格，利用该空格的闭回路在满足供需数对应的空格，利用该空格的闭回路在满足供需关系下调整各顶点的运量，得到费用更小的调运关系下调整各顶点的运量，得到费用更小的调运方案。方案。4、改进方案的方法-闭回路法篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例调整方法：调整方法：121-

20、11012（1 1）找出绝对值最大的负检验数对应的闭回路）找出绝对值最大的负检验数对应的闭回路（2 2）使所对应的空格达到最大的调整量）使所对应的空格达到最大的调整量1 1 此时此时x23=0，可看成非基变量。可看成非基变量。注：格子右上角注：格子右上角数字为单位物资数字为单位物资运价，左下角数运价，左下角数字为检验数，圆字为检验数，圆圈内数字为调运圈内数字为调运物资数量。物资数量。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 得到新的调运方案：得到新的调运方案：该方案就是用沃格尔法得到的初始方案。该方案就是用沃格尔法得到的初始方

21、案。B1B2B3B4A10200A20210A390120其检验数表为其检验数表为故该方案为最优方案，且有无穷多最优方案，故该方案为最优方案，且有无穷多最优方案，Zmin=85=85元。元。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5、用位势法求检验数（2 2）计算行位势）计算行位势ui和列位势和列位势vj 不妨令不妨令u u1 1=1=1，则依，则依cij=ui+vj 计算各计算各ui和和vj （3 3）计算空格处位势和）计算空格处位势和ui+vj（4 4）计算空格处检验数）计算空格处检验数ij=cij-（ui+vj）（1 1

22、）列一张只含有数字格单位运价）列一张只含有数字格单位运价cij的表；的表；注意：注意：行位势、列位势可能不唯一，但检验数是相同的。行位势、列位势可能不唯一，但检验数是相同的。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统产地销地A1 A2 A3B1 B1 B3 B4 3 10 1 8 4 5 (3)(9)(7)(-2)(1)(-2)行位势列位势 12-1-4289销地A1 A2 A3B1 B1 B3 B43 11 3 10 1 9 2 8 7 4 10 5 产地单位运价表单位运价表位势表位势表产地销地A1 A2 A3B1 B1 B3

23、 B47 4 9产量销量3 6 5 6635213调运方案表调运方案表A1 A2 A3B1 B1 B3 B40229112检验数表检验数表ij篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统B1B2B3B4A10200A20210A390120检验数表：检验数表：故该方案为最优方案，且该问题有无穷多最优方案。故该方案为最优方案，且该问题有无穷多最优方案。总费用总费用Zmin=85元。元。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2-3 小结（1 1）分析问题，列出产销平

24、衡表和单位运价表。分析问题，列出产销平衡表和单位运价表。（2 2）利用最小元素法或沃格尔法求初始调运方案。）利用最小元素法或沃格尔法求初始调运方案。注：沃格尔法是近似最优解。注：沃格尔法是近似最优解。（3 3）用闭回路法或位势法求检验数表。）用闭回路法或位势法求检验数表。注：位势法比较简单。注：位势法比较简单。（4 4）判断最优性）判断最优性 若无负检验数，则该方案为最优方案，计算相若无负检验数，则该方案为最优方案，计算相应的总运费，结束；应的总运费，结束；否则，利用绝对值最大的负检验数对应的闭回否则，利用绝对值最大的负检验数对应的闭回路调整方案，并转入（路调整方案，并转入（3 3）。）。1

25、1、表上作业法的前提：产销平衡、表上作业法的前提：产销平衡2 2、表上作业法的步骤、表上作业法的步骤篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统已知某运输问题的资料如下表：已知某运输问题的资料如下表：B B1 1B B2 2B B3 3B B4 4发量发量A A1 12 26 65 53 31515A A2 21 13 32 21 11212A A3 33 32 27 74 41313收量收量1010131312125 5 表中的发量、收量单位为：吨，运价表中的发量、收量单位为：吨，运价单位为：元单位为：元/吨，吨，试求出最优运输

26、方案。试求出最优运输方案。练习练习篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统解：解：1 1、用最小元素法求初始方案、用最小元素法求初始方案B1B2B3B4发量发量A1012315A210212A31313收量收量1013125 用沃格尔法求初始方案用沃格尔法求初始方案B1B2B3B4发量发量A1100515A21212A301313收量收量1013125总费用总费用z z=107=107元元总费用总费用z z=85=85元元篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系

27、统B1B2B3B4A15A2251A3102 2、用位势法求由沃格尔法得到的方案的检验数、用位势法求由沃格尔法得到的方案的检验数3 3、结论：、结论：表中无负检验数且有非基变量的检验数表中无负检验数且有非基变量的检验数为为0 0，本问题有无穷多最优方案。，本问题有无穷多最优方案。一个最优调运方案为：一个最优调运方案为：B1B2B3B4发量发量A1100515A21212A301313收量收量1013125综上所述，综上所述，总费用总费用Zmin=85元。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统3.3 产销不平衡的运输问题及其应

28、用一、原理一、原理篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统注：该销地的作用相当于多余物资就地库存。注：该销地的作用相当于多余物资就地库存。注：当销地需要刚性物资时，相应单价为注：当销地需要刚性物资时，相应单价为M M；当销地需要弹性物资时，相应单价为当销地需要弹性物资时，相应单价为0 0。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统B1B2B3B4A1211347A2103595A3781272346B1B2B3B4B5 A12113407A21035905A37

29、8120723464例例 求解下列运输问题。求解下列运输问题。解：解：产销产销 虚设一个销地虚设一个销地B B5 5，建立产销平衡的运输问题：，建立产销平衡的运输问题：产销产销产产=销销二、应用举例二、应用举例篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统用表上作业法求得最优方案为：用表上作业法求得最优方案为：B1B2B3B4B5 A1232A232A343总运价总运价zmin=35=35元。元。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统例例 有有A A、B B、C

30、C三个化肥厂供应四个地区三个化肥厂供应四个地区、的农用化肥，三个工厂每年各自的产量为的农用化肥，三个工厂每年各自的产量为A-A-5050万吨，万吨，B-60B-60万吨，万吨，C-50C-50万吨。四个地区的需求量万吨。四个地区的需求量分别是分别是地区最高地区最高5050万吨，最低万吨，最低3030万吨，万吨，地区为地区为7070万吨，万吨，地区为地区为3030万吨以下，万吨以下，地区不低于地区不低于1010万吨。万吨。已知从各化肥厂到各地区单位化肥的运价如下表。已知从各化肥厂到各地区单位化肥的运价如下表。问：如何调运，可使总的调运费用最小？问：如何调运，可使总的调运费用最小？篮球比赛是根据运

31、动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统解：解：对于需求有两种情况的地区，实际按两对于需求有两种情况的地区，实际按两个地区来处理。个地区来处理。1212A16161322171750B14141319151560C1919202350302070301050产销产销MM篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1212A16161322171750B14141319151560C1919202350D50302070301050产产=销销MMMMM0 00 00 0产销产销 虚设一个假想的化肥厂虚设一个假想的化肥厂D D，D D的年产量为的年产量为5050万吨万吨,建立产销平衡的运输问题。建立产销平衡的运输问题。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统用表上作业法求得最优方案为：用表上作业法求得最优方案为：总运价总运价zmin=2460=2460万元万元。1212A5050B20103060C3020050D302050302070301050