版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第三章运输问题3.1运输问题及其数学模型
3.2表上作业法3.3运输问题的进一步讨论2/6/20231浙江科技学院经济管理学院管工系本章学习要求掌握表上作业法及其在产销平衡运输问题求解中的应用掌握产销不平衡运输问题的求解方法2/6/20232浙江科技学院经济管理学院管工系3.1运输问题及其数学模型1.运输问题的一般提法:假设有m个生产地点,可以供应某种物资(以后称为产地),用Ai来表示,i=1,…,m,有n个销地,用Bj来表示,j=1,…,n,产地的产量和销地的销量分别为ai,bj,从产地Ai到销地Bj运输一个单位物资的运价为Cij,这些数据可汇总于下表,在假设产销平衡的条件下,即∑ai=∑bj,问该如何调运物品使总运费最小?B1B2…Bn产量A1C11C12…C1na1A2C21C22…C2na2………………AmCm1Cm2…Cmnam销量b1b2…bn2/6/20233浙江科技学院经济管理学院管工系建模:设xij表示从Ai到Bj的运量,则所求的数学模型为:minΖ=ΣΣcijxij
s.t.Σxij=aii=1,…mΣxij=bjj=1,…,nj=1ni=1mi=1mj=1nxij≥0i=1,…m,j=1,…,n2/6/20234浙江科技学院经济管理学院管工系2.例如:三个产地四个销地,用网络表示2312341b1=22b2=13b3=12b4=13a2=27a3=19a1=14产地运价销地6753482759106产量销量总产量60吨总销量60吨产销平衡的运输问题2/6/20235浙江科技学院经济管理学院管工系运输问题线性规划模型产地约束销地约束2/6/20236浙江科技学院经济管理学院管工系运输问题的表格表示2/6/20237浙江科技学院经济管理学院管工系注意:运输问题有可行解的充要条件为:平衡运输问题有最优解平衡运输问题的约束方程组的系数矩阵的系数矩阵A的秩为m+n-1运输问题的求解过程与单纯形法类似,只是更简单,通常称表上作业法,而且是求解极小化问题。运输问题的系数矩阵具有什么特点?运输问题的LD是怎样的?2/6/20238浙江科技学院经济管理学院管工系3.2表上作业法初始基可行解的确定最优性检验基变换2/6/20239浙江科技学院经济管理学院管工系运输问题基的表示
m个产地、n个销地的运输问题,除了满足可行的条件外,任何一个基要满足以下条件:基变量的个数为m+n-1;基变量不能形成闭回路;2/6/202310浙江科技学院经济管理学院管工系123412312341231234123123412312341231234123基在运输表中的表示2/6/202311浙江科技学院经济管理学院管工系123412312341231234123123412312341231234123运输表中同行同列组成回路的变量2/6/202312浙江科技学院经济管理学院管工系一.初始基可行解的确定西北角法最小元素法沃格尔法2/6/202313浙江科技学院经济管理学院管工系1.西北角法813131466方法:优先满足运输表中左上角空格的供销要求-填一个数字只能划去一行或一列2/6/202314浙江科技学院经济管理学院管工系2.最小元素法12015130113021930120200方法:按单位运价的大小,决定供应的先后,优先满足单位运价最小者的供销要求(就近供应)2/6/202315浙江科技学院经济管理学院管工系3.沃格尔法3212323311*3113行罚数列罚数414*13*1219方法:计算出每一行及每一列中单位运价最小和次小的两个元素之间的差值,再从差值最大的行或列中找出单位运价最小者,优先满足其供销关系。2/6/202316浙江科技学院经济管理学院管工系二.最优性检验-求非基变量的检验数闭回路法位势法2/6/202317浙江科技学院经济管理学院管工系1.闭回路法方法求非基变量检验数σij,以该变量所在格为顶点,其他顶点为基变量找一个闭回路,从该非基变量顶点为“+”,“-”,“+”,“-”依次加减其运价,即为检验数。意义:以该非基变量充当基变量时单位运量运费的损失。当所有的σij≥0,则已得运输问题的最优解。即单位物品由i-j引起总运费的变化。2/6/202318浙江科技学院经济管理学院管工系8131314661.闭回路法(1)σ12
=c12-c22+c21-c11=7-4+8-6=552/6/202319浙江科技学院经济管理学院管工系8131314661.闭回路法(2)5σ13
=c13-c23+c21-c11=5-2+8-6=552/6/202320浙江科技学院经济管理学院管工系8131314661.闭回路法(3)55σ14
=(c14-c34+c33-c23+c21-c11)=3-6+10-2+8-6=772/6/202321浙江科技学院经济管理学院管工系8131314661.闭回路法(4)557σ12
=c24-c34+c33-c23=7-6+10-2=992/6/202322浙江科技学院经济管理学院管工系8131314661.闭回路法(5)5579σ32
=c32-c24+c23-c33=9-4+2-10=-3-32/6/202323浙江科技学院经济管理学院管工系8131314661.闭回路法(6)5579-3σ31
=c31-c21+c23-c32=5-8+2-10=-11-112/6/202324浙江科技学院经济管理学院管工系2.位势法该法也称对偶变量法,我们知道一般标准运输问题的对偶问题为:Ui,Vj无约束由LP中σij的定义:
σij
=Cij-CBB-1Pij=Cij-Y’Pij=Cij-(u1,u2,……,um,v1,v2,……,vn)Pij=
cij-(ui+vj)对基变量而言:
cij=(ui+vj)由m+n-1个基变量对应m+n-1个线性方程而LD的变量有m+n个,对偶问题有无穷多解,则可设其中一个最优解为0,而推导出其他分量。从而求出非基变量的检验数。2/6/202325浙江科技学院经济管理学院管工系8131314662.位势法(1)uivj0622010-42/6/202326浙江科技学院经济管理学院管工系8131314662.位势法(2)uivj0622010-45579-13-32/6/202327浙江科技学院经济管理学院管工系三.基变换-闭回路法与单纯形法一样,如果所有非基变量检验数σij≥0,则该基解为最优解,否则不是最优解,需要进行基变换,换入变量的确定方法一样,设换入变量xlk的检验数为σlk
,换出变量为xsf
以xlk和基变量为顶点找一个闭回路,分别标号”+”,”-”,”+”,”_”;在标号为”-”的最小的运量为调整量,在闭回路上进行调整,“+”的加“-”的减,当存在xsf为0时,为换出变量,得一新的基可行解,再求检验数。2/6/202328浙江科技学院经济管理学院管工系8131314661.基变换-确定换入换出变量5579-3-11-11+-+-62/6/202329浙江科技学院经济管理学院管工系8131314661.基变换-得新的基解+-+-62122/6/202330浙江科技学院经济管理学院管工系1313141.基变换-得新的基解62122/6/202331浙江科技学院经济管理学院管工系确定初始基础可行解西北角法沃格尔法求非基变量的检验数闭回路法对偶变量法确定进基变量确定离基变量得到新的基础可行解表上作业法总结沿闭回路调整运量最小元素法2/6/202332浙江科技学院经济管理学院管工系单纯形法与表上作业法比较单纯形法(Min)表上作业法确定初始基变量XB+松驰变量+(人工变量)XB——系数矩阵为I,m个其余XN最小元素法、沃格尔法等XB——数字格,m+n-1个XN——空格检验数基变量j=0非基变量j=cj-cBB-1pj基变量ij=0非基变量ij=cij-Ui-Vj调整进基:min{j∣j<0}出基:θ=min{bi/aik,aik>0}进基:min{ij∣ij<0}出基:θ=min{闭回路上偶数点xij}2/6/202333浙江科技学院经济管理学院管工系例(P104,3.7):该问题是一个产销平衡问题,也是求极小化问题,可用表上作业法求解。2/6/202334浙江科技学院经济管理学院管工系解:1.用沃格尔法求初始基可行解行罚数列罚数3122111*5012*6254*215*1332/6/202335浙江科技学院经济管理学院管工系解:2.用位势法求非基变量检验数(求位势)562133uivj01410012/6/202336浙江科技学院经济管理学院管工系解:2.用位势法求非基变量检验数(求检验数)562133uivj0141001361115由此可知,所有非基变量检验数全≥0,已得最优调运方案;总运费为:5×1+3×4+6×1+2×0+3×5+1×1=392/6/202337浙江科技学院经济管理学院管工系3.3运输问题的进一步讨论一、产销不平衡问题(变成产销平衡问题)当总产量>总销量时,可增加一个假想销地Bn+1,销量=∑ai-∑bj,Ci,n+1=0,当总产量<总销量时,可增加一个假想产地Am+1,产量=∑bj
-∑ai
,Cm+1,j=02/6/202338浙江科技学院经济管理学院管工系例:某建筑公司有A1、A2、A3三个水泥库,其水泥贮存量分别为30吨、50吨、60吨,四个工地B1、B2、B3、B4需要水泥的数量依次为15吨、10吨、40吨、45吨,已知从各库到各工地运送每吨水泥的费用如下表,求使运费最少的调运方案?B1B2B3B4产量27040806050A310030502060销量15104045140110解:计算∑ai=140,∑bj=110,∑ai>∑bj(产量>销量)所以要虚构一销地B5,其销量b5=30,而ci5=0,这样,就转化成了一个产销平衡问题。
B1B2B3B4B5产量A130508040030A270408060050A3100305020060销量15104045301401402/6/202339浙江科技学院经济管理学院管工系例如:B1B2B3B4产量A13113109A219284A3741057销6/202340浙江科技学院经济管理学院管工系二、一些变形和推广1、最大化问题1)找出单位物资效益表(cij)中的最大元素M,即M=max{cij}2)令c’ij=M-cij,并视为运价。3)由c’ij构成单位运价表,按通常的表上作业法求解,求得最优解后把所得结果转换为原问题的答案。2、销量不确定(有最高需求和最低需求)设销地Bk的最低需求为bk’,最高需求为bk”,这时可把看作Bk’和Bk”两个销地,Bk’需求量bk’,Bk”的需求量bk”-bk’2/6/202341浙江科技学院经济管理学院管工系例:设某种材料有A1、A2、A3三个生产厂家,其产品供应B1、B2、B3、B4四个城市,假定等量的材料在这些城市的使用效果相同,已知各建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材的运价如表所示,求使运费最少的调运方案?B1B2B3B4产量A11613221750A21413191560A3192023M50最低需求3070010最高需求507030不限2/6/202342浙江科技学院经济管理学院管工系B1B2B3B4产量A11613221750A21413191560A3192023M50最低需求3070010最高需求507030不限B1’B1’’B2B3B4’B4’’销量302070301050A1A2A3A4产量50605050161419M1614190131320M22192301715MM1715M02/6/202343浙江科技学院经济管理学院管工系4、缺货损失问题
如下表,设销地1不允许缺货;销地2缺货,单位损失费3元;销地3缺货,单位损失费2元,问如何处理?B1B2B3产量A151710A264680A332515销量655525B1B2B3产量A151710A264680A332515销量655525A440M323、指定销售问题如规定销地1的需求量必须由产地4供应,如何处理?1)直接令x41=b12)令c41=-M,或者c11=c21=c31=M这样销地1的需求量肯定是由产地1供应了。2/6/202344浙江科技学院经济管理学院管工系三、生产与存储问题例:某厂按合同须于当年每个季度末分别提供10、15、25、20台同一规格的起重机,已知该厂各季度的生产能力及生产每台起重机的成本如表所示,若生产出来的起重机当季不交货,每台每积压一个季度工厂需支付保管及维护费0.15万元,试问在按合同完成任务的情况下,工厂应如何安排生产计划才能使全年消耗的生产与存贮费用的总和最少?季度工厂生产能力(台/季)成本(万元/台)交货量(台)12510.81023511.101533011.002541011.30202/6/202345浙江科技学院经济管理学院管工系发货点:生产起重机的四个季度
发货量:生产能力
收货点:按合同交付起重机的四个季度
收货量:按合同提供起重机的数量
cij=第i季度每台起重机的生产成本+(j-i)个季度每台起重机的存贮费(j>i)12345发量(台)125235330410收量(台)101525203010.8010.9511.1011.25
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026-2027学年上学期单元测试高一地理测试卷及答案
- 2026-2027学年上学期单元测试七年级化学专题训练卷及答案
- 2025法律职业资格商经法考前模拟及答案
- 2025大学英语四级词汇语法经典例题及答案
- 2025叉车司机场内机动车辆基础易混辨析题及答案
- 数据中心冷冻水二次泵变频调试方案
- 航空客户满意度实施评估表
- 特别管控危险化学品目录(第一版)及管控措施
- 酒店与度假村经理战略执行评估表
- 服务器硬件故障诊断与维修操作手册
- 2026秋小学人教版数学五年级上册第五单元学情测试练习卷含参考答案
- 大专护理专业毕业综合考试题(含详细答案)
- 工程力学 第2版 课件 第7章-扭转
- 消毒供应室降低纸塑包装物品灭菌后水迹发生率品管圈PDCA案例所有图表均可以直接点击编辑修改
- 银行对公业务分配制度
- 乡镇卫生院人员招聘制度
- DB11∕T 498-2021 南美白对虾淡水养殖技术规范
- 林草工程技术人员法律法规与职业道德试题库
- 难点解析-山东省海阳市中考数学真题分类(二元一次方程组)汇编必考点解析试题(含答案及解析)
- 内容电商运营(AIGC版 微课版 第2版)-课程标准、课程整体设计
- 20kV及以下配电网建设项目扩大工程量清单(2025年版)
评论
0/150
提交评论