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

2336426014

先来下个定义~

! b  N) k. Z6 {* }线性规划：研究在一组自变量的线性约束条件下，求线性函数的最小值或最大值，一般形式为：
min(max) f=cx, s.t. ax>=b(<=b);x>=0
整数规划：线性规划的特殊形式，其决策变量只能取整数，一般形式为：
0 S8 Y  g7 y* F4 u, Q: _4 A0 C* d! q/ mmin(max) f=cx, s.t. ax<=b;x>=0

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

# V  U6 Z1 u3 s0 }" m9 ~! t9 s此外还有大M法、变量有界单纯形法（自变量有取值区间），都是基于单纯形法，在此不多讨论~
# n7 t8 r7 t; F% k. R4 a# ~4 \
MATLAB函数应用--->linprog（线性规划）
1 T4 r& s* l$ @5 X' E+ _6 J例：
3 s7 F4 G! ~* K
+ E4 g) q5 s3 ~. b; S% q2 amatlab运行结果：
' ]1 D7 s2 t0 z. t" h
二、求解整数规划的方法：
1.Gomory割平面法：首先求解非整数约束的线性规划，再选择非整数基变量，定义新的约束从而缩小可行域，保留原问题的全部可行解
2.分支定界法：不断将可行域分割为小集合，然后在小集合上找整数最优解。（分割过程中不会丢失整数解）
2 ^$ g$ }% k1 j3.0-1规划法：若自变量数目少，可用穷举法；否则用隐枚举，只检查目标值（通过可行解不断改进，因此需要初始值）的取值组合的一部分
- V. B: x' p' f" w7 [! O$ P整数规划在实际中应用较多，主要包括以下方面：
1.运作问题，如货物分配、生产调度、机器排序等；
8 l: v8 S: f9 U7 f  g' C7 G2.计划问题，如资金预算、设施选址、证券组合分析等；
0 k: ~8 f3 J6 {: E: ]  S9 B7 E3.设计问题，如生产线设计、网络设计等。
1 ^2 M- R& _9 N1 M( M三种算法的例子及代码由于比较长，所以放文档里

# j: P; |$ E3 R& L, b7 f0 M