管理远筹学 谢家平博士副教授 研究领域:系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程:管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单位:上海财经大学国际工商管理学院供应链管理研究中心 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