机理模型资料教育课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,机理模型资料,优化问题与规划模型,优化问题,：,与最大、最小、最长、最短等等有关的问题。,解决最优化问题的数学方法：,运筹学,运筹学主要分支,：,线性规划、非线性规划、整数规划；,动态规划、多目标规划、分层规划；,存贮论、排队伦、对策论、,决策论；图与网络分析。,线性规划,1.问题,例1 家具生产的安排,一.家具公司生产桌子和椅子，,每张桌子要用,15,个工时，,0.2,立方木材，售价,80,元,每张椅子要用,10,个工时，,0.05,立方木材，售价,45,元,用于生产的劳力共计,450,个工时，木材共有,4,立方米,问为达到最大的收益，应如何安排生产？,分析：,1.求什么？,生产多少桌子？,生产多少椅子？,2.优化什么？,收益最大,3.限制条件？,原料总量,劳力总数,x,1,x,2,Max f=80 x,1,+45 x,2,0.2 x,1,+0.05 x,2,4,15,x,1,+10,x,2,450,模型I：,以产值为目标取得最大收益.,设：生产桌子 x,1,张,椅子 x,2,张,(决策变量),将,目标,优化为：max f=80 x,1,+45x,2,对决策变量的,约束,：,0.2x,1,+0.05x,2,4,20 x,1,+5x,2,400,15x,1,+10 x,2,450,x,1,0,x2,0,0.2x,1,+0.05x,2,4,规划问题：在约束条件下求目标函数的最优值点。,规划问题包含,3,个组成要素:,决策变量、目标函数、约束条件,。,1.规划问题分类：,当目标函数和约束条件,都是决策变量的线性函数时，,称为,线性规划问题,否则称为,非线性规划问题,。,2.线性规划问题求解方法,称满足约束条件的向量为,可行解,称可行解的集合为,可行域,称使目标函数达最优值的可行解为,最优解.,图解法：,(,解两个变量的线性规划问题,),在平面上画出可行域（凸多边形），,计算目标函数在各极点,(,多边形顶点,),处的值,比较后，取最值点为最优解。,命题 1,线性规划问题的可行解集是凸集,可行解集：线性不等式组的解,0.2x,1,+0.05x,2,=4,15x,1,+10 x,2,=450,命题2,线性规划问题的目标函数(关于不同的目标值)是一族平行直线,目标值的大小描述了直线离原点的远近,命题3,线性规划问题的最优解一定在可行解集的某个,极点,上达到,(,穿过可行域的目标直线组中最远离,(,或接近,),原点的直线所穿过的凸多边形的,顶点,),.,求解可得,生产计划,x,1,=14,x,2,=24,净收益,f=80 x,1,+45x,2,=2200（元）,共用木材,0.2x,1,+0.05x,2,=4（立方）,共需劳力,15x,1,+10 x,2,=450（工时）,单纯形法,:使用线性代数的方法求解线性规划问题,通过确定约束方程组的基本解,并计算相应目标函数值,在可行解集的极点中搜寻最优,模型的标准化,正则模型,:,决策变量:x,1,x,2,x,n,.,目标函数:Z=c,1,x,1,+c,2,x,2,+c,n,x,n,.,约束条件:a,11,x,1,+a,1n,x,n,b,1,a,m1,x,1,+a,mn,x,n,b,m,模型的标准化过程,1,0,.引入松弛变量将不等式约束变为等式约束,若有 a,i1,x,1,+a,in,x,n,b,i,则引入x,n+i,0,使得,a,i1,x,1,+a,in,x,n,+x,n+i,=b,i,若有 a,j1,x,1,+a,jn,xn,b,j,则引入x,n+j,0,使得,a,j1,x,1,+a,jn,x,n,-x,n+j,=b,j,.,且有 Z=c,1,x,1,+c,2,x,2,+c,n,x,n,+0 x,n+1,+0 x,n+m,.,2,0,.将目标函数的优化变为目标函数的极大化.,若求 min Z,令 Z=Z,则问题变为 max Z.,3,0,.引入人工变量,使得所有变量均为非负.,若 x,i,没有非负的条件,则引入 x,i,0 和 x,i,0,令 x,i,=x,i,x,i,则可使得问题的全部变量均非负.,标准化模型,求变量 x,1,x,2,x,n,max Z=c,1,x,1,+c,n,x,n,s.t.a,11,x1,+a,1n,x,n,=b,1,a,m1,x,1,+a,mn,x,n,=b,m,x,1,0,x,n,0,讨论模型I,模型可以标准化为,求变量：x1,x2,x3,x4,max f=80 x1+45x2,s.t.20 x1+5x2+x3=400,15x1+10 x2+x4=450,x10，x20,x30,x40,令x3=x4=0,关于x1,x2 求解方程(4),(5)可得,x1=14，x2=24,代入目标函数（3）得到,f=80,14+45,24=2200,令x2=x3=0,关于x1,x4 求解方程(4),(5)可得,x1=20，x4=150,f=80,20+45,0=1600,令x1=x4=0,关于x2,x3 求解方程(4),(5)可得,x2=45，x3=170,f=80,0+45,45=2025,令x1=x2=0,关于x3,x4 求解方程(4),(5)可得,x3=400，x4=4500,f=80,0+45,0=0,令x1=x3=0,关于x2,x4 求解方程(4),(5)可得,x2=80，x4=350,非可行解,令x2=x4=0,关于x1,x3 求解方程(4),(5)可得,x1=30，x3=400,非可行解,最优解为,x1=14，x2=24，,目标函数值f=80,14+45,24=2200,定义:若代数方程AX=B的解向量有n-m个分量为零,其余m个分量对应A的m个线性无关列,则称该解向量为方程组的一个,基本解.,在一个线性规划问题中,如果一个可行解也是约束方程组的基本解,则称之为,基本可行解,命题 4,一个向量 x 是线性规划问题可行解集的一个,极点,当且仅当它是约束方程的一个,基本可行解.,一般线性规划的数学模型及解法：,min f=c,T,x,s.t.Ax,b,A1x=b1,LB,x,UB,Matlab求解程序,x,f=linprog(c,A,b,A1,b1,LB,UB),练习1：农作物种植安排,一个农场计划种蔬菜,棉花和水稻.预计每亩产值（利润）分别为110元,75元,60元.农场有50亩土地,20个劳动力,种植这三种农作物每亩地分别需要劳动力1/2 1/3 1/4,如何规划经营使经济效益最大.,设决策变量：,种植蔬菜x,1,亩,棉花x,2,亩,水稻x,3,亩，,求目标函数,f=110 x,1,+75x,2,+60 x,3,在约束条件,x,1,+x,2,+x,3,50,1/2x,1,+1/3x,2,+1/4x,3,20,x,1,，x,2,，x,3,0,下的最大值,练习2 资源分配,生产甲肥1吨,需要磷酸盐0.4吨,硝酸盐1.8吨,利润1万元;生产乙肥1吨,需要磷酸盐0.1吨,硝酸盐1.5吨,利润0.5万元.现有磷酸盐10吨,硝酸盐66吨,问甲、乙肥各生产多少吨获利最大？,设决策变量：,生产甲肥x,1,吨,乙肥x,2,吨，,求目标函数,f=1x,1,0.5x,2,在约束条件,0.4x,1,+0.1x,2,10,1.8x,1,+1.5x,2,66,x,1,，x,2,0,下的最大值。,模型 II,.,在不降低当前生产水平的前提下评估资源的贡献，使“成本”投入最低。,设每立方木材和每个工时投入“成本”,分别为 y,1,y,2,(,决策变量,),则,目标函数,为：,g=4y,1,+450y,2,对决策变量的,约束,0.2y,1,+15y,2,80,0.05y,1,+10y,2,45,y,1,0,y,2,0,求解可得,y,1,=100,（元/m,3,），y,2,=4（元/工时）,总成本,g=4y,1,+450y,2,=2200,（元）,产品成本（资源的贡献）,0.2y,1,+15y,2,=,80,0.05y,1,+10y,2,=,45,3.对偶问题(Dual Problem),：,A 是m,n 矩阵，,c,是 n,1向量（价格），,b,是 m,1向量（原料）,x,是 n,1向量（产出）,y,是 m,1向量（成本）,问题,max f=,c,T,x,s.t.A,x,b,x,i,0,i=1,2,n.,对偶问题,min f=,b,T,y,s.t.A,T,y,c,y,i,0,i=1,2,m.,对偶定理,:,互为对偶的两个线性规划问题,若其中一个有有穷的最优解,则另一个也有有穷的最优解,且最优值相等.,若两者之一有无界的最优解,则另一个没有可行解模型 I 给出了生产中产品的最优 方案,模型 II 给出了生产中资源的最低估价.,这种估价涉及到资源的有效利用,它不是市场价格,而是根据资源在生产中的贡献确定的估价.,我们称之为,影子价格,(shadow price),例2.生产5种产品P,1,P,2,P,3,P,4,P,5,单价为 550,600,350,400,200.,三道工序:,研磨,、,钻孔,、,装配,。,每种产品所需工时,P,1,P,2,P,3,P,4,P,5,I 12 20 0 25 15,II 10 8 16 0 0,III 20 20 20 20 20,各工序的生产能力（工时数）288 192 384,如何安排生产，收入最大。,模型：设 x,i,生产 P,i,的件数。,则max Z=550 x,1,+600 x,2,+350 x,3,+400 x,4,+200 x,5,。,s.t.12 x,1,+20 x,2,+0 x,3,+25 x,4,+15 x,5,288,10 x,1,+8 x,2,+16 x,3,+0 x,4,+0 x,5,192,20 x,1,+20 x,2,+20 x,3,+20 x,4,+20 x,5,384,x,i,0,有解 x,1,=12，x,2,=7.2，x,3,=x,4,=x,5,=0,Z=10920,分析：,1.,约束条件（生产能力）限制的情况,12x,1,+20 x,2,=288,288,10 x,1,+8x,2,=177.6,192,20 x,1,+20 x,2,=384,384,三个工序的生产能力不平衡,如果改变三个工序的生产能力，每个工序的单位增长会带来多少贡献？,2.,产品价格的影响,x,1,x,2,x,3,x,4,x,5,550 600 350 400 200,结果表明与 P,1,P,2,相比 P,3,P,4,P,5,，定价低了.,在当前的生产能力下，产品的定价不平衡,价格如何改变,生产才能达到平衡?,对偶问题有解:,工序的成本（贡献）：,w,1,=6.25,w,2,=0,w,3,=23.75,Z,opt,=6.25,288+0192+23.75384,=10920,约束条件(影子价格）的情况,X,1,：126.25+100+2023.75=550550,X,2,：206.25+80+2023.75=600600,X,3,：,0 6.25+160+2023.75=475.00350,X,4,：,256.25+00+2023.75=631.25400,X,5,：,156.25+00+2023.75=568.75200,4.灵敏度分析,当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能)时,最优解是否会随之变化?,通常假定变化的常数是某参数的线性函数.讨论参数取值与最优解的关系的问题,被称为参数线性规划(参见线性规划书籍).,例如,当农作物的价格发生变化时,生产计划是否应马上随之改变?,可以稍微改变价格，观察最优解的变化，讨论参数的灵敏性。,练习3 营养配餐,甲种食品每10克含5个单位的蛋白,10个单位的铁,单价3元;乙种食品每10克含7个单位的蛋白,4个单位的铁,单价2元.现需要一份食品,含有35个单位的蛋白,40个单位的铁,问如何配餐最省钱?,思考1,一家大建筑公司正在三个地点开掘。同时又在其他四个地点建筑，这里需要土方的填充。在1、2、3处挖掘产生的土方分别为每天150，400，325立方码。建筑地点A、B、C、D处需要的填充土方分别为175，125，225，450立方码。也可以从地点4用每立方码5美元的价格获得额外的填充土方。填充土方运输的费用约为一货车容量每英里20美元。一辆货车可以搬运10立方码的土方，每立方码土方每英里运输费2美元。下表给出了各地点间距离的英里数。求使公司花费最少的运输计划。,挖掘与建筑地点间的距离（英里）,接收填充土方的地点,挖掘地点 A B C D,1 5 2 6 10,2 4 5 7 5,3 7 6 4 4,4 9 10 6 2,农作物问题,某农户有100英亩土地合5000美元可供投资。每年冬季家庭成员可以贡献3500小时的劳动时间，而夏季为4000小时。如果这些劳动时间有富裕，家庭成员可以去附近农场打工，冬季每小时4.8美元，夏季每小时5.1美元。,现金收入来源于3种农作物（大豆、玉米、燕麦）以及2种家禽（奶牛、母鸡）。农作物不需要投资，但每头奶牛需要400美元初始投资，每只母鸡需要3美元初始投资。,思考2,每头奶牛需要1.5英亩土地，冬季需要付出100小时劳动时间，夏季50小时，每年净收益为450美元；相应地，每只母鸡不占用土地，冬季0.6小时，夏季0.3小时，年净收益为3.5美元。养鸡房最多容纳3000只母鸡，栅拦最多能容纳32头奶牛。,种植一英亩的大豆、玉米、燕麦分别需要冬季劳动时间20、35、10小时，夏季劳动时间30、75、40小时，年景收益分别为175、300、120美元。建立数学模型，帮助该农户确定养殖计划，使得年净收入最多。,思考题*：有4名同学到一家公司参加三个阶段的面试，公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不许插队（即在任何阶段4位同学的顺序是一样的）。由于4位置同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下所示：,秘书初试 主管复试 经理面试,同学甲 13 15 20,同学乙 10 20 18,同学丙 20 16 10,同学丁 8 10 15,这4位同学约定他们面试完后一起离开公司，假定现在是早上8：00，问他们最早何时能离开公司。,3.3 机理模型,优化问题与规划模型,课堂讨论总结,参加组数：19组，人数57人,参加评分：411,包饺子模型：10组，洗衣服9组,优胜组包饺子 五组,刘达通 胡勤 王威,马锡豫,张郑,李直,杨雅婷,洗衣服,刘轶群,文豪,封达道,孙鹏举,帅清,4.非线性规划,当目标函数和约束条件中包含有决策变量的非线性函数时，,称为,非线性规划问题,。,例3.某公司有6个建筑工地，位置坐标为(a,i,b,i,)(单位：公里),水泥日用量d,i,(单位：吨）,建两个日储量为 e=20 吨的料场，,需要确定料场位置(,x,j,y,j,)和运量,c,ij,，,使总吨公里数最小。,假设：,1.只考虑两点间的直线距离,2.各工地的需求稳定,令 c,ij,为料场 j 向工地 i 运送的水泥量,min z=f(z),s.t.A1xb1,A2x=b2,c1(x)0,c2(x)=0,LB x UB,MATLAB 程序,x,z=fmincon(,fun,x0,A1,b1,A2,b2,LB,UB,nonlcon,）,用随机搜索算法确定初始点：,在可行域0.5,8.75,0.75,7.75内简单地选取n个随机的的点，,计算目标函数在这些点的值，选择其中最小的点即可。,然后，可采用Matlab求最值点程序求出精确的最小值点:求函数fun在x0点附近的最小值点,5.0-1规划,如果要求决策变量只取0 或 1的线性规划问题,称为整数规划.,0-1 约束不一定是由变量的性质决定的,更多地是由于逻辑关系引进问题的,例4 背包问题,一个旅行者的背包最多只能装 6 kg 物品.,现有4 件物品,重量为 2 kg,3 kg,3 kg,4 kg,价值为 100 元,120元,90元,115元.,应携带那些物品使得携带物品的价值最大?,建模:记x,j,：旅行者携带第 j 件物品的件数,x,j,=0,1.,约束条件,2x,1,+3x,2,+3x,3,+4x,4,6,求x,j,使目标函数 f=x,1,+1.2x,2,+0.9x,3,+1.15x,4,最大.,用Lingo 软件求解0-1规划,Linear Interactive and General Optimizer,Model:,Max=x1+1.2*x2+0.9*x3+1.15*x4;,2*x1+3*x2+3x3+4*x40表示每件第 j 类仪器的科学价值;,a,j,0表示每件第 j 类仪器的重量.,每类仪器件数不限,但装载件数只能是整数.,飞船总载荷不得超过数 b.,设计一种方案,使得被装载仪器的科学价值之和最大,.,建模 记 x,j,为第 j 类仪器的装载数.,求 各种仪器的装载数量 x,j,（整数）,在约束条件,j,a,j,x,j,b,下,使得目标函数 f=,j,c,j,x,j,达到最大值.,7.用Lindo软件求解整数规划Linear Interactive and Discrete optimizer,max 3x1+2x2,st,2x1+3x2=14,2x1+x2=9,end,gin x1,gin x2,(或者用 gin 2),求 整数 x,1,x,2,Max Z=3x,1,+2x,2,s.t.,2x,1,+3x,2,14,2x,1,+x,2,9,8.规划问题的建模艺术,将实际问题归结为线性规划模型是一个探索创造的过程。,例7 钢材截短,有一批钢材,每根长7.3米.,现需做100套短钢材.,每套包括长2.9米,2.1米,1.5米的各一根.,至少用掉多少根钢材才能满足需要,并使得用料最省.,解:可能的截法和余料,第1种 7.3-(2.92+1.51)=0,第2种 7.3-(2.91+2.12)=0.2,第3种 7.3-(2.91+1.52)=1.4,第4种 7.3-(2.91+2.11+1.51)=0.8,第5种 7.3-(2.12+1.52)=0.1,第6种 7.3-(2.13)=1,第7种 7.3-(2.11+1.53)=0.7,第8种 7.3-(1.54)=1.3,设按第i种方法截 x,i,根钢材(决策变量).,目标函数,min f,=0.2x,2,+1.4x,3,+0.8x,4,+0.1x,5,+x,6,+0.7x,7,+1.3x,8,约束条件,2x,1,+x,2,+x,3,+x,4,100,2x,2,+x,4,+2x,5,+3x,6,+x,7,100,x,1,+2x,3,+x,4,+2x,5,+3x,7,+4x,8,100,x,i,0,i=1,8,用Matlab程序解得,x,1,=40 x,2,=20 x,5,=30,f=7,（实际上应要求x,i,为正整数。这是一个整数规划问题）。,例 8 存储问题,有5种药品 S=1,2,3,4,5 要存放,有些药品不能存放在一起,能存放在一起存放的药品为,=,1,2,1,3,5,2,4,5,3,1,4,5,不同的组合所需的存放费用不同,其中第 i 种组合的存储费用为 c,i,求这五种药品费用最低的储存方案。,令x,i,为存储组合 i 的决策变量:,x,i,=1 时存储第 i 个组合,否则 x,i,=0,求存储方案x,=(x,1,x,2,x,3,x,4,x,5,x,6,),在约束条件 x,1,+x,2,+x,5,1,x,1,+x,3,1,x,2,+x,4,1,x,3,+x,6,1,x,2,+x,3,+x,6,1,x,i,0，1，i=1,2,6,下使得目标函数 f=,c,i,x,i,最小.,习题,一,资源的最优配置策略,某工厂有1000台机器,生产两种产品 A,B,若投入 y 台机器生产A 产品,则纯收入为 5y.,若投入 y 台机器生产B 产品,则纯收入为 4y.,又知,生产A 种产品机器的年折损率为20%,生产B 种产品机器的年折损率为10%,问在5年内如何安排各年度的生产计划,才能使总收入最高.,习题二,混合泳接力赛由蛙泳、蝶泳、自由泳、仰泳组成。如何根据 4位运动员的4种游泳竞赛成绩安排混合泳接力队，以取得最佳成绩。,蛙泳 蝶泳 自由泳 仰泳,甲,99 60 59 73,乙,79 65 93 87,丙,67 93 63 81,丁,56 79 86 76,习题三,在大约1000m高空的某边长为160km的正方形区域内有若干架飞机作水平飞行。,区域内每架飞机的位置和速度向量均有计算机记录其数据，以便进行飞行管理。,当一架欲进入该区域的飞机到达区域的边缘,时,记录其数据后要立即计算并判断是否会与区域内的飞机发生碰撞。,如果会碰撞，则应计算如何调整各架（包括新进入的）飞机的飞行的方向角，以避免碰撞。,先假定条件如下：,1）不碰撞的标准为任意两架飞机的距离大于8km,2）飞机飞行方向角调整的幅度不超过30,0,3）所有飞机飞行速度均为每小时800km,4）进入该区域的飞机到达区域的边界时，,与区域内的飞机的距离应在60km以上,5）最多考虑6架飞机,6）不必考虑飞机离开次区域后的状况,请你对这个避免碰撞的飞行管理问题建立数学模型，列出计算步骤，,对以下数据进行计算（方向角误差不超过0.01,0,）。,要求飞机飞行方向角调整的幅度尽量小,设该区域四个顶点的坐标为,(0,0),(160,0),(160,160),(0,160),记录数据为,飞机编号,横坐标x,纵坐标y,方向角(,0,),1,150,140,243,2,85,85,236,3,150,155,220.5,4,145,50,159,5,130,150,230,新进入,0,0,52,注：方向角指飞行方向与x轴正向的夹角,