[理学]运筹学教案整数规划与指派问题

6
x2
6
X1<=3
X1>=3+1
5

4


3



(3.25, 2.5)

2



1





o

1
2
3

4

5
67Fra bibliotekx1加上附加约束将问题分为两枝，即两个线性规划问 题，而且保证不丢失正数解。 7
B1：B
xj<=[bj] 分别求解问题B1与B2
B2：B
xj>=[bj]+1
4、定界：以当前目标值最大而又未分枝的子问题 的目标值为上界，当前最好的整数解目标值（若 还没有则选择为负无穷大）为下界。 5、逐步分枝，并求各分技问题，修改上下界，上 界将逐步减小，下畀将逐步增加，直到二者相等， 则得到原整数规划问题的解。 注意：分枝的优先顺序和剪技（不再继续分技） 的条件。以书上例子加以说明。
运筹学教案
整数规划
陈安明
1
4.1 整数规划问题及特点
4.1.1 整数规划的概念
1、整数规划的定义： 决策变量要求取整数的线性规划。 2、整数规划的分类： 纯整数规划：全部决策变量均要求取整数。 混合整数规划：只要部分决策变量要求取整数。 0,1规划：一类变量只取0,1特殊的整数规划问题。 3、整数规划的性质： （1）可行解域为点集。 （2）整数最优解的目标值劣于同问题非整数最优解 的目标值。
max z 3 x1 2 x2 2 x1 3 x2 14 4 x 2 x 18 1 2 x1 , x2 0 x1 , x2为整数 (1) ( 2) (3) ( 4)
x2
6 5 4 3 2 1
例：左边为一整数规划 问题 最优解（3.25,2.5)，四舍 五入化整为(3,3)已不是 可行解，去小数化束得 (3,2)虽可行但不是最
11
4.3 割平面解法
4.3.1 原理： 解伴随规划问题，若得到非整数最优解， 则增加被称为割平面的一个线性约束，再求 解。 增加的割平面能割掉一部分非可行域，但 不会去掉整数可行解。 不断增加割平面，使缩少后的可行域的出 现整数解的极点，并且为问题的最优解。 但割平面可能要经过多次构造才能出现此 种情况。
例:P48 最优解表中第一个约束条件:
约束为:x2+9/4x3-1/4x4=9/4可改写为： X2+(2+1/4)x3+(-1+3/4)x4=2+1/4
14
X2+(2+1/4)x3+(-1+3/4)x4=2+1/4 移项得： 1/4 –(1/4x3+3/4x4)=x2+2x3-x4 因xj>=0 且取整数，故有： 1/4 -（1/4x3+3/4x4)<=0 即1/4x3+3/4x4>1/4 即对任意整数变量，都满足上述不等式，亦 即原问题加上上述约束条件，不会割去原问 题的可行整数解，但会割掉包括其伴随规划 问题最优解（非整数）在内的部分非整数可 行解，故可作为此问题的一个割平面方程。 一般地前述约束的割平面方程有如下形式：
12
割平面法的关键： 在于如何根据线性规划问题最优单纯表 构造割平面（即新增的约束条件） 满足：能割掉一部分查行解，又不丢掉 任何整数可行解。 4.3.2 割平面方程的构造方法 下面是最优解表中某基变量所在行相应约 束方程
基变量 最优解表中非 基变量系数
13
将各系数分解为不超过此数是最大整数与 小数部分之和,即令:
9
P
分枝定界法注意：
1、分枝变量选择原则： （1）按目标函数系数：选系数绝对值最大者 变 量先分。 对目标值升降影响最大。 （2）选与整数值相差最大的非整数变量先分枝。 （3）或以经验选择。对整数要求的变量排优先 次序。
10
2、分枝节点选择： （1） 深探法(后进先出法)： 最后打开的节点最先选，尽快找到整数解。 但整数解质量可能不高。 （2） 广探法： 选目标函数当前最大值节点，可能找到较好 的整数解。
8
某一问题的 分枝定界解 法
原问 题 Max z =40x1+90x2 St 9x1+7x2<56
7x1+20x2<70
X1,x2>0且为整数
说及下 。明 直 面 。接结 第一枝 B1 Max z =40x1+90x2 用 合 St 9x1+7x2<56 软 7x1+20x2<70 件 x1<4 求 X1,x2>0 解软 第二枝 B2 。件 Max z =40x1+90x2 以说 St 9x1+7x2<56 书明 7x1+20x2<70 x1>=5 求 43 X1,x2>0 例解 子过 程 加 用LINDO软件求 。 以 解说明该过程 LINDO
基本原理：
1、首先求解整数问题的伴随问题（原问题A去掉整 数约束条件后得到的问题B）。
2、若为整数解，则为原问题的最优解。否则：
3、分枝：选择 xj=bj 不为整数，而原问题要求xj为 整数，则原问题最优解不可能在区域内： [bj]<xj<[bj]+1 故将前伴随问题分别加上约束条件 xj>=[bj]+1 Xj<=[bj] 从一分二技形成两个问题B1与B2
2
4.1.2 整数规划问题的求解方法
1、化整方法
包括：四舍五入、去掉小数部分化为整数。
化整后可能已不再是可行解，或即使可行但不是最优 解。此方法看似简单但行不通，后边以例子说明。 2、穷举法： 给出所有整数组合解，比较目标值大小，从而得最优 解，对于0，1规划问题也易想到此方法。但当变量数 目较大，如20个，计算量太大，计算机计算都要以年 万年时间计，故往往是无效的。在指派问题时说明。
3
3、有效的方法： 一类：先去掉整数约束条件，求解对应的线性
规划问题（伴随问题），增加附加约束条件，保证 不去掉整数可行解，再求解，直到得到整数最优解。 此类算法有：分枝定界法、割平面法等。
另一类：隐枚举法。
即设计的一些方法，只检查变量取值组合的一 部分，就能求到问题的最优解，此类方法类也较多。
4
优解，因为（4，1）的 函数值为14 比其13的函 数值还大。 用穷举法则要给出图中 所有红点（可行解）的 目标值，再比较大小， 对于变量较多时，效率 低。
1 2

3
h (3.25, 2.5)
4 5 6 7
o

x1
①
②
5
4.2 分枝定界法