一、线性规划模型基本原理与案例分享

线性规划问题

在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划 (Linear Programming 简记 LP)则是数学规划的一个重要分支。

实例与定义

例1.1 某机床厂生产甲、乙两种机床，每合销售后的利润分别为4千元与3千元。生产甲机床需用 A、B 机器加工，加工时间分别为每合2小时和1小时；
生产乙机床需用 A、B、C 三种机器加工，加工时间为每合各一小时。若每天可用于加工的机器时数分别为 A 机器10小时、B 机器8小时和 C 机器7小时，问该厂应生产甲、乙机床各几合，才能使总利润最大？

MATLAB 标准形式及软件求解

matlab 中标准形式：

其中都是列向量
matlab 中求解线性规划的命令：

1
2
3

[x,fval] = linprog(c,A,b)
[x,fval] = linporg(c,A,b,Aeq,beq)
[x,fval] = linprog(c,A,b,Aeq,beq,lb,ub)

其中 x 是返回决策向量的取值，fval 返回的是目标函数的最优值

示例：投资的收益和风险

二、整数规划基本原理与编程实践

整数规划模型（IP）

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

整数规划特点

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

求解方法

1. 图解法

直接枚举，研究约束条件内所有整数点

2. 分枝定界法

不考虑整数限制先求出相应松弛问题的最优解：
若松弛问题无可行解，则 LP 无可行解；
若求得的松弛问题最优解符合整数要求，则是 LP 的最优解；
若不满足整数条件，则任选一个不满足整数条件的变量 x 来构造新的约束添加到松弛问题中形成两个子问题，依次在缩小的可行域中求解新构造的线性规划的最优解，并重复上述过程，

3. 割平面法

如果(P0)的解含有非整数分量，则对(P0) 增加割平面条件：即对(P0)增加一个线性约束，将(P0)的可行区域割掉一块，使得非整数解恰好在割掉的一块中，但又没有割掉原问题§的可行解，得到问题(P1)，重复上述的过程。

4. 匈牙利算法（求解 0-1 规划）

0-1 规划：变量只能取 0 或者 1，出现互斥约束
互斥约束的推广：
M 取无穷大，使其小于无穷大（或大于无穷小）
特例：指派问题：
例：甲乙丙丁四个人，ABCD 四项工作，要求每人只能做一项工作，每项工作只由一人完成，问如何指派总时间最短？
标准形式：有 n 个人和 n 项工作，已知第 i 个人做第 j 项工作的代价为 (i,j=1,…,n),要求每项工作只能交与其中一人完成，每个人只能完成其中一项工作，问如何分配可使总代价最少？
数学模型：表示第 i 个人做第 j 项工作，或者表示代价/利润
非标准形式：
1. 最大化指派
2. 人数和工作数不等
3. 一个人可做多件工作
4. 工作一定不能由某人做
指派问题的匈牙利解法一般步骤
1. 变换指派问题的系数(也称效率)矩阵(cij) 为(bij)，使在 (bij) 的各行各列中都出现==（至少个数的）==0元素，先每行减最小，再每列减最小==（寻找最小元素）（此时每行每列已至少出现一个 0）==
2. 进行试指派寻找最优解
  从只有一个 0 元素的行列开始，==圈出==该 0 元素，==划去==同行同列（十字）中其他的 0，（已为该元素分配任务，不参与其他分配），直到尽可能多的0元素都被圈出和划掉为止。
3. 作最少直线覆盖所有 0 元素
4. 变换矩阵增加 0 元素，==注意不能改变已有零元素==，减去已有的最小元素，改变行加上一个数要注意要改变列减去一个数

三、非线性规划基本原理与编程实践

非线性规划模型(NP)

如果目标函数或约束条件中包含非线性函数（二次、三次等），就称这种规划问题为非线性规划问题。

MATLAB一般形式：

其中 f(x)是标量函数，A,b,Aeq,beq,lb,ub 是相应维数的矩阵和向量，c(x),ceq(x)是非线性向量函数。
MATLAB 命令：

1	[x,faval] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)

fun 是用 M 文件定义的函数，x0是 x 的初始值；（==可以用 rand 函数定义==） nonlcon 是用 M 文件定义的非线性向量函数 c(x),ceq(x)；options 定义了优化参数，可以使用 Matlab 缺省的参数设置。

二次规划

目标函数为自变量的二次函数，而约束条件全是线性
数学表述