优化模型举例

2023/11/22数学建模方法2023/11/22建立数学模型的方法层次分析法最小二乘法差分法定性理论法优化法变分法回归分析法机理分析法统计分析法聚类分析法主成分分析法马尔科夫猜测法系统分析法模糊数学法灰色系统法2023/11/22优化模型2023/11/22优化模型是中国大学生建模竞赛常见的类型，占很大的比重。92年以来，优化模型有：94年A题：“逢山开路”设计最短路径。95年A题：“一个飞行治理问题”，线性规划和非线性规划模型。96年A题：“最优捕鱼策略”，以微分方程为根底的优化模型。2023/11/2296年B题：“洗衣节水问题”，以用水量为目标函数的优化模型。97年A题：“零件的参数设计”，随机优化模型。97年B题：“截断切割”，动态优化模型。98年A题：“投资的收益和风险”，双目标优化模型。98年B题：“灾情巡察的最正确路线”，0-1线性规划模型。2023/11/2299年A题：“自动化车床治理”，双参数规划模型。99年B题：“钻井布局”，非线性混合整数规划模型。00年B题：“钢管订购和运输”，二次规划模型。01年B题：“公交车调度”，双目标规划模型。02年A题：“车灯线光源的优化设计”，规划模型。2023/11/2203年B题：“露天矿生产的车辆安排”，非线性规划模型。04年B题：“电力市场的输电堵塞治理”，双目标线性规划模型。05年B题：“DVD在现租赁”，0-1规划模型。06年A题：“出版社的资源优化配置”，线性规划模型。2023/11/22〔一〕优化模型的数学描述下的最大值或最小值，其中设计变量（决策变量）目标函数将一个优化问题用数学式子来描述，即求函数在约束条件和可行域2023/11/22“受约束于”之意2023/11/22〔二〕优化模型的分类1.依据是否存在约束条件有约束问题和无约束问题。2.依据设计变量的性质静态问题和动态问题。3.依据目标函数和约束条件表达式的性质线性规划，非线性规划，二次规划，多目标规划等。2023/11/22〔1〕非线性规划目标函数和约束条件中，至少有一个非线性函数。2023/11/22〔2〕线性规划〔LP〕目标函数和全部的约束条件都是设计变量的线性函数。2023/11/22〔3〕二次规划问题目标函数为二次函数，约束条件为线性约束2023/11/225.依据变量具有确定值还是随机值确定规划和随机规划。4.依据设计变量的允许值整数规划〔0-1规划〕和实数规划。2023/11/22〔三〕建立优化模型的一般步骤1.确定设计变量和目标变量；2.确定目标函数的表达式；3.查找约束条件。2023/11/22最优捕食策略运输问题点菜问题旅行商问题〔四〕线性规划模型举例2023/11/22实例1最优捕食者策略假设存在一种捕食者，穴居A处，在B和C处有两个食物源X、Y。捕食者从巢穴A到区域B和C带回一单位的食物所需的时间估量为2分钟和3分钟。捕食者在区域B平均花2分钟捕获一单位食物X，而在区域C只花1分钟就捕获一单位食物Y。一单位X所产生的热量估量为25焦耳，一单位Y所产生的热量估量为30焦耳。假设捕食者每天不行超过120分钟用于从巢穴到食物区来回行走，同时每天不行能花80分钟以上搜寻食物。估量捕食者每天能获得的最大热量值是多少？2023/11/22一单位实物行走时间(分钟)捕获时间(分钟)热量(焦耳)X2225Y3130

假设捕食者每天能得到x单位的食物X和y单位的食物Y，则每天获得的热量值为2023/11/22xyo2x+y=802x+3y=12060404080P(30,20)U=25x+30yU=25*30+30*20=1350焦耳图解法2023/11/22编制Matlab程序：f=[-25,-30];Aeq=[];Beq=[];A=[2,3;2,1];B=[120;80];xm=[0;0];xM=[Inf;Inf];ff=optimset;ff.Tolx=1e-15;ff.TolFun=1e-20;TolCon=1e-20;[x,f_opt,key,c]=linprog(f,A,B,Aeq,Beq,xm,xM,[0;0],ff)2023/11/22设有某物资从m个发点A1,A2,…,Am输送到n个收点B1,B2,…,Bn，其中每个发点发出量分别为每个收点输入量分别为，并且满足从发点A到收点B的距离〔或单位运费〕是的，设为。一个调运方案主要由一组从发点到收点的输送量来描述。问题：寻求一个调运方案，使总运输费用到达最小。实例2运输问题2023/11/22B1B2….BnA1A2Ama1a2amb1b2….bn…..…..X11X12…..X1nX21X22….X2nXm1Xm2…..Xmn收点发点2023/11/22总的费用A1的总费用A2的总费用2023/11/22s.t.数学模型求解：单纯形方法。2023/11/22实例3点菜问题我们在餐馆中点菜，需要包含某些养分成份，但同时又希望总价格最低。下表是这个餐馆的局部菜单，请你供给合理的选菜方案。序号菜单价格(元)蛋白质淀粉维生素矿物质1菜肉蛋卷1810112炒猪肝21.501013色拉12.500104红烧排骨2310005咖喱土豆10.501006清汤全鸡3210012023/11/22建模设xi表示点序号为i的菜，则目标函数：约束条件：2023/11/22注：0-1规划问题可用Matlab求解〔薛定宇PP189〕，对于简洁问题亦可使用穷举法。下面用Matlab软件，求得结果：f=[18,21.5,12.5,23.0,10.5,32.0];Aeq=[];Beq=[];A=[-100-10-1;0-100-10;-10-1000;-1-1000-1;];B=[-1;-1;-1;-1];x=bintprog(f,A,B,[],[])‘x=100010;fopt=28.52023/11/22进一步考虑假设至少点四个不同的菜，结果又如何？2023/11/22利用matlab软件，得f=[18,21.5,12.5,23.0,10.5,32.0];Aeq=[];Beq=[];A=[-100-10-1;0-100-10;-10-1000;-1-1000-1;];[-1-1-1-1-1-1];B=[-1;-1;-1;-1;-4];x=bintprog(f,A,B,[],[])‘x=111010Fopt=62.52023/11/22点菜价格（元）点菜价格（元）1,2,3,6844,5,3,267.54,2,1,694.54,5,3,6784,5,1,2736,5,1,2824,5,1,683.56,5,3,1734,5,3,1646,5,3,276.51,2,3,562.5也可利用穷举法，得2023/11/22实例4旅行商问题(TravellingSalemanProblem〕TSP某商人由一城市动身，拟去已确定的n个城市推销产品，最终回到动身城市。设任意两城市间的距离都是的，要求找出一条每个城市都只到一次的旅行线路，使其总旅程最短。2023/11/22建模TSP又称为货郎担问题。给这些城市编号。动身城市为0，拟访问城市分别为1,2,…,n问题就转化为：其中为城市到的距离，最小。求一个的排序使得2023/11/22TSP的数学规划形式：表示进入且仅进入城j一次;表示离开且仅离开城i一次;保证连通性。其中表示假设该旅行商在访问城i后接着访问城j，则令，否则令〔P〕2023/11/22定理：0-1规划问题(P)即为旅行商问题。证明：将n+1个城市看作顶点，可以作为一个完全图〔即任意两点均有边相连图〕，{1,2,…,n}的每一排序对应于图中一个由0点动身经每一顶点一次最终回到0点的图。现在只需证明是(P)的可行解的充分必要条件对应的边组成完全图中的一个圈。2023/11/22(P)的可行解必构成完全图中的假设干回路〔由约束条件中的前两个得知〕。假设不然，设城构成不过0的回路由第三个条件得：上式两边相加得，冲突。现证明这些回路必经过0，从而只能是唯一的回路，即完全图中的一个圈〔Hamilton圈〕。2023/11/22反之，对每一由城0动身过每城一次回到城0的圈均可找到一组，使得条件3成立。事实上，可如下取之。现令，假设城i为第k个访问的城市，则令，于是，当时，，从而成立，证毕。2023/11/22模型求解1穷举法的不同排序有个，当n稍大时，很难找出最正确答案。这是个NP-完全问题。2近似算法贪欲算法西德曾对一个有318个点的问题找到了最优方案。3利用数学软件2023/11/22一个送报员从送报中心动身到五个小区送报，最终要回到送报中心。送报中心到各小区的距离及各小区间的距离均〔见表1〕，问送报员应按怎样的线路行驶较好？〔距离单位为千米〕送报线路安排2023/11/22表1送报中心及各小区间的距离01234500745861703109142430591035105014948991407561410970起终2023/11/2201234500745861703109142430591035105014948991407561410970贪欲算法送报中心及五个小区分别用0，1，2，3，4，5来记。算法的中心思想：每次查找最小距离。起终2023/11/2201234500745861703109142430591035105014948991407561410970起终2132023/11/2201234500745861703109142430591035105014948991407561410970起终021433052023/11/220214330501234500745861703109142430591035105014948991407561410970起终4572023/11/220214330501234500745861703109142430591035105014948991407561410970起终4572023/11/220214330501234500745861703109142430591035105014948991407561410970起终457992023/11/2201234500745861703109142430591035105014948991407561410970起终0214530439795总距离：37千米。2023/11/22应用例子某类工件在加工时需在一些指定的位置上钻孔。钻头从初始位置动身，到各处钻孔，最终回到初始位置，以便连续对下一工件加工。问应如何安排钻孔的次序，使钻头在加工过程中移动的总距离最小。2023/11/22报童的诀窍问题：报童每天早晨从报社购进报纸零售，晚上将没有卖掉的报纸退回。设报纸每份的购进价为b，零售价为a，退回价为c，假设a>b>c。即报童售出一份报纸赚a-b，退回一份赔b-c。报童每天购进报纸太多，卖不完会赔钱；购进太少，不够卖会少挣钱。试为报童筹划一下每天购进报纸的数量，以获得最大收入。2023/11/221.确定设计变量和目标变量2.确定目标函数的表达式每天的总收入为目标变量每天购进报纸的份数为设计变量3.查找约束条件查找设计变量与目标变量之间的关系设计变量所受的限制问题分析2023/11/22假设每天购进0份，则收入为0。假设每天购进1份，售出，则收入为a-b。退回，则收入为–(b-c)。假设每天购进2份，售出1份，则收入为a-b–(b-c)

。退回，则收入为–2(b-c)。售出2份，则收入为2(a-b)

。收入还与每天的需求量有关，而需求量是随机变量则收入也是随机变量，通常用均值，即期望表示。2023/11/22数学期望离散型随机变量X的概率分布为则随机变量X的数学期望值为连续型随机变量X的概率密度函数为则随机变量X的数学期望值为期望值反映了随机变量取值的“平均”意义！2023/11/221设每天购进n份，日平均收入为G(n)3每天需求量为r的概率f(r),r=0,1,2…2售出一份赚a-b；退回一份赔b-c模型假设与符号说明2023/11/22求n使G(n)最大每天的收入函数记为U(n)，则收入函数的期望值为建模2023/11/22将r视为连续变量模型求解2023/11/22使报童日平均收入到达最大的购进量应满足上式。由于2023/11/22售完的概率由于当购进份报纸时，是需求量不超过的概率是需求量超过的概率售不完的概率上式意义为：购进的份数之比，恰好等于卖出一份赚的钱与退回一份赔的钱之比。应当使卖不完与卖完的概率2023/11/22依据需求量的概率密度的图形可以确定购进量在图中用分别表示曲线下的两块面积，则Onr当报童与报社签订的合同使报童每份赚钱与赔钱之比越大时，报童购进的份数就应当越多。结论求解的几何意义2023/11/22留意求解技巧：连续化建模方法：从特殊到到一般归纳抽象1998年B题灾情巡察路线单旅行商到多旅行商1999年B题钻井布局网格的平行移动到旋转运动2023年B题钢管的订购与运输线形到树形2023年C题飞越北极球形到椭球形人口模型，战斗模型随机变量的目标函数：期望值航空公司的超额订票模型2023/11/22社会热点问题

2023/11/22经济进展问题2023/11/22环保问题2023/11/22新一轮全国性房价上涨已经开头，土地也随之成了抢手货。令地产商犯难的是，拿不到地，很可能会被淘汰出局，但多拿了地，又意味着要担当诸多风险。房价问题2023/11/22股票问题依照机构乐观的分析，2023年股票市场整体时机大于风险，但股指整体在高位运行，市场预期震荡幅度加大。2023/11/22煤矿治理问题2023/11/22高校本科评估就是一场闹剧高校

高校本科评估问题2023/11/22价格将走向何方?石油价格问题2023/11/22洞庭湖鼠患问题20亿田鼠洞庭“跑马圈地”2023/11/22某效劳部一周中的每天需要不同数目的雇员：周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人。现规定应聘者需连续工作五天，试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。课后作业1效劳员的聘用问题2023/11/22优化问题决策变量：周一到周日每天聘请的人数，记为目标函数：聘用总人数约束条件：每天需要的人数，由于每人连续工作5天，所以周一的雇员应是周四到周一聘用的，依据需要至少有50人，于是2023/11/22优化模型2023/11/22求解模型用LINDO求解美国芝加哥大学的linusSchrage教授于1980年前后开发的一套特地用于求解优化问题的软件包。包括4种主要产品：LINDO，LINGO，LINDOAPI，Wath’sBest!LINDO：linearInteractiveandDiscreteOptimizer.交互式的线性和离散优化求解器LINDGO：linearInteractiveandGeneralOptimizer.交互式的线性和通用优化求解器用以求解线性规划〔LP〕和二次规划〔QP〕问题用以求解非线性规划问题2023/11/22用LINDO求解TITLE效劳员聘用问题的LINDO模型MINx1+x2+x3+x4+x5+x6+x7SUBJECTTOMON)x1++x4+x5+x6+x7>=50TUE)x1+x2++x5+x6+x7>=50WED)x1+x2+x3++x6+x7>=50THU)x1+x2+x3+x4++x7>=50FRI)x1+x2+x3+x4+x5>=80SAT)x2+x3+x4+x5+x6>=90SUN)x3+x4+x5+x6+x7>=90ENDGIN7GeneralInteger求解模型2023/11/22结果输出主要结果OBJECTIVEFUNCTIONVALUE1)94.00000VARIABLEVALUE

x10.000000x24.000000x340.000000x4