1、常见优化模型,东北大学 应用数学 王琪 ,常见优化模型,线性规划 整数规划 非线性规划,线性规划,线性规划的标准形式：,可以采用的解决方法：单纯性法 Matlab函数：linprog（）,问题一 加工费用最低,问题一 ： 任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,解 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、
2、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：,用MATLAB优化工具箱解线性规划,命令：x=linprog（c，A，b）,2、模型：min z=cX,命令：x=linprog（c，A，b，Aeq, beq）,注意：若没有不等式： 存在，则令A= ，b= .,3、模型：min z=cX,VLBXVUB,命令：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表示初始点,4、命令：x,fval=linprog
3、() 返回最优解及处的目标函数值fval.,解 编写M文件xxgh1.m如下： c=-0.4 -0.28 -0.32 -0.72 -0.64 -0.6;A=0.01 0.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),解: 编写M文件xxgh2.m如下：c=6 3 4;A=0 1 0;b=50;Aeq=1 1 1
4、;beq=120;vlb=30;0;20;x,fval=linprog(c,A,b,Aeq,beq,vlb),投资的收益和风险,二、基本假设和符号规定,三、模型的建立与分析,1. 总体风险用所投资的Si中最大的一个风险来衡量,即max qixi|i=1，2,n,4. 模型简化：,四、模型1的求解,由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度。我们从a=0开始，以步长a=0.001进行循环搜索，编制程序如下：,a=0; while(1.1-a)1c=-0.05 -0.27 -0.19 -0.185 -0.185;Aeq=1 1.01 1.02 1.045 1.0
5、65; beq=1;A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.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);ax=xQ=-valplot(a,Q,.)，axis(0 0.1 0 0.5)，hold ona=a+0.001; end xlabel(a),ylabel(Q),计算结果：,五、 结果分析,4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险
6、和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20% ，所对应投资方案为:风险度 收益 x0 x1 x2 x3 x40.0060 0.2019 0 0.2400 0.4000 0.1091 0.2212,3.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。,2.当投资越分散时，投资者承担的风险越小，这与题意一致。即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。,1.风险大，收益也大。,定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就
7、叫做非线性规划问题,非线性规划的基本概念,一般形式: （1）其中 ， 是定义在 En 上的实值函数，简记:,其它情况: 求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式Matlab函数：fmincon(),应用实例： 供应与选址,某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米 ）及水泥日用量d(吨)由下表给出。目前有两个临时料场位于A(5,1)，B(2,7)，日储量各有20吨。假设从料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从A，B两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少
8、吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大？,（一）、建立模型,记工地的位置为(ai，bi)，水泥日用量为di，i=1,6;料场位置为(xj，yj)，日储量为ej，j=1,2；从料场j向工地i的运送量为Xij。,当用临时料场时决策变量为：Xij， 当不用临时料场时决策变量为：Xij，xj，yj。,（二）使用临时料场的情形,使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题. 线性规划模型为：,设X11=X1, X21= X 2, X31= X 3, X41= X 4, X51= X 5, X61= X 6 X12= X 7, X22= X 8, X32= X 9, X42= X 10, X52= X 11, X62= X 12,（三）改建两个新料场的情形,改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：,
