第五章整数规划李超
第五章 整数规划 李超
第五章整数规划第一节夏整数规划问题及其数学模型第二节分枝定界法第三节0-1整数规划第四节指派问题第五节应用举例
第五章 整数规划 第一节 整数规划问题及其数学模型 第二节 分枝定界法 第三节 0-1整数规划 第四节 指派问题 第五节 应用举例
第一节整数规划问题及其数学模型一、问题的提出整数规划是为了解决实际问题而提出来的。例如我们在作决策时，对决策变量是人数、机器台数、医院的病床数等情况，若忽略整数条件，用一般的线性规划方法解，得到的最优解很可能是小数或分数而不符合整数要求。当然，有些整数规划问题的变量值很大，而成本或利润系数又较小，通过对相应线性规划最优解的舍入取整，得到的解是可以接受的。但大多数情况，这种舍入取整的方法是不可行的，此时得到的整数解不一定最优，甚至可能不是整数规划问题的可行解，因而有必要讨论整数规划的求解问题
第一节 整数规划问题及其数学模型 一、问题的提出 整数规划是为了解决实际问题而提出来的。例 如我们在作决策时，对决策变量是人数、机器台 数、医院的病床数等情况，若忽略整数条件，用 一般的线性规划方法解，得到的最优解很可能是 小数或分数而不符合整数要求。当然，有些整数 规划问题的变量值很大，而成本或利润系数又较 小，通过对相应线性规划最优解的舍入取整，得 到的解是可以接受的。但大多数情况，这种舍入 取整的方法是不可行的，此时得到的整数解不一 定最优，甚至可能不是整数规划问题的可行解， 因而有必要讨论整数规划的求解问题
【例1】某医院有资金45万元可用于购置甲、乙两种仪器。已知甲、乙仪器的每台价格分别为9万元和5万元，由于场地限制，购置的两种仪器总数不能超过6台。若一台甲仪器每年可增加收入8万元，一台乙仪器每年可增加收入5万元，问购置甲、乙两种仪器各多少台，可使每年增加的收入最大？解：设x、x2分别为购置的甲、乙两种仪器数，则xjx应为非负整数，这是一个纯整数规划问题，其数学模型为：Xi +x2 ≤69x +5x2 ≤45Max Z = 8x, +5x,s.t.Xi,X ≥0xi,x均为整数
【例1】某医院有资金45万元可用于购置甲、乙两种 仪器。已知甲、乙仪器的每台价格分别为9万元和5万 元，由于场地限制，购置的两种仪器总数不能超过6 台。若一台甲仪器每年可增加收入8万元，一台乙仪 器每年可增加收入5万元，问购置甲、乙两种仪器各 多少台，可使每年增加的收入最大？ 解：设x1、x2分别为购置的甲、乙两种仪器数，则x1、 x2应为非负整数，这是一个纯整数规划问题，其数 学模型为： Max 1 2 Z x x = + 8 5 1 2 1 2 1 2 1 2 6 9 5 45 . . , 0 , x x x x s t x x x x + + 均为整数
它与线性规划的不同之处仅在于增加了最后一个约束条件。现暂不考虑整数约束，用图解法可求得相应线性规划问题的最优解为：xj=3.75，x2=2.25，MaxZ=41.25（见图5-1)X29x+5x2= 45x,+x2=68x，+5x2=41.255X3B(3.75,2.25)211123456789x1图5-1不合要求！（不是整数，（5，0）为最优解）
它与线性规划的不同之处仅在于增加了最后一个 约束条件。现暂不考虑整数约束，用图解法可求得相 应线性规划问题的最优解为： 9x1+5x2 = 45 o 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 B(3.75,2.25) 8x1+5x2 = 41.25 x1+x2 = 6 • • • • • • • • • • • • • x1 x2 • • • • • • • • • • • • A C 图5-1 x1=3.75，x2=2.25，Max Z =41.25（见图5-1） 不合要求！（不是整数，（5，0）为最优解 ）