管理运筹学 第五章 整数规划

第一节 整数规划的数学模型
解的特点： 整数规划
松弛问题
max c x Ax b s .t . x 0, x为整数

max c x Ax b s .t . x 0

1、整数规划可行域是松弛问题可行域的子集
2、整数规划最优值小于等于松弛问题的最优值
第一节 整数规划的数学模型
P1 P2
P4
以上描述了目前解整数规划问题的一种思路。
第二节 分支定界法
思路：切割可行域，去掉非整数点。 解题步骤： 1、不考虑整数约束，解相应松弛问题。 2、检查是否符合整数要求，是，则得最优解，完毕。 否则，转下步。 3、任取一个非整数变量xi=bi，构造两个新的约束条 件：xi ≤[bi]，xi≥[bi]+1,分别加入到上一个LP问 题，形成两个新的分枝问题。 4、不考虑整数要求，解分枝问题。若整数解的Z值 大于所有分枝末梢的Z值，则得最优解。否则， 取Z值最大的非整数解，继续分解，Go to 3。
序号 1 2 3 4 5 6 7
物品
重量 系数
食品
5 20
氧气
5 15
冰镐
2 18
绳索
6 14
帐篷
12 8
相机
2 4
设备
4 10
第三节
0-1型整数规划
解：令xi=1表示登山队员携带物品i，xi=0表示登 山队员不携带物品i，则得： Max Z=20x1+15x2+18x3+14x4+8x5+4x6+10x7
第三节
(x1,x2,x3) z值
0-1型整数规划
1 2 3 4 过滤条件
(0,0,0)

分解 ai0 , j和 bi0 成最大整数与正分数之和：
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:21
xi0 ai0 , j x j bi0 xi0 ( Ni0 , j f i0 , j )x j Ni0 f i0 xi0 Ni0 , j x j Ni0 f i0 f i0 , j x j
S1
x2 2
B: x1=2,x2=23/9 Z=41/9
x2 3
D: S12 x1=33/14,x2=2 Z=61/14
S11
无可行解
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:15
对S12分枝：
构造约束：
x1 3
X
2 5
4
和
x1 2
3
3 10 A( , ) 2 3
形成分枝问题S121 和S122，得解E和F
形成松弛问题2
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:24
CB XB 3 x1 -1 0 0 x2 x4 x6
3 -1 0 0 x1 x2 x3 x4 1 0 1/7 0 0 0 0 0 1 -2/7 0
0 x5 2/7 3/7
0 x6 0 0 0 1 0
b 13/7 9/7 31/7 -6/7
首先不考虑变量的整数约束，求解相应的线性规划问题：
z0
Max z = CX AX = b X0
D
C
下界
O Ir
Max z = CX AX = b xr Ir X0 Max z = CX AX = b xr Ir+1 X0

X2 ≤ 1
B21 X1＝5.44，X2＝1.00 Z＝308
340 ≤ z ≤ 341
X2 ≥2
B22 无可行解
第三节 割平面法
割平面法的基本思想 这里仅介绍求解纯整数规划的割平面法 基本步骤：
设整数规划问题（IP），对应的松弛问题为（P） ①用单纯形法求解问题（P），设得到（P）的最优解。 ②若（P）的最优解符合取整约束，则停止；否则，必有一个基 变量Xi取值为分数。 ③任取一个基变量取值为分数的约束，构造切割平面（新约束）。 ④将新约束加入到原约束中，求解新的松弛问题（P）。用灵敏 度分析的方法求解问题（P），转② 。
？
Ma x化
？
？
第五节 指派问题
问题的扩展
人员数＝任务数
Min
化
基本问题
人员数≠任务数
人员数>任务数：虚设任务 人员数<任务数：虚设人员 系数矩阵中对应元素为0。 使人员数＝任务数 。
Ma 找出系数矩阵中的最大元
x化
素，记做W，用W减去系 数矩阵中的每个元素，得
到新矩阵。转化为Min化问
题。
第五节 指派问题
第三节 割平面法
例：求解 Max z＝x1＋x2 －x1+x2≤1 3x1+x2≤4 x1、x2≥0，且取整
注意：要求每个bi，以及aij必须取整。否则，可以对相应的约束乘上 一个数，使其变为整数。 Max z＝x1＋x2 －x1+x2 ＋x3 ＝1 3x1+x2 ＋ x4 ＝ 4 x1，x2，···， x4≥0，且取整
第四节 0-1规划及隐枚举法
求解纯0－1规划问题的隐枚举法 基本思想： 穷举法的不足； 隐枚举法： “最优解＝目标值最优的可行解” 只要目标值不是最优，不用检查是 否为可行解，必定不是最优解。 一个例子

§3整数规划的应用(5)
五、投资问题 例8．某公司在今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额 为4万元，第二、三、四年不限； 项目B：第三年初需要投资，到第五年未能回收本利128％，但规定最低投资金额为3万元，最高金额为5 万元； 项目 C：第二年初需要投资，到第五年未能回收本利140%，但规定其投资额或为2万元或为4万元或为6 万元或为8万元。 项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额 为最大? 解：1) 设xiA、xiB、xiC、xiD ( i ＝1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额； 设yiA， yiB，是0—1变量，并规定取 1 时分别表示第 i 年给A、B投资，否则取 0（ i = 1, 2, 3, 4, 5）。 设yiC 是非负整数变量，并规定：2年投资C项目8万元时，取值为4； 2年投资C项目6万元时，取值为3； 2年投资C项目4万元时，取值为2； 2年投资C项目2万元时，取值为1； 2年不投资C项目时， 取值为0； 这样我们建立如下的决策变量： 第1年 第2年 第3年 第4年 第5年
解：设：0--1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我们可建立如下的数学模型： Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720 x1 + x2 + x3 ≤ 2 x4 + x5 ≥ 1 x6 + x7 ≥ 1 x8 + x9 + x10 ≥ 2 xj ≥ 0 xj 为0--1变量，i = 1,2,3,……,10