运筹学06运输题目精华

2020/1/1916.1运输问题的数学模型若一家公司拥有多个工厂，这些工厂位于不同的地点，并且生产同一种产品。这些产品要运输到不同的地点，以满足用户的需求。供应节点：这些工厂，它们是运输的起点；需求节点：用户所在点，它们是运输的终点或目的地。同时假定产品不能在供应节点之间运输，也不能在需求节点之间运输。公司面临的问题是：应如何组织运输，才能在满足供应节点的供应量约束和需求节点的需求量约束的前提下，使得运输成本最低。这类问题就是运输问题。朴霉贩长割计淌朱懂盖诛堵佣弗烧奉点址笆占逾斗术淀寿芭挖捂慨葵堡垒运筹学06-运输问题运筹学06-运输问题2020/1/192(1)运输问题数学模型xij——供应节点i至需求节点j的运输量；aij——供应节点i的可供应量，i=1,2,…,m；bij——需求节点j的需求量，j=1,2,…,n；cij——供应节点i至需求节点j的单位运输成本。ji,0xn,,2,1jbxm,,2,1iax.t.sxcZMinijm1ijijin1jijm1in1jijij和对所有的卷佳图鲍部钞忽签邮蓝垂去赚礼兰送妮乍旦缎拳队跟窗钱砾教湿腹炮颖涕运筹学06-运输问题运筹学06-运输问题2020/1/193根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：平衡型运输问题和不平衡型运输问题。平衡型运输问题：n1jjm1iiba不平衡型运输问题：n1jjm1iiba对于不平衡型运输问题通常通过设立虚拟供应节点或虚拟需求节点将其转化为平衡型运输问题求解。(2)运输问题的分类哨哨盅朱祸三揣眩备汗渔单纂因旁仁榔载枷阀汾嗜厌赚姥擒铀郁仑森嫂烘运筹学06-运输问题运筹学06-运输问题2020/1/194ji,0xn,,2,1jbxm,,2,1iax.t.sxcZMinijm1ijijin1jijm1in1jijij和对所有的平衡型运输问题的数学模型111111111111111111A模型包含变量：m×n个约束方程：m+n个秩：r(A)=m+n-1m行n行稀疏矩阵弹追摇拣辊机佐查钳怒蔗钡涡墩朽垮疹风镁奶勘门蛰船纬卡析鲜甸昧宴闭运筹学06-运输问题运筹学06-运输问题2020/1/195(3)运输问题的特征定理：平衡运输问题必有可行解与最优解。证：对于平衡运输问题令：n1jjm1iibaQji,0xn,,2,1jbxm,,2,1iax.t.sxcZMinijm1ijijin1jijm1in1jijij和对所有的n,,2,1jm,,2,1iQbaxjiij罐毒皖洽龟称苑炽攒毡秩星筋戴晒攀肄慧扰喻阳缎朵庸饮技逢妙溢左踢魁运筹学06-运输问题运筹学06-运输问题2020/1/196则有n,,2,1j;m,,2,1i0xijn,,2,1jbaQbQbaxm1ijijm1ijim1iijm,,2,1iabQaQbaxn1jijin1jjin1jij所以是运输问题的一个可行解。n,,2,1jm,,2,1iQbaxjiij又由于n,,2,1j;m,,2,1i0cij所以0xcZm1in1jijij且为极小化问题，故一定存在最优解。馆鸥炙骋停僵辜黑择侧崭酣短悟利副牟阂份记译虐缕钦媚梆茹薄克诚硕撮运筹学06-运输问题运筹学06-运输问题2020/1/197定义：凡能排列成形式的变量集合，用一条封闭折线将它们连接起来形成的图形称之为一个闭回路。构成回路的诸变量称为闭回路的顶点；连接相邻两个顶点的线段称为闭回路的边。1sss232111jijijijijix,x,,x,x,x或s1ss321211jijijijijix,x,,x,x,x互不相同其中：s321s321j,,j,j,ji,,i,i,i每个顶点都是转角点；每一条边都是水平线段或垂直线段；每一行或列若有闭回路的顶点，则必有两个几何性质挟铅卞阑泡携栓辱拥兢置旗倒垫祁洼碎骄醒砰咒键怎冀锌忍咬兴顷蚤青湾运筹学06-运输问题运筹学06-运输问题2020/1/198b1b2C11C21C31C12C22C32C13C23C33C14C24C34ABCa1a2a3b3b41234x11x21x31x12x22x32x13x23x33x14x24x24(1)x12,x13,x33,x32(2)x23,x13,x14,x34,x31,x21转角点转角点漓何女凶呵腰醚扰描恩涨南采菊厘瘴嘛巡荐羚曳牧捎雕贺巾婉阿昏阔瞎芬运筹学06-运输问题运筹学06-运输问题2020/1/199运输问题是一类特殊的线性规划问题对于平衡型运输问题：约束方程数为m+n个，但有一个冗余方程，所以独立方程数为m+n-1个，即秩r(A)=m+n-1。存在最优解当供应量和需求量均为整数时，存在整数最优解。基可行解中基变量个数为m+n-1个基可行解中基变量的重要特征：不含闭回路。任何一个非基变量与基变量含且仅含一个闭回路。运输问题的基本性质瓤洗寸俭嗽律翘灌润目昭蝴汞摹邀谰亮榷鹃邵饼趴晕泼箩变欢仟岔贮菇蹭运筹学06-运输问题运筹学06-运输问题2020/1/1910(4)平衡型运输问题的对偶问题ji,xn,,,jbxm,,,iax.t.sxcZMinijmijijinjijminjijij和对所有的021211111n,,,jmiv,ucvu.t.svbuaWMaxjiijjinjjjmiii212111，，，无符号限制由于r(A’)=m+n-1，独立的约束方程个数为m+n-1;而变量个数为m+n，则其中有一个自由变量闹隘途缓扫舞奋华骏汹痪症辩茹邪容跌勇牲可垣拎盯盒门株丈翰叁逮讨峦运筹学06-运输问题运筹学06-运输问题2020/1/1911用户1用户2用户3用户4分厂A675314分厂B842727分厂C5910619下月设备需求量(吨)22131213分厂名称运输成本(元/台)月生产能力(吨)例：海华设备厂下设三个位于不同地点的分厂A，B，C，该三个分厂生产同一个设备，设每月的生产能力分别为14台、27台和19台。海华设备厂有四个固定的用户，该四个用户下月的设备需求量分别为22台、13台、12台和13台。设各分厂的生产成本相同，从各分厂到各用户的单位设备运输成本如下表所示，而且各分厂本月末的设备库存量为零。问该厂应如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。奔社箱肿雕惠欠夕娃拷踞柑奈降勇锰涧孟避千复澜由弱休苟一趁嘲辜跨岁运筹学06-运输问题运筹学06-运输问题2020/1/19122321341sB=27sC=19d1=22d2=13d3=12d4=13sA=14供应量供应节点运输成本需求量需求节点6753842759106海华设备厂运输问题网络图郊慑场蛹瓜遣炳乌戚巧辟淋萎窒底奋避因吠布侮糊咙资寒癌阉枣瑶著才掇运筹学06-运输问题运筹学06-运输问题2020/1/1913海华设备厂运输问题的表格表示22136857495210376ABC14271912131234x11x21x31x12x22x32x13x23x33x14x24x34槐沏陡逃渤埠充方焰粒铸劈蘑典姚俩绝掂导职肖氢口戌坷祸啥谓蓉矾待恕运筹学06-运输问题运筹学06-运输问题2020/1/1914供应量约束需求量约束海华设备厂运输问题线性规划模型1,2,3,4j1,2,3i0x13xxx12xxx13xxx22xxx19xxxx27xxxx14xxxxst6x10x9x5x7x2x4x8x3x5x7x6xzMinij342414332313322212312111343332312423222114131211343332312423222114131211综遁戮锚篡咳仑凭史冷冲锄手篇平套圣洪督噬履平丫合挖骤簿豆浅尊湍蓬运筹学06-运输问题运筹学06-运输问题2020/1/1915不平衡运输问题(1)：供过于求设置虚拟需求节点232131sB=27sC=19d1=22d2=13d3=12sA=14供应量需求量6758425910供应节点运输成本需求节点4d4=13000妹霓巳沧角测员岩恍柬揩唾杨哉每仲颤一蔽奉蔫美芯传怎泻置得撒旭男场运筹学06-运输问题运筹学06-运输问题2020/1/1916不平衡运输问题(2)：供不应求设置虚拟供应节点221341sB=27d1=22d2=13d3=12d4=13sA=14供应量需求量67538427供应节点运输成本需求节点3sC=190000基肚歹俩羌使咎戈段羹篇现汰北铆鼓荣宋凶久眺脑限磕铣险栋吵地塔痈鞘运筹学06-运输问题运筹学06-运输问题2020/1/19176.2初始基可行解的确定获得初始基可行解的常用方法：西北角法最小元素法Vogel法晌湖落香个墓索它称郡旗骋斩殷阐厚恍潜森晋屑讹承餐燎臆擅筹挎卜阴矢运筹学06-运输问题运筹学06-运输问题2020/1/191812346753A148427B2759106C1922131213813131466(1)西北角法吸辕且墩位给鲤酋改揭窝连讹灿稠表局涨宿厄跺得梆雨敖昼石构澎足萝满运筹学06-运输问题运筹学06-运输问题2020/1/191912346753A14148427B272759106C19192213121322131213(2)最小元素法(0)扔牟狗硕济卢旧矗布曝撂屉匈审穗铜桨悸滩取逮曳飘族玖叶夷辕雁据庆埔运筹学06-运输问题运筹学06-运输问题2020/1/192012346753A14148427B12271559106C1919221312132213013(2)最小元素法(1)骨骑员冈柑兢晶淳蘸抨壹冻竭音嗜恳翰蒂亥翌城懦铣犹肃谐赤厨好酶季与运筹学06-运输问题运筹学06-运输问题2020/1/1921(2)最小元素法(2)12346753A131418427B12271559106C191922131213221300诧尾昭滨冷怂嘻喇锨庚却霖吵锦期年溺蝶零谋甚夏宗芳至迈歹否勘虫懂巾运筹学06-运输问题运筹学06-运输问题2020/1/1922(2)最小元素法(3)12346753A131418427B131227259106C19192213121322000个铡焉抬樱姐璃人唉粘帝售坪聘汝跋泣定贪掠善癌铺量擒酞府首咕琳姨陋运筹学06-运输问题运筹学06-运输问题2020/1/1923(2)最小元素法(4)12346753A131418427B131227259106C19190221312133000榜端友婉绕奇戎勃迅数馋磺回哑王税挣炽键力域庙区诌估腾贤豹歧毒肆点运筹学06-运输问题运筹学06-运输问题2020/1/1924(2)最小元素法(5)12346753A1131408427B131227259106C19190221312132000唐箱妹向汹炒劳衙缺杜阀咎尹嫡鞋吭完潮蹈扼篷喜款霜噪诵锋呸崩蜒狗扁运筹学06-运输问题运筹学06-运输问题2020/1/1925(2)最小元素法(6)12346753A1131408427B2131227059106C19190221312130000乖萝巨鼓坠丫徊长护桑馏浸故奠擂式些诊睛坦凭镊拥筐红共娶郝吠盔纳至运筹学06-运输问题运筹学06-运输问题2020/1/192612346753A148427B2759106C1922131213(3)Vogel法2211333123311331314413131912膛汐钱澈个目枪改摸所眨忙仑召殉喧募窘悟丘比洲压绑译祭槐锗愉伞肺立运筹学06-运输问题运筹学06-运输问题2020/1/19276.3最优性检