《《运筹学》第三章-运输问题资料讲解ppt课件.ppt》由会员分享，可在线阅读，更多相关《《运筹学》第三章-运输问题资料讲解ppt课件.ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益运筹学第三章运输问题1为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1 运输问题的典例和数学模型 3.2 运输问题的求解方法：表上作业法3.3 几类特殊的运输问题3.4 运输问题的应用2为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 运输问题运输问题：根据已有的交通网，如何制定运输方案，使得这些物资被运送到各个销售地，并保证某个指标最优(
2、例如总运费最小)。3为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.1 运输问题的典例和数学模型一、典例 某食品公司经营糖果业务，公司下设三个工厂A1、A2、A3，四个销售门市部B1、B2、B3、B4。已知每天各自的生产量、销售量及调运时的单位运输费用情况。问：如何调运可使总费用最小？生产量：A17吨，A2 4吨，A3 9吨销售量：B1 3吨，B2 6吨，B3 5吨，B4 6吨产地单位运价销地B1 B2 B3 B4 A1A2A3 3 11 3 10 1 9 2 8 7 4 1054为了规范事业单位聘用关系，建立和完善适应社
3、会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益调运示意图A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地5为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益二、建立模型设 xij第i产地到第j销地之间的调运量，则有Min z=cij xij34i=1 j=1x11+x12+x13+x14=7x11+x21+x31=3xij0,(i=1,2,3；j=1,2,4)产量限制销量限制x21+x22+x23+x24=4x31
4、+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=66为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益单单位位运运价价表表产产销销平平衡衡表表7为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益一般模型表示(ai=bj)8为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益三、模型的特点1.变量数：mn个2.约束方程数：m+n个 最大独立方程数：
5、m+n-13.系数列向量结构：Pij=第i个分量第m+j个分量01 11 10 9为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益x11 x12 x1n x21 x22 x2n ,xm1 xm2 xmn1 1 1 0 0 0 0 0 00 0 0 1 1 1 0 0 00 0 0 0 0 0 1 1 11 0 0 1 0 0 1 0 00 1 0 0 1 0 0 1 00 0 1 0 0 1 0 0 1i=1i=2i=mj=1j=2j=n10为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度
6、，保障用人单位和职工的合法权益关于运输模型的几个结论：(1)设有m个产地，n个销地且产销平衡的运输问题，则基变量数是m+n-1；(2)若变量组B包含有闭回路，则B中变量对应的列向量线性相关；(3)m+n-1个变量组构成基变量的充要条件是它不包含任何闭回路。11为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 初始基可行解新的基可行解最优否？STOPYN 3.2 运输问题的求解方法：表上作业法单纯形法求解思路12为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益表
7、上作业法步骤表上作业法步骤:初始运输方案最优性检验改进运输方案一、初始方案的确定1.最小元素法最小元素法2.VogelVogel法法二、最优性检验1.闭回路法闭回路法2.位势法位势法三、方案改进方法在闭回路闭回路内改进。13为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量3 11 3 10 1 9 2 8 7 4 10 5 634133 6 5 67 4 9单位运价表产销平衡表最小元素法最小元素法14为了规范事业单位聘用关系，
8、建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例 产地销地A1 A2 B1 B215 1510 20产量销量2851最小元素法：z=810+25+115=105Vogel法：z=105+152+51=85VogelVogel法法15为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益产地销地A1 A2 A3B1 B2 B3 B47 4 9产量销量3 6 5 6635213产地销地A1 A2 A3B1 B2 B3 B4行两最小元素之差列两最小元素之差3 11 3 10 1 9 2 8 7
9、4 10 5 0 1 12 5 1 3 0 1 22 -1 30 1-2 -1 27 6-1 2VogelVogel法法产销平衡表16为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益针对最小元素法和vogel法，需要说明的几点：(1)任何运输问题都有基可行解，且有最优解；(2)如果供应量和需求量都是整数，那么一定可以得到整数形式的最优解;(4)若在中途同时有行列要求得到满足，将同时划掉一行一列，最后数字格个数将少于m+n-1个。为使数字格的个数恰好等于m+n-1，在同时划去的行列中，任选（或选其价格系数最小元素对应的）空格，填
10、上数字0作为特殊的数字格（即基变量）。(3)用最小元素法和vogel法得到的是运输问题的一个基可行解，数字格对应基变量；17为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量2 7 3 11 8 4 6 9 4 3 10 5 2030 25 10 1520 10 50单位运价表产销平衡表10251510018为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益产地销
11、地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量3 11 3 10 1 9 2 8 7 4 10 5 6343133 6 5 67 4 93 6 5 67 4 9产量销量363521(1)(2)(1)(-1)(10)(12)z=c11-c13+c23-c21=1=11z=c12-c14+c34-c32=2=12(0)(2)(2)(9)(1)(12)单位运价表产销平衡表闭闭回回路路法法19为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益注
12、:只要求的基变量是正确的，并且数目为m+n-1个，那么每个非基变量的闭回路存在且唯一，因此，检验数唯一。20为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益产地销地A1 A2 A3B1 B1 B3 B4位势法位势法4132.计算行位势和列位势；令v1=1，则依cij=ui+vj 计算各ui和vj 3.计算空格处位势；ij=ui+vj行位势ui列位势vj 110-42894.计算空格处检验数：ij=cij-ij1.数字格处上添上对应的运价；销地A1 A2 A3B1 B1 B3 B43 11 3 10 1 9 2 8 7 4 10
13、 5 产地单位运价表位势表:2105(2)(9)(8)(9)(-3)(-2)21为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益产地销地A1 A2 A3B1 B1 B3 B47 4 9产量销量3 6 5 66343(-1)3(1)(2)(1)(10)1(12)检验数表注：位势法求检验数的依据是对偶理论。22为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益注:(1)对于同一组基变量，所求的检验数是唯一的；(2)在最优解表中，有非基变量（即空格)的检验数为0，根据
14、线性规划单纯形法原理知，应有无穷多最优解，即有多解。运输问题表上作业法求多解的方法：任选一检验系数为0的空格入基，进行方案改进，可得新的最优解；(3)在进行调运方案改进时，若沿闭合回路出现多个可作为调出变量的数字格（即闭回路上的数字格最小值有多个），此时，任选一个为调出变量，其余的填0，保证调整后的调运方案中仍有m+n-1个数字格。23为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益5例：产地销地A1 A2 A3B1 B1 B3 B47 4 9产量销量3 6 5 6635213(0)(2)(2)(9)(1)(12)产地销地A1
15、 A2 A3B1 B1 B3 B47 4 9产量销量3 6 5 66331224为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益4(1)产地销地A1 A2 A3B1 B2 B3 B4产量销量632233 6 6 56 5 9(2)(1)(-1)(10)(12)例：6产地销地A1 A2 A3B1 B2 B3 B4产量销量63033 6 6 56 5 9 225为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益练习产地销地A1 A2 A3B1 B2 B3 B4产地销
16、地A1 A2 A3B1 B2 B3 B4产量销量10 1 20 11 12 7 9 20 2 14 16 18 5 15 15 1015 25 5单位运价表产销平衡表26为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益最小元素法产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量10 1 20 11 12 7 9 20 2 14 16 18 5 15 15 1015 25 5单位运价表产销平衡表15515100027为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事
17、业单位工作人员聘用制度，保障用人单位和职工的合法权益Vogel法产地销地A1 A2 A3B1 B2 B3 B4产地销地A1 A2 A3B1 B2 B3 B4产量销量10 1 20 11 12 7 9 20 2 14 16 18 5 15 15 1015 25 5单位运价表产销平衡表8 6 7 79 2 125-6 11 910 2 -15-6 -910 13 -10510028为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益注:表上作业法适用于下列情形：(1)cij0；(2)min z；(3)产销平衡。表表上上作作业业法法步步
18、骤骤29为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.3 几类特殊的运输问题一、产销不平衡问题1产销2销产二、需求量不确定三、中转问题30为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Min z=cij xijni=1j=1m一、产销不平衡问题1产销(aibj)Min z=cijxij+0 xi,n+1ni=1 j=1mi=1m31为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益产地销
19、地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnBn+1 产销问题单位运价表销量产量b1b2bna1 a2 amaibj32为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益Min z=cij xijni=1j=1m2销产(bjai)Min z=cijxij+0 xm+1,jni=1 j=1mj=1n33为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2
20、n Cm1Cm2CmnAm+1销产问题单位运价表0 0 0销量产量b1b2bna1 a2 ambjai34为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例：例：有A、B、C三个化肥厂供应四个地区、的农用化肥，三个工厂每年各自的产量为A-50万吨，B-60万吨，C-50万吨。四个地区的需求量分别是地区最高50万吨，最低30万吨，地区为70万吨，地区为30万吨以下，地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。产地销地A 产量最低需求16 13 22 17 14 13 19 15 19 20 2
21、3 单位运价表50 60 5030 70 0 10单位：万元/万吨设 xij-第i工厂调至第j需求地区的化肥数量二、需求量不确定BC最高需求 50 70 30 不限35为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益A B C 161613221717 14141319151519192023 M MM0M0M0供应需求产量销 量50 60 50 302070301050产销平衡表D50注：M表示无穷大正数，最低需求不能由D生产地提供。36为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，
22、保障用人单位和职工的合法权益最优方案：需求产地I产量A5050B20103060C3020050D302050销量30207030105037为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益练习产地销地A 最高发量4 6 7 -7 8 单位运价表60 40 400BC销量70 80 50D最低发量80 40 不限505 4 6 4 5 -38为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益三、中转问题在前面的例题中，若既可以从Ai运到Bj，也可以经过中间站T1
23、、T2、T3、T4或者Ai、Bj转运，称为扩大的运输问题。几点说明：1.所有的产地、销地、中间站均视作产地、销地；2.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为cii=0；3.转运量可定位总的产量之和；4.实际产地产量为转运量与该产地实际产量之和，实际销地销量为转运量与实际销量之和。39为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益A1 A2 A3T1 T2 T3 T4B1 B2 B3 B4A1 A2 A3T1 T2 T3 T4B1 B2 B3 B40 1 3 1 0 -3 -02 1 4 3 3 5 -2 1
24、 -2 33 11 3 10 1 9 2 8 7 4 10 52 3 1 1 5 -4 -2 3 2 33 1 7 11 9 4 3 2 10 10 8 50 1 3 2 1 0 1 1 3 1 0 2 2 1 2 0 2 8 4 6 4 5 2 7 1 8 2 4 1 -2 6 2 4 1 1 8 5 8 -4 2 2 2 6 7 4 60 1 4 2 1 0 2 1 4 2 0 3 2 1 3 0产销产量销量27 24 2920 20 20 2020 20 20 2020 20 2020 20 20 2023 26 25 26产销平衡表40为了规范事业单位聘用关系，建立和完善适应社会主义市
25、场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益3.4 运输问题的应用41为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益 例：例：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。季度生产能力(台)单位成本(万元/台)2535301010.811.111.011.342为了规范事业单位聘用
26、关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益模型：设xij第i季度生产，用于第j季度交货的数量。obj.min z=cij xiji=1j=1 4 4x11+x12+x13+x1425 x22+x23+x2435 x33+x3430 x4410 x11 =10 x12+x22 =15x13+x23+x33 =25x14+x24+x34+x44=20 xij 0,(i=1,4;j=1,4)供应：需求：43为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益单位费用表：10.8 10
27、.9511.10 11.25 M 11.10 11.25 11.40 M M 11.00 11.15 M MM 11.30单位：万元供应需求44为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益例例:某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天1000条，第二天700条，第三天800条，第四天1200条，第五天1500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要1元的费用，送洗时可选择两种方式：快洗
28、仅需要一天时间，每条洗涤费用为0.2元，慢洗需要两天时间，每条洗涤费用0.1元。问：如何安排，可使总费用最低？45为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益建立模型：设 xj第j天使用新毛巾的数量；yij第i天送第j天使用快洗 餐巾的数量；zij第i天送第j天使用慢洗餐巾的数量；第一天：x1=1000第二天：x2+y12=700第三天：x3+z13+y23=800第四天：x4+z14+z24+y34=1200第五天：x5+z15+z25+z35+y45=1500需求约束供应约束新购餐巾：x1+x2+x3+x4+x5520
29、0第一天送洗：y12+z13+z14+z151000第二天送洗：y23+z24+z25700第三天送洗：y34+z35800第四天送洗：y451200 xj0，yij0，zij0，（i=1,4；j=1,5）Min z=xj+0.2yij+0.1zij46为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益新 购 第一天第二天第三天第四天111110 M0.20.10.10.10MM0.20.10.10MMM0.20.10供应需求产量销 量5200 1000 700 800 1200MMM0.20.10100070080012001
30、5003700产销平衡表47为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益第3章学习要求掌握产销不平衡运输问题转化为产销平衡问题的处理办法；掌握掌握产销不平衡运输问题转化为产销平衡问题的处理办法；掌握运输问题在实践中的典型应用运输问题在实践中的典型应用；(1)(1)了解产销平衡运输问题的数学模型及其特点；了解产销平衡运输问题的数学模型及其特点；(2)(2)掌握运输问题的表上作业法，包括初始调运方案的确定、检掌握运输问题的表上作业法，包括初始调运方案的确定、检验数的计算、运输方案的调整方法；验数的计算、运输方案的调整方法；(3)(3)掌握产销不平衡运输问题转化为产销平衡问题的处理办法；掌握产销不平衡运输问题转化为产销平衡问题的处理办法；了解运输问题在实践中的典型应用。了解运输问题在实践中的典型应用。48为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢49