第七讲 整数规划 （一）.ppt

Operations Research Operations Research Prof. Wang Prof. Wang School of Economics & Management School of Economics & Management page page 1 1 21 December 2016 21 December 2016 第十四、十五讲第七讲整数规划整数规划(一) (一) §1 概述§2 割平面法§3 分枝定界法 Operations Research Operations Research Prof. Wang Prof. Wang School of Economics & Management School of Economics & Management page page 2 2 21 December 2016 21 December 2016 第十四、十五讲§ § 1 1 概述概述( (1 1) ) 一、定义规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。二、整数规划分类如不加特殊说明,一般指整数线性规划。对于整数线性规划模型大致可分为两类: ???变量全限制为整数的,称纯(完全)整数规划。???变量部分限制为整数的,称混合整数规划。 Operations Research Operations Research Prof. Wang Prof. Wang School of Economics & Management School of Economics & Management page page 3 3 21 December 2016 21 December 2016 第十四、十五讲§ § 1 1 概述概述( (2 2) ) 三、整数规划特点整数规划标准形式(实际为整数线性规划) AX =b,X≥0,C TX =min ,x j为整数( j =1 ,…,n) (1) 1 . 原线性规划有最优解,当自变量限制为整数后, 其整数规划解出现下述情况; ①原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。②整数规划无可行解。 Operations Research Operations Research Prof. Wang Prof. Wang School of Economics & Management School of Economics & Management page page 4 4 21 December 2016 21 December 2016 第十四、十五讲§ § 1 1 概述概述( (3 3) ) [ 例 2-1] 原线性规划为: 2 x 1 +4 x 2 =5 ,X≥0,C TX=x 1+x 2 =min 其最优实数解为: x 1 =0 ,x 2 =5/4 , min C TX =5/4 。③有可行解(当然就存在最优解),但最优解值变差。 [ 例 2-2] 原线性规划为: 2 x 1 +4 x 2 =6 ,X≥0,C TX=x 1+x 2 =min 其最优实数解为: x 1 =0 ,x 2 =3/2 , min C TX =3/2 。若限制整数则得: x 1 =1 ,x 2 =1 , min C TX =2 。 Operations Research Operations Research Prof. Wang Prof. Wang School of Economics & Management School of Economics & Management page page 5 5 21 December 2016 21 December 2016 第十四、十五讲§ § 1 1 概述概述( (4 4) ) 2 .整数规划最优解不能按照实数最优解简单取整而获得。[例 2-3] 物品装载问题:有若干类物品需一次性装运,每件物品的价值及重量分别,为 v j和w j (j =1, …,n), 车辆最大载重量为?,试求,每件物品应装多少件才能使总价值最大。[解] 令x j表示第 j类物品的装载件数,则可列写整数规划如下: ????????? max 11 11nn nnxvxv xwxw???x j≥0且取整(2) Operations Research Operations Research Prof. Wang Prof. Wang Sc