《优化问题与先进算法》由会员分享，可在线阅读，更多相关《优化问题与先进算法（75页珍藏版）》请在金锄头文库上搜索。
1、优化问题与先进算法,一、 优化问题与规划模型,优化问题：与最大、最小、最长、最短等等有关的问题。 优化问题分类：（非）线性规划、整数规划、0-1规划、（多）目标规划、（与时间有关的）动态规划、（系数是随机变量的）随机规划。,1.1 线性规划 1939年苏联数学家康托洛维奇发表生产组织与计划中的数学问题 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论.,1. 问题 例1 作物种植安排 一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规
2、划经营使经济效益最大.,分析： 1. 求什么？ 分别安排多少亩地 种蔬菜、棉花、水稻？ 2. 优化什么？ 产值最大 3. 限制条件？ 田地总量 劳力总数,亩,亩,亩,模型I ：模型 I : 设决策变量：种植蔬菜 亩, 棉花 亩, 水稻 亩， 求目标函数 在约束条件 下的最大值,规划问题：在约束条件下求目标函数的最优值点。 规划问题包含3个组成要素: 决策变量、目标函数、约束条件。 当目标函数和约束条件 都是决策变量的线性函数时， 称为线性规划问题, 否则称为非线性规划问题。,2. 线性规划问题求解方法 称满足约束条件的向量为可行解, 称可行解的集合为可行域 , 称使目标函数达最优值的可行解为最
3、优解. 线性规划问题求解方法：Matlab优化工具箱和专门解优化问题的软件 Lindo、Lingo，还有软件Excel，也可应用于解优化问题。,一般线性规划的数学模型及解法： min f=cTx s.t. Ax b A1x=b1 LB x UB Matlab求解程序 x,f=linprog(c,A,b,A1,b1,LB,UB),1. 求什么？ 土地成本价格 劳动力成本价格 2. 优化什么？ 成本价格最低 3. 限制条件？ 蔬菜的市场价 棉花的市场价 水稻的市场价,分析： 以最经济的投入达到收益最大的目标.（或者说以直接出售土地和劳动力的方式达到收益最大的目标.）,模型 II . 设决策变量:
4、对单位土地和对单位劳力投入成本价格分别为 , 求目标函数 在约束条件 , , 下的最小值.,3. 对偶问题： A 是m n 矩阵， c 是 n 1向量，b 是 m 1向量 x 是 n 1向量, y 是 m 1向量,问题 max f=cTx s.t. Ax b xi 0, i=1,2,n.,对偶问题 min f=bTy s.t. ATy c yi 0, i=1,2,m.,对偶定理: 互为对偶的两个线性规划问题, 若其中一个有有穷的最优解, 则另一个也有有穷的最优解, 且最优值相等. 若两者之一有无界的最优解, 则另一个没有可行解 模型 I II构成对偶问题. 模型 I 解得最优解Xopt=(30
5、 0 20), 最大值 f(xopt)=4500 模型 II 解得最优解yopt=(10 200), 最小值 g(yopt)=4500.,模型I 给出了生产中的产品的最优分配方案 模型 II 给出了生产中资源的最低估价. 进一步问：如果增加对土地和劳动力的投入，每种资源 的单位投入增加会带来多少产值？ 由最优解 y=(10,200) 可见, 多耕一亩地增加10元收入， 多一个劳动力增加200元收入。也就是说, 此时一个劳动力的估价为200元,而一亩土地估价为10元. 这种价格涉及到资源的有效利用, 它不是市场价格,而是 根据资源在生产中做出的贡献确定的估价, 被称为“影 子价格”. 再进一步问
6、，棉花价格提高到多少才值的生产？ 由 y1+1/3y2=10+200/3=76.675, （而其它两个约束条件是等式）可见，只有当棉花价格提高到 76.6元时才值得生产.,Lingo命令 Model: Max=110*x1+75*x2+60*x3; x1+x2+x3=50; 1/2*x1+1/3*x2+1/4*x3=20; end 输出结果 Global optimal solution found at iteration: 2 Objective value:最优值 4500.000 Variable Value最优解 Reduced Cost X1 30.00000 0.000000 X
7、2 0.000000 1.666667 X3 20.00000 0.000000 Row Slack or Surplus Dual Price对偶价格 1 4500.000 1.000000 2 0.000000 10.00000 3 0.000000 200.0000,结果解释 reduced cost值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量(对max型问题)也可理 解为：为了使该非基变量变成基变量，目标函数中对应系数 应增加的量 Row Slack or Surplus 松弛量或剩余量，土地、劳动力剩余 量为零。“资源” 剩余为零的约束为紧约束（有效约束）
8、,灵敏度分析 当线性规划问题中的常数发生变化(由于测量误差或具有多个取值可能)时, 最优解是否会随之变化? 通常假定变化的常数是某参数的线性函数.讨论参数取值与最优解的关系的问题, 被称为参数线性规划. 例如, 当农作物的价格发生变化时, 生产计划是否应马上随之改变? 参见线性规划书籍,4. 非线性规划 min z=f(z) s.t. A1xb1, A2x=b2, c1(x)0, c2(x)=0 LB x UB MATLAB 程序 x,z=fmincon(fun,x0,A1,b,A2,b2,LB,UB,nonlcon）,例3.某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里),水
9、泥日用量di (单位：吨）,建两个日储量e为20吨的料场，需要确定料场位置(xj,yj)和运量cij ，使总吨公里数最小。,min z=f(z) s.t. A1xb1, A2x=b2, c1(x)0, c2(x)=0 LB x UB MATLAB 程序 x,z=fmincon(fun,x0,A1,b,A2,b2,LB,UB,nonlcon）,用随机搜索算法确定初始点： 在可行域0.5,8.750.75,7.75内简单地选取n个随机的的点， 计算目标函数在这些点的值，选择其中最小的点即可。 然后，可采用Matlab求最值点程序求出精确的最小值点: 求函数fun在x0点附近的最小值点,随机搜索程序
10、的伪代码,算法：随机搜索法 变量：xl=x的下限 xu=x的上限 yl=y的下限 yu=y的上限 N =迭代次数 xm=极小点x的近似值 ym=极小点y的近似值 zm=极小点f(x,y)的近似值 输入：xl，xu，yl，yu 过程：开始 xrandomxl，xu yrandomyl，yu zmf(x,y),对n=1到N循环 开始 xrandomxl，xu yrandomyl，yu zf(x,y) 若zzm，则 xmx ymy zm z 结束 结束 输出：xm，ym，zm,5. 0-1规划 如果要求决策变量只取0 或 1的线性规划问题, 称为整数规划. 0-1 约束不一定是由变量的性质决定的,
11、更多地是由于逻辑关系引进问题的,例4 背包问题 一个旅行者的背包最多只能装 6 kg 物品. 现有4 件物品 重量为 2 kg , 3 kg, 3 kg, 4 kg, 价值为 1 元, 1.2元, 0.9元, 1.1元. 应携带那些物品使得携带物品的价值最大? 建模: 记xj：旅行者携带第 j 件物品的件数, xj = 0, 1. 约束条件 2x 1 +3x 2 +3x 3 +4x 4 6 求xj 使目标函数 f=x1+1.2x2+0.9x3+1.1x4最大.,用Lingo 软件求解0-1规划 Linear Interactive and General Optimizer Model: Ma
12、x=x1+1.2*x2+0.9*x3+1.1*x4; 2*x1+3*x2+3*x3+4*x4=6; bin(x1); bin(x2); bin(x3); bin(x4); end,例 5 供货问题 一家公司生产某种商品. 现有n 个客户, 第 j 个客户需要货物量至少为 bj, 可在m 个不同地点设厂供货. 在地区 i 设厂的费用为 di , 供货能力为 hi , 向第 j 个客户供应单位数量的货物费用为 cij. 如何设厂与供货使总费用最小.,模型： 记 xij 为在地区 i 向第 j 个客户供货数量, 记 yi =1 , 在地区 i 设厂， 记 yi =0 不在地区 i 设厂， 求设厂和供
13、货分配方案yi， xij 使得目标函数 f= yi (j cij xij + di ) 在约束条件 i yi xij bj, j=1,n j xij hi 0, I=1,m xij0, yi =0, 1 下达到最小,6. 整数规划 在许多实际问题中，我们必须要处理离散变量如整数。离散数学曾被认为是比较神秘的领域，没有或几乎没有什么实际的应用。随着数字计算机的发明，离散数学变得极其重要。离散优化对时间安排、物资存储、投资、运输、制造业、生态学和计算机科学等方面的问题都非常有用。 如果要求决策变量取整数, 或部分取整数的线性规划问题, 称为整数规划. 当连续的决策变量变为离散变量时非线性优化问题通
14、常会难解得多。没有连续性后可行域会变得很复杂，通常用一个图或树结构来描述。对一些类型的问题已经开发出了有效的求解算法，对这些算法的改进是一个非常活跃的研究领域，但与连续的情形一样，迄今还没有求解离散优化问题的普遍的有效算法。,例 6 . 飞船装载问题 设有n种不同类型的科学仪器希望装在登月飞船上, 令cj0表示每件第 j 类仪器的科学价值; aj0表示每件第 j 类仪器的重量. 每类仪器件数不限, 但装载件数只能是整数. 飞船总载荷不得超过数 b. 设计一种方案, 使得被装载仪器的科学价值之和最大.,建模 记 xj 为第 j 类仪器的装载数. 求 各种仪器的装载数量 xj （整数） 在约束条件
15、 jaj xj b 下, 使得目标函数 f= j cj xj达到最大值.,7. 用Lindo软件求解整数规划 Linear Interactive and Discrete optimizer,max 3x1+2x2 st 2x1+3x2=14 2x1+x2=9 end gin x1 gin x2 (或者用 gin 2 ),求 整数 x1, x2 Max Z=3x1+2x2 s. t. 2x1+3x214 2x1+x2 9,8. 规划问题的建模艺术 将实际问题归结为线性规划模型是一个探索创造的过程。,例7 钢材截短 有一批钢材, 每根长7.3米. 现需做100套短钢材. 每套包括长2.9米, 2.1米,1.5米的各一根. 至少用掉多少根钢材才能满足需要, 并使得用料最省.,解: 可能的截法和余料 第1种 7.3-(2.92+1.51)=0 第2种 7.3-(2.91+2.12)=0.2 第3种 7.3-(2.91+1.52)=1.4 第4种 7.3-(2.91+2.11+1.51)=0.8 第5种 7.3-(2.12+1.52)=0.1 第6种 7.3-(2.13)=1 第7种 7.3-(2.11+1.53)=0.7 第8种 7.3-(1.54)=1.3,
