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

2336426014

先来下个定义~
7 g- t% x, o) r# ?; o! X
( R% s: W# s, z# E- W线性规划：研究在一组自变量的线性约束条件下，求线性函数的最小值或最大值，一般形式为：
9 ?9 H6 J' D: E& m; k+ u. Z8 Emin(max) f=cx, s.t. ax>=b(<=b);x>=0
3 |! t* D  U9 L( e. `% ^整数规划：线性规划的特殊形式，其决策变量只能取整数，一般形式为：
& M- C% A- `3 Z: S+ `  wmin(max) f=cx, s.t. ax<=b;x>=0

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

: R- ^% h  ]: Z: D( |. B2 V此外还有大M法、变量有界单纯形法（自变量有取值区间），都是基于单纯形法，在此不多讨论~
5 y) {8 a- i9 N+ X
3 C0 E" ~6 g( Z, S, [  C2 _MATLAB函数应用--->linprog（线性规划）
例：
* |6 N7 x9 O3 _1 R- m) K( T
9 ]. B. n5 ?8 B$ rmatlab运行结果：
( A  _& O/ b- y3 B
" n! Q$ E" G# Y. R* g! U二、求解整数规划的方法：
1.Gomory割平面法：首先求解非整数约束的线性规划，再选择非整数基变量，定义新的约束从而缩小可行域，保留原问题的全部可行解
3 p4 U! q1 E% I  j. D  }: c# f2.分支定界法：不断将可行域分割为小集合，然后在小集合上找整数最优解。（分割过程中不会丢失整数解）
3.0-1规划法：若自变量数目少，可用穷举法；否则用隐枚举，只检查目标值（通过可行解不断改进，因此需要初始值）的取值组合的一部分
整数规划在实际中应用较多，主要包括以下方面：
1.运作问题，如货物分配、生产调度、机器排序等；
: z. e- n/ s# \+ {0 n- E) t7 f2.计划问题，如资金预算、设施选址、证券组合分析等；
4 A. n! s( i9 Z6 Q) K0 ~. H) A; |3.设计问题，如生产线设计、网络设计等。
3 d: U* |5 ]- M! s三种算法的例子及代码由于比较长，所以放文档里
* F% a# w) e" k' Q
) i: v( E0 W8 H

# e# d. m7 {" \. G: y5 |% H+ a