第一章 线性规划

§1 线性规划

1.1 线性规划的实例与定义

1.2 线性规划的 Matlab 标准形式

1.3 线性规划问题的解的概念

1.4 线性规划的图解法

1.5 求解线性规划的 Matlab 解法 （练习）

1.6 可以转化为线性规划的问题

§2 运输问题(产销平衡)

§3 指派问题

3.1 指派问题的数学模型

3.2 求解指派问题的匈牙利算法

注：有时问题会复杂些，有以下方法：

§4 对偶理论与灵敏度分析

4.1 原始问题和对偶问题

4.2 对偶问题的基本性质 （练习）

4.3 灵敏度分析

4.4 参数线性规划

§5 投资的收益和风险

这一节略看，当有需求时再翻阅查找。（数学建模算法与应用P9~12）

5.1 问题提出

5.2 符号规定和基本假设

5.3 模型的分析与建立

5.4 模型一的求解

5.5 结果分析

第二章 整数规划

§1 概论

1.1 定义

1.2 整数规划的分类

整数线性规划模型：

变量全限制为整数	变量部分限制为整数
纯（完全）整数规划	混合整数规划

1.3 整数规划特点

（i） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况：
①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
③有可行解（当然就存在最优解），但最优解值变差。
（ii） 整数规划最优解不能按照实数最优解简单取整而获得。

1.4 求解方法分类

§2 分枝定界法

§3 0 −1型整数规划

3.1 引入0 −1变量的实际问题

3.1.1 投资场所的选定——相互排斥的计划

3.1.2 相互排斥的约束条件

3.1.3 关于固定费用的问题（Fixed Cost Problem）

3.2 0 −1型整数规划解法之一（过滤隐枚举法）

§4 蒙特卡洛法（随机取样法）

§5 指派问题的计算机求解

§6 生产与销售计划问题

第三章 非线性规划

§1 非线性规划

1.1 非线性规划的实例与定义

NP

1.2 线性规划与非线性规划的区别

如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行
域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任
意一点达到。

1.3 非线性规划的 Matlab 解法

Matlab 中非线性规划的数学模型写成以下形式

其中 f (x)是标量函数， A, B, Aeq, Beq是相应维数的矩阵和向量，C(x),Ceq(x) 是非
线性向量函数。
Matlab 中的命令是
X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)
它的返回值是向量 x ，其中 FUN 是用 M 文件定义的函数 f (x)；X0 是 x 的初始值；
A,B,Aeq,Beq 定义了线性约束 A* X ≤ B, Aeq * X = Beq ，如果没有线性约束，则
A=[],B=[],Aeq=[],Beq=[]；LB 和 UB 是变量 x 的下界和上界，如果上界和下界没有约
束，则 LB=[]，UB=[]，如果 x 无下界，则 LB 的各分量都为-inf，如果 x 无上界，则 UB
的各分量都为 inf；NONLCON 是用 M 文件定义的非线性向量函数C(x),Ceq(x) ；OPTIONS
定义了优化参数，可以使用 Matlab 缺省的参数设置。

1.4 求解非线性规划的基本迭代格式

§2 无约束问题

2.1 一维搜索方法

2.1.1 Fibonacci 法

2.1.2 0.618 法

2.2 二次插值法

对极小化问题（2），当 f (t) 在[a,b] 上连续时，可以考虑用多项式插值来进行一
维搜索。它的基本思想是：在搜索区间中，不断用低次（通常不超过三次）多项式来近
似目标函数，并逐步用插值多项式的极小点来逼近（2）的最优解。

2.3 无约束极值问题的解法

无约束极值问题可表述为
( ) min ( ), n f x x ∈ E （5）
求解问题（5）的迭代法大体上分为两点：一是用到函数的一阶导数或二阶导数，
称为解析法。另一是仅用到函数值，称为直接法。

2.3.1 解析法

2.3.1.1 梯度法（最速下降法）

2.3.1.2 Newton 法

2.3.1.3 变尺度法

2.3.2 直接法

2.4 Matlab 求无约束极值问题

§3 约束极值问题

3.1 二次规划 （例8？）

若某非线性规划的目标函数为自变量 x 的二次函数，约束条件又全是线性的，就称
这种规划为二次规划。
Matlab 中二次规划的数学模型可表述如下：

3.2 罚函数法

3.3 Matlab 求约束极值问题

在 Matlab 优化工具箱中，用于求解约束最优化问题的函数有：fminbnd、fmincon、
quadprog、fseminf、fminimax，上面我们已经介绍了函数 fmincon 和 quadprog。

3.3.1 fminbnd 函数

3.3.2 fseminf 函数

3.3.3 fminimax 函数

3.4 Matlab 优化工具箱的用户图形界面解法

§4 飞行管理问题

总结思考

因为错过消息，自己迟了一周才开始学习，所以本次的打卡内容只截取了自认为重点的内容，建造了这三章的大体知识框架。学习资料要求的部分基本都细细看过，有些太难的也就没有太深究（太忙了这段时间QAQ），其中遗留两三道例题需要下次再练习，还有这些规划的函数得重新整理一遍，加深印象以免混淆。