北邮运筹学ch5-1 整数规划数学模型.ppt

运筹学 Operations Research Mathematical Model of IP 2 .分枝定界法 Branch and Bound Method 3. 割平面法 cutting-plane Method 4. 0-1规划 Binary Integer Programming 5. 指派问题 Assignment Problem Chapter 5 整数规划 Integer Programming 运筹学北京邮电大学§ 整数规划数学模型 Mathematical Model of IP Ch5 Integer Programming 2017-2-20 Page 2 of 15 一个规划问题中要求部分或全部决策变量是整数,则这个规划称为整数规划。当要求全部变量取整数值的,称为纯整数规划;只要求一部分变量取整数值的,称为混合整数规划。如果模型是线性的,称为整数线性规划。本章只讨论整数线性规划。很多实际规划问题都属于整数规划问题. 例如 1. 变量是人数、机器设备台数或产品件数等都要求是整数 2. 对某一个项目要不要投资的决策问题,可选用一个逻辑变量 x,当 x =1 表示投资, x =0 表示不投资; 3. 人员的合理安排问题,当变量 x ij =1 表示安排第 i人去做 j 工作, x ij =0 表示不安排第 i人去做 j工作。逻辑变量也是只允许取整数值的一类变量。运筹学北京邮电大学§ 整数规划数学模型 Mathematical Model of IP Ch5 Integer Programming 2017-2-20 Page 3 of 15 【 】某人有一背包可以装 10 公斤重、 3 的物品。他准备用来装甲、乙两种物品,每件物品的重量、体积和价值如表 5-1所示。问两种物品各装多少件,所装物品的总价值最大? 表5—1 物品重量(公斤/每件) 体积(m 3/每件) 价值(元/每件) 甲乙 43 【解】设甲、乙两种物品各装 x 1、x 2件,则数学模型为: ????????????且均取整数,0, 25 10 34 max 21 21 21 21xx xx xx xxZ() 运筹学北京邮电大学§ 整数规划数学模型 Mathematical Model of IP Ch5 Integer Programming 2017-2-20 Page 4 of 15 如果不考虑 x 1、x 2 取整数的约束(称为( )的松弛问题),线性规划的可行域如图 5—1中的阴影部分所示。图5-1 运筹学北京邮电大学§ 整数规划数学模型 Mathematical Model of IP Ch5 Integer Programming 2017-2-20 Page 5 of 15 用图解法求得点 B 为最优解: X= ( ,) ,Z= 。由于 x 1,x 2 必须取整数值,实际上整数规划问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合,但( 4, 7 )、( 4,8 )( 3,8 )都不是可行解,( 3,7 )虽属可行解,但代入目标函数得 Z =33, 并非最优。实际上问题的最优解是( 5,5 ), Z =35 。即两种物品各装 5件,总价值 35元。由图 5-1 知,点( 5,5 )不是可行域的顶点,直接用图解法或单纯形法都无法求出整数规划问题的最优解,因此求解整数规划问题的最优解需要采用其它特殊方法。还有些问题用线性规划数学模型无法描述,但可以通过设置逻辑变量建立起整数规划的数学模型。运筹学北京邮电大学§ 整数规划数学模型 Mathematical Model of IP Ch5 Integer Programming 2017-2-20 Page 6 of 15 【 】在例 中,假设此人还有一只旅行箱,最大载重量为 12 公斤,其体积是 m 3。背包和旅行箱只能选择其一,建立下列几种情形的数学模型,使所装物品价值最大。(1)所装物品不变; (2)如果选择旅行箱,载重量和体积的约束为 20 12 21 1????xx x解:此问题可以建立两个整数规划模型,但用一个模型描述更简单。引入 0-1变量(或称逻辑变量) y i,令 2,1 0 ,1?????ii iy i种方式装载时不采用第, 种方式装载时采用第 i =1,2 分别是采用背包及旅行箱装载。运筹学北京邮电大学§ 整数规划数学模