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

2336426014

先来下个定义~

" N$ w4 B  \. L线性规划：研究在一组自变量的线性约束条件下，求线性函数的最小值或最大值，一般形式为：
; `3 W! V" m4 r9 z  `  imin(max) f=cx, s.t. ax>=b(<=b);x>=0
整数规划：线性规划的特殊形式，其决策变量只能取整数，一般形式为：
0 N9 W$ w2 t8 Z5 n2 ^min(max) f=cx, s.t. ax<=b;x>=0
, `* i( }; J3 h3 b* f2 v0 L' M/ f

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

此外还有大M法、变量有界单纯形法（自变量有取值区间），都是基于单纯形法，在此不多讨论~

: ?& a) O2 g0 u" ]MATLAB函数应用--->linprog（线性规划）
例：

( p7 J# ?* j0 a7 w6 k( q5 Bmatlab运行结果：
5 }8 u9 k2 D0 r: d
( |6 h3 v) B! t2 W* Q, w二、求解整数规划的方法：
" I- p( H( D6 X* `  ~- i1.Gomory割平面法：首先求解非整数约束的线性规划，再选择非整数基变量，定义新的约束从而缩小可行域，保留原问题的全部可行解
# ?, v) R# k8 x2 j. s5 j2.分支定界法：不断将可行域分割为小集合，然后在小集合上找整数最优解。（分割过程中不会丢失整数解）
6 a: e/ S+ \4 |2 s3.0-1规划法：若自变量数目少，可用穷举法；否则用隐枚举，只检查目标值（通过可行解不断改进，因此需要初始值）的取值组合的一部分
整数规划在实际中应用较多，主要包括以下方面：
0 Q1 g& |' k# m! A1.运作问题，如货物分配、生产调度、机器排序等；
- \( }5 k* p/ q4 ~: }2.计划问题，如资金预算、设施选址、证券组合分析等；
3.设计问题，如生产线设计、网络设计等。
& F4 J$ I' f2 h6 \3 o) t三种算法的例子及代码由于比较长，所以放文档里
$ x6 t. e. B2 J) R: x
. n- P2 y/ ~- Y; Z6 G

8 ?! T9 K  a$ C+ f6 X9 |9 A