算例
max 3x1 5x2 4x3
2x1 3x2 1500
s.t.32xx12
4x3 2x2

800 5x3

2000

x1
,
x2
,
x3

0,
x1 , x3为整数
max 3 x1+5 x2+4 x3 subject to 2 x1+3 x2<=1500 2 x2+4 x3<=800 3 x1+2 x2 +5 x3<=2000 end gin x1 gin x3
注解
该问题本质上是个整数规划问题， 放松的线性规划的最优解是个整数 解，所以两规划等价。
定义整数变量用函数@gin(x1)…… @gin(x7); 0-1整数变量为@bin(x1)
应急选址问题
某城市要在市区设置k个应急服务中心, 经过初步筛选确定了m个备选地，现已 知共有n个居民小区，各小区到个备选地 的距离为 d ij , i 1,2,..., n, j 1,2,..., m,为了使 得各小区能及时得到应急服务，要求各 小区到最近的服务中心的距离尽可能的 短，试给出中心选址方案。
问题分析
为了便于说明问题引入间接变量，第i 小区是否由第j个中心服务
yij 0,1, i 1,2,..., n, j 1,2,..., m,
以及最远的距离 z,
约束条件
小区服务约束
yij x j , i 1,2,..., n, j 1,2,..., m,
m
yij 1, i 1,2,..., n,
方案 确定每天工作的人数，由于连续休息2天，当确定每 个人开始休息的时间就等于知道工作的时间，因而确定 每天开始休息的人数就知道每天开始工作的人数，从而 求出每天工作的人数。
变量 每天开始休息的人数 xi ,i 1,2,...,7 约束条件
1.每人休息时间2天，自然满足。
2. 每天工作人数不低于需求量，i 第 天工作的人数就是 从第i 2 天往前数 5 天内开始工作的人数，所以有约束：
x2 x3 x4 x5 x6 12 x3 x4 x5 x6 x7 15 x4 x5 x6 x7 x1 12 x5 x6 x7 x1 x2 14 x6 x7 x1 x2 x3 16 x7 x1 x2 x3 x4 18 x1 x2 x3 x4 x5 19
问题分析
该问题与传统的选址问题的主要区别在 于其目标不再是要求费用最小，而是要 求最长距离最短。也就是离服务中心距 离最远的小区离最近的服务中心距离最 小。 变量：当中心的位置确定下来后，各小 区对应的最近中心也就确定，所以真正 的变量也就是小区的位置。设
x j 0,1, j 1,2,..., m,
j0
n
xij 1; j 1,2,...n
i0
避免出现断裂
每个点给个位势 前点比后点大
除了初始点外要求
目标—总费用最小
nn
cij xij
i0 j0
nn
min
cij xij
i0 j0
n
xij 1; i 1,2,..., n j0
p
算法
分支定界算法 割平面算法
计算软件
整数变量定义 LinDo
一般整数变量:GIN <Variable> 0-1整数变量: INT <Variable>
LinGo
一般整数变量: @GIN( variable_name); 0-1整数变量：@BIN( variable_name);
算例
3
1 xij ;i 8,2...,17 j 1
17
3
pi (1 xij )
i 8
j 1
模型
17
3
min pi (1 xij )
i8
j 1
17
ci xij rj ; j 1,2,3
i 1
3
xij 1;i 1,2...,7
j 1
案例
有一旅行团从 v0 出发要遍游城市 v1, v2 ,..., vn，已知从vi 到v j的旅费 为 cij，问应如何安排行程使总费 用最小？
模型
变量—是否从i第个城市到第j个城市
约束
xij 1,0;
每个城市只能到达一次、离开一次
n
xij 1; i 1,2,...n
3.变量非负约束：
xi 0,i 1,2,...,7
目标函数：总费用最小，总费用与使用的总
人数成正比。由于每个人必然在且仅在某一
天开始休息，所以总人数等于
7
xi
i 1
模型
7
min 200 xi i 1
x2 x3 x4 x5 x6 12

x3

x4

x5
j 1
问题分析
最远距离约束
d ij yij z, i 1,2,..., n, j 1,2,.., m
中心个数约束
m
xj k,
j1
目标函数：最远距离 z 最小
模型
min z

y
ij

x j ,i
1,2,...,n,
j
1,2,...,m,
m

yij
1,i 1,2,...,n,
应用案例分析
旅行商问题（TSP） 人力资源分配问题 应急设施选址问题
1 2
3
4 5
1 2
3 4 5
1
23
5
23
45
1 3 4 5
23
1
3
3
5
人力资源分配问题
某个中型百货商场对售货人员（周工 资200元）的需求经统计如下表
星期 一 二 三 四 五 六 七
人数 12 15 12 14 16 18 19
旅行背包 容量一定的背包里装尽可能的多的物品
实例
某人出国留学打点行李，现有三个旅行包，容 积大小分别为1000毫升、1500毫升和2000毫 升，根据需要列出需带物品清单，其中一些物 品是必带物品共有7件，其体积大小分别为 400、300、150、250、450、760、190、 （单位毫升）。尚有10件可带可不带物品，如 果不带将在目的地购买，通过网络查询可以得 知其在目的地的价格（单位美元）。这些物品 的容量及价格分别见下表，试给出一个合理的 安排方案把物品放在三个旅行包里。
为了保证销售人员充分休息，销售人 员每周工作5天，休息2天。问应如何 安排销售人员的工作时间，使得所配 售货人员的总费用最小？
模型假设
每天工作8小时，不考虑夜班的情况； 每个人的休息时间为连续的两天时
间； 每天安排的人员数不得低于需求量，
但可以超过需求量
问题分析
因素 不可变因素：需求量、休息时间、单位费用； 可变因素：安排的人数、每人工作的时间、总费用；
整数规划
整数规划问题与模型 整数规划算法 计算软件 应用案例
整数规划问题
实例 特点 模型分类
应用案例
旅游售货员问题 背包问题
旅游售货员问题
背景 案例 模型
背景
旅游线路安排 预定景点走且只走一次 路上时间最短
配送线路—货郎担问题 送货地到达一次 总路程最短
s.t.dji1j yij z,i 1,2,...,n, j 1,2,...,m,
m


j 1
x
j

k

x j , yij 0,1,i 1,2,...,n, j 1,2,...,m, z 0

x6

x7
15

x
4

x5

x6

x7

x1

12
s.t.
x1 x1
x2 x2Fra bibliotek x5 x3

x6 x6

x7 x7
14 16

x1

x2

x3

x4

x7
18
x1 x2 x3 x4 x5 19
xi 0,i 1,2,...,7
一般整数规划模型
min c x
Ax b
s.t
.
x

0,
x为 整 数
0-1整数规划模型
min c x
Ax b
s.t
.
x
i

0,1; i
1,2,..., n
混合整数规划模型
min c x
Ax b
s.t.x 0

xi为整数
,
i
1,2,...,
s.t. n xij 1; j 1,2,..., n i0 ui u j nxij n 1;1 i j n xij 1,0, i 1,2,..., n, j 1,2,..., n
背包问题
背景 案例 模型
背景
邮递包裹 把形状可变的包裹用尽量少的车辆运走
3
xij 1;i 8,2...,17
j 1
xij 1,0; i 1,2...,17, j 1,2,3
特征—变量整数性要求 来源
问题本身的要求 引入的逻辑变量的需要
性质—可行域是离散集合
线性整数规划模型
一般整数规划模型 0-1整数规划模型 混合整数规划模型