基础教研室
第四章 整数规划(Integer Programming) 与分配问题
§1 整数规划的特点及其作用
• 特点 • 求解方法 • 建模 利用0-1变量建立整数规划数学模型
基础教研室
一、特点
• 变量要求取整数
纯整数规划：全部变量要求取整数
混合整数规划：某一部分变量要求取整数
整数规划目前还仅限于整数线性规划
1 －选择自备柴油机发电 设 y 2 0 －不选择自备柴油机发电
采用电网供电 采用自备柴油机发电
M-----非常大的正数
基础教研室
ห้องสมุดไป่ตู้
3. 表示条件性约束
【例4】：若在开采时还需满足下述条件：（a） 若开采8号，则必须同时开采6号； 若开采5号，则不许开采3号； （b） （c） 2
号和4号至少开采一个；
min f ( x j ) k j y j c j x j x j y j M st. x j 0, y j 0或1
M—非常大的正常数
f (x j ) k j y j c j x j x j y j M y j xjM x 0, y 0或1 j j
1 －－选择开采第j个构造 设 xj 0 －－不选择开采第j个构造
max Z c j x j
10
10
－－年总收益
－－-投资额限制 a j x j b j 1 x 0或1( j 1,2, 10) j
j 1
基础教研室
2. 表示选择性约束
【 例3】：上述例题中，如果在开采中需用电力，解决的方 案或由电网供电或由自备的柴油机发电。已知第j个构造开 采时每天耗电量为 dj 度，电网每天供电量限制为f 度。当使 用自备柴油机发电时，每度电平均耗油0.3公斤，而柴油供 应量限额为每天 p 公斤。试在模型中表示出该限制条件。
基础教研室
【例1】求下述整数规划的最优解
Max z= 3x1 + 2x2 st . 2x1 + 3x2 14 x1 + 0.5x2 4.5 x10，x20，且为整数
基础教研室
x2 x1+0.5x2=4.5
4
(3.25, 2.5) 2 2x1+3x2=14
2
4
6
x1
3x1+2x2=6
二、整数规划的求解方法
基础教研室
【例3】投资决策问题 某公司准备1000万元资金在10个地点中选择若干个建立 工厂（工厂名称用地点名来命名），有关数据如下：
由于各个工厂之间有配套和协作关系，因此必须满足条件： 1、 建工厂1就必须同时建工厂2； 2、 若建工厂2就不允许建工厂3； 3、 工厂4和工厂5至少建一个； 4、 工厂6，7，8恰好建2个； 5、 工厂8，9，10最多建2个； 6、 建工厂4或者建工厂6，就不能建工厂8，反过来也一样； 7、 条件2，3，5最多满足2个。 问选择哪几个地点建厂最有利？ Next
（c） x2 + x4 1
（d） x8 = x7 （e） x1 + x4 + x6 + x9 2
Back
基础教研室
4. 两组条件满足其中一组
若x1 4，则x21；否则x14，则x2 3。 设 yi=
1 第 i 组条件起作用

0
第 i 组条件不起作用
i=1,2
则
x1 4 (1 y1 ) M x2 1 (1 y1 ) M x1 4 (1 y2 )M x2 3 (1 y2 )M y1 y2 1 y1 , y2 0或1
基础教研室
• 凑整法的局限性： 1 变量取值小时，误差大 2 变量数量大时，计算工作量大 3 有时不一定能得到整数规划问题的最优解 • 整数规划的求解方法 1 图解法 2 分枝定（限）界法 3 割平面法 4 匈牙利法 5 隐枚举法
基础教研室
三、 建模---- 利用0-1变量 建立整数规划数学模型
• 0-1规划问题的概念
• 在整数规划问题中，若变量取值为0或者1， 则为0-1规划问题。 • 0-1变量通常用来表示逻辑性选择的决策。
基础教研室
0-1变量的应用 1、表示选择性决策
【例2】：某油田在10个有油气构造处要选择若干个钻探 采油，设第j个构造开采时需投资aj元，投产后预计年收 益为cj元，若该油田投资的总限额为b元，问：应选择哪 几个构造开采最为有利？
解: 设 xj=
10
0 在第j个地点不投资建厂
基础教研室
1 在第j个地点投资建厂
j 1
j=1,2,3, …, 10
x1 0 1 0 1 x2 0 0 1 1
Maxz c j x j
a1x1+ a2x2+…+ a10x10 ≤1000 x1 ≤ x2 x2 + x3 ≤1 +y1M M是任意大的正数 x4 + x5 ≥1 - y2M
M-----非常大的正数
基础教研室
5. 分段函数线性表示
K j c j x j，x j 0时 将 min f ( x j )表示成 设有 f ( x j ) x j 0时 0 线性函数。 当x j 0 1 令y j 当x j 0 0 则 或为：
号与7号必须同时开采；
（d） 8
（e）1号、
4号、6号、9号开采时不能超过两个，试表示上
述约束条件。
Next
基础教研室
（a）当x8=1 当x8=0 ∴ x8 x6
x6=1，x6≠0 x6=1，x6=0
（b）当x5 =1 当x5 =0 ∴ x5 + x3 1
x3=0， x3 ≠1 x3=0， x3 =1
x6 + x7 + x8=2 x8 + x9 + x10 ≤ 2 +y3M
x2
0 1 0
x3
0 0 1
x4 + x8 ≤ 1
x6 + x8 ≤ 1 y1+y2 +y3 ≥3-2
1
1
xj取0或1, yi取0或1,
j=1,2,3, …, 10, i=1,2,3
1 －选择电网供应 设 y1 0 －不选择电网供应
10 d j x j f (1 y1 ) M j 1 10 0.3d j x j p (1 y2 ) M j 1 y1 y2 1 y1 , y2 0或1