整数规划
1 _( q8 [% j( h' H# r9 R: b( o定义：
8 G: I9 M. |$ K y) U9 c规划中的变量（全部或部分）限制为整数，称为整数规划。若在线性模型中，变量限制为整数，则称为整数线性规划。 9 J8 n6 p: h. X3 f1 v; o- G+ J
一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线性的整数规划。
数学规划问题中有很多决策变量都只能取整数，如人员数量、机器设备台数、服装件数、汽车辆数等．如果规划问题中的决策变量xi(i=1,2,…,n),要求取整数值，则称这个模型为整数规划模型数学表现形式
* I/ { z* j" _8 G8 K3 Q
主要解法分为这几种:
（i）分枝定界法—可求纯或混合整数线性规划。
d% \( k' C, T# E) A7 K（ii）割平面法—可求纯或混合整数线性规划。 2 u8 @' e: S/ l& w" A1 b! K# m
（iii）隐枚举法—求解“0-1”整数规划： & A: D* N- h8 d- E9 B& s9 M
①过滤隐枚举法； ! |- j! a0 r5 m0 v
②分枝隐枚举法。 6 `5 x" @1 m& |
（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。
0 _0 e6 L! v1 A% D6 M E8 |- k（v）蒙特卡洛法—求解各种类型规划。
示例： . |5 ^/ g" z( k/ N! c1 j3 ^* q
乐家百货商场准备派小李、小张、小王三位销售人员去销售库存的120件大衣．由于他们以前的销售业绩不同，每销售一件产品小李、小张、小王的报酬分别为6元、4元、3元．商场为保证销售速度，规定小李至少要承担30件销售任务，小张至少要承担20件销售任务，而小王承担的销售任务不能超过50件．问应该如何安排销售计划使总销售成本最低．
一、模型假设与变量说明 3 J0 F1 _! b/ p
1．假设三位销售人员能销售完120件大衣． " y. O4 d+ ^( l q: z% v. u1 a
2．小李、小张、小王承担的销售任务分别为 x1,x2,x3．
二、模型的分析与建立
" i5 @2 Q# R% _8 z该问题是在对三位销售人员销售数量进行一定限制的情况下，合理安排各销售人员的销售数量，使得公司支付给三位销售人员的总报酬最少．
1 }( \) E( g+ D; n
目标：三位销售人员的总报酬最低．而总报酬为
) H& Y: [& M" G) }9 w
! n) d( ^8 L) E/ W约束条件：
+ r. S3 } E# F& H% o% C
1．受总销售数量的限制：
8 f4 k1 o. {0 Q y$ \
2．受销售员销售数量的限制（如小李）： X(1) ≥ 30
! v) ^# q" a$ f
/ G( \4 j& k2 B* P5 T1 q: [
由此可知，小李，小张，小王分别承担30，40，50件销售任务时，公司支付的总报酬最少．