最优化建模算法与理论答案

8¹

3Ã å`z3.1 `5^ .....................................3.2 { Ú½9Âñ5.............................3.3 eü{.....................................3.4Úî{.......................................3.5[Úî{......................................3.6

ÝFÝ{.....................................

11412152227

8¹·ii·

1nÙÃ å`z

â1 Ü© {nØÐÚ §3¦) 55y¯K L§¥§· I (½|¢ Ú

最优化理论与算法（数学专业研究生）

第一章 引论

§1.1 引言

一、历史与现状

最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括Fritz John最优性条件（1948），Kuhn-Tucker最优性条件（1951），和Karush最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。 二、最优化问题的一般形式 1、无约束最优化问题

minf(x) （1.1）

x?Rn2、约束最优化问题

minf(x)

?ci(x)?0, i?E （1.2）

s.t.??ci(x)?0, i?I这里E和I均为指标集。

§1.2数学基

第二章 5 生成树算法

定义2·13 （1）图G的每条边e赋与一个实数?(e)，称为e的权。图G称为加权图。 （2）设G1是G的子图，则G1的权定义为： ?(G1)???(e)

e?E(G1)定理2·10 Kruskal算法选得的边的导出子图是最小生成树。

l法所得子图T0显然是生成树，下证它的最优性。设证：Kruska算T0?G??e1,e2,?,e??1??不是最小生成树，T1是G的任给定的一个生成树，f(T)是

?e1,e2,?,e??1?中不在T1又E(T0)??e1,e2,?,e??1?，故e1,e2,?,e??1中必有不在E(T)中的

边。设f(T)?k，即e1,e2,?,ek?1在T与T0上，而ek不在T上，于是T?ek中有一个圈C，

?，使ek?在T上而不是在T0上。令T???，显然也是生成树，又（T?ek)?ekC上定存在ek?)，由算法知，ek是使G??e1,e2,?,ek??无圈的权最小的边，?(T?)??(T)??(ek)??(ek???是T之子图，也无圈，则有?(ek?)??(ek)，于是?(T?)??(T)，又G??e1,e2,?,ek

非诚勿扰男女最优组合

摘要：本文主要内容为寻求最大权匹配问题，即利用图论的最大权匹配知识，为非诚勿扰节目中的男女嘉宾进行最优组合。本文将其转化为二部图寻找最大权匹配的问题。 关键词：非诚勿扰，最大权匹配

1、问题描述

《非诚勿扰》是中国江苏卫视制作的一档大型生活服务类节目。 每期节目大部分都是5位男嘉宾，24位女嘉宾，女生有“爆灯”权利。首先男嘉宾选择心动女生，女嘉宾在“爱之初体验”根据第一印象选择是否留灯；然后在“爱之再判断”了解男嘉宾的一些基本情况，比如爱好、情感经历等；接下来在“爱之终决选”通过男嘉宾亲人或朋友的情况了解男嘉宾，做出最后的决定，如果有女生留灯的话就进入“男生权利”，男生做出最后选择，如果没有女生留灯则只能遗憾离场。

2、模型建立

通过观看20150124期节目，这期节目只有4位男嘉宾，然后在整个节目男女嘉宾交流过程中4号、19号、22号、23号女嘉宾都没有发过言，没有了解到这四位女嘉宾的基本情况以及对男嘉宾的要

求，所以在本次模型建立过程中没有考虑这四位女嘉宾。

经过上述分析，本期产生了4位男嘉宾和20位女嘉宾的可能匹配，我们将这4位男嘉宾和20位女嘉宾划分为X部和Y部，男生为X1，X2，X3，X4，女生

非诚勿扰男女最优组合

摘要：本文主要内容为寻求最大权匹配问题，即利用图论的最大权匹配知识，为非诚勿扰节目中的男女嘉宾进行最优组合。本文将其转化为二部图寻找最大权匹配的问题。 关键词：非诚勿扰，最大权匹配

1、问题描述

《非诚勿扰》是中国江苏卫视制作的一档大型生活服务类节目。 每期节目大部分都是5位男嘉宾，24位女嘉宾，女生有“爆灯”权利。首先男嘉宾选择心动女生，女嘉宾在“爱之初体验”根据第一印象选择是否留灯；然后在“爱之再判断”了解男嘉宾的一些基本情况，比如爱好、情感经历等；接下来在“爱之终决选”通过男嘉宾亲人或朋友的情况了解男嘉宾，做出最后的决定，如果有女生留灯的话就进入“男生权利”，男生做出最后选择，如果没有女生留灯则只能遗憾离场。

2、模型建立

通过观看20150124期节目，这期节目只有4位男嘉宾，然后在整个节目男女嘉宾交流过程中4号、19号、22号、23号女嘉宾都没有发过言，没有了解到这四位女嘉宾的基本情况以及对男嘉宾的要

求，所以在本次模型建立过程中没有考虑这四位女嘉宾。

经过上述分析，本期产生了4位男嘉宾和20位女嘉宾的可能匹配，我们将这4位男嘉宾和20位女嘉宾划分为X部和Y部，男生为X1，X2，X3，X4，女生

《最优化方法与数学建模》结课题目

1. 投资问题

某银行经理计划用一笔资金进行有价证券的投资，可供购进的证券以及其信用等级、到期年限、收益如下表所示。按照规定，市政证券的收益可以免税，其它证券的收益需按50%的税率纳税。此外还有以下限制： （1）政府及代办机构的证券总共至少要购进400万元；

（2）所购证券的平均信用等级不超过1.49，信用等级数字越小，信用程度越高； （3）所购证券的平均到期年限不超过5年. 1）若该经理有1000万元资金，应如何投资？

2）如果能够以2.75%的利率借到不超过100万元资金，该经理应如何操作？ 3）在1000万元资金情况下，若证券A的税前收益增加为4.5%，投资应否改变？若证券C的税前收益减少为4.8%，投资应否改变？

表 证券信息

到期税 证券种类 市政 代办机构 政府 政府 市政

信用等级 2 2 1 1 5

到期年限 （%） A B C D E

9 15 4 3 2

4.3 5.4 5.0 4.4 4.5 前收益2．阿桑的计划

阿桑小姐是一个小学教师，她刚刚继承了一笔遗产，交纳税金后净得50,000美元。阿桑小姐感到她的工资已足够她每年的日常开支，但是还不能满足她暑假旅游的计划。因此，她

《最优化理论与方法》复习内容要求和题型

一、复习内容要求

1、最优化问题及其分类，最优解的相关概念，最优化问题的算法的一般迭代格式及其收敛性和停止准则。

2、建立一个实际最优化问题的数学模型的思想和方法，包括线性规划、非线性规划、动态规划及多目标规划模型。

3、掌握单纯形法的理论依据、基本思想和最优性检验定理，熟练用大M法和两阶段求解线性规划问题，特别是构造的新问题与原问题的解的关系。

4、了解内点法的基本思想，掌握线性规划和0-1规划问题的计算机求解方法。

5、知道解决特殊线性规划问题的解法（含分支定界法、隐枚举法、表上作业法和匈牙利法）的思想方法。

6、了解非线性规划问题及数学模型，了解非线性规划的相关概念及理论，知道非线性规划的最优性条件。

7、掌握一维搜索的黄金分割法（0.618法）与Fibonacci法，知道二分法，特别注意这些算法的适用条件。

8、掌握最速下降法、牛顿类算法、FR共轭梯度法的算法步骤，并熟练使用它们求解多维无约束非线性规划，特别注意这些算法的异同点及它们与一维优化的关系。

9、了解惩罚函数法的算法思想，熟练掌握用内、外点法求解多维约束非线性规划问题，特别注意它们的异同点及适用条件。

10、了解乘子法的算法思想，熟练

铺路问题的最优化模型

摘 要

本文采用了两种方法，一种是非线性规划从而得出最优解，另一种是将连续问题离散化利用计算机穷举取最优的方法。

根据A地与B地之间的不同地质有不同造价的特点，建立了非线性规划模型和穷举取最优解的模型，解决了管线铺设路线花费最小的难题。

问题一：在本问题中，我们首先利用非线性规划模型求解，我们用迭代法求出极小值（用Matlab实现），计算结果为总费用最小为748.6244万元，管线在各土层中在东西方向上的投影长度分别为15.6786km，3.1827 km，2.1839 km，5.8887km，13.0661km。然后，我们又用穷举法另外建立了一个模型，采用C语言实现，所得最优解为最小花费为748.625602万元，管线在各土层中在东西方向上的投影长度分别为15.70km,3.20km,2.20km,5.90km,13.00km。

问题二：本问题加进了一个非线性的约束条件来使转弯处的角度至少为160度，模型二也是如此。非线性规划模型所得计算结果为最小花费为750.6084万元，管线在各土层中在东西方向上的投影长度分别为14.4566km,4.3591km,2.5984km,6.5387km,12.0472km

最优化方法习题1答案

《最优化方法》（研究生）期末考试练习题答案

二.简答题

min -5y1 9y2, s.t. 4y1 3y2 3, -2y1 y2 2, 1．

3y1 4y2 8, y1,y2 0;

x3 x4 0, （以x1为源行生成的割平面方程） 2．

注意：在x1为整数的情况下，因为x3,x4 0，该方程自然满足，这是割平面的退化情形

1

656

111

x3 x4 , （以x2为源行生成的割平面方程）

442

3．

a1 0,b1 3

1 a1 0.382(b1 a1) 0 0.382*3 1.146

1 a1 0.618(b1 a1) 0 0.618*3 1.854 ( 1) (1.146)3 2*1.146 1 0.2131 ( 1) (1.854)3 2*1.854 1 3.6648

事实上,不经计算也可以看出

( 1) ( 1)，所以a2 0,b2 1.854。

即：初始的保留区间为[0，1.854]。近似的最优解：x*

0 1.854

0.927.2

f1(x) x1e x2*( 1) 2.7 x1ex2 2.7

4．令

f2(x) x1

第六章 最优化问题数学模型

§1 最优化问题 1．1 最优化问题概念 （1）最优化问题

在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大

值最小值问题。

最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；

②求出取得极值时变量的取值。

最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的

关键因素：变量，约束条件和目标函数。

（2）变量

变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般

来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。

设问题中涉及的变量为x1,x2,?,xn；我们常常也用X?(x1,x2,?,xn)表示。 （3）约束条件

在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。 例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，