当前位置：文档之家 › 运筹学ABC-2整数规划建模课

运筹学ABC-2整数规划建模课

  • 格式：ppt
  • 大小：1.73 MB
  • 文档页数：18

下载文档原格式

  / 18

合集下载

运筹学课件第五章 整数规划

运筹学课件第五章 整数规划

第一节 整数规划的数学模型
解的特点： 整数规划
松弛问题
max c x Ax b s .t . x 0, x为整数

max c x Ax b s .t . x 0

1、整数规划可行域是松弛问题可行域的子集
2、整数规划最优值小于等于松弛问题的最优值
第一节 整数规划的数学模型
P1 P2
P4
以上描述了目前解整数规划问题的一种思路。
第二节 分支定界法
思路：切割可行域，去掉非整数点。 解题步骤： 1、不考虑整数约束，解相应松弛问题。 2、检查是否符合整数要求，是，则得最优解，完毕。 否则，转下步。 3、任取一个非整数变量xi=bi，构造两个新的约束条 件：xi ≤[bi]，xi≥[bi]+1,分别加入到上一个LP问 题，形成两个新的分枝问题。 4、不考虑整数要求，解分枝问题。若整数解的Z值 大于所有分枝末梢的Z值，则得最优解。否则， 取Z值最大的非整数解，继续分解，Go to 3。
序号 1 2 3 4 5 6 7
物品
重量 系数
食品
5 20
氧气
5 15
冰镐
2 18
绳索
6 14
帐篷
12 8
相机
2 4
设备
4 10
第三节
0-1型整数规划
解：令xi=1表示登山队员携带物品i，xi=0表示登 山队员不携带物品i，则得： Max Z=20x1+15x2+18x3+14x4+8x5+4x6+10x7
第三节
(x1,x2,x3) z值
0-1型整数规划
1 2 3 4 过滤条件
(0,0,0)

运筹学第五章 整数规划ppt课件

运筹学第五章 整数规划ppt课件
，求解过程停止。 3.B有最优解，但不符合A的整数条件，记其目标函数值为z1。
第二步：确定A的最优目标函数值z*的上下界，其上界即为 z ,再用观察法
找到A的一个整数可行解，求其目标函数值作为z*的下界，记为z。
第三步：判断 z 是否等于z 。若相等，则整数规划最优解即为其目标函
数值等于z的A的那个整数可行解；否则进行第四步。
2020/3/2
11
•割平面法，即通过添加约束条件，逐步切割可行区域的 边角余料，让其整数解逐步的露到边界或顶点上来，只要 整数解能曝露到顶点上来，则就可以利用单纯形法求出来。
•关键是通过添加什么样的约束条件，既能让整数解往边 界露，同时又不要切去整数解，这个条件就是Gomory约束 条件。 •Gomory约束只是割去线性规划可行域的一部分，保留了 全部整数解。
2020/3/2
7
7
第二节 割平面法
2x1 2x2 11
13/4,5/2
松弛问题 x1+x2≤5 第二次切割
2020/3/2
第一次切割 4,1
8
设纯整数规划
n
m a x Z c j x j j 1

s
.t
.

n j 1
aij x j

bi

x
j

0且
为
整
数
，
j

1,L
引入约束 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

数学建模整数规划PPT学习教案

数学建模整数规划PPT学习教案
x31 x32 x 33 90 y3
已知三工厂每月的经营费用 di (与 产量无关)分别为 100、90、120 .问如 何选址使每月经营和运输费用最低 .
x11 x21 x31 40
x12 x22 x32 60
x13 x23 x33 45
y1 y2 y3 2
Solution:
1、 先检查最大上界（极大化问题）的活问题
优点：检 查子问 题较其 他规则 为少；
缺点：计算机储存量较大 .
2、 先检查最新产生的最大上界的活问题 优点：计算机储存量较少 ；
缺点：需要更多的分支运算 .
选择的不 同，提 供了发 挥的余 地
第13页/共30页
第五章去掉整数约整束数为3＜规x 划＜4 之间无整数解P Example4
0123456789
x1第14页/共30页
P6 (x2≥5)
x1=0、x2=5 Z6=40
*
§2 整 数 规 划 的解 法 Example 5 （投资方案的最优选择）
投资 年度
项目
A1 A2 A3
投资 额度
1 042 5
某公司欲对三个项目进行投资， 根据预算 四年内 的投资 额、三 个项目 每年所需投资额以及所创利润如表. 问应对哪 几个项 目进行 投资， 可获利 最大？
整数规划
物品 重量 aj
1
3
2
4
3
3
4
3
5
15
6
13
7
16
价值 cj 12 12 9 15 90 26 112
Solution: 这是一个 0-1 规划问题.
1 x j 0
如果带第 j 件物品 否则 j = 1~7

运筹学 第五章 整数规划PPT课件

运筹学 第五章 整数规划PPT课件

x 32
x 42
400
x 13
x 23
x 33
x 43
300
x 14 x 24 x 34 x 44 1 5 0
s
.t
x 11 x 21
x 12 x 22
x 13 x 23
x 14 x 24
400 600
x
31
x 32
x 33
x 34
200 y3
x 41 x 42 x 43 x 44 2 0 0 y 4
max Z 85x11 92x12 73x13 90x14 95x21 87 x22 78x23 95x24 82x31 83x32 79x33 90x34 86x41 90x42 80x43 88x44
要求每人做一项工作，约束条件为：
x11 x12 x13 x14 1
例5.3 设整数规划问题如下
max Z x1 x2
14 x1 9 x2 51
6 x1
3x2
1
x
1
,
x2
0且 为 整 数
首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）
max Z x 1 x 2
14
x1 6x
1
9x2 3x
2
51 1
ቤተ መጻሕፍቲ ባይዱ
x
1
,
x2
0
用图解法求出最优解为：x1＝3/2, x2 = 10/3，且有Z = 29/6
在很多场合，我们建立最优化模型时，实际问题要求决 策变量只能取整数值而非连续取值。此时，这类最优化 模型就称为整数规划（离散最优化）模型。
整数规划的求解往往比线性规划求解困难得多，而且， 一般来说不能简单地将相应的线性规划的解取整来获得。

运筹学课件 第5章：整数规划

运筹学课件 第5章：整数规划


如果所有变量都取整数，就称为纯整数规划或全整 数规划 如果仅有一部分变量取整数，则称为混合整数规划 若变量值仅限于0或1，则称为0-1规划

在整数规划问题中，不考虑整数要求，由其他
约束条件和目标函数构成的规划问题称为该整 数规划问题的松弛问题。 若松弛问题是一个线性规划问题，则其对应的 整数规划问题称为整数线性规划（ILP）。
依照决策变量取整要求的不同，整数规划可分为纯 整数规划/全整数规划、混合整数规划、0－1整数规划
整数规划解的性质
求解整数规划问题
max Z 3 x1 2 x2 2 x1 x2 9 ( IP)2 x1 3 x2 14 x1 , x2 0且为整数
分析：考虑对应的线性规划问题(LP)
A2
A3 A4
8
7 4
3
6 5
5
1 2
7
2 5
600
200 200
需求量 （千吨/年）
350
400
300
150
工厂A3 或A4 开工后，每年的生产费用估计分别为1200万元或 1500万元。现要决定应该建设A3还是A4，才能使今后每年的总 费用最少。
(三)投资问题
【5-2】某投资公司可用于投资的资金是B，可供 投资的项目有n个，项目j所需投资额和预期收益 分别aj 和cj 。同时，由于种种原因，有三个附加 条件： 第一，若选择项目1，就必须同时选择项目2，反 之则不一定； 第二，项目3和项目4中至少选择一个； 第三，项目5、项目6和项目7中恰好选择两个。 应当怎样选择投资项目，才能使总预期收益最大？
例1、用分枝定界法求解整数规划问题
max Z 3 x1 2 x2 2 x1 x2 9 ( IP)2 x1 3 x2 14 x1 , x2 0且为整数

运筹学-整数规划(二)(名校讲义)共23页文档

运筹学-整数规划(二)(名校讲义)共23页文档
§1 匈牙利法 （1）
匈牙利法主要解决指派问题，指派问题是一种特殊的 “0 1”规划。 例如指派授课问题，现有A、B、C、D四门课程，需由 甲、乙、丙、丁四人讲授，并且规定： 每人只讲且必须讲１门课。 每门课必须且只需１人讲。 四人分别讲每门课的费用示于表2-3中：
§1 匈牙利法 （2）
表2-3 授课费用表
未做标记的零元素标Δ后，应对同一列其它的零元素画
×。
8 2 5
11 5
4
2 3 0 0
11 4
5
§1 匈牙利法 （10）
现在依次检查每列中只含一个未标记的零元素，并给未
标记的零元素标Δ。对同一行其它的零元素画×（如果
有的话）。
8 2 5
11
5
4
2 3
11 4
5
如果有多行多列同时有2个或以上的未标记零元素，则 可将其中的任意行或列中一个未标零元素标Δ，并将同 行和同列的其他零元素画×。
5 4
3
11
4
5 √
√
§1 匈牙利法 （14）
⑥在上述最后的缩减矩阵中，检查那些没有线通过的元 素。设k为其中最小元素。找出含有未画线元素的各行， 将这些行的每个元素减去k。本例中，k=2，因而由第1 行、第4行减去2，可得
2 6 0 3
11
0
5
4
2 3 0 0
2
1) 修改费用矩阵，使矩阵的每一行和第一列至少出现1 个零元素，处理方法即为每行（每列）都减去该行（列） 的最小元素。
§1 匈牙利法 （8）
2 10 9 7
0 8 7 5
15
4
14
8
13 14 16 11
4

《管理运筹学》03- 整数规划


ppt课件整数规划整数规划
3
3.1 整数规划问题及其建模
例3-1背包问题
max z= 17x1 +72x +35x
s.t.
10x1 2 +42x 3 +20x ≤50
x1, 2 x2,
3 x3
≥0
x1,
x2,
x3为整数
线性规划最优解为: x1=0，x2=0，x3=2.5
而整数规划的最优解是 x1=1，x2=0，x3=2
T
5
ppt课件整数规划整数规划
22
-2x2+3x1+5x3≥5 ◎
点
条件
◎
①
②
③
④
满足条件？ 是（T）否（F）
Z
（0 1 0） 3
F
（0 1 1） 8
0
2
1
5
T
8
-2x2+3x1+5x3≥8 ◎
点
条件
◎
①
②
③
④
满足条件？ 是（T）否（F）
Z
（1 0 0） -2
F
（1 0 1） 3
F
（1 1 0） 1
工件
A
B
C
D
工人
效
甲
14
9
4
15
率
乙
11
7
9
10
矩
丙
13
2
10
5
阵
丁
17
9
15
13
ppt课件整数规划整数规划
24
设xij=1表示第 i人送j货，否则xij=0
上述问题的模型为：
44

数学建模-整数规划

数学建模
整数规划
Integer Programming
数信学院 任俊峰
2012-4-15
数学建模之整数规划
整数规划模型（IP）
如果一个数学规划的某些决策变量或全部决策 变量要求必须取整数，则称这样的问题为整数规 划问题，其模型称为整数规划模型。 如果整数规划的目标函数和约束条件都是线性 的，则称此问题为整数线性规划问题.
松弛问题最优解满足整数要求，则该最优解为整数 规划最优解；
数学建模之整数规划
整数线性规划的求解方法
从数学模型上看整数规划似乎是线性规划的 一种特殊形式，求解只需在线性规划的基础上，通 过舍入取整，寻求满足整数要求的解即可。 但实际上两者却有很大的不同，通过舍入得到
的解（整数）也不一定就是最优解，有时甚至不能
1 xj 0
选中第j个项目投资 不 选中第j个项目投资
max Z 160 x 1 210 x 2 60 x 3 80 x 4 180 x 5 210 x 1 300 x 2 150 x 3 130 x 4 260 x 5 600 x x2 x3 1 1 x3 x4 1 x x 1 5 x1 , x 2 , x 3 , x 4 , x 5 0 或 1
1 2
14 x1 9 x 2 51 6 x1 3 x 2 1 x1 , x 2 0
数学建模之整数规划
用图解法求出最优解 x1＝3/2, x2 = 10/3 且有 z = 29/6 现求整数解（最优解）： 如用“舍入取整法”可得到4 个点即(1，3) (2，3) (1，4) (2，4)。显然，它们都不可能 是整数规划的最优解。
数学建模之整数规划
例5 固定费用问题

运筹学ABC-2整数规划建模课


表4-8 产品资源需求量表
资源 原材料/吨 劳动力（人/月） 机器设备（台/月） 产品A 2 2 1 产品B 4 3 2 产品C 8 4 3
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.3 固定成本问题

此问题的数学模型如下：
把上述模型输入WinQSB软件中，得到如下结果：最大目 标函300，最优解为x1=100, x2=0, x3=0, 也就是说生产100台 A产品可获取最大利润300万元。
整 数 规 划 在 经 济指派问题

在工作任务的安排中，有n项不同的任务，有m个人分别承担 这些任务，但由于每个人特长不一样，完成各种任务的效率也 不相同。现假设必须指派每个人去分别完成一项任务，怎么样 把n项任务指派给m个人，使得完成n项任务的总效率最高，这 就是指派问题。 对于有m个人n项任务的一般指派问题，设： xij 并设cij为第i个人去完成j项任务的成本（如所需时间、费用 等），则一般指派问题的模型可以写成：

整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.4 指派问题

约束条件：

因为m不一定等于n,当m>n时，即人多于任务时，就有人没有任 务，所以前面m个约束条件都是小于等于1，这就是说每人至多 承担一个任务，而后面的n个约束条件说明每项工作正好有一 个人承担，所以都是等于1。
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.2 选址问题

解：设0-1变量 这样我们可建立如下数学模型：
约束条件如下：
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.3 固定成本问题
【例4-10】某工厂生产三种类型的产品A、B、C，所用的资源为：原材料、劳动力 和机器设备。生产每个产品的资源需求量如表4-8所示。不考虑固定成本，每种产 品A、B、C的利润分别为4万元、5万元、6万元，可使用的材料总量为500吨，劳动 力300人/月，机器100台/月。此外，如果工厂开通该产品的生长线，不管生产多少 个A、B、C产品，工厂都需要付出一定量的固定成本，具体如下：A产品为100万， B产品为150万，C产品为200万元。现在要制定一个生产计划，使其获得利润最大。

运筹学——整数规划


5
4
x(0)=(4.81,1.82) Z0=356
3
B 2
1
7x1+20x2=70
C
0 1 2 3 4 5 6 7 8 9 10 x1
x1<=[x1(0)]
12
x1>=[x1(0)]+1
2021/7/26
解：第一步：先不考虑整数约束条件，求解相应的线性 规划问题，得最优解和最优值如下：
x1=4.81, x2=1.82, Z=356 解不满足整数条件。最优值Z=356作为整数规划目标函 数值的上界；用观察法可知x1=0，x2=0是可行解，对应 目标值Z=0作为整数规划目标值的下界，即0 Z* 356
1
2
x6 x7 1
xi 0或1
获利最大的设点方案，第 一个约束条件表示投资总 额限制，之后的三个约束 条件分别表示在东、西和 南区的设点数限制，决策 变量取值0或1。
5
2021/7/26
例3 解决某市消防站的布点问题。该市共有6个区，每 个区都可以建消防站。政府希望设置的消防站最少，但 必须满足在城市任何地区发生火警时，消防车要在15分 钟内赶到现场。据实地测定，各区之间消防车行驶的时 间见下表：
行解, 停止; b) 若有满足整数条件的最优解, 则已得到整数规划问 题的最优解, 停止; c) 若有最优解, 但不满足整数条件, 记此最优值 为原整数规划问题Z*的上界, 然后, 用观察法求出下界. (2)分支、定界直到得到最优解为止
分支：取目标函数值最大的一个支LPs，在LPs的解中任选一不 符合整数条件的变量xj，其值为bj，构造两个约束条件xj≤[bj]和 xj≥[bj]+1。将两个约束条件分别加入问题LPs，得两个后继规划问 题LPs1和LPs2。不考虑整数条件求解这两个后继问题，以每个后 继问题为一分支标明求解结果。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

4.5.2 选址问题
【例4-9】某公司计划在本市东、南、西、北四区建立销售部门，初 步考虑后有10个位置Ai(i=1,2,3…10)可供选择，考虑到各地区居民消 费的水平及居民居住密集度，设定： 在东城区由A1、A2、A3三个点至多选择两个； 在西城区由A4、A5两个点中至少选一个； 在南城区由A6、A7两个点中至少选一个； 在北城区由A8、A9、A10三个点中至少选二个； Ai各点的投资金额及每年可获利润由于地点不一样而不同，预测情 况如表4-7所示： 表4-7地区利润表 单位：万元
该整数规划的数学模型为：
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.6 工件排序问题
再加上约束条件：xij为0-1变量，对i=1,2,3,4。以上就组成了 此整数规划问题的数学模型。
我们将此模型输入WinQSB软件中，得到如下结果： x21=1,x12=1,x33=1,x44=1,其最小目标函数值为70，也就是说安排 乙干A工作，甲干B工作，丙干C工作，丁干D工作，这时消耗的 时间最少，即70小时。
表4-8 产品资源需求量表
资源 原材料/吨 劳动力（人/月） 机器设备（台/月） 产品A 2 2 1 产品B 4 3 2 产品C 8 4 3
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.3 固定成本问题

此问题的数学模型如下：
把上述模型输入WinQSB软件中，得到如下结果：最大目 标函300，最优解为x1=100, x2=0, x3=0, 也就是说生产100台 A产品可获取最大利润300万元。
整数规划在经济管理中的应用
整
数
4.5.1
4.5.2
• 装载问题 • 选址问题 • 固定成本问题 • 指派问题
规
划
4.5.3 4.5.4 4.5.5 4.5.6
• 投资问题
• 工件排序问题
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.1 装载问题
【例4-8】某公司准备用集装箱托运甲、乙二种货物，而这二种货物 每件的体积、重量、可获取利润及体积和重量托运限制如表4-6所示。 又知甲种货物至多托运4件，乙种货物最多托运5件，问两种货物各 托运多少件，可使获得利润最大，建立其数学模型。
表4-6 货物信息表
货物 每件体积（立方米） 每件重量（千克） 每件利润（百元）
甲 乙
托运限制
195 273 1365
4 40 140
2 3
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.1 装载问题

解：设x1,x2分别为甲、乙两种货物的托运件数，其数学模型建 立如下：
整 数 规 划 在 经 济 管 理 中 的 应 用

整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.4 指派问题

约束条件：

因为m不一定等于n,当m>n时，即人多于任务时，就有人没有任 务，所以前面m个约束条件都是小于等于1，这就是说每人至多 承担一个任务，而后面的n个约束条件说明每项工作正好有一 个人承担，所以都是等于1。
整 数 规 划 在 经 济 管 理 中 的 应 用
24 18 19 17
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.4 指派问题

解：引入0-1变量xij,并令： xij
为使总的消耗时间为最少，写出目标函数：
每人只能完成一项工作，其约束条件如下：
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.4 指派问题

每项工作只能由一个人来完成，其约束条件如下：
整 数 规 划 在 经 济 管 理 中 的 的安排中，有n项不同的任务，有m个人分别承担 这些任务，但由于每个人特长不一样，完成各种任务的效率也 不相同。现假设必须指派每个人去分别完成一项任务，怎么样 把n项任务指派给m个人，使得完成n项任务的总效率最高，这 就是指派问题。 对于有m个人n项任务的一般指派问题，设： xij 并设cij为第i个人去完成j项任务的成本（如所需时间、费用 等），则一般指派问题的模型可以写成：
4.5.2 选址问题

解：设0-1变量 这样我们可建立如下数学模型：
约束条件如下：
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.3 固定成本问题
【例4-10】某工厂生产三种类型的产品A、B、C，所用的资源为：原材料、劳动力 和机器设备。生产每个产品的资源需求量如表4-8所示。不考虑固定成本，每种产 品A、B、C的利润分别为4万元、5万元、6万元，可使用的材料总量为500吨，劳动 力300人/月，机器100台/月。此外，如果工厂开通该产品的生长线，不管生产多少 个A、B、C产品，工厂都需要付出一定量的固定成本，具体如下：A产品为100万， B产品为150万，C产品为200万元。现在要制定一个生产计划，使其获得利润最大。
a11 产品1 机床1 a21 产品2 机床1 a32 产品3 机床2 a22 机床2 a33 机床3 a13 机床3 a14 机床4 a24 机床4
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.6 工件排序问题

解：设xij表示产品i在机床j上的开始加工的时间（i=1, 2, 3 ; j=1, 2, 3, 4）。 为了容纳二种相互排斥的约束条件，对于每台机床，分别 引入0-1变量：
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.5 投资问题

此问题的数学模型如下：
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.6 工件排序问题
【例4-13】用4台机床加工3件产品。各产品的机床加工顺序，以及 产品i在机床j上的加工工时aij见表4-11。由于交货期要求，产品2的 加工总时间不得超过d。现要求确定各件产品在机床上的加工方案， 使在最短的时间内加工全部的产品。 表4-11 机床加工信息表
A1 投资额 100 A2 120 A3 150 A4 80 A5 70 A6 90 A7 80 A8 140 A9 160 A10 180
利润
36
40
50
22
20
30
25
48
58
61
投资总额不超过720万元，请问应选择哪几个销售点，使年利润最大？
整 数 规 划 在 经 济 管 理 中 的 应 用
整 数 规 划 在 经 济 管 理 中 的 应 用
4.5.5 投资问题


【例4-12】某公司在以后五年内考虑给以下项目投资，已知： 项目A：从第一年到第四年年初需要投资，并于次年回收本利 115%，但要求第一年投资最低金额为4万元，第二、三、四年 不限； 项目B：第三年初需要投资，到第五年末能收回本利128%，但 规定最低投资额为3万元，最高金额为5万元。 项目C：第二年年初需要投资，到第五年末能收回本利140%， 但规定其投资额为2万元或4万元，6万元、8万元。 项目D：五年内每年年初可购买公债，于当年归还，并加息6%， 此项目投资金额不限。 该部门现有10万元，问它应该如何确定给这些项目的投资金额， 使到第五年末拥有的资金本利总额为最大？
4.5.4 指派问题
【例4-11】有四个人甲、乙、丙、丁，每人分别去完成四项不同的 工作，每人做各项工作所消耗的时间如表4-9所示，问应该如何指 派工作，才能使总消耗的时间最短？ 表4-9 每人工作消耗时间表
时间/ 工
小时 作
工人 甲 乙 丙 丁
A
B
C
D
15 19 26 19
18 23 17 21
21 22 16 23