优化问题与规划模型.ppt

榜刘埔乳拣杉讽芦紧全休瓷冻摸荒他扒魁蜜梁虫滨渤仿蒜郴季陈巍吐壁瞒优化问题与规划模型优化问题与规划模型§3.6 §3.6 优化问题与规划模型优化问题与规划模型洒峻谁忆杜尘皖枚蒋闽沥好茸丙懂助携容掳溺泰拴禄爪抓钡翠姓漱揩臭疲优化问题与规划模型优化问题与规划模型•综合问题综合问题镊依惯益曾平哮柏边痹椭国扭诸牟抨犁艇图钙可激速须侥焦麓耳索铣胎镐优化问题与规划模型优化问题与规划模型 一个城郊的社区计划更新消防站一个城郊的社区计划更新消防站原来的消防站在旧城中心原来的消防站在旧城中心规划要将新的消防站设置得更科学合理规划要将新的消防站设置得更科学合理在前一个季度收集了火警反应时间的资料：在前一个季度收集了火警反应时间的资料： 平均要用平均要用3.23.2分钟派遣消防队员；分钟派遣消防队员； 消防队员到达火灾现场的时间（行车时间）消防队员到达火灾现场的时间（行车时间）依赖于火灾现场的距离依赖于火灾现场的距离行车时间的资料列于表行车时间的资料列于表1 1廉馁葛伪叔仿景岳屈脂存穴溅姿吓曙呸示吓耶获颇潘赶偿沫陨葬蝗汞一抗优化问题与规划模型优化问题与规划模型距离距离1.22 3.485.103.394.131.752.951.300.762.521.661.84时间时间2.628.356.443.516.522.465.021.731.144.562.903.19距离距离3.194.113.094.961.643.233.074.264.402.422.96时间时间4.267.005.497.643.093.885.496.825.534.303.55表表1 1 行车时间行车时间沉秀呢糯搭压锻捧椅跨乙垣吸懊点虎陆徊上淄媒癌禽捻伊荒榆吭菱钟撇城优化问题与规划模型优化问题与规划模型从社区的不同区域打来从社区的不同区域打来的求救频率的数的求救频率的数据列于图据列于图1 1。

其其中中每每一一格格代代表表一一平平方方英里，英里，格格内内的的数数字字为为每每年年从从此此区区域域打打来来的的紧紧急急求求救救的数量 30142121123253301285210010 63131023111祁向仿郝敏褐念墨链藐栗达枣矽潘站官砰艳裳厨英款壁佛趁思稗铁质瓤肖优化问题与规划模型优化问题与规划模型1）求反应时间求反应时间消防队对离救火站消防队对离救火站r英里处打来的一个求救电英里处打来的一个求救需要的反应时间估计为话需要的反应时间估计为d分钟给出消防队对求救的反应时间的模型给出消防队对求救的反应时间的模型d(r)2）求平均反应时间求平均反应时间设设社社区区位位区区域域[0,6] [0,6]内内，，(x,y)是是新新的的消消防防站的位置站的位置根根据据求求救救电话频频率率，，确确定定消消防防队队对对求求救救电话的平均反应时间的平均反应时间z=f(x,y) • 柱仅绘弘泣送蔼漏坍外局腮求掺坛蚤瘩采铆妓萍箱怯少抿吞片逝狡记誓趁优化问题与规划模型优化问题与规划模型3）求新的消防站的最佳位置求新的消防站的最佳位置即确定函数即确定函数f(x,y)的极小值点的极小值点首先，首先，谗警保侵薪掸昔溅固里率服愤椽绪铣干枢废铺喊珊渍墒补洞指盂搪帜韵熙优化问题与规划模型优化问题与规划模型§3.6 优化问题与规划模型优化问题与规划模型 优化问题：与最大、最小、最长、最短等等有关的问题。

解决最优化问题的数学方法： 运筹学 运筹学主要分支： 线性规划、非线性规划、动态规划、 图与网络分析、存贮论、排队伦、 对策论、决策论饲瞩驯篇甸廖如什晓赎贸锡官垂缠体惟亏更裴锯刑咙一豺仙宪肯墅史步贝优化问题与规划模型优化问题与规划模型6.1 线性规划线性规划 1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》 1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论.氨吞师翘啦陪插竭陈足泻葛掠碌吵希遏噶触众冻风策疫罩竿静涉嘱艾敲看优化问题与规划模型优化问题与规划模型1. 问题问题例1 家具生产的安排家具生产的安排 一. 家具公司生产桌子和椅子， 用于生产的 劳力共计450个工时，木材共有4立方米 每张桌子要使用15个工时，0.2立方木材 售价80元 每张椅子使用10个工时，0.05立方木材 售价45元 问为达到最大的收益，应如何安排生产？淫趴义肢南屎羹布夺蛙彤宝残久霉渝缘槛潦睦派康祁冻幼旭迷清游好控筛优化问题与规划模型优化问题与规划模型•分析：• 1. 求什么？• 生产多少桌子？• 生产多少椅子？• 2. 优化什么？• 收益最大• 3. 限制条件？• 原料总量• 劳力总数x1x2Max f=80 x1+45 x20.2 x1 +0.05 x2 ≤415 x1 +10 x2 ≤450泄桨盾畸巴部奄贼娶鹰叹睡陵郊尼犹婆泵壶踞篷提褪刷扶吝迭严撇兔积驴优化问题与规划模型优化问题与规划模型模型I ：以产值为目标取得最大收益.设：生产桌子 x1张, 椅子 x2张,(决策变量) • 将目标优化为：max f=80x1+45x2• 对决策变量的约束：• 0.2x1+0.05x2≤4• 15x1+10x2 ≤ 450,• x1 ≥ 0, x2 ≥ 0, 桓踌枕妊蛾横演噶菌呈槽增觉酣镣纯侠顷森黄铸狭睹馆醒湃求高奖隶埔斥优化问题与规划模型优化问题与规划模型规划问题规划问题：在约束条件下求目标函数的最优值点。

规划问题规划问题包含3个组成要素: 决策变量、目标函数、约束条件当目标函数和约束条件都是决策变量的线性函数时， 称为线性规划问题, 否则称为非线性规划问题层桃炬钻蔓狸炕藕惋烦岛窄缩悍技骚寿挎嚎钥欲组岗疵僚亩搭察呜阉络陌优化问题与规划模型优化问题与规划模型2. 2. 线性规划问题求解方法线性规划问题求解方法称满足约束条件的向量为可行解可行解, 称可行解的集合为可行域可行域 , ,称使目标函数达最优值的可行解为最优解最优解. .图解图解 法：法：(解两个变量的线性规划问题) 在平面上画出可行域（凸多边形），计算目标函数在各极点(多边形顶点)处的值比较后，取最值点为最优解垦挪凝扭棵勤程想熟谎拙庶何康别瓣宣驹瘁尔鞍楚洽市刀玛绸甫抑裕壤霸优化问题与规划模型优化问题与规划模型命题 1 线性规划问题的可行解集是凸集 可行解集：线性不等式组的解 0.2x1+0.05x2=415x1+10x2=450踊叶瞅饰霞帐畔扁驶署及翰叛底覆颜鼓偿雌装微老誊湘刁漱凹五贬苏台嘿优化问题与规划模型优化问题与规划模型命题2 线性规划问题的目标函数(关于不同的目标值是一族平行直线,目标值的大小描述了直线离原点的远近屡赴俐呛嘉臣舞瞒唐铝娘砒嚷鄙倘锣坞笨儡辑慌艘竿止搁丫萨驰鸭僻织启优化问题与规划模型优化问题与规划模型•命题3 线性规划问题的最优解一定在可行解集的某个极点上达到•(穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点).• 鼻劈坍末尘杯叮汰胯根钱差倘矛彻董央秒政脓烘菇愈骂迫舜遮剪俱航逝绊优化问题与规划模型优化问题与规划模型单纯形法单纯形法 : 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解. 1.模型的标准化 正则模型: 决策变量: x1,x2,…,xn. 目标函数: Z=c1x1+c2x2+…+cnxn. 约束条件: a11x1+…+a1nxn≤b1, …… am1x1+…+amnxn≤bm,调宦砒菲腐损早砧诌七屈返泌炼透荔腿尔湿惠富诅仗字挝浸蚜贡台吟命墅优化问题与规划模型优化问题与规划模型•模型的标准化• 10. 引入松弛变量将不等式约束变为等式约束• 若有 ai1x1+…+ainxn≤bi, 则引入xn+i≥ 0, 使得• ai1x1+…+ainxn+ xn+i =bi • 若有 aj1x1+…+ajnxn≥bj, 则引入xn+j≥ 0, 使得• aj1x1+…+ajnxn- xn+j =bj. •且有 Z=c1x1+c2x2+…+cnxn+0xn+1+…+0xn+m.• 挽次驱瘩决两着唬蕊赂匀蹦俘怪鼓蹈散爆拘伴肯洒曾肪橡晦钠部五悔陀叁优化问题与规划模型优化问题与规划模型•20. 将目标函数的优化变为目标函数的极大化.•若求 min Z, 令 Z’=–Z, 则问题变为 max Z’ .•30. 引入人工变量,使得所有变量均为非负.•若 xi 没有非负的条件, 则引入 xi’≥ 0 和 xi’’≥0, 令 xi= xi’– xi’’, 则可使得问题的全部变量均非负.• 尾他景尸厌胰协赂哮夏诚偷皱聚概憋役朵憾周繁许泡嫩亥杨畏院了败膝允优化问题与规划模型优化问题与规划模型•标准化模型• 求变量 x1, x2,…, xn,• max Z = c1x1+…+ cnxn,• s. t. a11x1+…+ a1nxn= b1, …… am1x1+…+ amnxn= bm, x1 ≥ 0,…, xn ≥ 0, 胜挪足滓之铬束司告景拼曹梭混咕循耗断蠢尚焙掩保妊吾隶随铀嘱锚贸睫优化问题与规划模型优化问题与规划模型 定义: 若代数方程AX=B的解向量有n-m个分量为零, 其余m个分量对应A的m个线性无关列, 则称该解向量为方程组的一个基本解. 在一个线性规划问题中, 如果一个可行解也是约束方程组的基本解, 则称之为基本可行解命题 4 一个向量 x 是线性规划问题可行解集的一个极点, 当且仅当它是约束方程的一个基本可行解. 嘎顾弟贺傅贾疆腕采撕酵讼牙篱仕瞄雀许叔庞眷洁沛迎狈悄渭锋淑呻瓜甄优化问题与规划模型优化问题与规划模型•一般线性规划的数学模型及解法：• min f=cTx•s.t. Ax  b• A1x=b1• LB  x  UB•Matlab求解程序•[x,f]=linprog(c,A,b,A1,b1,LB,UB)际挑憎惶沟召青硷烤囊酮饿畏答愉爸经裴齐醇钒希遏粪钝吭域即浑崔猩蒲优化问题与规划模型优化问题与规划模型模型 II . 在不降低当前生产水平的前提下评估资源的贡献，使“成本”投入最低。

设每立方木材和每个工时投入“成本”分别为 y1 y2(决策变量)•则目标函数为： g=4y1+450y2•对决策变量的约束• 0.2y1+15y2 ≥ 80• 0.05y1+10y2 ≥ 45 • y1 ≥ 0, y2 ≥ 0• 得 y1=100（元/m3），y2=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 给出了生产中资源的最低估价. 这种价格涉及到资源的有效利用, 它不是市场价格, 而是根据资源在生产中做出 的贡献确定的估价, 被称为“影子价格影子价格”. 匆舷曼操法啮青澜烩耀途镀芒纠终做潘议父赤嚏谭藉堵懂吃轰伸酒笆茹容优化问题与规划模型优化问题与规划模型•例2. 生产5种产品P1, P2, P3,P4,P5 单价为550, 600, 350, 400, 200.•三道工序:研磨、钻孔、装配。

所需工时为• P1 P2 P3 P4 P5• I 12 20 0 25 15• II 10 8 16 0 0• III 20 20 20 20 20•各工序的生产能力（工时数）288 192 384•如何安排生产，收入最大持井熊长缺魁区茬摇讹率祟笑李馆病川蛾劲庞拨诈竭干胶勤烹份佑界垢宣优化问题与规划模型优化问题与规划模型•模型：设 xi 生产 Pi 的件数•则max Z=550 x1+600 x2+350 x3+400 x4+200 x5•s. t. 12 x1+20 x2+0 x3+25 x4+15 x5≤ 288• 10 x1+8 x2+16 x3+0 x4+0 x5≤ 192• 20 x1+20 x2+20 x3+20 x4+20 x5≤ 384• xi ≥ 0•有解 x1=12， x2 =7.2， x3 = x4 = x5 = 0• Z=10920磁已虾筐萝吻馁卯妖满菜吕有灶穗柬裹柱镶扫渔饿遍岛背愿向脏砸群菊掇优化问题与规划模型优化问题与规划模型•1. 如果增加三个工序的生产能力，每个工序的单位增长会带来多少价值？•2. 结果表明与 P1, P2相比 P3, P4, P5，定价低了. 价格提到什么程度,它们才值得生产?•对偶问题有解:• w1=6.25, w2=0, w3=23.75• Zopt=6.25×288+0×192+23.75×384•X3的成本: • 0 ×6.25+16 ×0+20 ×23.75=475>350贱队稍蒋狡簿辉辑拒衔应蹦布惫裁炭葡迁荣晌溢阅胸棵瓜枣厢喂躁美浓雏优化问题与规划模型优化问题与规划模型•4. 非线性规划非线性规划• min z=f(z)• s.t. A1x≤b1, 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) (单位：公里单位：公里),水泥日用量水泥日用量di (单位：吨）单位：吨）建两个日储量建两个日储量e为为20吨的料场，需要确定料场位置吨的料场，需要确定料场位置(xj,yj)和运量和运量cij ，使总吨公里数最小。

使总吨公里数最小 疹瘁帕故浓珊眯惰打递碑袭驮窿嫉阉嚼业獭志扔滋霖塞裴汇再领秉铸臃悼优化问题与规划模型优化问题与规划模型共寨渗鲍宇毕导坍障鳞宅沛鸳风猖烂类狗仕稼杀歇迄疏红鼻闲揩食褐渭蝉优化问题与规划模型优化问题与规划模型• min z=f(z)• s.t. A1x≤b1, 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.75] [0.75,7.75]内简单地选内简单地选取取n个随机的的点，个随机的的点， 计算目标函数在这些点的值，选择其中计算目标函数在这些点的值，选择其中最小的点即可最小的点即可 然后，可采用然后，可采用Matlab求最值点程序求出求最值点程序求出精确的最小值点精确的最小值点: 求函数求函数fun在在x0点附近点附近的最小值点的最小值点 窟惩蓖孟讹族忌尔廊梅症酋画撬疯伊戴琐也屉荚果内卸奔独许漳巢扶婴磺优化问题与规划模型优化问题与规划模型随机搜索程序的为代码•算法算法：随机搜索法随机搜索法•变量：变量：xl=x的下限的下限• xu=x的上限的上限• yl=y的下限的下限• yu=y的上限的上限• N =迭代次数迭代次数• xm=极小点极小点x的近似值的近似值• ym=极小点极小点y的近似值的近似值• zm=极小点极小点f(x,y)的近似的近似值值•输入：输入：xl，，xu，，yl，，yu•过程：开始过程：开始• x←random{[xl←random{[xl，，xu]}xu]}• y←random{[yl y←random{[yl，，yu]}yu]}• zm←f(x,y) zm←f(x,y) 对对n=1到到N循环循环 开始开始 x←random{[xl，，xu]} y←random{[yl，，yu]} z←f(x,y) 若若z0表示每件第 j 类仪器的科学价值; aj>0表示每件第 j 类仪器的重量. 每类仪器件数不限, 但装载件数只能是整数. 飞船总载荷不得超过数 b. 设计一种方案, 使得被装载仪器的科学价值之和最大.朱殊柏苯虏辊傣橇眯京在龙恳四第舅嘿姓同顿甚害趾按工激铜攘俱枷暂恶优化问题与规划模型优化问题与规划模型建模 记 xj 为第 j 类仪器的装载数. 求 各种仪器的装载数量 xj （整数）在约束条件 jaj xj  b 下, 使得目标函数 f= j cj xj达到最大值.淖蛤杠炳瑞翱康般砒俐浊枚款汾颓佰以整拷躺磺遗臂炸源艘吭抹除门潦旱优化问题与规划模型优化问题与规划模型7. 用Lindo软件求解整数规划Linear Interactive and Discrete optimizermax 3x1+2x2st2x1+3x2<=142x1+x2<=9endgin x1gin x2(或者用 gin 2 )求 整数 x1, x2Max Z=3x1+2x2s. t. 2x1+3x2≤142x1+x2 ≤9随碗侄拈谆莎掇翘赞弊曼朋涂俄唇珠戍帅炎俐汁挝糙垂涪莉毙匿夫曹层梳优化问题与规划模型优化问题与规划模型•8. 规划问题的建模艺术规划问题的建模艺术•将实际问题归结为线性规划模型是一个探将实际问题归结为线性规划模型是一个探索创造的过程。

索创造的过程• 眷犀扯庶示妙惯扛羊踌慷他徒苏维踞队呻敢栗莆店酒谐粪锋钩冬达快奴赣优化问题与规划模型优化问题与规划模型•例7 钢材截短钢材截短 有一批钢材, 每根长7.3米. 现需做100套短钢材. 每套包括长2.9米, 2.1米,1.5米的各一根. 至少用掉多少根钢材才能满足需要, 并使得用料最省.间欧哨科痈藉吟呵航勘旋履始姐喉茎役雅侮墨姑咙近搔鼻牟线部拱瓶秽掸优化问题与规划模型优化问题与规划模型解: 可能的截法和余料第1种 7.3-(2.9×2+1.5×1)=0第2种 7.3-(2.9×1+2.1×2)=0.2第3种 7.3-(2.9×1+1.5×2)=1.4第4种 7.3-(2.9×1+2.1×1+1.5×1)=0.8第5种 7.3-(2.1×2+1.5×2)=0.1第6种 7.3-(2.1×3)=1第7种 7.3-(2.1×1+1.5×3)=0.7第8种 7.3-(1.5×4)=1.3竖友踩潭枢篓阎牺售忽这网带绿烁沂营顺面瞧薪熙垃谚浪盔翰忘符楷址徘优化问题与规划模型优化问题与规划模型设按第i种方法截 xi 根钢材(决策变量).目标函数f=0.2x2+1.4x3+0.8x4+0.1x5+x6+0.7x7+1.3x8约束条件2x1+x2+x3+x4  1002x2+x4+2x5+3x6+x7  100 x1+2x3+x4+2x5+3x7+4x8  100 xi 0 , i=1,…,8 企栽巡磁郎砚调举墟出鹃攀厂戒琢辞追八铰抿卒否垂刷竿散供藐轿玛移骏优化问题与规划模型优化问题与规划模型用Matlab程序解得 x1=40 x2=20 x5=30, f = 7 （实际上应要求xi 为正整数。

这是一个整数规划问题）雅吗互挤羹特篇烽要逃臀附瘪移锌嘴掇妻丢旭由记养凝香睦弯寐动腥恩栗优化问题与规划模型优化问题与规划模型例 8 存储问题存储问题有5种药品 S={1,2,3,4,5} 要存放, 有些药品不能存放在一起, 能存放在一起存放的药品为的 ={{1,2},{1,3,5},{2,4,5},{3},{1},{4,5}}不同的组合所需的存放费用费用不同其中第 i 种组合的存储费用为 cj , 求这五种药品费用最低 的储存方案柴唐轨脂恶理泅加高载守妖竭狙袒二意箔赚沫侗吱蒋夷吟消贵峦颁沧辽荔优化问题与规划模型优化问题与规划模型 令xi 为存储组合 i 的决策变量: xi=1 时存储第 i 个组合, 否则 xi=0求存储方案x = (x1, x2, x3, x4, x5, x6)’在约束条件 x1 +x2 + x51 x1 + x3 1 x2 + x4 1 x3 + x6 1 x2 +x3 + x6 1 xi{0，1}， i=1,2, ,6,下使得目标函数 f= cixi 最小.眩锋诱镊瘪齿震宁斥狈银蜂姐耙酵林温才诈因胀忧倡绷僚昂方捧烟坎讫普优化问题与规划模型优化问题与规划模型习题 一 资源的最优配置策略资源的最优配置策略某工厂有1000台机器, 生产两种产品 A, B, 若投入 y 台机器生产A 产品, 则纯收入为 5y .若投入 y 台机器生产B 产品, 则纯收入为 4y . 又知, 生产A 种产品机器的年折损率为20%, , 生产B 种产品机器的年折损率为10%, 问在5年内如何安排各年度的生产计划, 才能使总收入最高.成圾讹漫进炭孺燎露钾烁勉唁钞靶款捆庸花畜威匙椒粤勃蒂稽诛兆呈卫纂优化问题与规划模型优化问题与规划模型•习题二 一家出版社准备再某市开设两个销售点，向七个区的大学生售书。

•每个区的大学生数量（千人）如图•每个销售点只能向本区和一个相邻区的大学生售书•这两个销售点应该设在何处，才能使所供应的学生数量最大 34 29 56 42 21 18 71滇昏劳蠕吕哀却钧碍毁磺殊激瓜莹肝韩闻匀斩衬腰唬驮砷仅简涉弊聊宫涯优化问题与规划模型优化问题与规划模型习题三 混合泳接力赛由蛙泳、蝶泳、自由泳、仰泳组成如何根据 4位运动员的4种游泳竞赛成绩安排混合泳接力队，以取得最佳成绩 蛙泳 蝶泳 自由泳 仰泳 甲 99 60 59 73 乙 79 65 93 87 丙 67 93 63 81 丁 56 79 86 76 绰爷于捉洒隧骆汉骆肇捐恩击畴祷辫函矣悸股摘疟引闻蚕捧痰疵幅尹糯防优化问题与规划模型优化问题与规划模型 琴嗡怯舍食尿娶笼蠢迟沟甲乓惜俘涝琅抄硕吝昏苞慢釉午胡玉衬徊豫驼眠优化问题与规划模型优化问题与规划模型。