整数规划与01规划共25页文档

比如下面的例子：
例1.某厂拟用集装箱托运甲乙两种货物，每箱 的体积、重量、可获利润以及托运所受限制如 下表：
货物 体积（每 箱M3) 5 甲 4 乙 托运限制 24 重量(每箱 50kg) 2 5 13 利润(每 箱百元) 20 10
问两种货物各托运多少箱,可使利润最大?
为了满足整数解得要求，初看，似乎只要把已得到的分 数或小数， “舍入化整”就可以了。但是，这常常是不行的， 因为化整后，不一定是可行解，或者虽是可行解，但不一定 是最优解。
整数规划
§1 整数规划及其解法 §2 0-1型整数规划 §3 指派问题
整数规划
1、理解整数规划、0-1规划和指派问题的数学 模型 2、理解整数规划模型的类型 3、理解整数规划的求解方法:分支定界法和割 平面法、0-1规划的隐枚举法和指派问题的 匈牙利法的思想和步骤
求解方法
1、分支定界法 2、割平面法

a x
i 1 ij
n
j
bi yi M (i 1,, m)
y1 + y2 + „ + ym = m –1， yi = 0 或 1 (i=1，„，m)
3、关于固定费用问题
• 在讨论线性规划时，有些问题是要求使 成本最少的方案，那时总设固定成本为 常数，并在线性规划的模型中不必明显 列出。但有些固定成本的问题不能用一 般线性规划来描述，但可改为混合整数 规划来解决。
aj
值最大？
解：设 x j 为决策变量，且 x j 满足如下限制
xj {
1，携带第j件物品 0，不携带第j件物品
，j 1,2, n
则问题的数学模型为
x c j x j max
j 1
n

ax V : m z = 3x1 + 2x2 2x1 + 3x2 ≤14 x1 + 1 x2 ≤ 4 1 2 2 (L1,1) s.t x2 ≤ 2 x1 ≤ 3 x1, x2 ≥ 0
x2
X (2)
X
(1,1)
X (0)
因而在3<x1<4 由于 3.5 = 3, 3.5 = 4 ，因而在 之间已不可能有ILP的最优解， 的最优解， 之间已不可能有 的最优解 这样实际上把LP 故此部分可行域可删除 ,这样实际上把 这样实际上把 问题L 问题 1化为在剩余两块可行域上的两个 LP问题 1,1和L1,2 ，即 问题L 问题 o
因而在2<x2<3 x2 由于 2 1 = 2, 2 1 = 3，因而在 2 2
L2 X (2) 之间已不可能有ILP的最优解， 的最优解， 之间已不可能有 的最优解 3 X (0) 这样实际上把LP 2 这样实际上把 故此部分可行域可删除 ,这样实际上把 X (1) 问题L 问题 0化为在剩余两块可行域上的两个 L 1 LP问题 1和L2 ，即 问题L 问题 o
X (1) X (1,2) 34
ax V : m z = 3x1 + 2x2 2x1 + 3x2 ≤14 x1 + 1 x2 ≤ 4 1 2 2 (L1,2 ) s.t x2 ≤ 2 x1 ≥ 4 x1, x2 ≥ 0
• • • • 1、 引入0-1变量的实际问题 引入0 相互排斥的计划。 ①相互排斥的计划。 ②相互排斥的约束条件 。 ③关于固定费用的问题 。
相互排斥的计划。 ①相互排斥的计划。
某公司拟在市东、 南三区建立门市部。 个位置（ 例 ： 某公司拟在市东 、 西、 南三区建立门市部 。 拟议中有 7 个位置（ 点） Ai (i = 1,2,⋯,7) 可供选择。规定 可供选择。 在东区：由 A1 , A2 , A3 三个点中至多选两个； 三个点中至多选两个； 在东区： 在西区： 两个点中至少选一个； 在西区：由 A4 , A5 两个点中至少选一个； 在南区： 两个点中至少选一个。 在南区：由 A6 , A7 两个点中至少选一个。 如选用 Ai 点，设备投资估计为 bi 元，每年可获利润估计为 ci 元，但投资总 问应选择哪几个点可使年利润为最大？ 额不能超过 B 元。问应选择哪几个点可使年利润为最大？

一、问题的提出
在现实生活中我们经常遇到一些决策变量需要取 整数才有实际意义的问题，例如产品数量、工人人 数、设备台数、股票手数等等，还会经常遇到由一 系列相关的“是或否”的选择组成的决策问题，决 策变量只能有两个取值0或1（0-1变量）比如在被选 方案中进行项目决策、投资决策和设施决策等。下 面我们看一个例子 。
二、基本思想：如果松弛问题有非整数最优解，则 构造一个线性约束，即割平面，增加到松弛问题 中，借此割掉包含此非整数最优解，但不含任何 整数可行解的一部分可行域。不断重复此过程， 直至松弛问题的最优解是整数解，此解恰好是原 整数规划问题的最优解。
三、基本性质： 1. 非整数最优解不满足割平面约束，从而保证算法的
35
x1, x2为整数
其中第四个约束称为整数规划问题的整数性约束。
二、数学模型的一般形式
n
max(min) z cj xj j 1
（P）
n
aij x j (, ) bi ,
i 1, 2,
,m
s.t.
j 1
x j 0, j 1, 2,
,n
(1) (2)
x
j全部或部分为整数，j
1,
2,
,n
(3)
其中（1）是m个线性约束，（2）是非负要求，（3）是整
数性约束，若去掉整数性约束，则(P)就成为一个线性规划
模型，称之为（P）的（线性）松弛问题，记作（R）。松
弛问题（R）是线性规划问题，可以用单纯性法很容易地求
出最优解。
三、解的特点和求解思想
➢ 整数规划与线性规划在模型上的唯一区别在于决策变量是否取整数。 当可行域有界时，整数规划问题可行解的个数有限。然而可行解个数 有可能会是天文数字，性能最高的计算机也不能胜任用简单枚举法求 解50个变量以上的整数规划问题。

表示小于bj的最大整数。构造两个约束条件: x j [bj ] x j [bj ] 1
将这两个约束条件，分别加入B问题，求两个后继规划问题B1和B2。不考虑整数条件 求解这两个后继问题。
定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最 优目标函数值最大者作为新的上界 。从已符合整数条件的各分支中，找出目标函
1
例1
2
例 2 背包问题
3
整数规划特点
(1)原线性规划有最优解，当自变量限制为整数后， 其整数规划解出现下述情况：
1. 原线性规划最优解全是整数，则整数规划最优解与线 性规划最优解一致。
2. 原线性规划最优解不全是整数，则整数规划最优解小 于原线性规划最优解（max）或整数规划最优解大于 原线性规划最优解（min）。
5
整数பைடு நூலகம்划-分枝定界法
对有约束条件的最优化问题的可行解空间恰当 地进行系统搜索，这就是分枝与定界内容。通 常，把全部可行解空间反复地分割为越来越小 的子集，称为分枝；并且对每个子集内的解集 计算一个目标下界（对于最小值问题），这称 为定界。在每次分枝后，凡是界限不优于已知 可行解集目标值的那些子集不再进一步分枝， 这样，许多子集可不予考虑，这称剪枝。这就 是分枝定界法的主要思路。
初值选取----蒙特卡洛法
16
MATALB求解命令
%[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id)
%整数线性规划分支定界法，可求解全整数或混合整数线性规划。 % y=min f'*x s.t. G*x<=h Geq*x=heq x为全整数或混合整数列向量。
%[x,y]=IntLp(f,G,h) %[x,y]=IntLp(f,G,h,Geq,heq) %[x,y]=IntLp(f,G,h,Geq,heq,lb,ub) %[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x) %[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id) %[x,y]=IntLp(f,G,h,Geq,heq,lb,ub,x,id,options) % x:最优解列向量；y:目标函数最小值；f:目标函数系数列向量 % G:约束不等式条件系数矩阵；h:约束不等式条件右端列向量 % Geq:约束等式条件系数矩阵；heq：约束登时条件右端列向量 % lb:自变量下界列向量（default:-inf） % ub:自变量上界列向量（default:inf） % x:迭代初值列向量 % id:整数变量指标列向量，1-整数，0-实数（default:1） % options的设置请参见optimset或linprog

蝶泳 仰泳 蛙泳 自由泳
甲 1’06”8 1’15”6 1’27” 58”6
乙 57”2 1’06” 1’06”4 53”
讨论 丁蛙泳c43 =69.675.2，戊自由泳c54=62.4
57.5, 方案是否调整？ 敏感性分析？ IP规划一般没有与LP规划相类似的理论，LINDO 输出的敏感性分析结果通常是没有意义的。 c43, c54 的新数据重新输入模型，用LINDO求解
若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0
目标 函数
约束 条件
4
Min
Z
c
j 1 i 1
4
5
ij
x ij
每人最多入选泳姿之一
每种泳姿有且只有1人

x ij 1, i 1, 5

5
x ij 1, j 1, 4
j 1
i 1
模型求解
输入LINDO求解
0-1规划模型
课号 课名 微积分 线性代数 最优化方法 数据结构 应用统计 计算机模拟 计算机编程 预测理论 数学实验 先修课要求
约束条件
先修课程要求 x3=1必有x1 = x2 =1
x 3 x1 , x 3 x 2
2 x 3 x1 x 2 0
x4 x7
应用统计 微积分；线性代数
• 若生产某类汽车，则至少生产80辆，求生产计划。 方法3：化为非线性规划
x1=0 或 80
x2=0 或 80 x3=0 或 80
x 1 ( x 1 80 ) 0
x 2 ( x 2 80 ) 0
x 3 ( x 3 80 ) 0
非线性规划（Non- Linear Programming，简记NLP） NLP 虽 然 可 用 现 成 的 数 学 软 件 求 解 ( 如 LINGO, MATLAB)，但是其结果常依赖于初值的选择。 实践表明，本例仅当初值非常接近上面方法算出 的最优解时，才能得到正确的结果。

s.t.
max=6*x1+7*x2+3 *x3+9*x4;
? 2 x1 ? 3 x2 ? x3 ? 4 x 4 ? 5
? ?
xi?ຫໍສະໝຸດ 0,1 ?i?1, 2,3,
4?
2*x1+3*x2+x3+4* x4<=5;
@bin(x1);
@bin(x2);
@bin(x3);
@bin(x4);
例1投（资投项资问目题模）型华：美公司有 5个项目被列入投资计
? x11 ? x12 ? x13 ? x14 ? 1
? ?
?
x21 x31
? ?
x22 x32
? ?
x23 x33
? ?
x24 x34
?1 ?1
? x41 ? x42 ? x43 ? x44 ? 1
?
s.t
? ?
x11 x12
? ?
x21 x22
? ?
x31 x32
? ?
x41 ? 1 x42 ? 1
例1：一个旅行者要到某地作两周的带包旅行 ,装背包时,他 发现除了已装的必需物件外,他还能再装5公斤重的东西.他 打算从下列4种东西中选取,使增加的重量不超过5公斤又 能使使用价值最大.这4种东西的重量和使用价值( 这里用打 分数的办法表示价值) 如下表所示,问旅行者应该选取哪些 物件为好？
解：建立模型为 max Z=6x 1 ? 7 x 2 ? 3 x3 ? 9 x4
2.什么时候采用 0-1 整数规划法？
正如计算机只懂得 0,1 两个数， 1代表是， 0 代表否。同样的，在 0-1 整数规划中的 0和1并 不是真真意义上的数，而是一个衡量事件是否 发生的标准。一般来说，我们在从多个事物中 选出其中一部分，在一定的条件下求解最优情 况时可以采用 0-1 整数规划法。

Mathematical modeling
7
例2 今有一台机器将一周生产的两种型号的冷饮杯 存储在150立方米的储藏室 里,并同时进行出售.已 知这台机器能在6小时内生产一百箱Ⅰ号杯,5小时内 生产一百箱Ⅱ号杯,生产以百箱为单位计算,预计每 周生产60小时.如果Ⅰ号杯每百箱占体积10立方米, 每百箱可获利润500元,每周售出数量不会超过800 箱;Ⅱ号杯每百箱占体积20立方米, 每百箱可获利润 450元,每周售出数量不受限制.为保证总收益为最大 ,每周应安排生产Ⅰ、Ⅱ号杯各多少百箱？
5 x31 5 x32 7 x33 9 x 34 8 x 35 6 x 41 7 x 42 5 x 43 7 x 44 6 x 45
7 x51 4 x52 6 x53 2 x54 8 x55
5
x ij 1
j 1, 2 ,
,5
i1
5
x i j 1 i 1 , 2 , , 5
Mathematical modeling
2
整数规划的分类
变量全限制为整数时，称纯（完全）整数规划。 变量部分限制为整数的，称混合整数规划。 变量只能取0或1时，称之为0-1整数规划。
Mathematical modeling
3
·整数规划模型的建立 ·整数规划模型的求解
·完全枚举法 ·分支定界法 ·割平面法
j1
x ij
0或
1
i, j 1, 2 ,
,5
Mathematical modeling
24
Mathematical modeling
感谢亲观看此幻灯片，此课件部分内容来源于网络， 如有侵权请及时联系我们删除，谢谢配合！
Mathematical modeling

混合整数规划
总结词
混合整数规划是同时包含连续变量和整数变量的规划问题。
详细描述
混合整数规划问题在数学上表示为在一定的约束条件下，求一组连续变量和整数变量的函数的最优解 。这类问题在现实生活中应用广泛，如生产计划、物流优化、金融投资等。求解混合整数规划问题需 要同时考虑连续变量和整数变量的特性，通常需要使用特殊的算法进行求解。
通过不断分割解空间并确 定可行解的范围，逐步逼 近最优解。
割平面法
通过添加割平面方程来不 断缩小解空间，直到找到 最优解。
迭代优化法
通过迭代优化算法不断逼 近最优解，适用于大规模 整数规划问题。
02 整数规划问题建模
线性整数规划
总结词
线性整数规划是整数规划的一种，其目标函数和约束条件都是线性函数，且决 策变量都是整数。
装箱问题
总结词
装箱问题是一个经典的整数规划问题， 旨在确定如何将一组物品装入有限容 量的容器中，以最小化装载成本。
详细描述
装箱问题需要考虑物品的尺寸、重量、价值 等多个因素，通过整数规划的方法，可以确 定最佳的装箱方案，包括每个容器的装载物 品和数量等，从而实现装载成本最小化。
THANKS FOR WATCHING
遗传算法
要点一
总结词
一种基于生物进化原理的优化算法
要点二
详细描述
遗传算法是一种模拟生物进化过程的优化算法，通过选择 、交叉和变异等操作来逼近最优解。在整数规划问题中， 遗传算法将决策变量编码为染色体，通过不断进化染色体 群体来寻找满足整数约束的解。遗传算法具有全局搜索能 力强、能够处理多约束和离散变量等优点，因此在整数规 划问题中得到了广泛应用。
整数规划ppt课件
contents

运筹学课件第四节0-1型整数 规划
目录
CONTENTS
• 0-1型整数规划概述 • 0-1型整数规划的数学模型 • 0-1型整数规划的求解算法 • 0-1型整数规划的案例分析 • 0-1型整数规划的软件实现
01 0-1型整数规划概述
CHAPTER
定义与特点
定义
0-1型整数规划是一种特殊的整数规 划，其中决策变量只能取0或1。
解决方案通常采用动态规划或混合整数线性规 划方法，通过迭代和优化算法来找到最优解。
05 0-1型整数规划的软件实现
CHAPTER
Excel求解工具
适用范围
适用于简单的0-1型整数规划问题。
优点
操作简单，易学易用，适合初学者。
使用方法
利用Excel的Solver插件，设置目标函数、 约束条件和决策变量，进行求解。
其他约束
除了资源和需求约束外，还可能 存在其他类型的约束，如数量约 束、时间约束等，这些约束条件 都对决策变量的取值范围进行了 限制。
决策变量
离散变量 0-1型整数规划中的决策变量通常 是离散的，只能取0或1两个值。 这些决策变量代表了不同的策略 或选择。
最优解 最优解是指在所有可行解中使目 标函数达到最优值的决策变量的 取值组合。
缺点
对于大规模问题求解能力有限，可能存在精 度问题。
Python求解库
适用范围
适用于各种规模的0-1型整数规 划问题。
使用方法
利用Python的优化库，如PuLP 或CVXPY，编写目标函数和约束 条件，进行求解。
优点
功能强大，可处理大规模问题 ，精度高。
缺点
需要一定的编程基础，学习成 本较高。
MATLAB求解工具