PDF《最优化概述》

如果仅要求部分决策变量取整数, 称为混合 整数规划问题.有的问题要求决策变量仅取0或1两 个值,称为 0-1规划问题. 整数规划简称为IP问题(Integer Programming,IP)或ILP 问题(Integer Linear Programming).这里主要讨论的是整数 线性规划. Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 整数规划 最优化问题中的所有变量均为整数时,这类问题称为整 数规划问题. 如果线性规划中的所有变量均为整数时,称这类问题为 线性整数规划问题. 整数规划可分为线性整数规划和非线性整数规划 ,以及 混合整数规划等. 如果决策变量的取值要么为0,要么为1,则这样的规划 问题称为0-1规划. Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 列子 某钢厂两个炼钢炉同时各用一种方法炼钢.第一种炼法每 炉用 a 小时,第二种用 b 小时(包括清炉时间).假定这两 种炼法,每炉出钢都是 k 公斤,而炼

1 公斤钢的平均燃料费 第一法为 m 元,第二法为 n 元.若要求在 c 小时内炼钢公斤 数不少于 d ,试列出燃料费最省的两种方法的分配方案的数 学模型. Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 解法 设用第一种炼法炼钢 x1 炉,第二种炼钢 x2 炉max z = k(mx + ny) s.t. ? ? ? ? ? ? ? ax1 ≤ c bx2 ≤ c k(x1 + x2) ≥ d x1, x2 ≥ 0且为整数 具体求解运算在此不作过多叙述,都是矩阵运算,相信大家 对纯公式推导演算没多大兴趣. Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 单纯形法 单纯形法是优美国数学家G.B.Dantzig提出的,该方法的 基本出发点就是在可行域(凸集)的定点中搜索最优点.搜 索的过程是一个迭代的过程.首先找到一个基本可行解,判 别它是否为最优解,如不是就找一个更好的基本可行解,再 进行判别.如此迭代,直至找到最优解,或者判定该问题无 界. Liu Zheng 最优化概述 最优化概述 Liu Zheng 最优化方法概 述 经典极值问题 无约束极值问题 有约束最优化 有约束最优化问题的 数学建模 最优化方法主要内容 线性规划与整 数规划 整数规划 单纯形法 多目标规划 非线性规划 凸函数 下降迭代法 变分法与动态 规划 动态规划 智能优化方法 .. . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . .. . . . .. . .. . .. . . . .. . . . . .. . . . .. . . . .. . 凸集 定义: X 是En 空间的点集, x1 和x2 是X上任意两点, 若对任意