整数规划和动态规划-数学建模.pdf

第1 章 整数规划和动态规划 数学规划 （Mathematical Programming ）是应用数学学科的一个重要分支，该术 语出现于20 世纪40 年代末，是由美国哈弗大学的Robert Dorfman 最先使用的，其 初始含义具有相当的包容性. 数学规划学科的内容十分丰富，包括许多研究分支，如：线性规划、非线性规 划、多目标规划、动态规划、参数规划、组合优化和整数规划、随机规划、模糊规 划、非光滑优化、多层规划、全局优化、变分不等式和互补问题等. 本章介绍整数规划和动态规划. 1.1 优化模型简介 1.1.1 优化模型的数学描述 将一个优化问题用数学式子来描述，即求函数 u f (x) , x (x ,x , x ,..., x ) 1 2 3 n 在约束条件 g (x) 0 (g (x) 0),i 1,2,..., p . i i 和 h (x) 0, j 1,2,..., m. j 下的最大值或最小值，其中x 称为决策变量 （设计变量）, f (x ) 为目标函数，D 为 ( x D )可行域. 最优化问题的数学模型一般形式为 min( or max) u f (x) x D s.t. g (x) 0 (g (x) 0),i 1,2,..., p . i i h (x) 0, j 1,2,..., m. j min, max 和 s.t.非别是英语单词 minimize( 极小化) ，maximize(极大化)和 subject to （“受约束于”之意）的缩写. 1.1.2 优化模型的分类 ( 1) 根据是否存在约束条件分为有约束问题和无约束问题. (2) 根据决策变量 （设计变量）的性质分为静态问题和动态问题. (3) 根据目标函数和约束条件表达式的性质分为线性规划，非线性规划，二次规 划，多目标规划等. 西安理工大学理学院 王秋萍 1) 非线性规划 （Nonlinear Programming ） 目标函数和约束条件中，至少有一个非线性函数. 2) 线性规划 （Linear Programming ） 目标函数和所有的约束条件都是决策变量(设计变量) 的线性函数. n min u c x j j j 1 n a x b ,i 1,2,..., m. ij j i s.t. j 1 xj 0, j 1,2,...,n . 3) 二次规划问题(Quadratic Programming)