2_优化规化课件.ppt

Harbin Institute of Technology 数学规划（最优化原理）是运筹学的一个分支，用它可以对各种生产活动进行规划，在可供利用资源（如矿藏、水能、原料、生态环境、资金、时间等）的限制条件下，使生产活动得到最大的效益，或用最少的资源完成指定的生产活动。 数学规划广泛应用于国民经济各部门和工程领域，在所有可能的方案中有哪些信誉好的足球投注网站出最合理、达到事先预定目标的最优方案。 电力系统规划是一种约束最优化问题，需要利用数学规划方法进行建模和求解。 最优化问题的解决主要分两个步骤： 首先，如何根据实际应用中的具体问题，建立相应的数学模型。 即，如何用数学关系式来表示最优化问题所要达到的目标和各种约束条件。 然后，确定采用哪种合理的最优化方法对所建立的数学模型进行求解，得到最优化结果。 对于不同的数学优化模型，有不同的优化求解方法和技术。 线性规划 整数规划 二次规划 非线性规划 动态规划 第二次世界大战以前： 微分法、变分法，---进展缓慢！ 20 世纪中叶有大发展(计算机)，开辟了一系列新的优化问题RD领域： 如线性规划方法、非线性规划方法、动态规划方法、图论方法等。 20 世纪 80 年代以来，一些新型的智能优化算法，通过模拟或揭示某些自然现象或过程而得到发展： 如模拟退火算法、遗传算法、神经网络算法、模糊集算法等。 §0 概述 最简单、最基础的一类数学规划问题，有以下特征： 有一组未知数，表示决策变量，非负。 存在一定的限制条件(称为约束，用一组线性等式或线性不等式表达)。 有一目标函数。 求解方法： 单纯型法 Simplex Method,1947年由 Dantzig 提出。 内点法 /otc/InteriorPoint/ 1.1 问题的提出 [eg.1] 生产计划问题, 问: 产品Ⅰ、Ⅱ各生产多少件，使利润最大？ [eg.2] 污水处理问题 环保要求河水含污低于2‰，河水可自身净化20%。 问：化工厂1、2每天各处理多少污水，使总费用最少？ 线性规划的数学模型： max (min) z = c1x1 + c2x2 + ··· + cnxn a11x1 + a12x2 + ··· + a1nxn≤(=, ≥) b1 a21x1 + a22x2 + ··· + a2nxn≤(=, ≥) b2 ┆ ┆ am1x1+ am2x2+ ··· + amnxn≤(=, ≥) bm x1，x2，···，xn ≥ 0 说明： 1.2 线性规划的标准型 1、标准型 max z = c1x1 + c2x2 + … + cnxn a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 ┆ ┆ am1x1 + am2x2 + … + amnxn = bm x1，x2，…，xn ≥ 0 用向量表示： 用矩阵描述： max z = CX s.t. AX = b X ≥0 其中: X = (x1,x2,…,xn)T C = (c1,c2,…,cn) b = (b1,b2,…,bm)T 2、标准型的化法 (1)min→max ∵ min z = cx = -max(-z) ∴ max(-z) = -min z = -cx 令 z’= -z,则 max z’= -cx [eg.7] 将下述问题化为标准型 min z = -x1+2x2-3x3 x1+ x2 + x3 ≤ 7 ① x1 - x2 + x3 ≥ 2 ② -3x1+ x2+2x3 = 5 ③ x1, x2 ≥ 0，x3 无约束 HW: 将下述问题化为标准型，并用矩阵形表示？ [eg.3]用图解法求eg.1。 max z = 2x1 + 3x2 1x1 + 2x2 ≤ 8 ① 4x1 ≤ 16 ② 4x2 ≤ 12 ③ x1，x2