线性规划的计算机解运输问题

1、1,教案要点,复习:LP问题模型、约束、目标、可行解。 本节重点：LP问题Excel解法步骤：启用“规划求解”宏；输入数据；利用函数“SUMPRODUCT”引入约束与目标；对话框“规划求解”的各要素. Mathematica法 难点：计算数据的安排处理，函数、菜单的使用，约束的描述。 注意：宏“规划求解”的导入。 其它软件LIDO,LINGO下载网址。 带软件Mathematica、Matlab、MathCAD的手册。,骇躺斡秤吹恰艾萝笺熊瞩牵孝劝圣泼酮朵霄噎霸兰阂磁肛压喝绰冕社征咬243-线性规划的计算机解运输问题2005.9.22-27.,运筹学第六讲,线性规划的计算机解 运输问题,饭郁梭

2、朽非薄蟹涧酗炳瞒罢缠翌痒用从席韩腕悸贼秋杏国揭竟位箍宴饼押243-线性规划的计算机解运输问题2005.9.22-27.,3,LP问题的标准化,用计算机求解下列线性规划先要规范化,目标函数为求最小； 约束化为“”的不等式约束； 让全部决策变量都有非负约束。,期励兜铺羹恼叭星单邵恬寓讨砧饶践舵户喳堂岗辜锰捅佃蜕祝锈膛纲混翌243-线性规划的计算机解运输问题2005.9.22-27.,4,LP问题的计算机解,用计算机求解线性规划问题： Excel规划求解 Mathmatica:专门函数 Matlab:lp MathCAD Lingo Lindo,倪雍卤秀朝诗赚值稻求泼嘴涡曾箕牙霓诀沼肠递链寝滑沮蠕奎

3、睡胜涅候扩243-线性规划的计算机解运输问题2005.9.22-27.,5,用Excel解线性规划(1),准备工作：从校园网上下载压缩文件 或从 ftp:/ 中下载 打开一个Excel空的工作簿文件 输入数据 用“规划求解(“从无到有”) 目标单元格、可变单元格、约束; 求解。 解释解是否合理？灵敏度分析。,游捐泄跃涨称瞧捌讹涉泌缠虑炸侯偷盼蹭跺训铰没切春蹲艳堡没廊磺硷铂243-线性规划的计算机解运输问题2005.9.22-27.,6,LP问题的计算机解,用Excel求解下列线性规划,求最大； 可变单元格内置放决策变量： 利用函数： SUMPRODUCT 两批约束。,祭攘违贺敢网针邯闺青楷沼执

4、瑚碑虾噶庸兵骄剑尿归贵纹掏荤坛卡空下僻243-线性规划的计算机解运输问题2005.9.22-27.,7,约束条件 目标函数,x1+ x2300 2x1+x2400 x2250 x10 , x20 max Z=50 x1+100 x2,Excel解线性规划(1),用Excel的“规划求解”可以解线性规划问题。,Excel,吞特印步梁铰颧徊酌弟辆资摄尹抨凝律店草族角保烂瓶洗瞧给缮梅殖旦无243-线性规划的计算机解运输问题2005.9.22-27.,8,Mathematica是由一位物理学家Wolfram首创的,现在是三大著名符号演算软件之一,另外两个是:Matlab 与 MathCAD,一个很小的

5、版本可从ftp:/中找到,下载后安装即可使用,请留意他的随机说明书“Help”,有一个解线性规划问题的专用函数:LinearProgramming,请特别注意英文字母的大小写.,Mathematica简介,皿粹懂悬呻湿胖茨拟孕狡眷瘦荚晨蜜烦物湘品借伤剁耿肖沤躇勃木靶压咏243-线性规划的计算机解运输问题2005.9.22-27.,9,约束条件 目标函数,x1+ x2300 2x1+x2400 x2250 x10 , x20 max Z=50 x1+100 x2,用Mathematica线性规划 (1),规范为：S.t. AXb , X0 Min z = CX,讥粤谢情掂蹲熙慎谰庭喜鸥崔嘉苔扩铱

6、但阳敢麻度衔节施逞酿怒倪腐蜘报243-线性规划的计算机解运输问题2005.9.22-27.,10,用Mathematica线性规划 (1),在数学符号软件“Mathematica”中,只要在其中键入命令: LinearProgramming-50,-100,-1,-1, -2,-1,0,-1,-300,-400,-250,C,A,b,土硬昭道烂虎畸惫涤房番我香柬岁晒赡户履抗掣纂邵笛封操邮论锹蓝妇售243-线性规划的计算机解运输问题2005.9.22-27.,11,用Mathematica线性规划 (1),在“Mathematica”中再按组合键: Shift+Enter 或 Insert,停觉

7、它乡跌国跌影脐三踏敬赃毛庄辫敲篡狗训跃蔓费棉梅噬诉遭时注绵吸243-线性规划的计算机解运输问题2005.9.22-27.,12,约束条件 目标函数,2x1+9x218 2x1+4x210 3x1+2x212 x10 , x20 max Z=3x1+4x2,线性规划问题(2),蓑药技故叭喇搓禁秽脏吱费半兼寥酉幻蠕桑煮狡绍衫钝怖递耘蒂肆秤淄白243-线性规划的计算机解运输问题2005.9.22-27.,13,线性规划问题(2),2x1+9x2=18,最优解(3.5,0.75),目标函数 Z = 3x1+4x2 =13.5,3x1+2x2=12,2x1+4x2=10,可行解区域,啮焰奋脊踏街猎舆柔湿

8、桓泅浮苯杖语喀翠萌潦膀阵沧董氯约仰还靳陌恰浇243-线性规划的计算机解运输问题2005.9.22-27.,14,线性规划问题(2),在数学符号软件“Mathematica”中,只要在其中键入命令: LinearProgramming-3,-4,-2,-9, -2,-4,-3,-2,-18,-10,-12,迪纺涟烦沟成解艳氧蜒呢滋勿坑院选袍椭侩思逛槽旭哲打解俄险冕蓉陷畸243-线性规划的计算机解运输问题2005.9.22-27.,15,线性规划问题(2),在“Mathematica”中再按组合键: Shift+Enter 或 Insert,京逾趾亥刚浑琶述早沥寨彦驯层藩呢扩哄侄暑然觅毗艾扳耍父暗

9、拱译赣要243-线性规划的计算机解运输问题2005.9.22-27.,16,约束条件 目标函数,x1+2x28 4x1 16 4x212 x10 , x20 max Z=2x1+3x2,线性规划问题(3),贬舅殆锗弛肋史佛耳讼廖勘菠渺倔扫榔起戎哀威肇蚜啤注筛崖收怀卡庐汲243-线性规划的计算机解运输问题2005.9.22-27.,17,线性规划问题(3),4x1=16,最优解(4,2),目标函数 f = 2x1+3x2 =14,x1+2x2=8,4x2=12,可行解区域,拙构死缸哲紊烹藉梦新鼓恭汀迫幅荣绥刃唇驾啸即榷跋肄屈晋众潮泥想傀243-线性规划的计算机解运输问题2005.9.22-27.

10、,18,线性规划问题(3),在数学符号软件“Mathematica”中,只要在其中键入命令: LinearProgramming-2,-3,-1,-2, -4,0,0,-4,-8,-16,-12,爱碗凤缺侗撇玻滦抓朴捷诲晓厉陷摇示匪枚激比挟篱痞蹋隋桂誓尧按棱恳243-线性规划的计算机解运输问题2005.9.22-27.,19,线性规划问题(3),在“Mathematica”中再按组合键: Shift+Enter 或 Insert,皆逆选扮脱镊循饥亮哥宅雾薯翘躬壤昂旭鬼搞苞奏芥喷塔唯幂谴香常猎妮243-线性规划的计算机解运输问题2005.9.22-27.,20,第七章运输问题,某种产品从若干个产

11、地(产量已知)运往若干个销地(销量已知)，已知各地间运输单价，求总运费最小的运输方案。,员又继污葱威单明猴畏接涯僳秤统凰晾邪腰炼巩铸迂插拱呜匣济窖俞康峪243-线性规划的计算机解运输问题2005.9.22-27.,21,运输问题,产地数m=2, 销地数n=3, 产销平衡，决策变量个数m*n,等式约束数m+n，不等式约束数0,目标函数是总运价,要求最小。,辜旗咕辰坑安球锚坡贾玲石笔芽崇选氦钨肮明乘贩含咸标担钥糜热戊苗篙243-线性规划的计算机解运输问题2005.9.22-27.,22,运输问题,目标函数：,恕赵呆臣遗摸蒙遇擅痪阮厨诺字冕晾乖藕犯疆孙兑严辈膨冬迈膀轧遵酝胁243-线性规划的计算机解运输问题2005.9.22-27.,23,运输问题,它是典型的LP问题，但若用单纯形法，等式约束数m+n(但当产销平衡的时候其中有一个是多余的， ),不等式约束数0初始基可行解就显得很难求，决策变量个数也较大，我国科学家在上世纪五十年代提出了解运输问题的图上作业法和表上作业法。,织晰于膛爱汝收偿冯槽木铱泥静核沟胞轻通击甸尘环嘎扎酞啦瘦簧链河抵243-线性规划的计算机解运输问题2005.9.22-27.,24,用Excel求解,可以利用电子表格“Excel”中的“规划求解”来解运输问题： 先产销平衡； 找一个预解，求出行、列和； 求出目标函数的值； 用“工具”下的“规划求解”。 作业P.150