当前位置：文档之家 › 运筹学 整数规划案例

运筹学 整数规划案例

  • 格式：ppt
  • 大小：212.00 KB
  • 文档页数：19

下载文档原格式

  / 19

合集下载

《运筹学》之整数规划

《运筹学》之整数规划

…
Bn
…
X1n
…
X2n
……
…
Xnn
指派问题：分配要求
分配 B1 B2 … Bn 工作数
A1
X11
X12
… X1n
∑X1j
A2
X21
X22
… X2n
∑X2j
…
…
…
……
…
An 人数 要求
Xn1 ∑Xi1 1
Xn2 ∑Xi2 1
… Xnn … ∑Xin …1
∑Xnj
要求 1 1
… 1
指派问题：模型
n n
X1 1
P1:(1,9/10 X2 2 X2 3 P12: (0,3) Z=9
原问题的最优解（1，2） Z=10。
指派问题
设有n 个人A1, A2, …An,要分派去做n件事B1, B2… Bn,要求每一件事都 必须有一个人去做,而 且不同的事由不同的人去做.已知每个人Ai做每 件事Bj的效率(如劳动工时或成本,或创造的价值 等)为Cij,问应如何进行指派(哪个人做哪件事),才 能使 工作效益最好(如工时最少,或成本最低,或 创造的价值最大)?
乙
19 23 22 18
丙
26 17 16 19
丁
19 21 23 17
指派问题：思考问题
1、人数比工作数多怎么处理？ 2、人数比工作数少，模型会怎
样变化? 3、计算机求解方法？
特殊约束的处理
➢互斥约束 ➢矛盾约束 在建立数学模型时，有时会遇到相 互矛盾的约束，模型只要求其中的 一个约束起作用。
12 8
x5
6 相机
2 4
x6
7 设备
4 10
x7

运筹学——.整数规划与分配问题

运筹学——.整数规划与分配问题

2.4 匈牙利法实例(2)
第二步：找出矩阵每列的最小元素，再分别从各列中减去。
必定满足：bij = aij–ui–vj
0 11 2 0 0
8 0 3 11 0
7 5 0 11 10 4 2 5 0 9 5 0 5 0
8 2 5 0 5 4 3 0 0 11 4 5
二、分配问题与匈牙利法
2.3 匈牙利法
分配问题可以用单纯形法或运输表求解。 库恩(W.W.Kuhn)于1955年提出了指派问题的解 法，他引用了匈牙利数学家康尼格(D.Kö nig)一 个关于矩阵中零元素的定理：系数矩阵中独立0 元素的最多个数等于能覆盖所有0元素的最少直 线数。这个解法称为匈牙利法。
二、分配问题与匈牙利法
2.2 分配问题实例(1)
例：有一份中文说明书，需要译成英、日、德、 俄四种文字。现有甲、乙、丙、丁四人，他们 将中文说明书译成不同语种的说明书所需时间 如下，问应指派何人去完成工作，使所需总时 间最少? 人员
任务 译成英文 译成日文 译成德文 译成俄文 甲 乙 丙 丁 7 8 11 9 2 15 13 4 10 4 14 15 9 14 16 13
一、整数规划的特点及作用
1.2 0-1整数规划
某公司拟在市东、西、南三区建立门市部。拟 议中有7个位置（点）Ai供选择。规定
在东区，由A1，A2，A3三个点中至多选两个； 在西区，由A4，A5两个点中至少选一个； 在南区，由A6，A7两个点中至少选一个。
如选用Ai点，设备投资估计为bi元，每年可获利 润估计为ci元，但投资总额不能超过B元。 问：应如何选址，可使年利润为最大？
第一步：找出每 行的最小元素， 每行对应减去这 个元素。

运筹学第五章整数规划

运筹学第五章整数规划

分解 ai0 , j和 bi0 成最大整数与正分数之和：
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:21
xi0 ai0 , j x j bi0 xi0 ( Ni0 , j f i0 , j )x j Ni0 f i0 xi0 Ni0 , j x j Ni0 f i0 f i0 , j x j
S1
x2 2
B: x1=2,x2=23/9 Z=41/9
x2 3
D: S12 x1=33/14,x2=2 Z=61/14
S11
无可行解
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:15
对S12分枝：
构造约束：
x1 3
X
2 5
4
和
x1 2
3
3 10 A( , ) 2 3
形成分枝问题S121 和S122，得解E和F
形成松弛问题2
浙江理工大学 经济管理学院
管理运筹学
wxj
Page:24
CB XB 3 x1 -1 0 0 x2 x4 x6
3 -1 0 0 x1 x2 x3 x4 1 0 1/7 0 0 0 0 0 1 -2/7 0
0 x5 2/7 3/7
0 x6 0 0 0 1 0
b 13/7 9/7 31/7 -6/7
首先不考虑变量的整数约束，求解相应的线性规划问题：
z0
Max z = CX AX = b X0
D
C
下界
O Ir
Max z = CX AX = b xr Ir X0 Max z = CX AX = b xr Ir+1 X0

管理运筹学案例演示混合整数规划

管理运筹学案例演示混合整数规划

1 2 3 4 5 6 7 8 9 10 11 J CPM/PERT
B Integer Programming
1234567
K Inventory Models
C Zero One Programming
1234567
L Queueing Theory
D Goal Programming
12345678
H Decision Theory
Q Game Theory
I Network Models
ESC Exit to Dos
123
总目录
例1.(投资问题 )某厂要制订一个产品宣传计划，可利用的广告渠 道有三种：电视、广播、杂志。市场调研的结果如下表所示。该 厂计划用于广告费用不超过 16万元。此外还要求：（ 1）受到广 告影响的妇女至少要有200千人；（2）电视广告费用不超过10万 元；（3）白昼电视至少要订 3个广告，热门时间至少 2个广告； （4）广播和杂志上的广告数都应在5到10之间。该厂如何制订一 个广告计划使受到影响的总人数最多。
每个广告的费用（千元）
电
白昼时间
8
视
热门时间
15
广杂 播志
63
每个广告影响总人数（千人）
40
90
50 2
每个广告影响妇女数（千人）
30
40
20 1
解：设电视白昼时间的广告个数为 x1、电视热门时间的广告个 数为 x2、广播的广告个数为 x3、杂志的广告个数为 x4。
该广告计划模型为：
max z ? 40x1 ? 90x2 ? 50x3 ? 2x4
金属板吨劳动力人月机器设备台月小号容器中号容器大号容器不考虑固定费用每种容器售出一只所得的利润分别为4万元5万元6万元可使用的金属板有500吨劳动力有300人月机器有100台月此外不管每种容器制造的数量是多少都要支付一笔固定的费用

割平面法-运筹学整数规划

割平面法-运筹学整数规划

第二节 分枝定界法(Branch and Bound method)
引言：穷举法对小规模的问题可以。大规模问题则不行。
一、基本思想和算法依据
基本思想是：先求出相应的线性规划最优解，若此解不 符合整数条件，则其目标函数的值就是整数规划问题最优值 的上界，而任意满足整数条件的可行解的目标函数值将是其 下界（定界），然后将相应的线性规划问题进行分枝，分别 求解后续的分枝问题。如果后续分枝问题的最优值小于上述 下界, 则剪掉此枝; 如果后续某一分枝问题的最优解满足整数 条件，且其最优值大于上述下界，则用其取代上述下界，继
s .t
2 x1 x1 , x 2
x2 0
6
x1 , x 2取整数
19
解: 1 求解相应的线性规划得
cj
4
CB
XB
b
x1
0
x3
20
4
0
x4
6
2
检验数
0
4
0
x3
8
0
4
x4
3
1
检验数
-12
0
3
x2
8 /3
0
4
x1
5 /3
1
检验数
-4 4 /3
0
3
0
0
x2
x3
x4
5
1
0
1
0
1
3
0
0
3
1
-2
1 /2
-3x3 - x4 -3 引 得入松弛变量x5，将其加入到原规划的约束条件中，利用上述最终1表5
cj
1
CB
XB
b
x1
0
x3
1

第六章 运筹学 整数规划案例

第六章 运筹学 整数规划案例

第六章整数规划6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。

1、 max z=3x1+2x2S.T. 2x1+3x2≤122x1+x2≤9x1、x2≥0解：2、 min f=10x1+9x2S.T. 5x1+3x2≥45x1≥8x2≤10x1、x2≥06.2 求解下列整数规划问题1、 min f=4x1+3x2+2x3S.T. 2x1-5x2+3x3≤44x1+x2+3x3≥3x2+x3≥1x1、x2、x3=0或1解：最优解（0，0，1），最优值：22、 min f=2x1+5x2+3x3+4x3S.T. -4x1+x2+x3+x4≥2-2x1+4x2+2x2+4x2≥4x1+x2-x2+x2≥3x1、x2、x3、x3=0或1解：此模型没有可行解。

3、max Z=2x1+3x2+5x3+6x4S.T. 5x1+3x2+3x3+x4≤302x1+5x2-x2+3x2≤20-x1+3x2+5x2+3x2≤403x1-x2+3x2+5x2≤25x1、x2、x3、x3=正整数解：最优解（0，3，4，3），最优值：474、min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19约束条件x1 + x2+x3≤30x4+ x5＋x6-10 x16≤0x7+ x8＋x9-20 x17≤0x10+ x11＋x12-30 x18≤0x13+ x14＋x15-40 x19≤0x1 + x4+ x7+x10+ x13＝30x2 + x5+ x8+x11+ x14＝20x3 + x6+ x9+x12+ x15＝20x i为非负数（i=1,2…..8）x i为非负整数（i=9,10…..15）x i为为0－1变量（i=16,17…..19）解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：8606.3 一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：公司办公会决定选择原则如下：（1）B5、B3和B7只能选择一个。

运筹学导论第八版8整数线性规划

运筹学导论第八版8整数线性规划
c 1 x 1 c 2 x 2 c n x n ,其 中 c j 0 ,j 1 ,2 , n .
上例中，对所有的 j，cj=1. 如果 cj 表示位置 j 安装 的费 用，那么这些系数就是这些费用值而不再是1.
习题
MobileCo公司拿出1500万美元，最多建造7个发射台来覆盖15个 相邻社区中尽可能多的人口。下表给出了每个发射台可以覆盖 的社区以及建造这个发射台的费用以及社区人口。确定出需要 建设哪几个发射台。
由上例看出，
将其相应的线性规划的最优解“化整”来解原整数线 性规划，虽是最容易想到的，但往往不可行。
化整后不见得是可行解；或虽是可行解，但不一定是 最优解。
因此有必要对整数线性规划的解法进行专门研究。
此类问题为整数线性规划(Integer Linear Programming ， ILP)，整数线性规划是最近几十年来发展起来的规划论 中的一个分支。
有部分变量取小数，这不符合实际，若采用舍入方法，则 x1= x5=1，这意味着5个项目都要选择，显然是不可行解，
对于采用“是否”决策问题，舍入法不可行。
习题
某唱片公司与一位新的歌手签约录制8首歌曲，这8首歌曲 的时间长度分别为8,3,5,5,9,6,7,12分钟，公司希望将所有的 歌曲分配在磁带的两面，使得两面的歌曲时间长度尽量相 同。请建立整数规划模型，求出最优解。
发射台
覆盖社区
1
1，2
2
2，3，5
3
1，7，9，10
4
4，6，8，9
5
6，7，9，11
6
5，7，10，12，14
7
12，13，14，15
各个社区人口数目
建造费用(百万) 3.6 2.3 4.1 3.15 2.8 2.65 3.1

管理运筹学案例演示混合整数规划

管理运筹学案例演示混合整数规划

? ?
1 1
? ?
y4
?
1
??x1, x2, x3, x4 ? 0, yj ? 0 , j ? 1,2,3,4
用QM软件求解结果如下：
最优方案 :装配线A生产100件,装配线 B生产1400件,装配线 C 生产1000件,装配线D生产1500件;
例3.(固定成本问题)高压容器公司制造小、中、大三种尺寸的金属 容器，所用资源为金属板、劳动力和机器设备，制造一个容器所 需所需的各种资源的数量如下表：
?8x1 ? 15x2 ? 6x3 ? 3x4 ? 160 ??30x1 ? 40x2 ? 20x3 ? x4 ? 200
???8x1x1??315x2 ? 100
? ?
x2
?
2
?5 ? ?5
? ?
x3 x4
? 10 ? 10
?? xj ? 0 , j ? 1,2,3,4 , 整数
用QM软件求解结果如下：
使用计算机软件包求解(附件1)
A Linear Programming
1 2 3 4 5 6 7 8 9 10 11 J CPM/PERT
B Integer Programming
1234567
K Inventory Models
C Zero One Programming
1234567
L Queueing Theory
每个广告的费用（千元）
电
白昼时间
8
视
热门时间
15
广杂 播志
63
每个广告影响总人数（千人）
40
90
50 2
每个广告影响妇女数（千人）
30
40
20 1
解：设电视白昼时间的广告个数为 x1、电视热门时间的广告个 数为 x2、广播的广告个数为 x3、杂志的广告个数为 x4。

运筹学 第五章 整数规划

运筹学 第五章 整数规划

M是足够大的整数，y 是0-1变量
14
f(x)-5 0
f(x) 0
(1)
(2)
-f(x)+5 M（1-y)
f(x) My
(3)
(4)
当y=1时,(1)(3)无差别,(4)式显然成立;
当y=0时,(2)(4)无差别,(3)式显然成立。
以上方法可以处理绝对值形式的约束
f(x) a (a>0)
31
5.1 分枝定界法 （Branch and Bound Method)
原问题的松驰问题： 任何整数规划（IP），凡放弃某些约束 条件（如整数要求）后，所得到的问题 （P） 都称为（IP）的松驰问题。 最通常的松驰问题是放弃变量的整数性 要求后，（P）为线性规划问题。
32
去掉整数约束,用单纯形法 IP LP
23
解法概述
当人们开始接触整数规划问题时，常会有 如下两种初始想法： 因为可行方案数目有限，因此经过穷举 法一一比较后，总能求出最好方案，例如， 背包问题充其量有2n种方式，实际上这种 方法是不可行。
设想计算机每秒能比较1000000个方式，那 么比较完260种方式，大约需要360世纪。
24
先放弃变量的整数性要求，解一个 线性规划问题，然后用“四舍五入” 法取整数解，这种方法，只有在变量 的取值很大时，才有成功的可能性， 而当变量的取值较小时，特别是0-1规 划时，往往不能成功。
Yes xI* = xl*
xl*
判别是否整数解
No 去掉非整数域 多个LP ……
33
分枝定界法步骤
一般求解对应的松驰问题，可能会出现 下面几种情况：
若所得的最优解的各分量恰好是整数， 则这个解也是原整数规划的最优解，计 算结束。

运筹与决策PPT：整数规划

运筹与决策PPT：整数规划

案例2： California制造公司问题－ Excel求解
多个决策变量
0-1变量
相依决策
互斥方案
案例2： California制造公司问题－ 灵敏度分析
Capital Spent 100 <=
Capital Available
100
Total Profit ($millions)
10
取整约束
G 12 SUMPRODUCT(UnitProduced,UnitProfit)
6.2 整数规划问题的分类
▪ 纯整数规划问题：
– 所有决策变量均为整数
▪ 混合整数规划问题（MIP）：
B
C
3 NPV ($millions)
LA
4
Warehouse
6
5
6
Factory
8
7
8 Capital Required
9
($millions)
LA
10
Warehouse
5
11
12
Factory
6
13
14
15
Build?
LA
16
Warehouse
0
17
<=
18
Factory
1
19
20
Total NPV ($millions)
原因分析
▪线性规划的可分性假设
–线性规划的决策变量必须允许在满足一定函数 约束与非负约束下取任意实数。
TBA公司的问题由于决策变量只能取整 数，故不满足可分性假设。
整数规划的Excel求解模型－ 案例1
B
3
4
Unit Profit ($millions)

运筹学整数线性规划

运筹学整数线性规划
min c x
Ax b s.t.x 0,i 1,2,...,n
xi为整数,i 1,2,...,p
1 整数线性规划问题举例
•例311 某财团有 B 万元的资金，有 n(n 2) 个可以考
虑的投资项目，假定每个项目最多投资一次。其中
第 j 个项目需投资金额为 b j 万元，将会获得的利润
为 c j 万元，问应如何选择项目才能使得获得的总 利润最大？
2 解整数线性规划问题的困难性
LP的可行集合
费用下降方向 LP问题的最优解
ILP问题的最优解
2 解整数线性规划问题的困难性续
• 最优解不一定在顶点上达到 • 最优解不一定是松弛问题最优解的邻近整数解 • 整数可行解远多于松弛问题的顶点;枚举法不可
取 • 解ILP问题要远难于解松弛的LP问题 • 如果松弛的LP问题无解;显然原ILP问题无解 反
bjxj B
j1
x
j
0或 1;
j
1, 2..., n
旅行售货员问题
• 此外;运筹学还有一个著名的问题：
旅行售货员问题TSP
显示问题
2 解整数线性规划问题的困难性
整数规划
min z c x Ax b
s.t.x 0, x为整数
松弛的线性规划问题
min z c x
s.t. xAห้องสมุดไป่ตู้x
0
b
可行解是松弛问题的可行解 最优值大于等于松弛问题的最优值
第一节 整数线性规划问题
• 整数线性规划问题举例 • 解整数线性规划问题的困难性
整数线性规划问题
• 整数线性规划ILP具有下述形式
min c x
Ax b
s .t .
x

运筹学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: 相互排斥的约束条件

运筹学之整数规划

运筹学之整数规划
* X 2 (6,3.75)T 解为:
f 130
* 1
f 2* 135
B1 的解 X1* (5,4)T 是整数最优解,它当然也是问题 A0 问题
* * 的整数可行解,故 A0 的整数最优解 Z f1 130.
即此时可将 Z 修改为:
Z f1* 130
同时问题 B1 也被查清, 成为“树叶”。
题 A0 的最优目标函数值决不会比它小,故可令 Z =0.
3. 增加约束条件将原问题分枝 当问题 A0 的最优解 X 0* 不满足整数条件时,在 X 0* 中任选一个
不符合整数条件的变量.如本例选 x1 5.6,
显然问题 A0 的
整数最优解只能是 x1 5 或 x1 6 ,而绝不会在5与6之间.
规划.
问题 A1
max Z 20x1 10x2
问题 A2
max Z 20x1 10x2
5 x1 8 x2 60 x1 8 s.t x2 4 x1 5 x1 , x2 0, 取整数
5 x1 8 x2 60 x1 8 s.t x2 4 x1 6 x1 , x2 0, 取整数
用 图 解法求出最优解 x1＝3/2, x2 = 10/3 且有Z = 29/6
x2
3
⑴
⑵
(3/2,10/3)
现求整数解（最优解）： 如用“舍入取整法”可得 到4个点即(1，3) (2， 3)(1，4)(2，4)。显然， 它们都不可能是整数规划 的最优解。
3
x1
按整数规划约束条件，其可行解肯定在线性规划问题 的可行域内且为整数点。故整数规划问题的可行解集 是一个有限集，如图所示。

运筹学第五章 整数规划

运筹学第五章 整数规划

2、0-1型变量常用来表示是否处于某个特定状态
例5.6
有三种资源被用于生产三种产品，资源量、产 品单件可变费用及售价、资源单耗量及组织三种产品 生产的固定费用见下表。要求制定一个生产计划，使 总收益最大。
0-1型变量常用来表示两个选项中非此即彼的选择

例5.7 用4台机床加工3件产品。各产品的机床加工顺序，以及产品在机 床上的加工工时见下表，且要求工件二的总工时不超过d。现要求确定 各件产品在机床上的加工方案,使在最短的时间内加工完全部产品.
A 甲 15 B 17 C 21 D 24
乙
丙 丁
19
26 19
23
17 21
22
16 23
18
19 17
解：令 xij=
1 若指派第i 人做第j 事 （i, j=1, …, n） 0 若不指派第i 人做第j 事
每个人只能完 成一项任务
满足约束条件的可行解 也可写成矩阵形式，称 为解矩阵。如例5.9的一 个可行解矩阵是:
每行减该行最小数
0 1 10 2
2 5 1 4
6 4 0 6
9 0 3 0
每列减该列最小数
0 1 10 2
1 4 0 3
6 4 0 6
产品1
产品2
产品3
a11 机床1 a21 机床1
a22 机床2 a32 机床2
a13 机床3
a33 机床3
a14 机床4 a24 机床4
xij表示第i种产品在第j台机床上加工的开始时间。 同一件产品在下一台机床上加工的开始时间不得早 1 同一 于在上一台机床上加工的结束时间 件产品 产品1：x11+a11x13 及 x13+a13x14 在不同 机床上 产品2：x21+a21x22 及 x22+a22x24 的加工 产品3：x32+a32x33 顺序

2.运筹学_整数规划案例

2.运筹学_整数规划案例
1. 投资问题 现有总额为b的资金可用于投资，共有n个项目可 供投资者选择，已知项目j所需投资额为aj，投资后可 得利润cj（j ＝ 1，2，…，n），不妨设b，aj，cj 均是 整数，试问为使所得利润最大，应选取那些项目进行 投资？ 1…对项目j投资 先引入0－1变量xj，令 xj＝ 0…否则 n
设每个月从仓库i运往地区j的产品的货物数量为xij，引入0－ 1变量yi= 1表示在Ai设立仓库，否则不设。 设每个月的总花费为z，则上述问题的数学模型为 Min z＝200x11+400x12+500x13+300x21+250x22+450x23 +600x31+400x32+250x33+300x41+150x42+350x43+45000y1+5000 0y2+70000y3+40000y4 s.t. x11+x12+x13≤1000y1 x21+x22+x23≤1000y2 x31+x32+x33≤1000y3 x41+x42+x43≤1000y4 x11+x21+x31+x41≥600 x12+x22+x32+x42≥700 x13+x23+x33+x43≥800 y2-y4≤0 y1+y2+y3+y4≤3
y3+y4 ≤ 1
工厂选址运输问题
设有n个需求点，有m个可供选择的厂址， 每个厂址只能建一个工厂，在i处建厂，生产 能力为Di，单位时间的固定成本为ai，需求点 j的需求量为bj，从厂址i到需求点j的单位运费 为Cij，问应如何选择厂址才能获得经济上的总 花费最小的方案。

运筹学实验6整数规划

运筹学实验6整数规划

实验六、用EXCEL 求解整数规划用单纯形法求解线性规划问题，最优解可能是整数，也可能不是整数，但在很多实际问题中，要求全部或部分变量的取值必须是整数，如所求的解是安排上班的人数，按某个方案裁剪钢材的根数，生产设备的台数等等。

对于整数解的线性规划问题，不是用四舍五入或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决，如分枝定界法和割平面算法。

这些算法比单纯形法更为复杂，因此，一般的学习者要想掌握整数规划的数学算法有一定的困难。

然而事实上，由于Excel 的[工具][规划求解]可以求解整数规划问题，所以，对于一个真正有志于运用运筹学方法解决生产经营中问题的管理者来说，算法将不是障碍因素。

一、实验目的1、 掌握如何建立整数线性规划模型，特别是0～1逻辑变量在模型中的应用。

2、 掌握用Excel 求解整数线性规划模型的方法。

3、 掌握如何借助于Excel 对整数线性规划模型进行灵敏度分析，以判断各种可能的变化对最优方案产生的影响。

4、 读懂Excel 求解整数线性规划问题输出的运算结果报告和敏感性报告。

二、 实验内容1、 整数规划问题模型该问题来自于《运筹学基础及应用》（第四版）胡运权主编P126习题4.13,题目如下: 需生产2000件某种产品，该种产品可利用A 、B 、C 、D 设备中的任意一种加工，已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如表1所示，问企业应该如何安排设备生产该产品才能使得总的生产成本最少，试建立该问题的数学模型并求解。

该产品可以利用四种不同的设备加工，由于采用不同的设备加工需要支付不同的准备结束费用，而如果不采用某种设备加工，是不需要支付使用该设备的准备结束费用的，所以必须借助于逻辑变量来鉴定准备结束费用的支付。

再设，种设备加工的产品数量为利用第设;4,3,2,1=j j x j⎪⎩⎪⎨⎧=>=）种设备生产（即，若不使用第）种设备生产（即若使用第000,1j j i x j x j y 4,3,2,1=j则问题的整数规划模型为：43214321281624207008009801000min x x x x y y y y z +++++++=⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥≤≤≤≤=+++4,3,2,110,01600120010009002000..443322114321j y x y x y x y x y x x x x x t s j j，或2、 [工具][规划求解]命令求解下面我们用Excel 中的[工具][规划求解]对该问题进行求解。

运筹学——整数规划

运筹学——整数规划

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。不考虑整数条件求解这两个后继问题，以每个后 继问题为一分支标明求解结果。

运筹学实验报告四整数规划

运筹学实验报告四整数规划

2018-2019学年第一学期《运筹学》实验报告（四）班级：交通运输171学号： 1000000000姓名： *****日期： 2018.11.22实验一：用Lingo 软件求解下列整数规划问题（要求附程序和结果）12121212max 25062210,1,2i z x x x x x x x x x i =++≤⎧⎪-+≤⎪⎨+≤⎪⎪≥=⎩且取整数12312323123123123max 232452244,,01z x x x x x x x x x x x x x x x x x =+-++≤⎧⎪+≤⎪⎪+-≤⎨⎪+-≤⎪=⎪⎩或解：例题（左）解题程序及运行结果如下：sets :bliang/1,2/:x,a; yshu/1,2,3/:b;xshu(yshu,bliang):c; endsets data : a=2,1; b=5,0,21; c=1,1 -1,1 6,2; enddatamax =@sum (bliang(i):a(i)*x(i));@for (yshu(j):@sum (bliang(i):x(i)*c(j,i))<=b(j)); @for(bliang(i):@gin(x(i)));Global optimal solution found.Objective value: 7.000000 Objective bound: 7.000000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0Variable Value Reduced CostX( 1) 3.000000 -2.000000X( 2) 1.000000 -1.000000A( 1) 2.000000 0.000000A( 2) 1.000000 0.000000B( 1) 5.000000 0.000000B( 2) 0.000000 0.000000B( 3) 21.00000 0.000000C( 1, 1) 1.000000 0.000000C( 1, 2) 1.000000 0.000000C( 2, 1) -1.000000 0.000000C( 2, 2) 1.000000 0.000000C( 3, 1) 6.000000 0.000000C( 3, 2) 2.000000 0.000000Row Slack or Surplus Dual Price1 7.0000001.0000002 1.000000 0.0000003 2.000000 0.0000004 1.000000 0.000000例题（右）解题程序及运行结果如下：sets:bliang/1,2,3/:x,a;yshu/1,2,3,4/:b;xshu(yshu,bliang):c;endsetsdata:a=2,1,-1;b=2,5,2,4;c=1,3,10,4,11,2,-11,4,-1;enddatamax=@sum(bliang(i):a(i)*x(i));@for(yshu(j):@sum(bliang(i):x(i)*c(j,i))<=b(j));@for(bliang(i):@bin(x(i)));Global optimal solution found.Objective value: 2.000000Objective bound: 2.000000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 0Variable Value ReducedCostX( 1) 1.000000 -2.000000X( 2) 0.000000 -1.000000X( 3) 0.000000 1.000000A( 1) 2.000000 0.000000A( 2) 1.000000 0.000000A( 3) -1.000000 0.000000B( 1) 2.000000 0.000000B( 2) 5.000000 0.000000B( 3) 2.0000000.000000B( 4) 4.000000 0.000000C( 1, 1) 1.000000 0.000000C( 1, 2) 3.000000 0.000000C( 1, 3) 1.000000 0.000000C( 2, 1) 0.000000 0.000000C( 2, 2) 4.000000 0.000000C( 2, 3) 1.000000 0.000000C( 3, 1) 1.000000 0.000000C( 3, 2) 2.000000 0.000000C( 3, 3) -1.000000 0.000000C( 4, 1) 1.000000 0.000000C( 4, 2) 4.000000 0.000000C( 4, 3) -1.000000 0.000000Row Slack or Surplus Dual Price1 2.0000001.0000002 1.000000 0.0000003 5.000000 0.0000004 1.000000 0.0000005 3.000000 0.000000实验二：一、问题重述某学校规定，运筹学专业的学生毕业时必须至少学习过两门数学课、三门运筹学课和两门计算机课。

运筹学 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变量 相互排斥的约束条件。为了统一在一个问题中，引入 变量
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

m
x ij
b
，
j
j
1,2 ,
,n
i1
x ij 0， y i 0 或 1
4.集合覆盖和布点问题
集合覆盖问题也是典型的整数规划问题，在集合 覆盖问题中，一个给定集合（集合一）的每一个元素 必须被另一个集合（集合二）的元素所覆盖。在满足 覆盖集合一所有元素的前提下，集合覆盖问题的目标 是求需要的集合二的元素最少，该问题之所以又称为 布点问题，是因为它常被用于一些公共设施，如：学 校、医院、商业区、消防队等设施的布点问题，解决 如何既满足公共要求，又使布的点最少，以节约投资 费用。
y2-y4≤0
y1+y2+y3+y4≤3
2020/4/1
y3+y4 ≤ 1
工厂选址运输问题 设有n个需求点，有m个可供选择的厂址，
每个厂址只能建一个工厂，在i处建厂，生产 能力为Di，单位时间的固定成本为ai，需求点 j的需求量为bj，从厂址i到需求点j的单位运费 为Cij，问应如何选择厂址才能获得经济上的总 花费最小的方案。
2020/4/1
0-1变量的作用
1…方案j被选中 1. xj＝
0…方案j未被选中
n
2. 从n个方案中必须选中一个： x j 1 j 1 n
3. 从n个方案中最多选中m个： x j m j 1
4. 方案i只有在方案j选中时，才可能被选中：
x xj
2020/4/1
设每个月从仓库i运往地区j的产品的货物数量为xij，引入0－ 1变量yi= 1表示在Ai设立仓库，否则不设。
设每个月的总花费为z，则上述问题的数学模型为
Min z＝200x11+400x12+500x13+300x21+250x22+450x23
+600x31+400x32+250x33+300x41+150x42+350x43+45000y1+5000
于是产生了指派哪个人去完成哪项任务，使 总效率最高，称为指派问题（Assignment Problem）。
2020/4/1
2020/4/1
s.t.
210x1 +300x2 +100x3 +130x4 +260x5 ≤600
x1
+x2
+x3
=1
x3
+x4
=1
x1
-x5 ≥0
x1,
x2,
x 3,
x 4, x 5＝0 或 1
2020/4/1
2. 背包问题
背包问题由来以久，它是从旅行者如何选择放在 背包中的用品引出的。
旅行者可背负的重量有限，但旅行者需要携带的 物品很多，如：食品、水、衣物、帐篷、急救用品等 等，旅行者不可能将所有想携带的物品都统统背上， 他只能选择那些最重要的物品随身携带，又不超过他 可能负担的最大重量，为解决这个问题，旅行者可给 每种物品指定一个重要性系数，他的目标是在小于一 定重量的前提下，使所携带的物品的重要性系数之和 最大。
2020/4/1
例4：解决某市消防站的布点问题：某城市共有6个区，
每个都可以建消防站。市政府希望建设的消防站最少，
但必须满足在城市任何地区发生火警时，消防车要在
15分钟内赶到现场。据实地测定，各区之间消防车行 驶的时间见下表：请帮助该市制定一个最节省的计划。
地区1 地区2 地区3 地区4 地区5 地区6
整数规划建模
应用最广泛的整数规划问题是各种类型的决策问 题，决策者希望模型能回答诸如：是否要执行某些项 目（或某些活动），在什么时候或什么地点执行等决 策问题，回答这类“是—否”或“有—无”问题可借助整 数规划中的0-1整数变量。
0-1整数变量只有两个选择，0由于它在数学上的 特性可以很好的代表“无”或“否”，而1则可以很好地 表“有”或“是”。0-1变量由于它的特殊性也被称为二 制变量、决策变量或逻辑变量。
表3.5消防车在各区行驶距离表
地区1 地区2 地区3 地区4 地区5 地区6 0 10 16 28 27 20 10 0 24 32 17 10 16 24 0 12 27 21 28 32 12 0 15 25 27 17 27 15 0 14 20 10 21 25 14 0
2020/4/1
解：Xj=1表地区设消防站， Xj=0表地区不设消 防站。Z＝消防站总数，则模型如下：
2020/4/1
与0－1变量相关的几个实际问题
1. 投资问题 现有总额为b的资金可用于投资，共有n个项目可
供投资者选择，已知项目j所需投资额为aj，投资后可 得利润cj（j ＝ 1，2，…，n），不妨设b，aj，cj 均是 整数，试问为使所得利润最大，应选取那些项目进行
投资？
1…对项目j投资
先引入0－1变量xj，令 xj＝ 0…否则 n max c j x j
j 1
则可得到如下整数规划问题：
n
a
j
x
j
b
j 1
2020/4/1
x j 0或 1， j 1，2， ， n
2020/4/1
解：
令0-1变量为决策变量，即xi＝1表示选中项目i， 否则xi＝0表示项目i未被选中。则模型可以表示为：
max z= 150x1 +210x2 +60x3 +80x4 +180x5
2020/4/1
设在单位时间内，从厂址i运往需 求点j的产品数量为xij，
1…在i地建厂 引入0－1变量yi=
0…否则
设在单位时间内的总花费为z，则
mn
m
min z
c ij x ij a i y i
i1 j1
i1
上述问题的数学模型为
n
x ij
D
i
y
，
i
i
1,2 ,
，
m
j1
2020/4/1
2020/4/1
2020/4/1
解： 令xi＝1表示登山队员携带物品i，xi＝0表示
不带物品i。则问题可写为：
Max z =20x1+15x2+18x3 +14x4+8x5+4x6+10x7
s.t. 5x1+ 5x2 + 2x3 +6x4+12x5+2x6+4x7≤25 xi=1或0，i=1,2,…,7
0y2+70000y3+40000y4
s.t.
x11+x12+x13≤1000y1
x21+x22+x23≤1000y2
x31+x32+x33≤1000y3
x41+x42+x43≤1000y4
x11+x21+x31+x41≥600
x12+x22+x32+x42≥700
x13+x23+x33+x43≥800
2020/4/1
背包问题应用（作业） 要把7种规格的包装箱装到两辆铁路平板车上去，包装 箱的宽和高相同，但厚度和重量不同，见下表：
每辆车有10.2m长的地方可以用来装箱（类似面包片 ），载重为40吨。C5， C6 ， C7 ，三类包箱所占总空 间（厚度）不超过302.7cm，试建立数学模型，尽量将 这2些020/4/包1 装箱装到平板车上去，使浪费的空间最小。
MinZ=X1+X2+X3+X4+X5+X6 s.t： X1+X2≥1
X1+X2+X6≥1 X3+X4≥1 X3+X4+X5≥1 X4+X5+X6≥1 X2+X5+X6≥1 Xj=0，1；j=1，2，3，4，5，6。
2020/4/1
2020/4/1
5. 指派问题
在生活中经常遇到这样的问题，某单位需要 完成n项任务，恰好有n个人可以承担这些任务， 由于每个人的专长不同，个人完成不同任务的效率 （时间、费用等）也不同。