运筹学整数规划案例

第六章整数规划 6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域 “×”标出 ) 。 1、 max z=3 x 1+2x2 1 S.T. 2x +3x ≤ 12 2 ( 在图上用 2x1+x2≤ 9 x1、 x2≥ 0 解： 2、 min f=10 S.T. x1+9x2 5x1+3x2≥ 45 x1≥8 x2≤10 x1、 x2≥ 0 、 6.2求解下列整数规划问题 1、 min f=4 S.T. x1+3x2+2x3 2x1-5x2+3x3≤4 4x1+x2+3x3≥ 3 x2+x3≥ 1 、x1 x2x3=0 或 1 解：最优解（0， 0， 1），最优值： 2 x1+5x2+3x3+4x3 S.T.-4 x1+x2+x3+x4≥2 -2 x1+4 x 2+2x2+4x2≥ 4 x1+x2-x2+x2≥ 3 x1 x2x3 x3 =0 或 1 解：此模型没有可行解。 3、 maxZ=2x1+3x 2+5x3+6x4 S.T.5x +3x +3x +x ≤ 30 1234 、、、 2、 min f=2 2x1+5x2-x 2+3x2≤20 - x1+3x2+5x2+3x2≤ 40 3x1-x2+3x 2+5x2≤25 x1 x2x3 x3 =正整数 解：最优解（0， 3， 4，3），最优值： 47 、、、 4、 min z =8x 1 +4 x 2+3 x3+5 x4+2 x5 ＋ 3 x 6＋ 4 x7＋ 3 x8+4 x9+9 x10+7 x11+ 5 x12 +10 x 13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19 约束条件x + x +x ≤ 30 123 x + x ＋ x -10 x 456 ≤ 0 16 x7+ x8＋ x9-20 x 17≤ 0 x+ x 10 ＋ x 1112 -30 x ≤0 18 x13+ x14＋ x15-40 x 19≤ 0 x1 + x4+ x7+x10+ x13＝30 x2 + x5+ x8+x11+ x14＝ 20 x + x+ x +x + x ＝20 x 为非负数（ i=1,2 ⋯ 8） i 3691215 xi为非负整数（ i=9,10 ⋯15） x 为为 0－1 i 变量（ i=16,17 ⋯ 19） 解：最优解（ 30 ， 0， 0， 0，0， 0， 0，0， 0， 0， 0， 0， 0， 20 ， 20 ， 0， 0，0， 1），最优值： 860 6.3一餐饮企业准备在全市范围内扩展业务，将从已拟定的 店的费用情况如下表： 14 个点中确定8 个点建立 分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14 个 店名B 1 1.2 B 2 1.5 B3B4B5B6B7 2.8 B8B9B10 3.0 B11 2.4 B12 2.4 B13B 14 2.11.6费用 (万元 )1.72.13.31.22.51.9 公司办公会决定选择原则如下： （1） B 5、B3 和 B7只能选择一个。 （2）选择了 B 1 或 B14就不能选 B6。 （3） B 2、B6、 B1、B12，最多只能选两个。 （4） B 5、B7、 B10、 B8 ，最少要选两个。 问应选择哪几个点，使总的建店费用为最低？ 解：数学模型： minf＝ 1.2 x +1.5 x+1.7 x +2.1 x+3.3 x +1.2 x +2.8 x +2.5 x +1.9 x +3 x+2.4 x+2.4 x +2.1 x +1.6 x 1234567891011 121314 S.T. x x 1+x + x -2 x =2 2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14=8 x 357 + x =1 16 x x 6+ x +x +x +x 14=1 ≤ 2 x 12612 +x +x +x ≥ 2 57810 xi≥ 0 且 xi为 0－ 1 变量， i ＝ 1， 2， 3，⋯， 14。 最优解：（ 1， 1， 1， 1， 1， 0， 0， 0， 1， 0， 0， 0， 1， 1）最优值： 15.4 。 即： B1， B2， B3， B4,B5,B9,B13,B14选中，建店的最低费用15.4 万元。 6.4 有四个工人（甲、乙、丙、丁），要分别指派他们完成四项不同的工作（A、 B、 D），请按以下要求求解指派问题。 1、每人做各项工作所消耗的时间如下表所示，问应如何分配工作，才能使总的消耗时 间为最少？ 每人完成各项工作的所需时间小时 是工作 否 分 工作 A工作 B工作 C工作 D 工人配 甲1816-19 乙-201620 丙19181721 丁121520- 2、每人做各项工作所创的利润如下表所示，问应如何指派工作，才能使总的创利为最 多？ 所工作 创 利 工作 A工作 B工作 C工作 D 工人益 甲4579 乙7568 C、 丙3 7 4 6 3 8 5 8丁 解： 1、消耗时间为最少问题 线性规划数学模型： min f= 18x 1+16x2+19x3+20 x4+16x5+20 x6+19x7+18x8+17x9+21x10+12x11+15x12+20 x13 S.T.x1+x2+x3=1 x4+x5+x6=1 x7+x8 +x9+x10=1 x11+x12+x13=1 x1+x7 +x11 x5+x9 +x13 x3+x6 +x10 =1 =1 =1 x2+x4 +x8 +x12 =1 xi≥ 0 且 xi为 0－ 1 变量， i＝ 1，2， 3，⋯， 13。 最优解：（ 0， 1， 0， 0， 1， 0， 0， 0， 0， 1， 1， 0， 0，），最优值： 65。 即：给甲分配工作 B，给乙分配工作 C，给丙分配工作 D，给丁分配工作 A，所用最少的时间 为 65 小时。 2、总的创利为最多问题 线性规划数学模型： maxZ = 4 1+52+73 +94+75+5x6+6x7+8x8+3x9+4x10+3x11+5 x12+7x13+6 x14+8x15+8 x16 S.T.x +x +x+x=1 14 x +x +x +x =1 5678 23 x9+x10+x11+x12=1 x+x+x +x =1 13141516 x +x +x+x=1 15913 +x=1 371115 x +x +x+x=1 481216 x2+x6+x10+x14=1 x +x +x xi≥ 0 且 xi为 0－ 1 变量， i＝ 1， 2， 3，⋯， 16 最优解：（ 0， 0， 0， 1， 1， 0， 0， 0， 0， 1， 0， 0， 0， 0,1,0 ），最优值： 28。 即：给甲分配工作D，给乙分配工作A，给丙分配工作B，给丁分配工作C，所创最多的 利润为 28 元。 6.5 某企业在 A 1 地已有一个工厂，其产品的生产能力为 在 A 2， A3， A4，A5 地中再选择几个地方建厂。已知在 在 A 3 地建厂的固定成本为30 万元，在 A 4 地建厂的固定成本为 3万箱，为了扩大生产，打算 37.5 万元，在 A 5