常见优化模型

1、编辑课件常见优化模型常见优化模型东北大学东北大学应用数学应用数学王琪王琪编辑课件常见优化模型 线性规划 整数规划 非线性规划编辑课件 线性规划 线性规划的标准形式：可以采用的解决方法：编辑课件问题一 加工费用最低 问题一问题一 ： 任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？ 单位工件所需加工台时数 单位工件的加工费用 车床类 型 工件 1 工件 2

2、工件 3 工件 1 工件 2 工件 3 可用台时数 甲 0.4 1.1 1.0 13 9 10 800 乙 0.5 1.2 1.3 11 12 8 900 编辑课件 解解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：编辑课件用用MATLAB优化工具箱解线性规划优化工具箱解线性规划min z=cX bAXts. .1、模型：命令：x=linprog（c，A，b） 2、模型：min z=cX bAXts. .beqXAeq命令：x=linprog（c，A，b，Aeq, beq）注意：若没有不等式： 存

3、在，则令A= ，b= .bAX 编辑课件3、模型：min z=cX bAXts. .beqXAeqVLBXVUB命令：1 x=linprog（c，A，b，Aeq, beq, VLB，VUB） 2 x=linprog（c，A，b，Aeq, beq, VLB，VUB, X0） 注意：1 若没有等式约束: , 则令Aeq= , beq= . 2其中X0表示初始点 beqXAeq4、命令：x,fval=linprog()返回最优解及处的目标函数值fval.编辑课件解解 编写编写M文件文件xxgh1.m如下：如下：c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6; A=0.01 0

4、.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08; b=850;700;100;900; Aeq=; beq=; vlb=0;0;0;0;0;0; vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub) 例例1 max 6543216 . 064. 072. 032. 028. 04 . 0 xxxxxxz 85003. 003. 003. 001. 001. 001. 0. .654321xxxxxxt s 70005. 002. 041xx 10005.

5、002. 052xx 90008. 003. 063xx 6, 2 , 10jxj编辑课件解解: 编写编写M文件文件xxgh2.m如下：如下： c=6 3 4; A=0 1 0; b=50; Aeq=1 1 1; beq=120; vlb=30;0;20; x,fval=linprog(c,A,b,Aeq,beq,vlb)321)436(minxxxz5020030321xxx120111 s.t. 321xxx编辑课件 投资的收益和风险投资的收益和风险编辑课件二、基本假设和符号规定二、基本假设和符号规定符符号号规规定定：Si 第 i 种投资项目，如股票，债券ri,pi,qi -分别为 Si的

6、平均收益率,风险损失率，交易费率ui -Si的交易定额 0r -同期银行利率xi -投资项目 Si的资金 a -投资风险度Q -总体收益 Q -总体收益的增量编辑课件三、模型的建立与分析三、模型的建立与分析1. 总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n2购买 Si所付交易费是一个分段函数,即 pixi xiui 交易费 = piui xiui而题目所给定的定值 ui(单位:元)相对总投资 M 很小, piui更小,可以忽略不计,这样购买 Si的净收益为(ri-pi)xi 3要使净收益尽可能大，总体风险尽可能小,这是一个多目标规划模型: 目标函数 MAXn

7、iiiixpr0)( MINmax qixi 约束条件 niiixp0)1 (=M xi0 i=0,1,n4. 模型简化：编辑课件c投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重 s（0s1)，s 称为投资偏好系数.模模型型 3 目标函数：min smaxqixi -（1-s）niiiixpr0)( 约束条件 niiixp0)1 (=M， xi0 i=0,1,2,nb若投资者希望总盈利至少达到水平 k 以上，在风险最小的情况下寻找相应的投资组合。模模型型 2 固定盈利水平，极小化风险 目标函数： R= minmax qixi 约束条件：nii

8、iixpr0)(k， Mxpii)1 ( ， xi 0 i=0，1，na 在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限 a，使最大的一个风险 qixi/Ma，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。模模型型 1 1 固定风险水平，优化收益 目标函数： Q=MAX11)(niiiixpr 约束条件： Mxqiia Mxpii)1 (， xi 0 i=0，1，n编辑课件四、模型四、模型1 1的求解的求解 模型1为: minf = (-0.05, -0.27, -0.19, -0.185, -0.185) (x0 x1 x2 x3 x 4 ) T x0 + 1.

9、01x1 + 1.02x2 +1.045x3 +1.065x4 =1s.t. 0.025x1 a 0.015x2 a 0.055x3 a 0.026x4a xi 0 (i = 0,1,.4) 由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：编辑课件a=0;while(1.1-a)1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.

10、055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)编辑课件a = 0.0030 x = 0.4949 0.1200 0.2000 0.0545 0.1154 Q = 0.1266a = 0.0060 x = 0 0.2400 0.4000 0.1091 0.2212 Q = 0.2019a = 0.0

11、080 x = 0.0000 0.3200 0.5333 0.1271 0.0000 Q = 0.2112a = 0.0100 x = 0 0.4000 0.5843 0 0 Q =0.2190a = 0.0200 x = 0 0.8000 0.1882 0 0 Q =0.2518 a = 0.0400 x = 0.0000 0.9901 0.0000 0 0 Q =0.2673计算结果：计算结果：编辑课件五、五、 结果分析结果分析4 4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长 很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和 收益没有特殊偏

12、好的投资者来说，应该选择曲线的拐点作为最优投资组合， 大约是a*=0.6%，Q*=20% ，所对应投资方案为: 风险度 收益 x0 x1 x2 x3 x4 0.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212 3.3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。2 2.当投资越分散时，投资者承担的风险越小，这与题意一致。即: 冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。1.1.风险大，收益也大。编辑课件 定义定义 如果目标函数或约束条件中至少有一个是非线性函数时的

13、最优化问题就叫做非线性规划问题非线性规划问题非线性规划的基本概念非线性规划的基本概念 一般形式一般形式: （1） 其中 ， 是定义在 En 上的实值函数，简记: Xfmin .,.,2 , 1 0 m;1,2,., 0. . ljXhiXgtsjinTnExxxX,21jihgf,1nj1ni1nE :h ,E :g ,E :EEEf 其它情况其它情况: 求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式 Matlab函数：fmincon()编辑课件应用实例：应用实例： 供应与选址供应与选址 某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距

14、离单位：千米 ）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。 （1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。 （2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？工地位置（a，b）及水泥日用量 d 1 2 3 4 5 6 a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.25 d 3 5 4 7 6 11 编辑课件（一）、建立模型（一

15、）、建立模型 记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为di，i=1,6;料场位置为料场位置为(xj，yj)，日储量为，日储量为ej，j=1,2；从料场；从料场j向工地向工地i的运送量为的运送量为Xij。目标函数为：216122)()(minjiijijijbyaxXf 约束条件为：2 , 1 ,6 , 2 , 1 ,6121jeXidXjiijijij 当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：Xij，xj，yj。编辑课件（二）使用临时料场的情形（二）使用临时料场的情形 使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题. 线性规划模型为：2161),(minjiijXjiaaf2 , 1 , 6 , 2 , 1 , s.t.6121jeXidXjiijijij其中 22)()(),(ijijbyaxjiaa，i=1,2,6,j=1,2,为常数。 设X11=X1, X21= X 2, X31= X 3, X41= X 4,