《运筹学》课程PPT教学课件（Operations Research）第四章（4.1）整数规划

运筹学 Operations Research §4.1整数规划 整数规划(IP, Integer programming):决策变量的全部或部 分取整数值的线性规划 分类 1.纯整数规划(IP,AIP, all integer programming):全 部决策变量均取整数值的整数规划 max2三Cx (IP): s.t. Ax=b ≥0,整数,=1,2,…,n 2021/2/20

2021/2/20 1 运 筹 学 Operations Research §4.1 整数规划 整数规划（IP，integer programming）：决策变量的全部或部 分取整数值的线性规划. 分类： 1.纯整数规划（IP，AIP，all integer programming）：全 部决策变量均取整数值的整数规划.       = = = x j n st Ax b z c x IP j T 0, , 1,2, , . . max ( ) : 整数 

运筹学 Operations Research 2.混合整数规划(MIP, mixed integer programming):决 策变量的一部分取整数值的整数规划 max C X s t. Ax=b (MP) x,≥0,整数,j∈Nc{1,2,…,n} 0,j∈{1,2,…,n}\N 问:(MIP)与(LP),(IP)有何关系? 2021/2/20 2

2021/2/20 2 运 筹 学 Operations Research 2.混合整数规划（MIP，mixed integer programming）：决 策变量的一部分取整数值的整数规划.             = = x j n N x j N n st Ax b z c x MIP j j T 0, {1,2, , } \ 0, , {1,2, , } . . max ( ) :  整数  问：（MIP）与(LP),(IP)有何关系？

运筹学 Operations Research 3.0-1规划(0-1 programming):x=01,j=1,2,…,n maX Z=C x (BIP): s.t. Ax=b 2021/2/20 3

2021/2/20 3 运 筹 学 Operations Research 3.0-1规划（0-1 programming）： x j = 0,1, j = 1,2,  ,n      = = = = x j n st Ax b z c x BIP j T 0,1, 1,2, , . . max ( ) : 

运筹学 Operations Research 例1今将m种物品装入容积为b的背包中第种物品的体积为a, 价值为c,j=12,…,n间:应如何选择物品装入背包中,才 能使得装入物品的总体积不穿过背包的容积,且总价值最大? 解:令x 装入第j种物 0.否则 maX s t b x1=0,1,j=1,2,…, 2021/2/20 4

2021/2/20 4 运 筹 学 Operations Research 能使得装入物品的总体积不穿过背包的容积，且总价值最大？ 价值为 ， 问：应如何选择物品装入背包中，才 例 今将 种物品装入容积为 的背包中第 种物品的体积为 ， 1,2, , . 1 . c j n m b j a j j =  解：令 j n j x j , 1,2, , 0, 1, =     = 否则， 装入第 种物品，          = =  =   = = x j n st a x b z c x j n j j j n j j j 0,1, 1,2, , . . max 1 1  则 ▌

运筹学 Operations Research §4.1over 2021/2/20

2021/2/20 5 运 筹 学 Operations Research §4.1 over