文档介绍：整数规划数学模型 Mathematical Model of IP
纯整数规划的求解 Solving Pure Integer Programming
0-1规划的求解 Solving Binary Integer Programming
Chapter 6 整数规划
Integer Programming
运筹学
Operations Research
很多实际规划问题都属于整数规划问题
1. 变量是人数、机器设备台数或产品件数等都要求是整数;
2. 对某一个项目要不要投资的决策问题,可选用一个逻辑变量 x,当x=1表示投资,x=0表示不投资;
3. 人员的合理安排问题,当变量xij=1表示安排第i人去做 j工作,xij=0表示不安排第i人去做 j工作。逻辑变量也是只允许取整数值的一类变量。
整数规划的数学模型
Mathematical Model of IP
整数线性规划数学模型的一般形式:
要求一部分或全部决策变量取整数值
不考虑整数条件,由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。
整数线性规划问题的分类
一个规划问题中要求部分或全部决策变量是整数,则这个规划称为整数规划(IP)。当要求全部变量取整数值的,称为纯整数规划(PIP);只要求一部分变量取整数值的,称为混合整数规划(MIP) .决策变量全部取0或1的规划称为0—1规划。如果模型是线性的,称为整数线性规划。本章只讨论整数线性规划。
整数规划数学模型
Mathematical Model of IP
【】投资项目选取问题
某单位拟利用闲置资金15 万元进行对外投资,现有 5个投资项目可供选择,所需资金及投资回报收益期望值为
项目
所需资金(万元)
收益期望值(万元)
A
B
C
D
E
6
4
2
4
5
10
8
7
6
9
A,B,C,D,E 之间的关系是:
① A、C、E 三项中需且只能选一项;
② B、D 两项中需且只能选一项;
③选 C 必须先选 D 。
问题:如何选择投资决策,使总投资期望值最大?
整数规划的数学模型
Mathematical Model of IP
【解】
用 xj 分别表示 A ,B ,C ,D ,E 的被选情况,则
于是投资总收益期望值:
约束条件:
①资金总额限制:
② A,C,E 选且只选一项:
整数规划的数学模型
Mathematical Model of IP
③ B,D 选且只选一项:
④选 C 必须先选 D :
于是数学模型为以下 0-1 规划:
Þ
3
1
x
=
,
4
1
x
=
Þ
,
4
1
0
x
=
或
3
0
x
=
或
整数规划的数学模型
Mathematical Model of IP
【 】某人有一背包可以装10公斤重、。他准备用来装甲、乙两种物品,每件物品的重量、体积和价值如表6-1所示。问两种物品各装多少件,所装物品的总价值最大?
表6-1
【解】设甲、乙两种物品各装x1、x2件,则数学模型为:
()
整数规划的数学模型
Mathematical Model of IP
物品
重量
(公斤/每件)
体积
(m3/每件)
价值
(元/每件)
甲
乙
4
3
【 】,假设此人还有一只旅行箱,最大载重量为12公斤,。背包和旅行箱只能选择其一,建立下列几种情形的数学模型,使所装物品价值最大。
(1) 所装物品不变;
(2) 如果选择旅行箱,则只能装载丙和丁两种物品,价值分别是4和3,载重量和体积的约束为
【解】此问题可以建立两个整数规划模型,但用一个模型描述
更简单。引入0-1变量 yi,令
i=1,2 分别是采用背包及旅行箱装载。
整数规划的数学模型
Mathematical Model of IP
由于所装物品
不变, 式()约束
左边不变, 整数规
划数学模型为
(2) 由于不同载体
所装物品不一样,数学模型为
整数规划的数学模型
Mathematical Model of IP