中国建设银行网站客户注册,开发公司需要什么资质,申请网站免费,工程建设合同模板优化入门多目标规划 优化入门知识什么是优化问题如何判断是不是优化问题优化模型建模求解器优化问题的分类 多目标规划 优化入门知识
什么是优化问题
优化问题#xff1a;求最优#xff0c;例如获利最大、最少损失、最短路径、最小化风险等等。 例如#xff1a;之前文章提… 优化入门多目标规划 优化入门知识什么是优化问题如何判断是不是优化问题优化模型建模求解器优化问题的分类 多目标规划 优化入门知识
什么是优化问题
优化问题求最优例如获利最大、最少损失、最短路径、最小化风险等等。 例如之前文章提到华为杯2019F题多约束条件下智能飞行器航迹快速规划其中第一问就涉及求飞行器从A点到B点带约束下的最短路径。
如何判断是不是优化问题
题目带有优化、规划、最值、安排、分配、最合理等等。
题目涉及到图例如三维空间飞行、二维地图上旅行。
优化模型建模
优化模型格式决策变量目标函数约束条件。
决策变量能够对目标结果产生影响的变量。 x i , i 1 , 2 , . . . , n x_i,i1,2,...,n xi,i1,2,...,n
目标函数通常都是一个Min或者Max求某个决策变量的函数表达式。例如 M i n ( o r M a x ) z f ( x ) , x ( x 1 , . . . , x n ) T Min(or Max)zf(x),x(x_1,...,x_n)^T Min(orMax)zf(x),x(x1,...,xn)T 约束条件以s.t.为开头后面写上约束条件。 s . t . { g 1 ( x ) ⩽ 0 g 2 ( x ) ⩽ 0 . . . g n ( x ) ⩽ 0 s.t. \begin{cases} g_1(x)\leqslant0\\ g_2(x)\leqslant0\\ ...\\ g_n(x)\leqslant0\\ \end{cases} s.t.⎩ ⎨ ⎧g1(x)⩽0g2(x)⩽0...gn(x)⩽0
求解器
优化模型建立好之后选择什么样的算法去解模型是比赛的关键。
求解器用来求解模型的程序、算法之类的在matlab里面求解器填写的其实就是函数模型。
优化问题的分类
从目标函数的个数来说可以分成单目标和多目标。
从问题的类型来说可以分为规划类、图论和动态规划。
规划类按照决策变量在目标函数和约束条件中是否线性可以分为线性规划和非线性规划。 规划类中比较特殊的是决策变量为整数的“整数规划”和决策变量只能取0或者1的“0-1规划”。 非线性规划中比较特殊的是二次规划目标函数是关于决策变量的二次函数约束条件是线性函数。
图论中常见的问题有最短路、最小生成树、网络流和排队论。
多目标规划
条件线性规划和非线性规划只有一个目标函数多目标函数有多个目标函数 f i ( x ) f_{i}(x) fi(x)讲究一个既要还要。
方法多目标转化为单目标。
优先因子可以主观上给目标函数进行一个重要性排序来使得整体的完成情况尽量好也就是优先因子相当于权重 P i P_i Pi。 m i n ∑ P i f i ( x ) min\sum P_{i}f_{i}(x) min∑Pifi(x)平方加权知道每个目标理想值的情况下可以求每个目标函数和理想值的平方和可以带上权重。 m i n ∑ λ i [ f i ( x ) − f i ∗ ] 2 min\sum \lambda_{i}[f_{i}(x)-{f_i}^*]^2 min∑λi[fi(x)−fi∗]2乘除法如果每个目标重要程度一样。 m i n f 1 ( x ) f 2 ( x ) . . . f k ( x ) f k 1 ( x ) f k 2 ( x ) . . . f n ( x ) min\frac{f_{1}(x)f_{2}(x)...f_{k}(x)}{f_{k1}(x)f_{k2}(x)...f_{n}(x)} minfk1(x)fk2(x)...fn(x)f1(x)f2(x)...fk(x)分开求最优解对比有时候单独最优解之间差距可能不是很大例如之前华为杯2019F题有个论文就是分别求最优路径和最少矫正点然后对比。
特殊问题中存在刚性约束和柔性约束。刚性约束就是必须要满足的否者就是不可行解。柔性约束就是可以存在偏差的例如使目标f(x)尽可能不少于5可以在5左右有正负偏差。这个正负偏差可以记作 d 和 d − d^和d^- d和d− d m i n { f ( x ) − f ∗ , 0 } , d − − m i n { f ∗ − f ( x ) , 0 } d^min\{f(x)-f^*,0\},d^--min\{f^*-f(x),0\} dmin{f(x)−f∗,0},d−−min{f∗−f(x),0}。 例子三个目标函数 f 1 ( x ) 、 f 2 ( x ) 、 f 3 ( x ) f_1(x)、f_2(x)、f_3(x) f1(x)、f2(x)、f3(x)三个目标是柔性约束1尽量不超过、2尽量等于、3尽量不少于会发现柔性约束都有“尽量”两个字作为修饰。最终的多目标规划函数可以写成 min { P 1 d 1 P 2 ( d 2 − d 2 ) P 3 d 3 − } \min{\{P_1{d_1}^P_2({d_2}^-{d_2}^)P_3{d_3}^-\}} min{P1d1P2(d2−d2)P3d3−} 扩展一下格式 m i n ∑ P i ( w i d i w i − d i − ) min\sum {P_i({w_{i}}^{d_{i}}^{w_{i}}^-{d_{i}}^-)} min∑Pi(widiwi−di−)
总结多目标规划可以转换成为单目标问题然后单目标去看符合单目标中那种取套根据情况套回规划类、图论和动态规划中。
