第四章 整数线性规划 §1整数线性规划的图解法 §2整数线性规划的计算机求解 §3整数线性规划的应用
管 理 运 筹 学 1 第四章 整数线性规划 §1 整数线性规划的图解法 §2 整数线性规划的计算机求解 §3 整数线性规划的应用
§1 整数规划的图解法 例1.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、 重量、可获利润以及托运所受限制如表所示。 货物 每件体积 每件重量 每件利润 (立方英尺) (百千克) (百元) 甲 195 4 2 乙 273 40 3 托运限制 1365 140 甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。 解：设x1、x2分别为甲、乙两种货物托运的件数，建立模型 目标函数：Maxz=2X1+32 约束条件：s.t 195x1+273x2≤1365 4x1+40x2≤140 X1≤4 x1,2≥0为整数。 如果去掉最后一个约束，就是一个线性规划问题。利用图解法， 曹建运筹学
管 理 运 筹 学 2 §1 整数规划的图解法 例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、 重量、可获利润以及托运所受限制如表所示。 甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。 解：设x1 、x2分别为甲、乙两种货物托运的件数，建立模型 目标函数： Max z = 2x1 +3 x2 约束条件： s.t. 195 x1 + 273 x2 ≤1365 4 x1 + 40 x2 ≤140 x1 ≤4 x1，x2 ≥ 0 为整数。 如果去掉最后一个约束，就是一个线性规划问题。利用图解法， 货物 每件体积 （立方英尺） 每件重量 （百千克） 每件利润 （百元） 甲 乙 195 273 4 40 2 3 托运限制 1365 140
第五章 整数线性规划 整数规划一类要求问题的解中的全部或一部 分变量为整数的数学规划。从约束条件的构 成又可细分为线性，二次和非线性的整数规 划。 。 求整数解的线性规划问题，不是用四舍五入 法或去尾法对线性规划的非整数解加以处理 都能解决的，而要用整数规划的方法加以解 决
管 理 运 筹 学 3 第五章 整数线性规划 • 整数规划一类要求问题的解中的全部或一部 分变量为整数的数学规划。从约束条件的构 成又可细分为线性，二次和非线性的整数规 划。 • 求整数解的线性规划问题，不是用四舍五入 法或去尾法对线性规划的非整数解加以处理 都能解决的，而要用整数规划的方法加以解 决
第五章 整数线性规划 在整数规划中，如果所有的变量都为整数，则称为 纯整数规划问题；如果有一部分变量为整数，则称 之为混合整数规划问题。在整数规划中，如果变量 的取值只限于0和1，这样的变量我们称之为0-1变 量。如果所有的变量都为0-1变量，则称之为0-1规 划。 0-1变量可以数量化地描述诸如开与关、取与弃、 有与无等现象所反映的离散变量间的逻辑关系、顺 序关系以及互斥的约束条件，因此0-1规划非常适 合描述和解决如线路设计、工厂选址、生产计划 安排、旅行购物、背包问题、人员安排、代码选取、 可靠性等人们所关心的多种问题。实际上，凡是有 界变量的整数规划都可以转化为0-1规划来处理
管 理 运 筹 学 4 第五章 整数线性规划 • 在整数规划中，如果所有的变量都为整数，则称为 纯整数规划问题；如果有一部分变量为整数，则称 之为混合整数规划问题。在整数规划中，如果变量 的取值只限于0和1，这样的变量我们称之为0-1变 量。如果所有的变量都为0-1变量，则称之为0-1规 划。 • 0-1变量可以数量化地描述诸如开与关、取与弃、 有与无等现象所反映的离散变量间的逻辑关系、顺 序关系以及互斥的约束条件 ，因此0-1规划非常适 合描述和解决如线路设计 、工厂选址 、生产计划 安排、旅行购物、背包问题、人员安排、代码选取、 可靠性等人们所关心的多种问题。实际上，凡是有 界变量的整数规划都可以转 化为0-1规划来处理
§1 整数线性规划的图解法 3 2x1+3x2=14.66 2 2x1+3x2=14 22x+3=6 3 4 得到线性规划的最优解为x1=2.44,X2=3.26,目标函数值为14.66。 由图表可看出，整数规划的最优解为x=4,X2=2,目标函数值为14。 性质1：任何求最大日标函数值的纯整数规划或混合整数规划的最大目 标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目 标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相 应的线性规划的最小目标函数值
管 理 运 筹 学 5 得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。 由图表可看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。 性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目 标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目 标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相 应的线性规划的最小目标函数值。 1 2 3 4 1 2 3 2x1+3x2 =14.66 x1 x2 2x1+3x2 =14 2x1+3x2 =6 §1§1 整数线性规划的图解法 整数规划的图解法