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

2336426014

先来下个定义~

+ X$ D5 J6 z8 l) Y0 U: j线性规划：研究在一组自变量的线性约束条件下，求线性函数的最小值或最大值，一般形式为：
- ]# I* T$ T# f! L; ]4 {min(max) f=cx, s.t. ax>=b(<=b);x>=0
8 M3 E* |3 J( R8 [+ A. u整数规划：线性规划的特殊形式，其决策变量只能取整数，一般形式为：
min(max) f=cx, s.t. ax<=b;x>=0
2 f8 P/ L9 M- D  |* F2 }0 l: _+ T

5 ]1 T2 V, H; S, v

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

+ A5 p: V$ O2 s4 L此外还有大M法、变量有界单纯形法（自变量有取值区间），都是基于单纯形法，在此不多讨论~
7 u7 J4 ]! M* f2 `# D* H
: j9 k) y* h8 g7 r2 @- i6 F% pMATLAB函数应用--->linprog（线性规划）
例：

matlab运行结果：

二、求解整数规划的方法：
+ W( D2 ^7 D0 @$ _/ ?$ T  i: Z& X! ~1.Gomory割平面法：首先求解非整数约束的线性规划，再选择非整数基变量，定义新的约束从而缩小可行域，保留原问题的全部可行解
& s, ?) g) ?# j2.分支定界法：不断将可行域分割为小集合，然后在小集合上找整数最优解。（分割过程中不会丢失整数解）
3.0-1规划法：若自变量数目少，可用穷举法；否则用隐枚举，只检查目标值（通过可行解不断改进，因此需要初始值）的取值组合的一部分
# T* ^( h' h* k6 D( j. O- P1 _整数规划在实际中应用较多，主要包括以下方面：
: g! X+ e, G2 N- t5 e. F1.运作问题，如货物分配、生产调度、机器排序等；
  P1 v& b/ y- a3 a1 R  E' }: D2.计划问题，如资金预算、设施选址、证券组合分析等；
6 [* |4 B3 S$ g3.设计问题，如生产线设计、网络设计等。
三种算法的例子及代码由于比较长，所以放文档里

: C6 x) ]; g* }) ?2 F& V

2 M" x- _% X1 K0 C( ~
# W/ F) e4 z2 i1 m- n