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

2336426014

先来下个定义~

线性规划：研究在一组自变量的线性约束条件下，求线性函数的最小值或最大值，一般形式为：
5 q' E8 ^$ _7 ]min(max) f=cx, s.t. ax>=b(<=b);x>=0
6 s( o# F$ I$ D. a; |! W整数规划：线性规划的特殊形式，其决策变量只能取整数，一般形式为：
. S) U7 U1 ]/ y3 U% \/ q- ~+ b: U$ pmin(max) f=cx, s.t. ax<=b;x>=0
8 N4 O5 e) V# {( L0 G# Z! L

. r0 c6 H; s8 z# K  \; v, ?

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

此外还有大M法、变量有界单纯形法（自变量有取值区间），都是基于单纯形法，在此不多讨论~
4 [9 [' _( ^. M  n- ?5 }4 ]
3 K4 ~# z0 k; QMATLAB函数应用--->linprog（线性规划）
, d. B* f# M5 y0 A! P# T8 o例：
! D; Q* G6 @) o3 j$ `
matlab运行结果：
8 w- E8 a6 Q9 T+ `  i- `3 R$ d
二、求解整数规划的方法：
1.Gomory割平面法：首先求解非整数约束的线性规划，再选择非整数基变量，定义新的约束从而缩小可行域，保留原问题的全部可行解
( O) s& `: z2 v- g2.分支定界法：不断将可行域分割为小集合，然后在小集合上找整数最优解。（分割过程中不会丢失整数解）
/ E& E2 j8 V; ^( G+ h3.0-1规划法：若自变量数目少，可用穷举法；否则用隐枚举，只检查目标值（通过可行解不断改进，因此需要初始值）的取值组合的一部分
整数规划在实际中应用较多，主要包括以下方面：
8 r+ |. R( b' M2 E2 H; d) d1 V1.运作问题，如货物分配、生产调度、机器排序等；
2.计划问题，如资金预算、设施选址、证券组合分析等；
3.设计问题，如生产线设计、网络设计等。
4 I9 f' x' i- h- z3 R3 Y三种算法的例子及代码由于比较长，所以放文档里

3 m8 g- a! l: a

4 F0 w3 |3 X% D7 ~