最优化第1章.ppt

最 优 化 方 法 主讲：黄海新 简介 人类的一切活动都是认识世界和改造世界的过程 即： 认识世界 → 改造世界 ↓ ↓ (建模) (优化) 简介 一切学科都是建模与优化在某个特定领域中的应用 概念模型(定性) → 结构模型(图)→ 数学模型(定量） → 智能模型 简介 最优化是一门应用十分广泛的学科，它研究在有限种或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法。达到最优目标的方案，称为最优方案，有哪些信誉好的足球投注网站最优方案的方法，称为最优化方法。这种方法的数学理论，称为最优化理论。 简介 最优化理论的发展 极值理论； 运筹学的兴起(Operation Research)； 数学规划：线性规划(LP)；非线性规划(NLP)；动态规划(DP)；马尔托夫规划(MDP)；博弈论；排队论；决策论；存储论。 简介 实际上最优化方法已广泛应用于空间技术、军事科学、电子工程、通讯工程、自动控制、系统识别、资源分配、计算数学、生产制造、物流运输、经济管理等等领域。 第1章 线性规划 1.1 线性规划问题的基本概念 1.1.1 线性规划问题及其数学模型 ？如何合理地使用有限的劳动力、设备、资金等资源，以得到最大的效益（如生产经营利润）。 ？为了达到一定的目标（生产指标或其他指标），应如何组织生产，或合理安排工艺流程，或调整产品的成分等，以使消耗资源（人力、设备台时、资金、原材料等）为最少。 第1章 线性规划 例1： 第1章 线性规划 例2：某铁器加工厂要制作100套钢架，每套要用长为2.9m、2.1m、1.5m的圆钢各一根。已知原料长为7.4m，问应如何下料，可使所用材料最省。 第1章 线性规划 线性规划问题的一般数学模型： 第1章 线性规划 1.1.2 两个变量问题的图解法 图解法（略） 线性规划问题的解： 有唯一最优解 有无穷多个最优解 无界解（无最优解） 无可行解——可行域为空 第1章 线性规划 线性规划问题可行域与解之间的性质： 若可行域非空且有界，则可行域是一个多边形，其顶点个数是有限个；若可行域非空但无界，其顶点个数也只有有限个。 若可行域非空且有界则必有最优解；若可行域无界，则可能有最优解，也可能无最优解。 若线性规划问题有最优解（不论可行域是有界还是无界），其最优解必在某个顶点上达到。最优解的个数或是唯一的，或有无穷多个。 第1章 线性规划 1.1.3 线性规划数学模型的标准形式及解的概念 （1）标准形式： 一般表达式 记号简写式 矩阵形式 向量形式 第1章 线性规划 （2）将非标准形式化为标准形式 min，max ，松弛变量 ，剩余变量 ，约束方程两端乘以（－1） 决策变量 无非负要求，令两个新变量 作 第1章 线性规划 （3）有关解的概念 若模型为 式中， 定义1.1.1 凡是满足(1.1.20)式及（1.1.21）式的解 称为线性规划问题的可行解，同时满足（1.1.19）式的可行解为最优解。 定义1.1.2 设线性规划约束方程组中的系数矩阵 的秩为m(nm)，则A中某m列组成的任一个m阶可逆阵B称为线性规划问题的一个基矩阵，简称为一个基。若记 则称 为基B中的一个基向量。而A中其余n-m个列向量称为非基向量。 第1章 线性规划 定义1.1.3 基变量，非基变量 定义1.1.4 基本解 定义1.1.5 基本可行解 基本解、基本可行解的个数均小于 第1章 线性规划 1.1.4 线性规划的基本理论 线性规划问题的可行域是一个有界或无界的凸多边形，其顶点个数是有限个。 若线性规划问题有最优解，则其最优解必可在某顶点上达到。 1. 凸集与凸组合 定义1.1.6 凸集 定义1.1.7 凸组合 定义1.1.8 极点 第1章 线性规划 2. 线性规划基本定理 定理1.1.1 若线性规划问题存在可行域，则可行域 为一凸集。 定理1.1.2 线性规划问题可行解 为基本可行解的充分必要条件是：x中正分量所对应的系数列向量线性无关。 定理1.1.3 线性规划问题的每一个基本可行解x对应于可行域S的一个极点。 定理1.1.4 有界凸集S上任一点x都可表示为S的极点的凸组合。 定理1.1.5 对线性规划问题，若可行域有界，