运筹学整数规划

令
1 当Ai点被选用 xi 0 当Ai点未被选用
i=1, …,7
max Z
ci xi
i 1
7
s.t
7 bi xi B i 1 x1 x2 x3 2 x4 x5 1 x x 1 7 6 xi 0 or 1
其中
1 y 0
当采用船运方式
当采用车运方式
一般情况下, m个约束条件中选择q个约束条件, 则可变成为:
ai1x1+ai2x2+…+ainxnbi+yiM, i=1,2,…,m y1+y2+…+ym=m-q 其中yi是0, 1变量，且只有一个取0。 • 0-1整数规划问题的解法 若有n个决策变量, 则可以产生2n个可能变量的组合, 故完全枚 举是不可能的. 求解0-1整数规划问题的解法均是部分枚举法或称 为隐枚举法(Implicit enumeration) 基本思想是: 在2n个可能的变量组合中, 往往只有一部分是可行 解. 只要发现某个变量组合不满足其中的某一约束条件时, 就不必 要检验其它的约束条件是否可行。 若发现一个可行解, 则根据它 的目标函数值可以产生一个过滤条件(Filtering constraint), 对于目 标函数值比它差的的变量组合就不必再去检验它的可行性（类似 分支定界法中的定界。实际上，隐枚举法是一种特殊的分支定界 法）。 在以后求解过程中, 每当发现比原来更好的可行解, 则依次 替代原来的过滤条件 (可减少运算次数, 较快地发现最优解)。
所以，最优解为（x1，x2，x3)T=(1,0,1)T, 最优值为8.
注： 当决策变量(x1, x2 , x3)按(0,0,0), (0,0,1), (0,1,0), (0,1,1),... 方式取值时, 为了减少计算次数, 通常将目标函数中的决策变量的 顺序按其系数的大小重新排序, 以使最优解能较早出现。对最大化 问题, 按从小到大的顺序排列；对极小化问题, 则相反。 例2：求解下述0-1整数规划问题
例1. 某工程公司拟从四个项目中选择若干项目，若令
xi
=
，第i个项目被选中； 1 i 1,2,3,4 0 ，第 i 个项目未被选中；
用xi的线性表达式表示下列要求： （1）从1，2，3项目中至少选2个： （2）项目2和4同时被选中或同时不被选中： ； ；
（1）x1+x2+x3 2
min z
c
j 1
10
j
xj
10 xj 5 j 1 x1 x8 1, x7 x8 1 s.t. x3 x5 1, x4 x5 1 x5 x6 x7 x8 2 x j 0, 1
第四节 0-1整数规划
•
问题的提出：
0-1整数规划是线性规划及整数规划的一种特殊形式。 模型结构和形式是线性规划，只是决策变量取0或1。 例1：投资场所的选定——相互排斥的计划
某公司拟在城市的东、西、南三区建立分公司，拟议中有七 个位置Ai（i=1, 2,…,7), 规定在东区A1,A2,A3个点中至多选二个; 在 西区A4,A5两点中至少选一个; 在南区A6,A7中至少选一个, 如选用Ai 点,设备投资估计为bi元, 每年可获利润估计为ci元, 但投资总额不能 超过B元, 问应选择那几个点可使年利润为最大?
解：求解过程见下表
(x1,x2,x3) （0,0,0） (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1)
Z值 0 5 -2 3 3 8 1 6
约束条件
过滤条件 Z0 Z5




Z8
（2）x2+x4 =2 或 x2+x4 =0
例2. 有A、B、C三种资源可用来生产甲、乙、丙三种产品。 资源量、单位产品利润和单位产品资源消耗量、各种产品 生产的固定费用如下表所示。现在要求制定一个生产计划， 使总收益最大，试建立数学模型。
单位产品 产品
资源消耗量 资源 A B C 单件利润 固定费用 甲 乙 丙 资源限量
例2: 相互排斥的约束条件
某厂拟采用集装箱托运甲乙两种货物，每箱的体积、重量、可获 利润以及托运(车运)所受限制如下表, 如采用船运, 其体积托运限制则为 45,问两种货物托运多少箱，可使获得利润为最大？
货物 甲 乙
体积 重量 每箱（m3） 每箱（吨） 4 5 2 1 6
利润 每箱（百元） 4 3
2 2 1 4 100
4 3 2 5 150
8 4 3 6 200
500 300 100
Leabharlann Baidu
1, 生产第i种产品 解：设xi 代表第 i 种产品的生产数量，yi= 0，不生产第i种产品
max z 4 x1 5 x2 6 x3 100 y1 150 y2 200 y3 2 x1 4 x2 8 x3 500 2 x 3 x 4 x 300 2 3 1 x1 2 x2 x3 100 x1 My1 s.t. x2 My2 x3 My3 xi 0, i 1, 2,3 yi 0,1, i 1, 2,3
以例子说明上述求解方法 例1: 求解下述0-1整数规划问题
max Z 3 x1 2 x2 5 x3 x1 2 x2 x3 2 x 4x x 4 1 2 3 s.t x1 x2 3 4 x x 6 3 2 x1 , x2 , x3 0 or 1
M是一个充分大的整数
例3. 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探 费用为最小。若10个井位的代号为s1，s2，…，s10，相应的钻探费用为c1， c2，…，c10，并且井位选择上要满足下列限制条件： (1) 或选择s1和s7，或选择钻探s8； (2) 选择了s3或s4就不能选s5，或反过来也一样(选了s5就不能选s3和s4)； (3) 在s5，s6，s7，s8中最多只能选两个。 试建立此问题的整数规划模型。
min Z 3 x1 7 x2 x3 x4 2 x1 x2 x3 x4 1 x x 6x 4x 8 1 2 3 4 s.t 5 x1 3 x2 x4 5 x1 , x2 , x3 , x4 0 or 1
解：重新排序为
min Z 7 x2 3x1 x4 x3 x2 2 x1 x4 x3 1 x x 4 x 6 x 8 2 1 4 3 s.t 3x2 5 x1 x4 5 x1 , x2 , x3 , x4 0 or 1
(x2,x1,x4 ,x3) （0,0,0,0） (0,0,0,1) (0,0,1,0) (0,0,1,1) (0,1,0,0) (0,1,0,1) (0,1,1,0) (0,1,1,1) (1,0,0,0) (1,0,0,1) (1,0,1,0) (1,0,1,1) (1,1,0,0) (1,1,0,1) (1,1,1,0) (1,1,1,1)
托运限制 20
解: 设x1, x2分别表示甲乙两种货物的托运箱数, 则其整数规划数学模型为
max Z 4 x1 3 x2
4 x1 5 x2 20 yM 4 x 5 x 45 (1 y ) M 1 2 s.t 2 x1 x2 6 x , x 0 1 2 x1 , x2取整数
Z值 0 -1 1 0 3 2 4 3 7 6 8 7 10 9 11 10
约束条件
过滤条件



Z3
练习：求解下述整数规划问题
min Z 10 x1 5 x2 8 x3 4 x4 2 x5 3x1 2 x2 4 x3 x4 x5 4 s.t. 2 x1 x2 4 x3 x4 x5 5 x 0 or 1 j 1,2,,5 j