建模打卡

第一章 线性规划(Linear Programming 简记 LP)

意义：
在约束条件下求目标函数的最值，用现有资源来安排生产，以取得最大经济效益。

第一节
1.1定义：
可行解：满足约束条件s.t.（subject to）的解向量x；
最优解：使目标函数（3）达到最大值的可行解叫最优解。
可行域：有可行解构成的集合称为问题的可行域，记为 R 。
存在最优解的条件：可行域多胞形存在顶点
定义1：称 n 维空间中的区域 R 为一凸集，若 ∀x x ∈ R 1 2 , 及 ∀λ ∈(0,1) ，有 x + − x ∈R 1 2 λ (1 λ) 。
定义2： 为n 维空间中的一个凸集， R 中的点 x 被称为 R 的一个极点，若不 存在 x x ∈ R 1 、 2 及λ ∈(0,1) ，使得 1 2 x = λx + (1− λ)x 。
1.2 线性规划的 Matlab 标准形式

其中 c 和 x 为 n 维列向量， A 、 Aeq 为适当维数的矩阵，b 、beq 为适当维数的列向 量

Matlab中的基本函数形式为 linprog(c,A,b)，它的返回值是向量 x 的值。还有其它的一些函数调用形 式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如： [x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS) 这里 fval 返回目标函数的值，LB 和 UB 分别是变量 x 的下界和上界， 0 x 是 x 的初始值， OPTIONS 是控制参数

1.6 可以转化为线性规划的问题
很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决。如

应用：
1，运输问题(产销平衡)
2…指派问题(匈牙利算法）
3 对偶理论与灵敏度分析
4 资的收益和风险

第二章 整数规划

1.1 定义
规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中， 变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适 用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

1.2 整数规划的分类
如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.2 整数规划特点 （i） 原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况： ①原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 ②整数规划无可行解。③有可行解（当然就存在最优解），但最优解值变差。
1.3 求解方法分类：
（i）分枝定界法—可求纯或混合整数线性规划。
（ii）割平面法—可求纯或混合整数线性规划。
（iii）隐枚举法—求解“0-1”整数规划：(互斥计划引入0-1变量)
①过滤隐枚举法；（即先比较再验证）②分枝隐枚举法。
（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）
（v）蒙特卡洛法（随机取样法）—求解各种类型规划。

第三章 非线性规划

1.1引入：
对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：（i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基 础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。
（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化 或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。 （iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或 “坏”的价值标准，并用某种数量形式来描述它。
（iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或 极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些 不等式或等式来表示。
1.2 线性规划与非线性规划的区别
如果线性规划的最优解存在，其最优解只能在其可行域的边界上达到（特别是可行 域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任 意一点达到。

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 缺省的参数设置