南人文科技学院 数学建模併义之
数学建模讲义之优化模型 数学建模讲义之 优化模型
数学建模讲义之优化模型 引言:最优化方法的发展进程 最优化方法和理论来源于军事,管理和经济。我 国古代军事天才孙武所著《孙子兵法》成书于公元 前五世纪春秋未期,是我国也是世界上最古老的军 事理论著作,《孙子兵法》十三篇把军事运筹学的 思想,理论和方法阐述得淋漓尽致,可谓达到了神 化的地步。连外国人也对孙武子倍加赞赏,1984 年美国军事运筹学会出版专著《 System Analysis and Modeling in Defence》,书中称孙武子是世 界上第一个军事运筹学的实践家。 两次世界大战,尤其是二战中提出的很多均是最 优化问题,诸如搜索潜艇问题;护航问题;布雷问 题;轰炸问题以及运输问题等等。二战中所提到的 军事问题及其解决方法有如下特点
数学建模讲义之优化模型 一 引言:最优化方法的发展进程 最优化方法和理论来源于军事，管理和经济。我 国古代军事天才孙武所著《孙子兵法》成书于公元 前五世纪春秋末期，是我国也是世界上最古老的军 事理论著作，《孙子兵法》十三篇把军事运筹学的 思想，理论和方法阐述得淋漓尽致，可谓达到了神 化的地步。连外国人也对孙武子倍加赞赏，1984 年美国军事运筹学会出版专著《System Analysis and Modeling in Defence》，书中称孙武子是世 界上第一个军事运筹学的实践家。 两次世界大战，尤其是二战中提出的很多均是最 优化问题，诸如搜索潜艇问题；护航问题；布雷问 题；轰炸问题以及运输问题等等。二战中所提到的 军事问题及其解决方法有如下特点：
数学建模讲义之优化模型 数据是实践中的真实数据;解决问题的人员组成是多学科的 处理问题的方法渗透着物理学的思想。第二次世界大战以后最优 化方法的应用由军事问题转入民用问题,提出了现代管理的理论 和方法,如计划管理,运输管理,工程建设管理,库存管理,工 业工程管理等等。 1930年苏联数学家 Cantolovch首创图上作业法解决小规模 (以二维为类)得线性规划问题,如物资调运方案,合理下了方 案等。而大规模的线性规划(高维问题)则是在电子计算机问世 以后才得发展; 1936年美国的经济学家列昂?夫首创投入产出分析法,而反 映国民经济动态运行的大型投入产出表的制定也是在大型计算机 的支持下才能够实现;
数学建模讲义之优化模型 数据是实践中的真实数据；解决问题的人员组成是多学科的； 处理问题的方法渗透着物理学的思想。第二次世界大战以后最优 化方法的应用由军事问题转入民用问题，提出了现代管理的理论 和方法，如计划管理，运输管理，工程建设管理，库存管理，工 业工程管理等等。 1930年苏联数学家Cantolovch首创图上作业法解决小规模 （以二维为类）得线性规划问题，如物资调运方案，合理下了方 案等。而大规模的线性规划（高维问题）则是在电子计算机问世 以后才得发展； 1936年美国的经济学家列昂？夫首创投入产出分析法，而反 映国民经济动态运行的大型投入产出表的制定也是在大型计算机 的支持下才能够实现；
1935-1940年 Dodge(道奇)和Bake(自莱盖)首 创统计抽样法,为此后数理统计学科发展奠定基础。 二战以后,科学和工业的蓬勃发展引起了许多新的变 化,主要表现在:生产规模日益庞大,生产技术日益复 杂,商业经营日趋国际化,环境污染和生态问题日益产 重 管理人员和计划人员面临十分复杂的问题,迫切需要 种统筹兼顾,行之有效的科学方法来处理复杂的管理 问题。一个最典型的例子即是邮递员问题或旅行商问题
数学建模讲义之优化模型 1935-1940年Dodge（道奇）和Blaket（白莱盖）首 创统计抽样法，为此后数理统计学科发展奠定基础。 二战以后，科学和工业的蓬勃发展引起了许多新的变 化，主要表现在：生产规模日益庞大，生产技术日益复 杂，商业经营日趋国际化，环境污染和生态问题日益严 重。 管理人员和计划人员面临十分复杂的问题，迫切需要 一种统筹兼顾，行之有效的科学方法来处理复杂的管理 问题。一个最典型的例子即是邮递员问题或旅行商问题
二优化模型的一般意义 数学建模讲义之优化模型 (一)优化模型的数学描述 将一个优化问题用数学式子来描述,即求函数 =f(x)x=(x1,x2,x32…,x2) 在约束条件(x)=0.=12m 和8(x)≤0g(x)20)=12P 下的最大值或最小值,其中 设计变量(决策变量) f(x) 目标函数 x∈Q 可行域
数学建模讲义之优化模型 （一）优化模型的数学描述 下的最大值或最小值，其中 h ( ) ,i , ,...,m. i x = 0 =1 2 g ( ) (g ( ) ),i , ,..., p. i x 0 i x 0 =1 2 设计变量（决策变量） 目标函数 ( , , ,..., ) n x x x x x = 1 2 3 将一个优化问题用数学式子来描述，即求函数 u = f (x) 在约束条件 和 x f (x) x 可行域 二 优化模型的一般意义
数学建模讲义之优化模型 min( or max)u=f(x)x∈ s.t.h1(x)=0,=1,2…,m g(x)≤0(g(x)≥0),i=1,2,…,p S.t. subject to“受约束于”之意
数学建模讲义之优化模型 s. t. h ( ) ,i , ,...,m. i x = 0 =1 2 g ( ) (g ( ) ),i , ,..., p. i x 0 i x 0 =1 2 min( or max) u = f (x) x s. t. subject to “受约束于”之意
数学建模讲义之优化模型 (二)优化模型的分类 有约束问题和无约束问题。 静态问题和动态问题。 线性规划,非线性规划,二次规划,多目标规划等
数学建模讲义之优化模型 （二）优化模型的分类 1.根据是否存在约束条件 有约束问题和无约束问题。 2.根据设计变量的性质 静态问题和动态问题。 3.根据目标函数和约束条件表达式的性质 线性规划，非线性规划，二次规划，多目标规划等
数学建模讲义之优化模型 (1)非线性规划 目标函数和约束条件中,至少有一个非线性函数 minu=f(x)x∈g s.t.h1(x)=0,i=1,2,…,m g(x)≤0(g1(x)≥0),i=1,2,…,p
数学建模讲义之优化模型 （1）非线性规划 目标函数和约束条件中，至少有一个非线性函数。 s. t. h ( ) ,i , ,...,m. i x = 0 =1 2 g ( ) (g ( ) ),i , ,..., p. i x 0 i x 0 =1 2 min u = f (x) x
数学建模讲义之优化模型 (2)线性规划(LP) 目标函数和所有的约束条件都是设计变量 的线性函数。 mn u- ∑cx a.,x1=b.i=1.2 S.t.1k=1 x1≥0,i=1,2,,n
数学建模讲义之优化模型 = = = = = = , , ,..., . , , ,..., . . . min x i n a x b i n st u c x i n k i k k i n i i i 0 1 2 1 2 1 1 （2）线性规划（LP） 目标函数和所有的约束条件都是设计变量 的线性函数
数学建模讲义之优化模型 (3)二次规划问题 目标函数为二次函数,约束条件为线性约束 min=f(x)=∑cx+∑bxx 2 a.x.<b,i=1.2...n. st x1≥0.=1,2,…,n
数学建模讲义之优化模型 （3）二次规划问题 目标函数为二次函数，约束条件为线性约束 = = = = + = = = . , ,..., . , , ,..., . . . min ( ) , x i n a x b i n st u f x c x b x x i n j i j j i n i j i j i j n i i i 0 1 2 1 2 2 1 1 1 1