[管理学]《运筹学》第五章 整数规划1.pptVIP

例2、某公司在城市的东、西、南三区建立门市部。 拟议中有7个位置（地点）Ai（i=1，2，…，7） 可供选择。公司规定： 在东区，由 A1，A2，A3 三个点中至多选两个； 在南区，由 A4，A5 两个点中至少选一个； 在西区，由 A6，A7 两个点中至少选一个。 如果选用 Ai 点，设备投资估计为 bi 元，每年 可获利润估计为 ci 元，但投资总额不能超过 B 元。 问公司选择哪几个点可使年总利润最大？ 设：工序 B 有两种方式完成 方式（1）的工时约束: 0.3X1 + 0.5X2 ≤ 150 方式（2）的工时约束: 0.2X1 + 0.4X2 ≤ 120 问题是完成工序 B 只能从两种方式中任选一种， 如何将这两个互斥的约束条件统一在一个线性规划 模型中呢？ 二、分枝定界法 例题 例2:用分枝定界法求解整数规划问题 例3、用分枝定界法求解整数规划问题（单纯形法） 练习：用分枝定界法求解整数规划问题 （单纯形法） 练习：用隐枚举法求解0—1规划问题 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 先求（LP1）,如图所示。此时在B 点取得最优解。 x1＝1, x2 =3, Z(1)＝－16 找到整数解，问题已探明，此枝停止计算。 1 1 同理求（LP2） ,如图所示。 在C 点取得最优解。 即x1＝2, x2 =10/3, 　Z(2) ＝－56/3≈－18.7 B A C ∵Ｚ(2) Z(１)＝－16 ∴原问题有比（－16）更小的最优解，但 x2 不是整数，故利用 3 ≥ x2 ≥4 加入条件。 加入条件： x2≤3, 　x2≥4 有下式： 只要求出（LP3）和（LP4）的最优解即可。 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C 先求（LP3）,如图所示。此时在D 点取得最优解。 即 x1＝12/5≈2.4, x2 =3, Z(3)＝-87/5 ≈-17.4 Z(1)≈-16 但x1＝12/5不是整数，可 继续分枝。即 3≤x1≤2。 D 求（LP4），如图所示。 无可行解，不再分枝。 在（LP3）的基础上继续分枝。加入条件3≤x1≤2有下式： 只要求出（LP5）和（LP6）的最优解即可。 x1 x2 ⑴ ⑵ 3 3 (18/11,40/11) ⑶ 1 1 B A C D 先求（LP5）,如图所示。此时在E 点取得最优解。 即 x1＝2, x2 =3, Z(5)＝－17 找到整数解，问题已探明，此枝停止计算。 E 求（LP6），如图所示。此时在F点取得最优解。 x1＝3, x2 =2.5, Z(6)＝－31/2≈－15.5 Z(5) F 如对 Z(6) 继续分解，其最小值也不会低于－15.5 ，问题探明,剪枝。 至此，原问题（IP）的最优解为： x1=2， x2 =3, Z* = Z(5) ＝－17 以上的求解过程可以用一个树形图表示如右： LP1 x1=1, x2=3 Z(1) ＝－16 LP x1=18/11, x2=40/11 Z(0) ＝－19.8 LP2 x1=2, x2=10/3 Z(2) ＝－18.5 LP3 x1=12/5, x2=3 Z(3) ＝－17.4 LP4 无可 行解 LP5 x1=2, x2=3 Z(5) ＝－17 LP6 x1=3, x2=5/2 Z(6) ＝－15.5 x1≤1 x1≥2 x2≤3 x2≥4 x1≤2 x1≥3 ＃ ＃ ＃ ＃ LP1 x1=1, x2=7/3 Z(1) ＝10/3 LP x1=3/2, x2=10/3 Z(0) ＝29/6 LP2 x1=2, x2=23/9 Z(2) ＝41/9 x1≤1 x1≥2 LP5 x1=1, x2=2 Z(5) ＝3 LP6 无可 行解 ＃ ＃ x2≤2 x2≥3 LP3 x1=33/14, x2=2 Z(3) ＝61/14 LP4 无可 行解 x2≤2 x2≥3 ＃ LP7 x1=2, x2=2 Z(7) ＝4 LP8 x1=3, x2=1 Z(8) ＝4 x1≤2 x1≥3 ＃ ＃ LP1 x1=1, x2=7/3 Z(1) ＝10/3 LP x1=2/3, x2=10/3 Z(0) ＝29/6 LP2 x1=2, x2=23/9 Z(2) ＝41/9 LP3 x1=33/14, x2=2 Z(3) ＝61/14 LP4 无可 行解 LP7 x1=2, x2=2 Z(7) ＝4 LP8 x1=3, x2=1