Prof. Wang School of Economics & Management
Operations Research
第十四、十五讲
§1 概述（4）
2 ．整数规划最优解不能按照实数最优解简单取整而获 得。 [例2-3] 物品装载问题：有若干类物品需一次性装运，每 件物品的价值及重量分别，为vj和wj (j=1, …,n)，车辆最 大载重量为 ，试求，每件物品应装多少件才能使总价 值最大。 [解] 令xj表示第j类物品的装载件数，则可列写整数规划 如下： w x w x
page 7 18 November 2018
Prof. Wang School of Economics & Management
Operations Research
第十四、十五讲
§1 概述（7）
四、求解方法分类： 1． 割平面法——主要求解纯整数线性规划 2． 分枝定界法——可求纯或混合整数线性规划
①原线性规划最优解全是整数，则整数规划最优解与线性 规划最优解一致。 ②整数规划无可行解。
page 3 18 November 2018
Prof. Wangnagement
Operations Research
第十四、十五讲
§1 概述（3）
[例2-1] 原线性规划为： 2x1+4x2=5，X≥0，CTX=x1+x2=min 其最优实数解为：x1=0，x2=5/4，min CTX =5/4。
Operations Research
第十四、十五讲
第七讲 整数规划 （一）
§1 概述 §2 割平面法 §3 分枝定界法
page 1 18 November 2018
Prof. Wang School of Economics & Management
Operations Research
第十四、十五讲
目标函数 min z =x1+4x2 x1+2x2≥6 x1，x2≥0且为整数
page 10 18 November 2018
约束条件 2x1+x2≤8
Prof. Wang School of Economics & Management
3． 隐枚举法——求解“01”整数规划：
① 过滤隐枚举法； ② 分枝隐枚举法 4 ． 匈牙利法 —— 解决指派问题（“ 01” 规划特殊情 形）。 5．蒙特卡洛法——求解各种类型规划。
page 8 18 November 2018
Prof. Wang School of Economics & Management
Prof. Wang School of Economics & Management
Operations Research
第十四、十五讲
§3 分枝定界法 （1）
分枝定界法目前已成功地应用于求解整数规划问题、生 产进度表问题、旅行推销员问题、工厂选址问题、背包 问题及分配问题等。因此，分枝定界算法是求解整数规 划的最有用的算法之一。现结合例题说是该算法的思路。 [例2-5]求解下述整数规划
v1 x1 vn xn max
xj≥0且取整
1 1
n n
(2)
page 5 18 November 2018
Prof. Wang School of Economics & Management
Operations Research
第十四、十五讲
§1 概述（5）
若不限制为整数，其最优解的基础分量xm为：
xm / wm，其中，vm / wm max v j / w j
当j≠m，则xj=0
当限制为整数时，就需仔细计算（其方法将在后面阐 述）。
例如，将例[2-3]具体化为：
51x1+50x2+50x3≤100
150x1+100x2+99x3=max
page 6 18 November 2018
page 2 18 November 2018
Prof. Wang School of Economics & Management
Operations Research
第十四、十五讲
§1 概述（2）
三、整数规划特点 整数规划标准形式（实际为整数线性规划） AX=b，X≥0，CTX=min，xj为整数（j=1，…，n） (1) 1．原线性规划有最优解，当自变量限制为整数后， 其整数 规划解出现下述情况；
Operations Research
第十四、十五讲
§2 割平面法
该法适于求解纯整数规划问题。其基本思路是首先去掉 整数约束去求解普通线性规划问题，若获得的最优解全 为整数，结束；否则，以此最优非整数变量为基准，在 原约束条件下，增加割约束，再继续求解，这样反复下 去，直到结束为止。
page 9 18 November 2018
§1 概述（1）
一、定义 规划中的变量（部分或全部）限制为整数时，称为整数规 划。若在线性规划模型中，变量限制为整数，则称为整数 线性规划。 二、整数规划分类 如不加特殊说明，一般指整数线性规划。对于整数线性规 划模型大致可分为两类： Ÿ变量全限制为整数的，称纯（完全）整数规划。 Ÿ变量部分限制为整数的，称混合整数规划。
x j≥ 0
Prof. Wang School of Economics & Management
Operations Research
第十四、十五讲
§1 概述（6）
若不限制整数，得出m=1，比率为150/51→max，故最优 实数解为：x1=100/51，x2=x3=0，总价值15000/51=294.12。 然而，物品不能切开，故限制为整数时，其最优解为： x1=0，x2=2，x3=0；总价值为200。 从该例得出结论，整数规划最优解不能简单的从最优 实实数解中4舍5入取整所得。因此，对于整数规划的求 解必须开拓新技术。
③有可行解（当然就存在最优解），但最优解值变差。 [例2-2] 原线性规划为： 2x1+4x2=6，X≥0，CTX=x1+x2=min 其最优实数解为：x1=0，x2=3/2，min CTX =3/2。 若限制整数则得：x1=1，x2=1，min CTX =2。
page 4 18 November 2018