数学规划模型概述

数学规划模型

实际问题中的优化模型x~决策变量f(x)~目标函数gi(x)0~约束条件多元函数条件极值n和m较大最优解在边界上取得数学规划线性规划非线性规划整数规划不等式约束无法用微分法求解特殊情形1）无约束2）二次规划基本概念多峰函数，存在局部最大(小)和整体最大(小)函数曲面图形图形解释基本概念无约束非线性规划算法1、选择初始解x0；2、对第k次迭代解xk，确定搜索方向dk∈Rn，并在此方向上确定步长αk，令xk+1=xk+αkdk，使得f(xk+1)<f(xk);3、若xk+1符合给定的迭代终止条件，如‖xk+1-xk‖＜ε，停止迭代，最优解近似为xk+1。算法概述数值迭代法:确定搜索方向有如下方法：1、最速下降法；2、牛顿法；3、拟牛顿法；在实际应用中，真正无约束的情况是很少的。无约束非线性规划算法算法概述数值迭代法:1、可行方向法；2、罚函数法；3、梯度投影法；4、逐步二次规划法（SQP）（SequentialQuadraticProgramming）MATLAB软件中主要采用SQP算法。约束非线性规划算法算法概述Matlab能求解的优化模型fgoalattain多目标规划fminbnd有界标量非线性优化问题fmincon

约束非线性极小化fminimax极小极大最优化fminsearchfminunc

无约束非线性最优化fseminf半无限极小化linprog

线性规划quadprog

二次规划MATLAB软件求解优化工具箱主要命令混合泳接力队的选拔指派(Assignment)问题：有若干项任务,

每项任务必有且只能有一人承担，每人只能承担一项，不同人员承担不同任务的效益(或成本)不同，怎样分派各项任务使总效益最大(或总成本最小)?

人员数量与任务数量相等

人员数量大于任务数量(本例)

人员数量小于任务数量

?建立0-1规划模型是常用方法如何选拔队员组成4

100米混合泳接力队?例1混合泳接力队的选拔

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候选人的百米成绩枚举法：组成接力队的方案共有5!=120种。目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=0

0-1规划模型

cij(秒)~队员i

第j种泳姿的百米成绩约束条件每人最多入选泳姿之一

ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有1人小规模问题可用枚举法求解模型求解

最优解：x14=x21=x32=x43=1,其它变量为0;成绩为253.2(秒)=4’13”2MIN66.8x11+75.6x12+87x13+58.6x14+……+67.4x51+71x52+83.8x53+62.4x54SUBJECTTOx11+x12+x13+x14<=1

……x41+x42+x43+x44<=1x11+x21+x31+x41+x51=1

……x14+x24+x34+x44+x54=1ENDINT20

输入LINDO求解

甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.模型求解

MODEL:sets:person/1..5/;position/1..4/;link(person,position):c,x;endsetsdata:c=66.8,75.6,87,58.6,57.2,66,66.4,53,78,67.8,84.6,59.4,70,74.2,69.6,57.2,67.4,71,83.8,62.4;enddata输入LINGO求解

min=@sum(link:c*x);@for(person(i):@sum(position(j):x(i,j))<=1;);@for(position(i):@sum(person(j):x(j,i))=1;);@for(link:@bin(x));END

小结：数学规划问题的化简尽量化非线性问题为等价或近似线性问题；有些整数变量可用实数变量近似代替；灵活使用0-1变量可化简复杂的函数关系；尽量减少变量个数；缩小非线性规划的可行域可加快计算速度；冗余的约束条件可以删去；适当缩小数据间的数量级差可提高计算精度。Lingo简介Lingo包含Lindo功能,Lindo模型可在Lingo环境运行Lingo增加了非线性规划Lingo的基本模型(非编程)Lingo提供了编程功能Lingo风格模型(编程功能)Lingo的基本用法(非编程)model:Title钢管下料LINGO模型;min=x1+x2+x3;x1*r11+x2*r12+x3*r13>=50;x1*r21+x2*r22+x3*r23>=10;x1*r31+x2*r32+x3*r33>=20;x1*r41+x2*r42+x3*r43>=15;4*r11+5*r21+6*r31+8*r41<=19;4*r12+5*r22+6*r32+8*r42<=19;4*r13+5*r23+6*r33+8*r43<=19;4*r11+5*r21+6*r31+8*r41>=16;4*r12+5*r22+6*r32+8*r42>=16;4*r13+5*r23+6*r33+8*r43>=16;x1+x2+x3>=26;x1+x2+x3<=31;x1>=x2;x2>=x3;@gin(x1);@gin(x2);@gin(x3);@gin(r11);@gin(r12);@gin(r13);@gin(r21);@gin(r22);@gin(r23);@gin(r31);@gin(r32);@gin(r33);@gin(r41);@gin(r42);@gin(r43);end注：0-1规划@binLingo编程模型构成主体MODEL:--END集合段SETS--ENDSETS数据段DATA--ENDDATA初始段INIT--ENDINIT计算段CALC--ENDCALC集合基本集合派生集合函数@for(集合|条件:表达式)对集合中满足条件的元素循环执行表达式@sum(集合|条件:表达式)对集合中满足条件的元素求表达式的和关系运算符（“集合|条件”里使用）#LT#(lessthen),#EQ#,#LE#,#GT#,#GE#类似Lingo编程model:Title钢管下料LINGO模型;SETS:!集合段;NEEDS/1..4/:LENGTH,NUM;CUTS/1..3/:X; PATTERNS(NEEDS,CUTS):R;ENDSETSDATA:!数据段; LENGTH=4568; NUM=50102015;ENDDATAINIT:!初始段

X=101010;ENDINIT!模型目标与约束开始;min=@SUM(CUTS(J):X(J));@FOR(NEEDS(I):@SUM(CUTS(J):X(J)*R(I,J))>NUM(I));@FOR(CUTS(J):@SUM(NEEDS(I):LENGTH(I)*R(I,J))<19);@FOR(CUTS(J):@SUM(NEEDS(I):LENGTH(I)*R(I,J))>16);@SUM(CUTS(I):X(I))>26;@SUM(CUTS(I):X(I))<31;@FOR(CUTS(J)|J#LT#3:X(J)>X(J+1));@FOR(CUTS(J):@GIN(X(J)));@FOR(PATTERNS(I,J):@GIN(R(I,J)));end基本用法model:Title钢管下料LINGO模型;min=x1+x2+x3;x1*r11+x2*r12+x3*r13>=50;x1*r21+x2*r22+x3*r23>=10;x1*r31+x2*r32+x3*r33>=20;x1*r41+x2*r42+x3*r43>=15;4*r11+5*r21+6*r31+8*r41<=19;4*r12+5*r22+6*r32+8*r42<=19;4*r13+5*r23+6*r33+8*r43<=19;4*r11+5*r21+6*r31+8*r41>=16;4*r12+5*r22+6*r32+8*r42>=16;4*r13+5*r23+6*r33+8