建模算法基础（1）线性规划

2336426014

先来下个定义~
1 r, @0 R) W0 w: d
线性规划：研究在一组自变量的线性约束条件下，求线性函数的最小值或最大值，一般形式为：
. u: v2 C& b: A" @! G' omin(max) f=cx, s.t. ax>=b(<=b);x>=0
整数规划：线性规划的特殊形式，其决策变量只能取整数，一般形式为：
0 G& t) H, y) L4 K/ w; O" Dmin(max) f=cx, s.t. ax<=b;x>=0
8 j2 ?, }& O- m- W

基于函数simplemthd()求解得到：

3 @3 Z& o% m: K此外还有大M法、变量有界单纯形法（自变量有取值区间），都是基于单纯形法，在此不多讨论~

/ u- P3 u  i; E; u) _; VMATLAB函数应用--->linprog（线性规划）
例：

matlab运行结果：

9 P% z3 r) r& W& ^, V2 t* k: U二、求解整数规划的方法：
" l' v' V, {2 \* K0 W1.Gomory割平面法：首先求解非整数约束的线性规划，再选择非整数基变量，定义新的约束从而缩小可行域，保留原问题的全部可行解
2.分支定界法：不断将可行域分割为小集合，然后在小集合上找整数最优解。（分割过程中不会丢失整数解）
) o3 ~5 _8 Q, D( R3.0-1规划法：若自变量数目少，可用穷举法；否则用隐枚举，只检查目标值（通过可行解不断改进，因此需要初始值）的取值组合的一部分
6 N3 m+ [' s8 q整数规划在实际中应用较多，主要包括以下方面：
" Q/ z/ E1 C. i9 R# e2 L- I/ b1.运作问题，如货物分配、生产调度、机器排序等；
  w6 S" M3 Y  h) f; m& a& k2.计划问题，如资金预算、设施选址、证券组合分析等；
3.设计问题，如生产线设计、网络设计等。
. w4 {" C$ D/ J. o三种算法的例子及代码由于比较长，所以放文档里
  D  Y5 H  X: m8 h! k, a3 i4 h

9 M" \4 d, q3 @3 I" R2 l0 w+ Y0 }' M