优化问题的一般形式

《优化问题的一般形式》由会员分享，可在线阅读，更多相关《优化问题的一般形式（8页珍藏版）》请在金锄头文库上搜索。

1、1大学数学实验大学数学实验实验8 线性规划实验8 线性规划清 华 大 学 数 学 科 学 系清 华 大 学 数 学 科 学 系优化问题三要素：优化问题三要素：决策变量决策变量；目标函数目标函数；约束条件约束条件约 束 条 件约 束 条 件决策变量决策变量优化问题的一般形式优化问题的一般形式njiDxljxgmixhtsxf=,.,1, 0)(,.,1, 0)(.)(min当最优解在可行域边界上取得时 不能用无约束优化方法求解当最优解在可行域边界上取得时 不能用无约束优化方法求解目标函数目标函数约束优化的分类约束优化的分类 线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数 非

2、线性规划非线性规划(NLP) 目标或约束中存在非线性函数目标或约束中存在非线性函数 ? 二次规划二次规划(QP) 目标为二次函数、约束为线性目标为二次函数、约束为线性 整数规划整数规划(IP)决策变量决策变量(部分部分)为整数为整数 ? 整数整数线性线性规划规划(ILP) ? 整数整数非线性非线性规划规划(INLP) ? 0-1规划规划整数决策变量只取或整数决策变量只取或njiDxljxgmixhtsxf=,.,1, 0)(,.,1, 0)(.)(min连 续 优 化连 续 优 化离 散 优 化离 散 优 化本实验基本内容本实验基本内容2. 基本原理和算法基本原理和算法3. MATLAB实现实

3、现1. 实例及其数学模型实例及其数学模型4. LINGO实现实现确定每种食物的用量，以最小费用满足营养需求确定每种食物的用量，以最小费用满足营养需求实例实例1: 食谱问题食谱问题 A的需求增加的需求增加1单位，是否改变食谱？成本增加多少？营养需求人天单位，是否改变食谱？成本增加多少？营养需求人天背景背景8222795.5个（44g）鸡蛋222795.5个（44g）鸡蛋60578903.5杯（178g）枣汁578903.5杯（178g）枣汁519202530.7个（72g）胡萝卜19202530.7个（72g）胡萝卜157961.2个（118g）香蕉7961.2个（118g）香蕉109.6730

4、.3个（138g）苹果价格(美分)钙9.6730.3个（138g）苹果价格(美分)钙(mg)维生素维生素A (IU)蛋白质蛋白质(g)单位食物单位食物50g蛋白质蛋白质 4000IU维生素维生素A 1000mg钙钙 胡萝卜价格增胡萝卜价格增1美分，是否改变食谱？成本增加多少？美分，是否改变食谱？成本增加多少？实例实例1: 食谱问题食谱问题5种食品数量：种食品数量： x1, x2,x3, x4, x5满足 需求满足 需求决策 变量目标 函数决策 变量目标 函数费用费用约束 条件约束 条件 非负约束非负约束0,51xx L5432186051510xxxxxzMin+=505 . 55 . 37

5、. 02 . 13 . 054321+xxxxxLP400027989020253967354321+xxxxx 100022571976 . 954321+xxxxx = 22571976 . 92798902025396735 . 55 . 37 . 02 . 13 . 0Ax = (x1, x2, x3, x4, x5)T c = (10, 15, 5, 60, 8)T b = (50, 4000, 1000)T0. . min=xbAxtsxczT21桶 牛奶桶 牛奶3千克千克A112小时小时8小时小时4千克千克A2或获利或获利12元元/千克千克获利获利8元元/千克千克0.8千克千克B

6、1 2小时小时,1.5元元1千克获利千克获利22元元/千克千克0.75千克千克B22小时小时,1.5元元1千克获利千克获利16元元/千克千克制订生产计划，使每天净利润最大制订生产计划，使每天净利润最大 15元可增加元可增加1桶牛奶，应否投资？桶牛奶，应否投资？50桶牛奶桶牛奶, 480小时至多小时至多100公斤公斤A1 B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？实例实例2: 奶制品生产销售计划奶制品生产销售计划 聘用临时工人增加劳动时间，工资最多每小时几元？聘用临时工人增加劳动时间，工资最多每小时几元？1桶 牛奶桶 牛奶3千克千克 A112小时小时

7、8小时小时4千克千克 A2或获利或获利12元元/千克千克获利获利8元元/千克千克0.8千克千克 B12小时小时,1.5元元1千克千克获利获利22元元/千克千克0.75千克千克 B22小时小时,1.5元元1千克千克获利获利16元元/千克千克出售出售x1 千克千克 A1,x2 千克千克 A2， x3千克千克 B1, x4千克千克 B2原料 供应劳动 时间加工能力原料 供应劳动 时间加工能力决策 变量目标 函数决策 变量目标 函数利润利润约束 条件约束 条件非负约束非负约束0,61xx Lx5千克千克 A1加工加工B1， x6千克千克 A2加工加工B26543215 . 15 . 11622812x

8、xxxxxzMax+=50436251+xxxx48022)(2)(4656251 +xxxxxx10051+ xx附加约束附加约束5380x.x=64750x.x =LP实例3：供应与选址实例3：供应与选址某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里), 水泥日用量di(单位：吨）i a1.258.750.55.7537.25 b1.250.754.7556.57.75 d3547611现有 2 料场，位于 A (5, 1), B (2, 7), 记(xj,yj),j=1,2, 日储量 ej各有 20 吨。假设：料场和工地之间有直线道路 目标：制定每天的供应计划，即从 A,

9、 B 两料场分别 向各工地运送多少吨水泥，使总的吨公里数最小。线性规划模型决策变量：线性规划模型决策变量： ci j(料场料场j到工 地到工 地i的运量）的运量） 12维维2 , 1; 6,.,1, 02 , 1,6,.,1,. .)()(min612121612/122=+=jicjecidctsbyaxcijjij iiij jjiijijij求解线性规划求解线性规划(LP)的基本原理的基本原理基本模型基本模型0,. .,min)max(=xbAxtsRxxczornTmnmnRbRARc,二维线性规划的图解法二维线性规划的图解法 一般线性规划的单纯形算法一般线性规划的单纯形算法 线性规划

10、的敏感性分析线性规划的敏感性分析 线性规划的对偶问题线性规划的对偶问题 线性规划的其他算法线性规划的其他算法二维线性规划的图解法二维线性规划的图解法x2x10L1L2L3z1=0z2=2z3=6z4=10z5=13grad zx*起作用约束：起作用约束：L2;L3最优解（最优解（4，1），最优值），最优值zmax=13L1L2L3 0,1423222.3max2121212121+=xxxxxxxxtsxxz 221 xx3求解求解LP的基本思想的基本思想从可行域的某一顶点开始，只需在有限多个顶点中 一个一个找下去，一定能得到从可行域的某一顶点开始，只需在有限多个顶点中 一个一个找下去，一定能

11、得到最优解最优解。LP的约束和目标函数均为线性函数的约束和目标函数均为线性函数2维可行域维可行域 线段组成的凸多边形线段组成的凸多边形目标函数目标函数 等值线为直线等值线为直线 最优解最优解 凸多边形的某个顶点凸多边形的某个顶点n维维超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点算法：怎样从一点转到下一点，尽快找到最优解。超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点算法：怎样从一点转到下一点，尽快找到最优解。x2x10L1L2L3x2x10L1 L2L3x2x10L1L2求解LP的特殊情形求解LP的特殊情形L1L2L3无可行解无可行解无最优解无最优解(无界无界)最优解不唯

12、一最优解不唯一3214123Lxx+3L无x2x10L1L2L3z=c0,1423222.3max2121212121+=xxxxxxxxtsxxz 221 xx321413Lxx+线性规划的标准形和基本性质线性规划的标准形和基本性质nmRAxbAxtsxcznmT=,0,. .min标 准 形标 准 形加入松弛变量加入松弛变量/剩余变量将不等式变为等式剩余变量将不等式变为等式0,0,14230, 220003min215521442154321=+=+=xxxxxxxxxxxxxxxz 0, 2.3321=+xxxxts0,1423222.3max2121212121+=xxxxxxxxts

13、xxz 221 xx假设：假设：A行满秩行满秩b非负非负0,1423, 222. .0003min5432152142132154321=+=+=+=xxxxxxxxxxxxxxtsxxxxxz0,1423, 22254321521421321=+=+=+xxxxxxxxxxxxxx对标准形求解先求可行解对标准形求解先求可行解nmRAxbAxtsxcznmT=,0,.min0,=xbAx满足再在有限个可行解中寻找最优解再在有限个可行解中寻找最优解1423222521421321=+=+=+xxxxxxxxx = 100230102100111A可逆，BNBAAAA,T NBTxxx, bxAx

14、AAxNNBB=+= 54321ppppp=bAxxBBN10=x2x1OT BxpppA)14, 2 , 2 , 0 , 0(543=T BxpppA) 8 , 0 , 4 , 0 , 2(531=T BxpppA)16, 0 , 3 , 1, 0(532=O点点Q点点R点点QR基基(本本)可行解可行解x ：Ax=b, x 0 (xB 0，xN=0)T BxpppA)0 , 0 , 5 , 1 , 4(321=P点点PAB: 基基(矩阵矩阵)x: 基基(本本)解解xB: 基变量基变量xN: 非基变量非基变量可行域存在时，必是凸多面体； 最优解存在时，必在可行域的顶点取得； 基本可行解对应于可

15、行域的顶点。LP基本性质LP基本性质基本解数量不超过基本解数量不超过LP的通常解法是单纯形法的通常解法是单纯形法(G. B. Dantzig, 1947)最优解只需在有限个可行解（基本可行解）中寻找最优解只需在有限个可行解（基本可行解）中寻找)!( ! mnmn mn= 4选取初始基可行解（顶点） ；选取初始基可行解（顶点） ；判断当前解是否最优；判断当前解是否最优； 选择进基和出基变量；选择进基和出基变量； 防止迭代过程出现循环 。防止迭代过程出现循环 。单纯形法的基本思路单纯形法的基本思路用迭代法从一个顶点（基可行解）转换到另一个顶 点（称为一次用迭代法从一个顶点（基可行解）转换到另一个顶 点（称为一次旋转旋转），每一步转换只将一个非基变 量（指一个分量）变为基变量，称为），每一步转换只将一个非基变 量（指一个分量）变为基变量，称为进基进基，同时将 一个基变量变为非基变量，称为，同时将 一个基变量变为非基变量，称为出基出基，进基和出基 的确定需要使目标函数下降（至少不增加）。，进基和出基 的确定需要使目标函数下降（至少不增加）。r? x(0)最优最优检验