整数规划 . h* w9 e9 I. m8 x
定义：
+ b& }- V1 x+ c B9 B) a/ P规划中的变量（全部或部分）限制为整数，称为整数规划。若在线性模型中，变量限制为整数，则称为整数线性规划。 ) R4 s" K J7 a! C. k( J5 V5 s% X
一类要求问题的解中的全部或一部分变量为整数的数学规划。从约束条件的构成又可细分为线性，二次和非线性的整数规划。
数学规划问题中有很多决策变量都只能取整数，如人员数量、机器设备台数、服装件数、汽车辆数等．如果规划问题中的决策变量xi(i=1,2,…,n),要求取整数值，则称这个模型为整数规划模型数学表现形式
% O2 {5 O; ^5 n& q
主要解法分为这几种:
（i）分枝定界法—可求纯或混合整数线性规划。 7 }+ B( k+ O" F4 t9 b9 ]
（ii）割平面法—可求纯或混合整数线性规划。 ! `4 Y4 ]& q3 n l! P
（iii）隐枚举法—求解“0-1”整数规划： ; m2 ~( e; W0 j
①过滤隐枚举法；
5 o* L8 ^: d d②分枝隐枚举法。
& {. o$ ?: o$ u1 y( G: K9 |! @（iv）匈牙利法—解决指派问题（“0-1”规划特殊情形）。
; d7 p& s. V- ~0 P! ^（v）蒙特卡洛法—求解各种类型规划。
示例： 9 u9 ?2 r$ o* e& j3 D2 ]; Z- ]
乐家百货商场准备派小李、小张、小王三位销售人员去销售库存的120件大衣．由于他们以前的销售业绩不同，每销售一件产品小李、小张、小王的报酬分别为6元、4元、3元．商场为保证销售速度，规定小李至少要承担30件销售任务，小张至少要承担20件销售任务，而小王承担的销售任务不能超过50件．问应该如何安排销售计划使总销售成本最低．
一、模型假设与变量说明
+ }9 M* j& n$ D3 ~' w, u4 V1．假设三位销售人员能销售完120件大衣． * e; u' e% [, a# H& Y
2．小李、小张、小王承担的销售任务分别为 x1,x2,x3．
二、模型的分析与建立
5 e' D8 O* L: f0 \* s该问题是在对三位销售人员销售数量进行一定限制的情况下，合理安排各销售人员的销售数量，使得公司支付给三位销售人员的总报酬最少．
/ b4 P8 @+ S, N) j# p
目标：三位销售人员的总报酬最低．而总报酬为
" G8 g4 K' z# U7 ~0 C& b
- R% V* O0 D- |' v6 A, `
约束条件：
1 W/ }9 h5 k: r3 ?
1．受总销售数量的限制：
8 H6 Y4 ?. A, d% k+ ^8 J
2．受销售员销售数量的限制（如小李）： X(1) ≥ 30
( w- M" E" h8 z, y0 a/ |2 S1 a
, W' c: E4 y. y; o$ g% K; k6 d7 n1 c4 e
由此可知，小李，小张，小王分别承担30，40，50件销售任务时，公司支付的总报酬最少．