哈工大运筹学课件整数规划.ppt

哈工大运筹学课件整数规划
LINDO软件及EXCEL求解：
LINDO程序软件：同求解LP模型时的输入及编辑修改过程，在使用‘ GO ’命令求解之前，对整数变量给予说明。命令格式：GIN <变量名>。
EXCEL求解：
200下步；否则继续分枝。
④ 剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。 (a) 对可行解，保留边界值最小的一枝zmin，其余全剪掉； (b) >zmin分枝，剪掉； (c) 能判断出为无可行解的分枝，剪掉； (d) 非上述情况，继续分枝。
2006/08
16
--第4章 整数规划--
例：求解下述 0-1规划问题：
Max z=8x1+2x2-4x3-7x4-5x5 st. 3x1+3x2+x3+2x4+3x5 4 5x1+3x2- 2x3 - x4+ x5 4 xj=0或1 (j=1,2,3,4,5)
1) 目标函数极小化:
min z=-8x1-2x2+4x3+7x4+5x5
① 化标准形：
2) 约束条件：
-3x1-3x2-x3-2x4-3x5 -4
-5x1-3x2+ 2x3 + x4- x5 -4
xj=0或1 (j=1,2,3,4,5)
2006/08
17
--第4章 整数规划--
3) 使目标函数系数皆为正：
令 x1=1-x1 ，x2=1-x2
min z=-8+8 x1 -2+2 x2 +4x3+7x4+5x5
st. -3+3 x1 -3+3 x2 -x3-2x4-3x5 -4
-5+5 x1 -3+3 x2 + 2x3 + x4- x5 -4
x1 , x2 ,xj=0或1 (j=3,4,5)
4) 变量按顺序排列：
min z= 2 x2 +4x3 +5x5 +7x4+8 x1 -10
st. 3 x2 -x3 -3x5 -2x4 +3 x1 2
3 x2 + 2x3 - x5 + x4+5 x1 4
x1 , x2 ,xj=0或1 (j=3,4,5)
2006/08
18
--第4章 整数规划--
求解图示：
1
2
3
4
5
6
7
8
9
10
11
z=-10
z =-8
z=-4
z=-6
z=-5
z=-1
z=1
z=-5
z=-3
z=-6
x2=1
x2=0
x3=1
x3=0
x3=1
x3=1
x5=1
x5=0
x5=1
x5=0
z=-3
√
×
×
×
×
×
2006/08
19
--第4章 整数规划--
分配问题及匈牙利算法(Assignment Problem)
一、问题的提出和数学模型
例：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。
问：如何分配，能使所需的总时间最少？
甲 乙 丙 丁
工作
人
译英文
译日文
译德文
译俄文
2 10 9 7
15 4 14 8
13 14 16 11
4 15 13 9
2006/08
20
--第4章 整数规划--
建立模型：
设 xij=
1
0
译英文：
x11+ x12 + x13 + x14 =1
译日文：
x21+ x22 + x23 + x24 =1
译德文：
x31+ x32 + x33 + x34 =1
译俄文：
x41+ x42 + x43 + x44 =1
甲：
x11+ x21 + x31 + x41 =1
乙：
x12+ x22 + x32 + x42 =1
丙：
x13+ x23 + x33 + x43 =1
丁：
x14+ x24 + x34 + x44 =1
xij =0或1 (i=1,2,3,4; j=1,2,3,4)
Min z= aijxij (aij---效率)
i=1j=1
4 4
若第i项工作交与第j个人完成
若第i项工作不交与第j个人完成
2006/08
21
--第4章 整数规划--
分配问题一般数学模型结构：