管理远筹学 谢家平博士副教授 研究领域:系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程:管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单位:上海财经大学国际工商管理学院供应链管理研究中心 E-mail:jiapingxie@sina.com.cn 电话:55036936(H)65903541(O)
管理运筹学 谢家平 博士 副教授 研究领域：系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程：管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单 位：上海财经大学国际工商管理学院供应链管理研究中心 E-mail：jiaping_xie@sina.com.cn 电 话：55036936(H) 65903541(O)
SHUFE 第6章整数规划 线性规划的决策变量取值可以是任意非负实数,但许多 实际问题中,只有当决策变量的取值为整数时才有意义。 例如,产品的件数、机器的台数、装货的车数、完成工作的人 数等,分数或小数解显然是不合理的。 要求全部或部分决策变量的取值为整数的线性规划问题, 称为整数线性规划,简称整数规划( Integer Programming) 全部决策变量的取值都为整数,则称为全整数规划(AIP; 仅要求部分决策变量的取值为整数,则称为混合整数规划 (Mixed l); 要求决策变量只能取0或1值,则称为01规划(01 Programming) 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 2 第6章 整数规划 • 线性规划的决策变量取值可以是任意非负实数，但许多 实际问题中，只有当决策变量的取值为整数时才有意义。 ▪ 例如，产品的件数、机器的台数、装货的车数、完成工作的人 数等，分数或小数解显然是不合理的。 • 要求全部或部分决策变量的取值为整数的线性规划问题， 称为整数线性规划，简称整数规划(Integer Programming)。 ▪ 全部决策变量的取值都为整数，则称为全整数规划(All IP)； ▪ 仅要求部分决策变量的取值为整数，则称为混合整数规划 (Mixed IP)； ▪ 要求决策变量只能取0或1值，则称为0-1规划(0-1 Programming)
SHUFE 第一节整数规划问题 、问题的提出 为了满足整数要求,似乎可以把线性规划的小数最优解 进行“舍入化整”以得到与最优解相近的整数解。 “舍入化整”一般是不可行的: 化整后的解有可能成为非可行解; 虽是可行解,却不是最优解。 例如 产品 资源 甲 乙 现有量 A B 256 7 35 单台利润 问如何安排甲、乙两产品的产量,使利润为最大。 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 3 第一节 整数规划问题 • 为了满足整数要求，似乎可以把线性规划的小数最优解 进行“舍入化整”以得到与最优解相近的整数解。 • “舍入化整”一般是不可行的： ▪ 化整后的解有可能成为非可行解； ▪ 虽是可行解，却不是最优解。 • 例如 一、问题的提出 产品 资源 甲 乙 现有量 A 2 1 9 B 5 7 35 单台利润 6 3 ▪ 问如何安排甲、乙两产品的产量，使利润为最大
SHUFE 第一节整数规划问题 解:设x/为甲产品的台数,x2为乙产品的台数 maxz= 6x, +5x2 5x1+7x2≤35 xn,x2≥0 x1x2取整数 不考虑整数约束则是一个LP问题称为原整数规划的松弛问题。 不考虑整数约束的最优解:x1=28/9,x2=25/9,Z*=2939 舍入化整 x1=3,x2=3,Z=33,不满足约束条件x1+7x2≤35,非可行解; nx1=3,x2=2,z=28,满足约束条件,是可行解,但不是最优解; 1=4,x2=1,Z=29,满足约束条件,才是最优解。 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 4 第一节 整数规划问题 • 解：设x1为甲产品的台数，x2为乙产品的台数。 maxZ= 6x1 +5 x2 2x1 + x2 ≤9 5x1 +7 x2 ≤35 x1 , x2 ≥0 x1 , x2取整数 • 不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题。 ▪ 不考虑整数约束的最优解：x1 *=28/9， x2 * =25/9，Z * =293/9 • 舍入化整 ▪ x1 =3， x2 =3，Z=33，不满足约束条件5x1 +7 x2 ≤35，非可行解； ▪ x1 =3， x2 =2，Z=28，满足约束条件，是可行解，但不是最优解； ▪ x1 =4， x2 =1，Z=29，满足约束条件，才是最优解
SHUFE 第一节整数规划问题 整数规划的图解法 步骤 在线性规划的可行域内列出所有决策变量可能取的整数值, 求出这些变量所有可行的整数解, 比较它们相应的目标函数值,最优的目标函数值所对应的 解就是整数规划的最优解。 实用性: 2x1+x,=9 只有两个决策变量, 可行的整数解较少。 3,3) 5x1+7x,=35 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 5 • 步骤： ▪ 在线性规划的可行域内列出所有决策变量可能取的整数值， ▪ 求出这些变量所有可行的整数解， ▪ 比较它们相应的目标函数值，最优的目标函数值所对应的 解就是整数规划的最优解。 • 实用性： ▪ 只有两个决策变量， ▪ 可行的整数解较少。 5x1 +7 x2 =35 2x1 + x2 =9 • (3,3) • • • • • • • • • • 第一节 整数规划问题 二、 整数规划的图解法 x1 x2 1 2 3 1 2 5 3 4 4 ) 9 7 ,2 9 1 (3
SHUFE 第一节整数规划问题 三、整数规划问题举例 设备购置问题:某厂拟用M元资金购买m种设备,设备i的单价 为pi;,现有n个地点可装置这些设备,第处最多可装置b台;设备i 装置在j处可获利c元。如何购置,总利润最大? 假设:购买第种设备台数,将第i种设备安装在第处的台数x 该问题的数学模型 maxz=∑∑cx i=1.2n ∑ j=1,2,…,n D,y≤M xn,y为整数 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 6 第一节 整数规划问题 • 设备购置问题：某厂拟用M元资金购买m种设备，设备i 的单价 为pi；现有n个地点可装置这些设备，第j 处最多可装置bj 台；设备i 装置在j 处可获利cij元。如何购置，总利润最大？ 假设：购买第i 种设备yi台数，将第i 种设备安装在第j 处的台数xij 该问题的数学模型 三、 整数规划问题举例 i j i为整数 i j i m i i i m i i j j n j i j i m i n j i j i j x y x y p y M x b j n x y i m Z c x , , 0 1,2,..., 0 1,2,..., max 1 1 1 1 1 = − = = = = = = =
SHUFE 第一节整数规划问题 投资决策问题:某厂拟用b元资金投资n个项目,项目需资金 元,可获利c元。应选择那些项目,获利最大? 假设:x=1表示投资项目;x=0表示不投资项目 该问题的数学模型 max Z <6 1或O,j=1,2, 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 7 第一节 整数规划问题 • 投资决策问题：某厂拟用b元资金投资n个项目，项目j 需资金aj 元，可获利cj元。应选择那些项目，获利最大？ 假设：xj =1表示投资项目j ； xj =0表示不投资项目j 该问题的数学模型 x j n a x b Z c x j n j j j n j j j 1 0, 1,2,..., max 1 1 = = = = = 或
SHUFE 第一节整数规划问题 厂选址问题:某商品有n个销地,各销地的需求量为b吨天; 现拟在m个地点中选址建生产厂,一个地方最多只能建一个工厂; 若选地建厂,生产能力为a吨/天,固定费用为元/天;已知址至 销地j的运价为c;元吨。如何选址和安排调运,总费用最小? 假设:y=1,选择第i址建厂,y=0,不选择第址建厂;从厂址 至销地j运量为x 该问题的数学模型 min z 能力约束:∑x≤ayt=1,2 需求约束∑x=b l.2 非负约束: O 整数约東 1或O 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 8 第一节 整数规划问题 • 工厂选址问题：某商品有n个销地，各销地的需求量为bj吨/天； 现拟在m个地点中选址建生产厂，一个地方最多只能建一个工厂； 若选i 地建厂，生产能力为ai吨/天，固定费用为di元/天；已知i 址至 销地j 的运价为cij元/吨。如何选址和安排调运，总费用最小？ 假设：yi=1，选择第i 址建厂， yi=0，不选择第i 址建厂；从厂址i 至销地j 运量为xij 。 该问题的数学模型 1 0 0 1,2,..., 1,2,..., min 1 1 1 1 1 整数约束： 或 非负约束： 需求约束： 能力约束： = = = = = + = = = = = i i j j m i i j i i n j i j m i i i m i n j i j i j y x x b j n x a y i m Z c x d y
SHUFE 第二节分枝定界法 分枝定界法( Branch and bound method) 基本思想: 先求出整数规划相应的LP(即不考虑整数限制)的最优解 若求得的最优解符合整数要求,则是原IP的最优解; 若不满足整教条件,则任选一个不满足整数条件的变量来 构造新的约束,在原可行域中剔除部分非整数解。 然后,再在缩小的可行域中求解新构造的线性规划的最优 解,这样通过求解一系列线性规划问题,最终得到原整数 规划的最优解。 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 9 第二节 分枝定界法 • 分枝定界法(Branch and Bound Method) • 基本思想： ▪ 先求出整数规划相应的LP(即不考虑整数限制)的最优解， ▪ 若求得的最优解符合整数要求，则是原IP的最优解； ▪ 若不满足整数条件，则任选一个不满足整数条件的变量来 构造新的约束，在原可行域中剔除部分非整数解。 ▪ 然后，再在缩小的可行域中求解新构造的线性规划的最优 解，这样通过求解一系列线性规划问题，最终得到原整数 规划的最优解
SHUFE 第二节分枝定界法 定界的含义: 整数规划是在相应的线性规划的基础上增加变量为整数的 约束条件,整数规划的最优解不会优于相应线性规划的最 优解。 对极大化问题来说,相应线性规划的目标函数最优值是原 整数规划函数值的上界; 对极小化问题来说,相应线性规划的目标函数的最优值是 原整数规划目标函数值的下界。 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 10 第二节 分枝定界法 • 定界的含义： ▪ 整数规划是在相应的线性规划的基础上增加变量为整数的 约束条件，整数规划的最优解不会优于相应线性规划的最 优解。 ▪ 对极大化问题来说，相应线性规划的目标函数最优值是原 整数规划函数值的上界； ▪ 对极小化问题来说，相应线性规划的目标函数的最优值是 原整数规划目标函数值的下界