当前位置：文档之家 › 运筹学课件 第四节 01型整数规划

运筹学课件 第四节 01型整数规划

  • 格式：ppt
  • 大小：2.20 MB
  • 文档页数：32

下载文档原格式

  / 32

合集下载

运筹学-0-1规划指派问题PPT课件

运筹学-0-1规划指派问题PPT课件
在0-1规划问题中，遗传算法通过模拟生物进化过程中的基因突变、交叉 和选择等过程来寻找最优解。算法从一个初始种群出发，通过不断迭代 进化，最终找到最优解。
遗传算法的优点是能够处理大规模、复杂的优化问题，且具有较强的鲁 棒性和全局搜索能力。缺点是算法实现较为复杂，需要较高的计算资源 和时间，且在某些情况下可能会陷入局部最优解。
指派问题通常具有整数约束和 0-1约束，即每个工人只能被分 配一项任务，且每个任务只能 由一个工人完成。
指派问题的解通常具有最优子 结构和局部最优解的特性。
变量定义
• $x{ij}$：如果第i个工人被分配第j项任务，则$x{ij}=1$； 否则$x_{ij}=0$。
目标函数
• $min \sum{i=1}^{n} \sum{ j=1}^{n} c{ij} x{ij}$： 最小化总成本。
04
指派问题在0-1规划中的应用
指派问题的定义
• 指派问题是一种组合优化问题，旨在将一组任务分配给一组工 人，使得总成本最小化。每个工人只能完成一项任务，每项任 务只能由一个工人完成。目标是找到一种最优的分配方式，使 得总成本最低。
指派问题的特点
指派问题具有NP难解的特点， 即没有已知的多项式时间算法 来解决该问题。
04
总结词：整数规划
பைடு நூலகம்
案例三：旅行商问题
总结词：旅行商问题
总结词：图论
详细描述：旅行商问题是一个经典的组合优 化问题，涉及到寻找一条最短路径，使得一 个旅行商能够访问一系列城市并返回出发城 市，同时最小化总旅行距离。
详细描述：图论是研究图形和图形结构的数 学分支，提供了解决旅行商问题和其他优化 问题的理论基础。
在0-1规划问题中，分支定界法将问题分解为多个子问题，每个子问题对应一种指派 方案。算法通过不断排除不可能的解来缩小搜索范围，最终找到最优解。

运筹学--整数规划 ppt课件

运筹学--整数规划 ppt课件

三、投资问题
某公司在今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末
回收本利115%，但要求第一年投资最低金额为4万元，第 二、三、四年不限； 项目B：第三年初需要投资，到第五年未能回收本利128％， 但规定最低投资金额为3万元，最高金额为5万元； 项目 C：第二年初需要投资，到第五年未能回收本利140%， 但规定其投资额或为2万元或为4万元或为6万元或为8万元。 项目 D：五年内每年初可购买公债，于当年末归还，并加利 息6%，此项投资金额不限。
= 1.15x1A+ 1.06x2D； 第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A + x4D =
1.15x2A+ 1.06x3D； 第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D =
引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以 保证当 yi = 0 时，xi = 0 。
这样我们可建立如下的数学模型：
Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 -
200y3
s.t. 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300 x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 xj ≥ 0 yj 为0--1变量，i = 1,2,3
一、投资场所的选择
京成畜产品公司计划在市区的东、西、南、北四区建立销售
门市部，拟议中有10个位置 Aj ( j＝1，2，3，…，10)可供 选择，考虑到各地区居民的消费水平及居民居住密集度，规

运筹学第四章--整数规划和分配问题(新)aPPT课件

运筹学第四章--整数规划和分配问题(新)aPPT课件

-
1
整数线性规划的一般形式: n max(或min)z cj xj j 1
n
aij xj ( 或 ）bi (i 1,2,...m)
j 1
xj 0( j 1,2,...n),且部分或全部取整数
例1.求下述整数规划问题的最优解
max z 3x1 2x2
2x1 3x2 14 x1 0.5x2 4.5
先不考虑整数解的限制，用单纯形法求 解其松弛问题，如果求得的解恰好是整数解， 则得整数规划最优解，停止计算。否则，将 松弛问题分解为两个子问题（也称后继问 题），每个子问题都是在原松弛问题的基础 上增加一个变量取整数的约束条件，这样就 缩小了原来的可行域，然后用单纯形法求解， 直至得到最终结果。
-
21
-
23
例.用分枝定界法求下述数整规划问题的最优
maxz 3x1 2x2
2x1 3x2 14 x1 0.5x2 4.5 x1, x2 0,且均取整数值
-
24
-
25
-
26
-
27
-
28
-
29
第四节 割平面法 一、割平面法的基本思想
先不考虑整数条件，用单纯形法求解其 松弛问题，若得整数解，即得整数规划最优 解。否则，增加线性约束条件（称为割平面 方程），将原问题的可行域切割掉一部分， 被切割掉的都是非整数解，再用单纯形法求 解新的线性规划问题，依次进行下去，直到 使问题的最优解恰好在可行域的某个具有整 数坐标的顶点上得到。
0.5 + 0.4 x4 + 0.4 x5≥ 1
-
35
2. 借助单纯形表法
对求解整数规划问题的松弛问题（LP问题）得到
最优单纯形表，设xi=bi 是最优解中取分数值（分数 部分最大）的基变量，则有

运筹学PPT 第四章 线性整数规划

运筹学PPT 第四章 线性整数规划

s.t.
x
i 1
8
i
5
x1 x2 1
x6 x7 x8 1
x6 x2
xi 0 或 1，i=1, … ,8
2. 指派问题 问题描述：n项任务可由n个人完成，由于专长不同，各人 完成各任务的时间也不同，求最优安排。 要求：每人只能完成一项任务，每项任务只能由一人完成。 例： 有一份中文说明书，需译成英、日、德、俄四种文字， 分别记作任务E、J、G、R，现有甲、乙、丙、丁四人，他们 将中文说明书翻译成不同语种说明书所需的时间如下表所示， 问应指派何人去完成何项任务，使所需总时间最少？
运动员 甲 乙
丙 丁
仰泳 75.5 65.8
67.6 74.0
蛙泳 86.8 66.2
84.3 69.4
蝶泳 66.6 57.0
77.8 60.8
自由泳 58.4 52.8
59.1 57.0
3. 背包问题 问题描述 已知：一个背包最大容量为b公斤；有m件物品供选择，每 件物品重ai公斤，价值为ci（i=1,…,m）。 问题：携带哪些物品可使总价值最大？ 一般模型 xi=
解：令 x i=

7
1， Ai被选中
i 1
0， Ai没被选中
bixi≤B ∑ i=1 x1+x2+x3≤2 s.t. x4+x5≥1 x6+x7≥1 x =0或 1，i=1, … ,7
i
7
课堂练习1:
某钻井队要从S1~S10共10个井位中确定五个钻 井探油，如果选Si，估计钻探费用为ci元，并且 井位选择上要满足下列条件： （1）或选择S1和S7，或选择S8 ;
解：令 x i=

运筹学课件 第四节 0—1型整数规划

运筹学课件 第四节 0—1型整数规划
2
分析：
如果生产第j种产品，xj>0. 约束条件xj<=Mjyj,yj=1; 如果不生产第j种产品， xj=0.约束条件 xj<=Mjyj,yj=1或0。当 yj=1不利于目标函数的最大 化，因此在最优解必然是 yj=0。
件， M 1 100 ,
50 , M
3
34
运 设工序B的每周工时约束条件为0.3x1+0.5x2≤150,式(1) 现有一新的加工方式,相应的每周工时约束条件为0.2x1+0.4x2≤120 ,式(2) 如果工序B只能选择一种,那么(1)和(2)变成相互排斥的约束条件.
产品3
a32
机床2
a33
机床3
运筹学教程
解 设xij表示产品i在机床j 上开始加工的时间(i=1,2,3;j=1,2,3,4) 1.同一件产品在不同机床上的加工顺序约束 同一件产品在下一台机床上的加工的开始时间不早于在上一台机床上加工 的结束时间,故应有
产品1:x11+a11≤x12 ; x13+a13≤x14
运筹学教程
4 求解： 7 C 6 6 6 0 0 0 0 0
当y1=1,y2=0;采用 新工艺,(2)式成立;
1 2
运筹学教程
p 个约束条件
a
j 1
p
ij
x j b i ( i 1, 2 ,..., p ) p 个 0 1变量
选择 q 个约束条件，引入
0 , 选择第 i 个约束条件 ( i 1, 2 ,..., p ) yi 1, 不选择第 i 个约束条件 ( i 1, 2 ,..., p )
约束条件组
n a ij x j b i My i j 1 st . ( i 1, 2 ,..., p ) p yi p q i 1

运筹学01整数规划

运筹学01整数规划
货物体积每箱m3重量每箱吨利润每箱百元托运限制20分别表示甲乙两种货物的托运箱数则其整数规划数学模型为当采用船运方式当采用车运方式其中一般情况下m个约束条件中选择q个约束条件则可变成为
第四节 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
所以，最优解为（x1，x2，x3)T=(1,0,1)T, 最优值为8.
令
xi

1

0
当Ai点被选用 当Ai点未被选用
i=1, …,7
7
max Z c i x i
i1

7

bixi
B
i1
x1 x 2 x 3 2
s .t

x
4

x5
1

x
0 or 1
例2: 相互排斥的约束条件

运筹学课件第四节0-1型整数规划

运筹学课件第四节0-1型整数规划
运筹学课件第四节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求解工具

运筹学整数规划PPT课件

运筹学整数规划PPT课件
2
B1 (x1≤4)
2
4
B2 6
(4,2.1) z=349
(5,1.57) z=341 7x1+20x2=70
若情况③发生，得到(A)问题最优值的一个上界。同时可以通 过观察的方法任找(A)问题的一个可行解，那么对应的目标函 数值是(A)最优值的一个下界 z 。即得到
z ≤ z* ＜z，转2，进行以下一步的迭代；
步骤2.对当前问题进行分支和定界
分支：任取非整数的分量 xr。构造两个附加约束： xr ≤ [xr] 和 xr ≥ [xr]+1 ，
s.t.
9 7
x1 x1
7 x2 56 20 x2 70
x1,x
2
0, 且为整数
x2
8
6
4 (0,3.5) Z=315
2
等值线
9x1+7x2=56
选x1来分支
松弛规划问题最优解
(4.81,1.82) Z=356 7x1+20x2=70
2
4
6
8
10
x1
x2 8
6
9x1+7x2=56
4 (0,3.5) Z=315
① 过滤隐枚举法 ② 分支隐枚举法 4．匈牙利法——解决指派问题(0-1规划特殊情形)
5．蒙特卡洛法——求解各种类型规划(不要求掌握) 6. 分支切割方法(不要求掌握) 7. 启发式算法(不要求掌握)
分 支 定 界 法
分支定界法是求整数规划的一种常用的有效的 方法，既能解决纯整数规划的问题，也能解决 混合整数规划的问题。
划 变量全限制为整数的，为纯(完全)整数规划。
定
特例：0-1整数规划
义 变量部分限制为整数的，为混合整数规划。

01型整数规划模型

01型整数规划模型

§5.4 0—1型整数规划模型1、 0—1型整数规划模型概述整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。

在整数规划问题中，0—1型整数规划则是其中较为特殊的一类情况，它要求决策变量的取值仅为0或1，在实际问题的讨论中，0—1型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。

0—1型整数规划的的数学模型为： 目标函数nn x c x c x c z M i n M a x +++= 2211)(约束条件为：⎪⎪⎩⎪⎪⎨⎧==≥≤++=≥≤++=≥≤++1 | 0 ) ,() ,() ,(22112222212111212111n m n mn m m n n n n x x x b x a x a x a b x a x a x a b x a x a x a , , ,21这里，0 | 1表示0或1。

2、0—1型整数规划模型的解法0—1型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量nx x x , , ,21 的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解。

这种方法一般适用于决策变量个数n 较小的情况，当n 较大时，由于n 个0、1的可能组合数为n2，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的。

隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。

此时，就只能用穷举法了。

3. 应用实例例1 工程上马的决策问题1）问题的提出某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大。

2）模型分析与变量的假设这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别对应二进制数中的1、0，大凡这样的实际背景所对应的工程问题，大都可考虑用0—1型整数规划模型建立其相应的模型。

运筹学课件--第四章 整数规划

运筹学课件--第四章 整数规划
上述分枝过程可用下图表示
LP0:X=(3.57,7.14),Z0=35.7
x1≤3 x1≥4
LP1:X=(3,7.6) Z1=34.8
x2≤6
LP2:X=(4,6.5) Z2=35.5
x2≥7 无可行解 x1≥5 LP5:X=(5,5) Z5=35
OR:SM OR:SM
LP3:X=(4.33,6) Z3=35.33
10
OR:SM OR:SM
第二节 整数规划求解
【例3.5 】用分枝定界法求解例3.1
max Z 4 x 1 3 x 2 1 . 2 x 1 0 . 8 x 2 10 2 x 1 2 . 5 x 2 25 x 1 , x 2 0 , 且均取整数
【解】先求对应的松弛问题（记为LP0）：
7
OR:SM OR:SM
第二节 整数规划求解
一、舍入化整法
为了满足整数解的要求，自然想到“舍入”或“截尾”处理，以得到 与最优解相近的整数解。 这样做除少数情况外，一般不可行，因为化整后的解有可能超出 了可行域，成为非可行解；或者虽是可行解，却不是最优解。

不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题 对于例1的数学模型，不考虑整数约束的最优解：
6
LP1 LP3
LP3:X=(4.33,6),Z3=35.33
C o
14
3
4
10
x1
OR:SM OR:SM
x2 ① ②
10 A
由于 Z 3 Z 1，选择 LP 3 进行分枝，增加约束 x 1 4 及 x 1 5，到线性规划 LP 4 及 LP 5：
max Z 4x1 3x2 LP1:X=(3,7.6),Z1=34.8 1.2x1 0.8x2 10 2x1 2.5x2 25 LP4 : LP4:X=(4,6),Z4=34 x1 4，x2 6，x1 4 x1 , x2 0 即x1 4, 可行域是一条线段 max Z 4x1 3x2

运筹学-4-整数规划ppt课件

运筹学-4-整数规划ppt课件

.
8
第四章 整数规划 0-1规划
解：设xi
1 0
带第 i件物品
不带第 i件物品 数学模型：
Z表示所带物品的总价值
m
Z ci 带第i件
ci xi
i 1
m
携带物品的总重量 bi x i
i 1
m
max Z ci xi
m i1
s.t
i1
bi xi
b
xi 0,1，
i 1, 2, m
i1
1, 2,..., m
i1
s.t. xij bj j 1, 2 , n
i1
xij
0
,
yi 0,1
混合型整数规划
.
11
第四章 整数规划
例 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再 建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有 B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需 求地的单位物资运费cij，见下表：
.
10
第四章 整数规划
解：设 xij表示A 工 i运厂 往B 商 j的店 运量
m
n
则总运费为
c ij x ij
i1 j 1
数学模型：
mn
m
设yi
1 0
则总建厂费为
在第 i个地点建m厂in Z
不在第 i个地点建厂 n
m
fi yi
j1 m
xij
i1
j
ai
1
yi
cij xij
i
fi yi
1 若 建 工 厂 yi 0 若 不 建 工 厂(i3,4)
再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用， 单位万元。

运筹学课件 0-1 整数规划

运筹学课件 0-1 整数规划

§4 0-1 整数规划
决策变量仅取为0或1的整数规划问题。
xi 是0-1变量的表示： xi = 0 或1
或 xi 0，xi 1，xi Z
4.1 1.
典型的0-1整数规划问题 相互排斥的计划
例4．某公司拟在市东、西、南三区建立门市部。拟议 中有7个位置(点)Ai (i =1，2，…，7)可供选择。规定 在东区，由A1，A2，A3三个点中至多选两个； 在西区，由A4，A5两个点中至少选一个； 在南区，由A6，A7两个店中至少选一个。 如选用Ai点，设备投资估计为bi 元，每年可获利润 估计为ci 元，但投资总额不能超过B元。问选择哪几个 点可使年利润最大？
5
点 (x1,x2,x3) (0，1，0) (0，1，1) 3 8
条 ① 0 ② 2
件 ③ 1 ④ 1
满足条件?
z值
8
再将过滤条件改进为 3x1-2x2 + 5x3 8
点 (x1,x2,x3) (1，0，0) (1，0，1) (1，1，0) (1，1，1) 2 3 1 6 条 ① ② 件 ③ ④ 满足条件? z值
解题时先引入0-1变量xi (i =1，2，…，7)
令
1 xj 0
选择在A i建店 否则
收益最大
于是问题可列成：
Max z ci xi
i 1 7
投资总额不超过B
A4，A5两个点中至 少选一个
A1，A2，A3三个点中至多选两个 bi xi B i 1 x1 x2 x3 2 A6，A7两个店中至少 x x 1 4 5 选一个 x x 1 7 6 xi 0或1( i 1 , ,7 )
y1 + y2 + … + ym = m –1， yi = 0 或 1 (i=1，…，m)

北京交通大学管理运筹学0-1整数规划

北京交通大学管理运筹学0-1整数规划

第五步 将子域固定变量的值代入第一个不等式约束条件方程，并令 不等式左端的自由变量当系数为负时取值为1，系数为正时取值为0， 这就是左端所能取的最小值。若此最小值大于右端值，则称此子域 为不可行子域，不再往下分枝，若子域都检验过，转第七步，否则， 不可行子域， 不可行子域 转第六步；若此最小值小于右端值，则依次检验下一个不等式约束 方程，直至所有的不等式约束方程都通过，若子域都检验过，转第 七步，否则，转第六步。 第六步 定出尚未检验过的另一个子域的解，进行第三步至第五步， 若所有子域都停止分枝，计算停止，目标函数值最小的可行解就是 最优解；否则，转第七步。 第七步 检查有无自由变量。若有，转第二步；若没有，计算停止。
目标函数值最小的可行解就是最优解。
现举例说明上述计算步骤。 例8 min z=
8 x1 + 2 x2 + 4 x3 + 7 x4 + 5 x5
满足：
−3 x1 − 3 x2 + x3 + 2 x4 + 3 x5 ≤ −2 −5 x1 − 3 x2 − 2 x3 − x4 + x5 ≤ −4 x = 0或1 对一切j j
第四节 0-1整数规划 整数规划
•
问题的提出：
0-1整数规划是线性规划及整数规划的一种特殊形式。 模型结构和形式是线性规划，只是决策变量取0或1。 例1：投资场所的选定——相互排斥的计划
某公司拟在城市的东、西、南三区建立分公司，拟议中有七 个位置Ai（i=1, 2,…,7), 规定在东区A1,A2,A3个点中至多选二个; 在 西区A4,A5两点中至少选一个; 在南区A6,A7中至少选一个, 如选用Ai 点,设备投资估计为bi元, 每年可获利润估计为ci元, 但投资总额不能 超过B元, 问应选择那几个点可是年利润为最大?

运筹学 0-1整数规划

运筹学 0-1整数规划

n ∑ a ij x j < = b i + M i y i j =1 p ∑1 y i = p - q i=
三、固定成本问题
某公司制造小、 大三种尺寸的容器，所需资源为金属板、 例4.8 某公司制造小、中、大三种尺寸的容器，所需资源为金属板、劳 动力和机器设备，制造一个容器所需的各种资源的数量如下表所示： 动力和机器设备，制造一个容器所需的各种资源的数量如下表所示： 不考虑固定费用， 大号容器每售出一个其利润分别为4万元 万元、 不考虑固定费用，小、中、大号容器每售出一个其利润分别为 万元、 5万元、6万元，可使用的金属板有 万元、 万元 可使用的金属板有500吨，劳动力有 万元， 万元 吨 劳动力有300人/月，机器有 人月 100台/月，另外若生产，不管每种容器生产多少，都需要支付一笔固定 台 月 另外若生产，不管每种容器生产多少， 费用：小号为100万元，中号为 万元， 万元， 万元。 费用：小号为 万元 中号为150万元，大号为 万元 大号为200万元。问如何制定 万元 生产计划使获得的利润对大？ 生产计划使获得的利润对大？
0－1 整数规划求解方法
0－1 整数规划是一种特殊形式的整数规划，这时的 － 整数规划是一种特殊形式的整数规划， 决策变量x 只取两个值0或 ，一般的解法为隐枚举法。 决策变量 i 只取两个值 或1，一般的解法为隐枚举法。 例一、求解下列0－ 例一、求解下列 －1 规划问题 max Z = 3 x 1 − 2 x 2 + 5 x 3
(1) (2)
•
工序B 只能从两种加工方式中选择一种，那么约束条件（ ） 工序 3只能从两种加工方式中选择一种，那么约束条件（1）和（2）就成为 ） 相互排斥的约束条件。为了统一在一个问题中，引入0-1变量 相互排斥的约束条件。为了统一在一个问题中，引入 变量

0—1 型整数规划

0—1 型整数规划

例5 求解maxZ=3x1-2x2+5x3 解：调整x1,x2的顺序，使目标函数 x1+2x2-x3≤2 中变量的系数呈递增（不减）的顺 x1+4x2+x3≤4 序,则问题变为： maxZ=-2x2+3x1+5x3 x1+ x2 ≤3 2x2+x1-x3≤2 ① 4x2+x3≤6 4x2+x1+x3≤4 ② x1,x2,x3=0或1 x2+x1 ≤3 ③ 解 约束条件 目 4x2 +x3≤6 ④ 标 ① ② ③ ④ （x2，x1，x3） 值 x1,x2,x3=0或1 0 √ √ √ √ （0 0 0） 按二进制数码从小到大的顺序排列 5 √ √ √ √ （0 0 1） 并检查各个解，先计算解的目标值， 若目标值小于目前可行解最好的目 （0 1 0） - - - 标值，则不必检查是否满足约束条 8 √ √ √ √ （0 1 1） （1 0 0） - - - - 件，当所有解被检查完毕，就可判 （1 0 1） - - - - 断出最优解。计算结果可列表表示， 见左表。 （1 1 0） - - - 最终得到最优解：x1=1，x2=0， （1 1 1） - - - 6 x3=1，最优值：Z=8
x =
1 ,是 0 ,否
4.1 引入 引入0—1 变量的实例 1.确定投资方案——相互排斥的计划 例4 某市工商银行拟抽调a万元资金对小五金、小百货和洗 涤剂三个行业给予低息贷款。由于资金有限，只能在四个小五金 企业A1、A2、A3、A4 中至多选两个；在五个小百货企业A5、A6、 A7、A8 中至多选三个；在四个洗涤剂企业A9、A10、A11、A12 中 至多选两个给予低息贷款。已知企业Ai得到贷款ai万元后，可获 利bi万元。问工商银行应如何发放贷款，可使总利润最大？ 解：因为本问题只要求解决是否给企业贷款，因此可用0—1 变量描述所求方案。设 1, 给A 贷款 i xi = ,i =1,2,L,12 不给A 贷款 0, i 于是，根据题意，本问题可描述为： 12 maxZ= ∑bi xi
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
化，因此在最优解必然是 yj=0 。
M j为xj的上界, 例如根据第三个约束条件，M1 ? 100,
M2 ? 50, M3 ? 34
运筹学教程
例 含有相互排斥的约束条件的问题
设工序B的每周工时约束条件为0.3x1+0.5x2 ≤150,式(1) 现有一新的加工方式,相应的每周工时约束条件为 0.2x1+0.4x2≤120 ,式(2) 如果工序B只能选择一种,那么(1)和(2)变成相互排斥的约束条件.
3.产品2的加工总时间约束
产品2的开始加工时间 x21, 结束家工时间为 x 24 +a24 ,所以
x 24 +a24 -x21≤d
4.目标函数的建立
由于三件产品的加工时间分别为 x14+a14,x24+a24,x33+a33,全部产品的实际 加工时间为:w=max(x 14+a14,x24+a24,x33+a33)
运筹学教程
p
? p个约束条件 aij xj ? bi (i ? 1,2,..., p) j?1
选择q个约束条件，引入,选择第i个约束条件(i ? 1,2,..., p) ??1,不选择第i个约束条件(i ? 1,2,..., p)
在约束条件中保证了在P个0-1
约束条件组
2.每一台机床对不同产品的加工顺序约束 一台机床在工作中,如果已经开始加工还没有结束,则不能开始加工另一件产 品.对于机床1,先加工1不能加工2. 为了容纳两种相互排斥的约束条件,对于每台机床,分别引入0-1变量:
运筹学教程
yj ? ???10，, 先先加加工工某另种外产产品品（j ? 1,2,3,4） 机床1:x 11+a11≤x21+My1 ; x 21+a21≤x11+M(1-y1) 机床2:x 22+a22≤x32+My2 ; x 32+a32≤x22+M(1-y2) 机床3:x 13+a13≤x33 +My3 ; x 33+a33≤x13+M(1-y3) 机床4:x 14+a14≤x24 +My4 ; x 24+a24≤x14+M(1-y4) 当y1=0,表示机床1先加工产品1,后加工产品2;当y1=1,表示机床1先 加工产品2,后加工产品1.
??2x1 ? 3x2 ? 4x3 ? 300
如果不生产第 j 种产品，
? ? st.?? ?
x1
?
2x2 ? 3x3 ? x1 ? M1 y1 x2 ? M2 y2
100
? ? ?
x3 ? M3 y3 xj ? 0且为整数
??
yj ? 1或0
x j=0. 约束条件 x j<=M jyj,yj=1 或0 。当 yj=1 不利于目标函数的最大
xj
?
? 1, ??0,
E E
j j
选择Aj 选择 Aj
( x1,...xn )T
?
? ?
(1,1,...,1)T
,
选择（
A1,...
An）T
?
:
? ?
(1,1,...,
0)T
,
选择（
A1,...
An）T
运筹学教程
一、0—1规划数学模型
例：固定费用问题 有三种产品被用于生产三种产品，资源量、产品单件费用、 资源消耗量以及生产产品的固定费用。要求制定一个生产计 划，总收益最大。
产品1 a11
机床1 产品2 a21
机床1 产品3
a23
机床2 a32
机床2
a13 机床3
a33 机床3
a14
机床4 a24
机床4
运筹学教程
解 设xij表示产品i在机床j 上开始加工的时间(i=1,2,3;j=1,2,3,4) 1.同一件产品在不同机床上的加工顺序约束 同一件产品在下一台机床上的加工的开始时间不早于在上一台机床上加工 的结束时间,故应有 产品1:x 11+a11≤x12 ; x 13+a13≤x14 产品2:x 21+a21≤x22 ; x 23+a23≤x24 产品3:x 32+a32≤x33 ;
变量中有p-q 个1,q个0;凡取值
=0的yi对应的约束条件为原约束
??
st.???
n j?1
aij x j ?
p
bi
?
Myi
(i
?
1,2,...,
条件,凡取值=1的yi对应的约束 条件将自然满足,因而为多余.
p)
? ?
??
yi ? p ? q
i?1
运筹学教程
例 工件排序问题
使用4台机床加工3件产品.各个产品的机床加工顺序以及产品 i在机床j 上的加工时间 aij见表.由于某种原因,产品2的加工总是件不得超过d.现 在要求各件产品在机床上的加工方案 ,使在最段时间内加工完全部产品 .
消耗 产品 产品1
资源
A
2
产品2 4
产品3 8
资源量 500
B
2
3
4
300
C
1
2
3
100
单件费用 4
5
6
固定费用 100
150
200
单件售价 8
10
12
运筹学教程
解：xj是生产第j种产品的产量。
总收益等于销售减去所生产的产品的总费用。建立数学模型时，无法确
定某种产品是否生产，不能确定相应的固定费用是否发生，用0-1变量解
运筹学教程
第四节 0—1型整数规划
一、0-1变量及其应用
某些特殊问题，只做是非选择，故变量设置简化为 0或1，
1代表选择，0代表不选择。
选取某个特定方案
x
?
? 1,当决策选取方案 ??0,当决策不选取方案
问题含有较多的要素， 每项要素有 2种选择，用0 ? 1变量描述。
有限要素E1, E 2,...En , 每项E j有两种选择 Aj , Aj
决此问题。
yj
?
???0,1不,生生产产第第j种j种产产品品（（xjx?j
0） ? 0）
分析： 如果生产第j种产品，x j>0.
max Z ? 4x1 ? 5x2 ? 6x3 ? 100 y1 ? 150 y2 ? 200 y3 ?2x1 ? 4x2 ? 8x3 ? 500
约束条件x j<=M
jy j,y j=1;
Minz=W st. W≥x 14+a14, W≥ x24+a24, W≥ x33+a33
运筹学教程
二、0-1型整数规划的解法
求解思路：
检测可行解的目标函数值，根据其目标函数值可以产生一个 过滤条件，对于目标函数数值比它差的变量组合删除，这样 有效减少运算次数，使最优解快速找到。
? 0 , B 采用原加工方式
y1
?
? ?1,
B
不采用原加工方式
多余的约束
? 0 , B 采用新加工方式
y2
?
? ?
1
,
B
不采用新加工方式
st
? .??
0.3 0.2
x1 x1
? ?
0.5 x2 0.4 x2
? ?
150 120
? ?
My 1 My 2
??
y1 ? y2 ? 1
当y 1=1,y2=0; 采用 新工艺,(2)式成立;