第八章_整数规划.pdf

第八章 整数规划 Integer Programming 第八章 整数规划 在前面讨论的线性规划问题中，最优解 可能是整数，也可能不是整数，但对于 某些实际问题，要求答案必须是整数 。 如， 所求的解是安排上班的人数， 按某个方案裁剪钢材的根数， 生产机器的台数等。 第八章 整数规划  8.1 整数规划模型 §8.1 整数规划模型 整数规划模型的一般形式 Max（或Min） Z = Σc x j j s.t. Σa x ≤ ( 或 = , ≥ ) b i=1,2, …, m ij j i xj ≥0 j=1,2, …, n x 1 , x2 , … xn 中部分或全部取整数 §8.1 整数规划模型 在线性规划模型中 • 如果所有的决策变量都要求为非负整数，则这样 的线性规划问题称之为纯整数规划问题。 • 如果只有一部分决策变量要求为非负整数，则这 样的线性规划问题称之为混合整数规划问题。 • 如果决策变量的取值只限于 0 和 1，则这样的 整数线性规划问题称之为 0－1型整数规划问题。 §8.1 整数规划模型 例：一登山队员做登山准备，他需要 携带的物品有：食品，氧气，冰镐， 绳索，帐篷，照相机和通讯设备，每 种物品的重要性系数和重量如下：假 定登山队员可携带最大重量为25公 斤。 序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 相机 设备 重量 5 5 2 6 12 2 4 重要 20 15 18 14 8 4 10 系数 §8.1 整数规划模型 解： 令x =1表示登山队员携带物品i， i x =0表示登山队员不携带物品i: i Max Z= 20x +15x +18x +14x +8x +4x +10x 1 2 3 4 5 6 7 s.t. 5x1 + 5x2 +2x3 +6x4 +12x5 +2x6 +4x7 25 x =1 或 x =0 i=1,2,….7 i i 序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 相机 设备 重量 5 5 2 6 12 2 4 重要 20 15 18 14 8 4 10 系数 §8.1 整数规划模型 背包问题( Knapsack Problem) 一个旅行者,为了准备旅行的必须用品,要在背包内 装一些最有用的东西,有限制: • 最多只能装b公斤的物品 • 而每件物品只能整个携带 • 每件物品规定了一个“价值”以表示其有用的程度 • 如果共有n件物品,第 j 件物品a 公斤,其价值为c .