1、物流运筹学物流运筹学Logistics Operational Research物流管理专业基础课程物流管理专业基础课程郭淑红guoshuhong_13074553453Chapter4 整数规划整数规划( Integer Programming )整数规划问题及数学模型整数规划问题及数学模型分支定界法分支定界法割平面法割平面法0 1规划与隐枚举法规划与隐枚举法指派问题与匈牙利法指派问题与匈牙利法本章主要内容：本章主要内容：第一节第一节 整数规划问题及数学模型整数规划问题及数学模型v线性规划的决策变量取值可以是任意非负实数，但许线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当
2、决策变量的取值为整数时才有多实际问题中，只有当决策变量的取值为整数时才有意义意义n 例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。v要求全部或部分决策变量的取值为整数的线性规划问要求全部或部分决策变量的取值为整数的线性规划问题，称为整数规划题，称为整数规划 (Integer Programming)。n 全部决策变量的取值都为整数，则称为全整数规划 (All IP)n 仅要求部分决策变量的取值为整数，则称为混合整数规划 (Mixed IP)n 要求决策变量只取 0或 1值，则称 0-1规划 (0-1 Programming) v整数规划（简称：整数规划
3、（简称： IP）要求一部分或全部决策变量取整数值的规划问题称为整数规要求一部分或全部决策变量取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性问题称为该整数规划问题的松弛问题。若该松弛问题是一个线性规划，则称该整数规划为整数线性规划。规划，则称该整数规划为整数线性规划。整数线性规划数学模型的一般形式：第一节第一节 整数规划问题及数学模型整数规划问题及数学模型v一、纯整数规划一、纯整数规划第一节第一节 整数规划问题及数学模型整数规划问题及数学模型第一节
4、第一节 整数规划问题及数学模型整数规划问题及数学模型解：解：例：例： 某公司拟建设某公司拟建设 A、 B两种类型的生产基地若干个，两种类型两种类型的生产基地若干个，两种类型的生产基地每个占地面积，所需经费，建成后生产能力及现有的生产基地每个占地面积，所需经费，建成后生产能力及现有资源情况如下表所示。问资源情况如下表所示。问 A、 B类型基地各建设多少个，可使总类型基地各建设多少个，可使总生产能力最大？生产能力最大？ 解：设解：设 A、 B两类基地各建设两类基地各建设 个，则其模型为：个，则其模型为： 第一节第一节 整数规划问题及数学模型整数规划问题及数学模型人员安排规划某服务部门各时段 (每
5、2小时为一时段 )需要的服务人数如表：解：设第 j 时段开始时上班的服务员人数为 xj 第 j 时段来上班的服务员将在第j+3 时段结束时下班，故决策变量有x1,x2,x3,x4,x5 。 按规定，服务员连续工作按规定，服务员连续工作 8小时小时(4个时段个时段 )为一班。请安排服务员为一班。请安排服务员的工作时间，使服务员总数最少的工作时间，使服务员总数最少 .第一节第一节 整数规划问题及数学模型整数规划问题及数学模型二、 0-1规划登山队员可携带最大重量为登山队员可携带最大重量为 25公斤。问都带哪些物品的重要性最大。公斤。问都带哪些物品的重要性最大。解：对于每一种物品无非有两种状态，带或
6、者不带，不妨设解：对于每一种物品无非有两种状态，带或者不带，不妨设序号序号 1 2 3 4 5 6 7物品物品 食品食品 氧气氧气 冰镐冰镐 绳索绳索 帐篷帐篷 相机相机 设备设备重量重量 5 5 2 6 12 2 4重要性系数重要性系数 20 15 18 14 8 4 100-1规划的模型：规划的模型：第一节第一节 整数规划问题及数学模型整数规划问题及数学模型三、混合整数规划三、混合整数规划例：例： 某产品有某产品有 n个区域市场，各区域市场的需求量为个区域市场，各区域市场的需求量为 bj吨吨 /月；现拟在月；现拟在 m个地点中选址建生产厂，一个地方最多只能建一家工厂；若选个地点中选址建生产
7、厂，一个地方最多只能建一家工厂；若选 i地建厂，地建厂，生产能力为生产能力为 ai吨吨 /月，其运营固定费用为月，其运营固定费用为 F元元 /月；已知址月；已知址 i至至 j区域市场的运区域市场的运价为价为 cij元元 /吨。如何选址和安排调运，可使总费用最小？吨。如何选址和安排调运，可使总费用最小？解：解： 选址建厂与否是个选址建厂与否是个 0-1型决策变量，型决策变量，假设假设 yi =1，选择第，选择第 i 址建厂，址建厂， yi=0，不选择第，不选择第 i 址建厂；址建厂；计划从计划从 i 址至区域市场址至区域市场 j 的运输的运输运量运量 xij为实数型决策变量。为实数型决策变量。第一节第一节 整数规划问题及数学模型整数规划问题及数学模型
