第六章运筹学整数规划案例.docVIP

第六章 整数规划 6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。 1、 max z=3x1+2x2 S.T. 2x1+3x2≤12 2x1+x2≤9 x1、x2≥0 解： 2、 min f=10x1+9x2 S.T. 5x1+3x2≥45 x1 ≥8 x2 ≤10 x1、x2≥0 6.2 求解下列整数规划问题 1、 min f=4x1+3x2+2x3 S.T. 2x1-5x2+3x3≤4 4x1+x2+3x3≥3 x2+x3≥1 x1、x2、x3=0或1 解：最优解（0，0，1），最优值：2 2、 min f=2x1+5x2+3x3+4x3 S.T. -4x1+x2+x3+x4≥2 -2x1+4x2+2x2+4x2≥4 x1+x2-x2+x2≥3 x1、x2、x3、x3=0或1 解： 此模型没有可行解。 3、max Z=2x1+3x2+5x3+6x4 S.T. 5x1+3x2+3x3+x4≤30 2x1+5x2-x2+3x2≤20 -x1+3x2+5x2+3x2≤40 3x1-x2+3x2+5x2≤25 x1、x2、x3、x3=正整数 解：最优解（0，3，4，3），最优值：47 4、 min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+ 5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19 约束条件 x1 + x2+x3≤30 x4+ x5＋ x6-10 x16≤0 x7+ x8＋ x9-20 x17≤0 x10+ x11＋ x12-30 x18≤0 x13+ x14＋ x15-40 x19≤0 x1 + x4+ x7+x10+ x13＝30 x2 + x5+ x8+x11+ x14＝20 x3 + x6+ x9+x12+ x15＝20 xi为非负数（i=1,2…..8） xi为非负整数（i=9,10…..15） xi为为0－1变量（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个店的费用情况如下表： 店名 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 费用(万元) 1.2 1.5 1.7 2.1 3.3 1.2 2.8 2.5 1.9 3.0 2.4 2.4 2.1 1.6 公司办公会决定选择原则如下： （1）B5、B3和B7只能选择一个。 （2）选择了B1或B14就不能选B6。 （3）B2、B6、B1、B12，最多只能选两个。 （4）B5、B7、B10、B8，最少要选两个。 问应选择哪几个点，使总的建店费用为最低？ 解：数学模型： min f＝1.2 x1+1.5 x2+1.7 x3+2.1 x4+3.3 x5+1.2 x6+2.8 x7+2.5 x8+1.9 x9+3 x10+2.4 x11+2.4 x12+2.1 x13+1.6 x14 S.T. x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14=8 x3+ x5-2 x7=2 x1+ x6=1 x6+ x14=1 x1+x2+x6+x12≤2 x5+x7+x8+x10≥2 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、C、D），请按以下要求求解指派问题。 1、每人做各项工作所消耗的时间如下表所示，问应如何分配工作，才能使总的消耗时间为最少？ 每人完成各项工作的所需时间 小时 是 工作 否 分 工人 配 工作A 工作B 工作C 工作D 甲 18 16 - 19 乙 - 20 16 20 丙 19 18 17 21 丁 12 15 20 - 2、每人做各项工作所