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

2336426014

先来下个定义~

线性规划：研究在一组自变量的线性约束条件下，求线性函数的最小值或最大值，一般形式为：
# e7 I# W7 i1 b; I2 Cmin(max) f=cx, s.t. ax>=b(<=b);x>=0
% w3 L: j3 I0 n" M5 y5 u' c整数规划：线性规划的特殊形式，其决策变量只能取整数，一般形式为：
min(max) f=cx, s.t. ax<=b;x>=0
# ]2 C/ U5 U! ^8 a1 {4 L6 D; c4 m

# W6 A  s: Y) U4 Z

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

7 {" o6 Y! ]/ M7 b: K3 _8 G此外还有大M法、变量有界单纯形法（自变量有取值区间），都是基于单纯形法，在此不多讨论~
8 a6 U+ F& W4 R5 [* o5 [
' k' y* p0 I4 G, W" A4 c( kMATLAB函数应用--->linprog（线性规划）
例：
6 ?  k" C2 F; T
  n4 d! V8 ]. z8 L" \- L& E) b2 Vmatlab运行结果：

; q1 j+ G# J& y- {& G( N0 ]二、求解整数规划的方法：
) U7 m+ Q. o; n. w% b( `5 @) \1.Gomory割平面法：首先求解非整数约束的线性规划，再选择非整数基变量，定义新的约束从而缩小可行域，保留原问题的全部可行解
2.分支定界法：不断将可行域分割为小集合，然后在小集合上找整数最优解。（分割过程中不会丢失整数解）
: N9 t  U* A1 p- @" U2 M3.0-1规划法：若自变量数目少，可用穷举法；否则用隐枚举，只检查目标值（通过可行解不断改进，因此需要初始值）的取值组合的一部分
整数规划在实际中应用较多，主要包括以下方面：
* A6 i# p8 ^0 Y% {- V( s9 w1.运作问题，如货物分配、生产调度、机器排序等；
- v4 F8 {7 y8 ^: k; L( N8 i- b2.计划问题，如资金预算、设施选址、证券组合分析等；
0 N1 y- z" ~+ k$ K) w6 r+ Y- H3.设计问题，如生产线设计、网络设计等。
7 s2 e* J) O  J. Z/ ~' C三种算法的例子及代码由于比较长，所以放文档里

9 H: `, T0 R1 t! B( _, N, Y8 p

' z0 _2 q3 P( I* B! X