《Lec1---一些优化问题介绍PPT课件》由会员分享，可在线阅读，更多相关《Lec1---一些优化问题介绍PPT课件（88页珍藏版）》请在金锄头文库上搜索。
1、28.11.2020,1,一些优化问题介绍,28.11.2020,2,最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题, 如:结构设计、资源分配、生产计划、运输方案,优化模型和算法的重要意义,解决优化问题的手段：1）经验积累，主观判断；2）作试验，比优劣；3）建立数学模型，求解最优策略,最优化:在一定条件下,寻求使目标最大(小)的决策,28.11.2020,3,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,无约束优化(没有约束)与约束优化(有约束) 可行解（只满足约束）与最优解(取到最优值),28.11.2020,4,局部最优解与整体最优解,局部最优解 (Lo
2、cal Optimal Solution, 如 x1 ) 整体最优解 (Global Optimal Solution, 如 x2 ),28.11.2020,5,连续优化,离散优化,整数规划(IP) 决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划,优化模型的简单分类,线性规划(LP): 目标和约束均为线性函数 非线性规划(NLP): 目标或约束中存在非线性函数 二次规划(QP): 目标为二次函数、约束为线性,28.11.2020,6,单目标优化模型： 多目标优化模型：,光滑优化模
3、型： 非光滑优化模型：,仅一个目标 多个目标,目标函数、约束条件函数全部都可微 否则,凸优化模型 非凸优化模型,28.11.2020,7,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,28.11.2020,8,单目标优化问题,光滑优化问题,多目标优化问题,非光滑优化问题,问题求解的难度增加,凸优化问题,非凸优化问题,28.11.2020,9,线性规划（LP）:目标和约束均为线性函数,目标 函数,约束 条件,28.11.2020,10,简写形式：,28.11.2020,11,例1 ：某企业计划生产、两种产品。这两种产品都要分别在A、B
4、、C、D四种不同设备上加工。生产每件产品需占用各设备分别为2、1、4、0h，生产每件产品，需占用各设备分别为2、2、0、4h。已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12h，又知每生产一件产品企业能获得2元利润，每生产一件产品企业能获得3元利润，问企业应安排生产两种产品各多少件，使总的利润收入为最大。,28.11.2020,12,28.11.2020,13,分析,-生产产品的件数,-生产产品的件数,28.11.2020,14,需满足条件：,实现目的：,28.11.2020,15,Lingo程序,max=2*x1+3*x2; 2*x1+2*x212; x1+2*x28;
5、4*x116; 4*x212;,28.11.2020,16,结果：,Global optimal solution found. Objective value: 14.00000 Total solver iterations: 2 Variable Value X1 4.000000 X2 2.000000,28.11.2020,17,例2：某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划,28.11.2020,18,决策变量：每天生产三种产品的数量，分别设为 目标：每天的生产利润最大 利润函数 受制条件： 每天原料的需求量不超过可用量： 原料 ： 原料 ：
6、原料 ： 蕴含约束：产量为非负数,分析,28.11.2020,19,得到模型,28.11.2020,20,Lingo程序,max=3*x1+5*x2+4*x3; 2*x1+3*x21500; 2*x1+4*x2800; 3*x1+2*x2+5*x32000;,28.11.2020,21,结果：,Global optimal solution found. Objective value: 2280.000 Total solver iterations: 1 Variable Value X1 0.000000 X2 200.0000 X3 320.0000,28.11.2020,22,非线性
7、规划模型 nonlinear Programming(NLP),中至少有一个 为非线性函数,28.11.2020,23,例3: 某公司经营两种设备，第一种设备每件售价 30 元，第二种设备每件售价 450 元。据统计，每销售一件第一种设备所需时间平均 0.5 小时，第二种设备是（2 + 0.25X2）小时，其中 X2 是第二种设备的售数量。已知该公司在这段时间内的总营业时间为 800 小时，试确定使其营业额最大的营业计划。,28.11.2020,24,分析,-是第一种设备的售数量,-是第二种设备的售数量,28.11.2020,25,目标函数：,约束条件：,即,28.11.2020,26,Lin
8、go程序,max=30*x1+450*x2; 0.25*x22+2*x2+0.5*x1800;,28.11.2020,27,结果：,Local optimal solution found. Objective value: 49815.00 Extended solver steps: 5 Total solver iterations: 79 Variable Value X1 1495.500 X2 11.00000,28.11.2020,28,例4: 某工厂向用户提供发动机，按合同规定，其交货数量和日期是：第一季度末交 40 台，第二季度末交 60 台，第三季度末交 100 台。工厂的
9、最大生产能力为每季度 100 台，每季的生产费用是 f（X）= 50X + 0.2X2 （元），X 为该季度生产的发动机数量。若某季度生产的多，多余的发动机可移到下季度向用户交货，这样，工厂就需要支付存储费，每台发动机每季的存储费为 4 元。问该厂每季应生产多少发动机，才能既满足交货合同，又使工厂所花费的费用最少（假定第一季开始时发动机无存货）。,28.11.2020,29,分析,-第i季度生产的发动机数量,假设第一季度初该工厂没有存储的发动机 不考虑第三季度末多余的发动机数量,则第二、三季度初存储的发动机数量分别为,28.11.2020,30,目标函数,约束条件,28.11.2020,31,
10、Lingo程序,min=0.2*(x12+x22+x32)+58*x1+54*x2; x1+x2100; x1+x2+x3200; bnd(40,x1,100); bnd(0,x1,100); bnd(0,x1,100);,28.11.2020,32,结果：,Local optimal solution found. Objective value: 8590.000 Extended solver steps: 5 Total solver iterations: 28 Variable Value X1 45.00000 X2 55.00000 X3 100.0000,28.11.2020
11、,33,二次规划模型(QP) : 目标为二次函数、约束为线性,其中 是 对称阵,注：(1)若Hesse阵是半正定的，则称为凸二次规划，此问题有时并不比求解线性规划困难 (2)对非凸二次规划，可能有多个局部极小点，求解比较困难,28.11.2020,34,例5(投资组合模型) :美国某三种股票（A,B,C）12年(1943-1954)的价格(已经包括了分红在内)每年的增长情况如表所示(表中还给出了相应年份的500种股票的价格指数的增长情况)。例如，表中第一个数据1.300的含义是股票A在1943年的年末价值是其年初的1.300倍，即收益为30%，其余数据的含义依次类推。假设你在1955年时有一笔
12、资金准备投资这三种股票，并期望年收益率至少达到15%，那么你应该如何投资？当期望的年收益变化时，投资组合和相应的风险如何变化？,28.11.2020,35,期望年收益率至少达到15%，应当如何投资？,28.11.2020,36,分析,收益不确定,收益的期望值,风险 收益的方差,一种股票收益的均值衡量这种股票的平均收益状况,一种股票收益的方差衡量这种股票收益的波动幅度,两种股票收益的协方差表示他们之间的相关程度,方差越大，风险越大；方差越小，风险越小。,28.11.2020,37,数学期望： ER1=0.0890833, ER2=0.213667, ER3=0.234583 协方差矩阵： COV
13、 =,假设股票A、B、C每年的收益率分别为R1，R2和R3,28.11.2020,38,年收益率（的数学期望）不低于15%,资金 全部用于投资这三种股票,决策变量,x1投资股票A；x2投资股票B； x3投资股票C,约束条件,x1, x2 , x3 0，x1+x2 +x3 = 1,x1ER1+x2ER2+x3ER3 0.15,目标函数,年投资收益率的方差极小,二次规划模型(QP),A占53%，B占36%，C占11%,28.11.2020,39,Lingo程序,MODEL: SETS: YEAR/1.12/; STOCKS/ A, B, C/: Mean,X; link(YEAR, STOCKS)
14、: R; STST(Stocks,stocks): COV; ENDSETS DATA: TARGET = 1.15; ! R是原始数据; R = 1.300 1.225 1.149 1.103 1.290 1.260 1.216 1.216 1.419 0.954 0.728 0.922 0.929 1.144 1.169,28.11.2020,40,1.056 1.107 0.965 1.038 1.321 1.133 1.089 1.305 1.732 1.090 1.195 1.021 1.083 1.390 1.131 1.035 0.928 1.006 1.176 1.715 1.
15、908; ENDDATA !计算均值向量Mean与协方差矩阵COV; for(stocks(i): Mean(i) = sum(year(j): R(j,i) / size(year) ); for(stst(i,j): COV(i,j) = sum(year(k): (R(k,i)-mean(i)*(R(k,j)-mean(j) / (size(year)-1) ); MIN = sum(STST(i,j): COV(i,j)*x(i)*x(j); SUM(STOCKS: X) = 1; SUM(stocks: mean*x) = TARGET; END,28.11.2020,41,结果：,Local optimal solution found. Objective value: 0.2241378E-01 Extended solver steps: 2 Total solver iterations: 16 Variable Value X( A) 0.5300926 X( B) 0.3564076 X( C) 0.1134998,28.11.2020,42,
