运筹学整数规划习题

1、第四章一一 1 第四章整数规划 4.1某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料 A、材料B,有关数据如 下，问这两种设备各生产多少使工厂利润最大？（只建模不求解） 表 4 1 设备 材料 甲 乙 资源限量 材料 A (kg) 2 3 14 材料 B (kg) 1 0.5 4.5 利润（元/件） 3 2 max 3x1 2x2 2x1 3x2 14 x1 0.5x2 4.5 xx 2 0 xx 2为整 割平面法求解。（下表为最优表） 5 7 9 0 0 b CB XB X1 X2 X3 X4 9 X2 0 1 7/22 1/22 7/2 7 X1 1 0 1/22 3/22 9/

2、2 Cj z 0 0 28/11 15/11 解: 线性规划的最优解为: x1 9/ 2, x2 7/2,x3 x4 O,maxz 63 由最终表中得： 7 1 x3 x4 22 3 22 4 将系数和常数项分解成整数和非负真分式之和，上式化为; 移项后得:解：设生产甲、乙这两种设备的数量分别为 建立模型如下： XI、X2,由于是设备台数，则其变量都要求为整数, 4.2 max z 7x1 9x2 X1 3x2 6 s.t 7x1 X2 35 X1，X2 0 且为整 x2 7 22 22 X4 第四章一一 2 在的最优单纯形表中加上此约束，用对偶单纯形法求解: Cj 7 9 0 0 0 0 b

3、 CB XB X1 X2 X3 X4 X5 X6 9 X2 0 1 0 0 1 0 3 7 X1 1 0 0 1/7 1/7 0 32/7 0 X3 0 0 1 1/7 22/7 0 11/7 0 X6 0 0 0 * 1/7 6/7 1 4/7 Cj z 0 0 0 1 8 0 9 X2 0 1 0 0 1 0 3 7 X1 1 0 0 0 1 1 4 0 X3 0 0 1 0 4 1 1 0 X4 0 0 0 1 6 7 4 Cj z 0 0 0 0 2 7 则最优解为x； 4, x； 3，最优目标函数值为 z*=55。 max z= 4x1 + 3x2+ 2x3即: 7 1 1 22X3

4、 22x4 2 22 X3 1 22 X4 只要把增加的约束条件加到 B问题的最优单纯形表中。 Cj 7 9 0 0 0 b CB XB x1 X2 X3 X4 X5 9 X2 0 1 7/22 1/22 0 7/2 7 X1 1 0 1/22 3/22 0 9/2 0 x5 0 0 * 7/22 1/22 1 1/2 Cj z 0 0 28/11 15/11 0 Cj 7 9 0 0 0 b CB XB X1 X2 X3 X4 X5 9 X2 0 1 0 0 1 3 7 X1 1 0 0 1/7 1/7 32/7 0 X3 0 0 1 1/7 22/7 11/7 a -zj 0 0 0 1

5、8 X1 1 X4 32 7 将系数和常数项分解成整数和非负真分数之和: 得到新的约束条件: 1 6 4 X1 -X4 X5 X5 4 7 7 7 1 6 4 X4 X5 7 7 7 1 6 4 X4 XX6 7 7 7 4.3 表 4 3 第四章一一 3 2x1 5x2 3x3 4 4x1 x2 3x3 3 s.t X2 X3 1 x1, x2, x3 0 或 1 隐枚举法 解：(1 )先用试探的方法找出一个初始可行解，如 X1 = X2= 0, X3= 1。满足约束条件，选其作为 初始可行解，目标函数 zo= 2。 (2)附加过滤条件 以目标函数z z0作为过滤约束： 4x1 3x2 2x

6、3 2 原模型变为： max z = 4x1 + 3x2 + 2x3 2x1 5X2 3x3 4 4x1 X2 3x3 3 X2 X3 1 4x1 3x2 2x3 2 x1, x2, x3 0 或 1 求解过程如表所示。 占 八、 过滤条件 约束 z 值 4x1 + 3x2+ 2x3 2 (0, 0, 0) T X (0, 0,1) T n V V V V 2 (0, 1, 0) T V V X (0, 1, 1) T V V V V 5 4x1 + 3x2+ 2x3 5 (1, 0, 0) T X (1, 0 , 1) T V X (1, 1 , 0) T 1 V V V V 7 4x1 +

7、 3x2+ 2x3 7 (1, 1 , 1) T V V V V 9 所以该0 1规划最优解为x, x2 x3 1,z 9。 4.4 某公司拟在市东、西、南三区中建立门市部，有 7个点Ai (i = 1, 2，7)可供选择， 要求满足以下条件： (1) 在东区，在 A1, A2, A3三个点中至多选两个； (2) 在西区，A4, A5两个点中至少选一个； (3) 在南区，A6, A7两个点为互斥点。 (4) 选A2点必选A5点。 若Ai点投资为bi万元，每年可获利润为 Ci万元，投资总额为 B万元，试建立利润最大化的 0- 1规划模型。 解：设决策变量为 Xi 1, 0, 当 A 点被选用 当

8、A点未被选用 i 1,2, ,7 第四章一一 4 建立0- 1规划模型如下:第四章一一 5 7 maxz c1X1 C2X2 C7X7 cix 7 i 1 bi Xi B X1 X2 X3 2 S.t X4 X5 1 X6 X7 1 X2 X5 0 Xi 0, 或 1,i 1,2, ,7 4.5某城市消防队布点问题。该城市共有 6个区，每个区都可以建消防站，市政府希望设置的 消防站最少，但必须满足在城市任何地区发生火警时，消防车要在 15分钟内赶到现场。据实地测 定，各区之间消防车行驶的时间见表 4 9,请帮助该市制定一个布点最少的计划。 表 4 9消防车在各区间行驶时间表 单位：min 地区

9、 1 地区 2 地区 3 地区 4 地区 5 地区 6 地区 1 0 10 16 28 27 20 地区 2 10 0 24 32 17 10 地区 3 16 24 0 12 27 21 地区 4 28 32 12 0 15 25 地区 5 27 17 27 15 0 14 地区 6 20 10 21 25 14 0 解：引入0 1变量Xi作决策变量，令 目标函数为 min Z= X1+ X2 + X3+ X4 + X5 + X6 本问题的约束方程是要保证每个地区都有一个消防站在 可知，在地区1及地区2内设消防站都能达到此要求，即 X1 + X2 1 因此本问题的数学模型为: min Z= X

10、1+ X2 + X3+ X4 + X5 + X6 广 X1 + X2 1 X1 + X2 + X6 1 X3 + X4 1 S.t 1 X4 + X5 + X6 1 X2 + X5 + X6 1 .Xi = 1 或 0 （i = 1，6） 4.7 一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信 器材等，每种物品的重量及重要性系数见表 4- 10所示，能携带的最大重量为 25 kg，试选择该队员 所应携带的物品。 表 4 10 序号 1 2 3 4 5 6 7 物品 食品 氧气 冰镐 绳索 帐篷 照相器材 通信设备 重量 kg 5 5 2 5 10 2 3 1, X 0, 表示在地区 i 设消防站 表示在地区 i 不设消防站 i 1,2, ,6 15分钟行程内。如地区 1,由表4 9 第四章一一 6 重要性系数 20 15 16 14 8 14 9 第四章 7 解：引入 0 1 变量 xi