0-1型整数规划习题

用Lingo求解整数(0-1)规划模型

要求：
1、建立数学模型， 2、用lingo循环语句编写程序.
上机作业题人员安排问题
某城市的巡逻大队要求每天的各个时间段都有一
定数量的警员值班, 以便随时处理突发事件, 每人连续工作6h, 中间不休息. 如表所示是一天8个班次所需值班警员的人数情况统计:
班次
时间段
人数班次
时间段
人数
1
6:00～9:00
例 4 求函数 z x 22 y 22 的最小值.
例 4 求函数 z x 22 y 22 的最小值.
解: 编写Lingo 程序如下:
min=(x+2)^2+(y-2)^2; @free(x); 求得结果: x=-2, y=2
二、Lingo 循环编程语句
(1) 集合的定义包括如下参数: 1) 集合的名称.
12,8 3,0; enddata
!数据赋值;
max=@sum(bliang(i):a(i)*x(i)); !目标函数;
@for(yshu(j):@sum(bliang(i):x(i)*c(j,i))<=b(j));
!约束条件;
例6：人员选拔问题
队员号码身高 / m 位置队员号码身高 / m 位置
例 2 用Lingo软件求解整数规划问题
min z 2 x1 5 x2 3 x3
4 x1 x2 x3 0
2
x1
4 x2
2 x3
2
x1
x2
x3
2
xi 0 且取整数, i 1, 2, 3
Lingo 程序:
min=2*x1+5*x2+3*x3; -4*x1-x2+x3>=0; -2*x1+4*x2-2*x3>=2; x1-x2+x3>=2; @gin(x1);@gin(x2);@gin(x3);

运筹学 0-1整数规划

x 1 + 2 x 2 − x 3 ≤ 2 (1) x 1 + 4 x 2 + x 3 ≤ 4 (2) ≤ 3 (3) x1 + x 2 4 x 2 + x 3 ≤ 6 (4) x 1 , x 2 , x 3 = 0或1
两个值，解：对于0－1 规划问题，由于每个变量只取，1两个值，一般会用穷举法来解，对于－规划问题，由于每个变量只取0，两个值一般会用穷举法来解，即将所有的0，组合找出，使目标函数达到极值要求就可求得最优解。即将所有的，1 组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。的求得最优解。
每周工时(小时月每周工时小时/月) 小时
B1 0.3 0.7 250
B2 0.2 0.1 100
B3 B31 0.3 0.5 150 B32 0.2 0.4 120
利润（元/件）件 25 40
– 解：设A1、A2产品的生产数量分别为 1、x2件，在不产品的生产数量分别为x 考虑B 相互排斥的情况下，考虑 31和B32相互排斥的情况下，问题的数学模型为
约束条件 x1 . x2. x3 ( 0. ( 0. ( 0. ( 0. ( 1. ( 1. ( 1. ( 1. 0. 0 ) 0. 1. 1. 0. 0. 1. 1. 1) 0) 1) 0) 1) 0) 1) Z值 0 5 －2 3 3 8 1 6 0 2 1 1 Z≥8 (1) 0 －1 (2) 0 1 (3) 0 0 0 1 (4) 过滤条件 Z≥0 Z≥5
m a x z = 2 5 x1 + 4 0 x 2

运筹学与最优化方法习题集

一．单纯性法一．单纯性法1.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 122121212max 25156224..5,0z x x x x x s t x x x x =+£ìï+£ïí+£ïï³î 2.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 12121212max 2322..2210,0z x x x x s t x x x x =+-³-ìï+£íï³î 3.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 1234123412341234max 24564282..2341,,,z x x x x x x x x s t x x x x x x x x =-+-+-+£ìï-+++£íï³î4.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 123123123123123max 2360210..20,,0z x x x x x x x x x s t x x x x x x =-+++£ìï-+£ïí+-£ïï³î 5.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 12312312123max 224..26,,0z x x x x x x s t x x x x x =-++++£ìï+£íï³î6.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 12121212max 105349..528,0z x x x x s t x x x x =++£ìï+£íï³î7.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 16 分）分） 12121212max 254212..3218,0z x x x x s t x x x x =+£ìï£ïí+£ïï³î二．对偶单纯性法二．对偶单纯性法1.灵活运用单纯形法和对偶单纯形法解下列问题（共灵活运用单纯形法和对偶单纯形法解下列问题（共 15 分）分）12121212max 62..33,0z x x x x s t x x x x =++³ìï+£íï³î 2.灵活利用单纯形法和对偶单纯形法求解下列线性规划问题（共灵活利用单纯形法和对偶单纯形法求解下列线性规划问题（共 15 分）分） 121212212max 3510501..4,0z x x x x x x s t x x x =++£ìï+³ïí£ïï³î 3.用对偶单纯形法求解下列线性规划问题（共用对偶单纯形法求解下列线性规划问题（共 15 分）分） 1212121212min 232330210..050z x x x x x x s t x x x x =++£ìï+³ïï-³íï³ïï³î4.灵活运用单纯形法和对偶单纯形法求解下列线性规划问题（共灵活运用单纯形法和对偶单纯形法求解下列线性规划问题（共 15 分）分） 124123412341234min 262335,,,0z x x x x x x x s t x x x x x x x x =+-+++£ìï-+-³íï³î5.运用对偶单纯形法解下列问题（共运用对偶单纯形法解下列问题（共 16 分）分） 12121212max 24..77,0z x x x x s t x x x x =++³ìï+³íï³î6.灵活运用单纯形法和对偶单纯形法解下列问题（共灵活运用单纯形法和对偶单纯形法解下列问题（共 15 分）分） 12121212max 62..33,0z x x x x s t x x x x =++³ìï+£íï³î三．0-1整数规划整数规划1.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 12345123451234512345123345max 567893223220..32,,,,,01z x x x x x x x x x x x x x x x s t x x x x x x x x x x x or =++++-++-³ìï+--+³ïí--+++³ï=î 2.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共 10 分） 12312312323123min 4322534433..1,,01z x x x x x x x x x s t x x x x x or =++-+£ì++³ïí+³ïï=î 3.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共 10 分） 1234512345123451234512345max 20402015305437825794625..81021025,,,,01z x x x x x x x x x x x x x x x s t x x x x x x x x x x =++++++++£ìï++++£ïí++++£ïï=î或 4.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 12345123451234512345max 2534327546..2420,,,,01z x x x x x x x x x x s t x x x x x x x x x x =-+-+-+-+£ìï-+-+£íï=î或 5.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 12341234123412341234min 25344024244..1,,,01z x x x x x x x x x x x x s t x x x x x x x x =+++-+++³ì-+++³ïí+-+³ïï=î或6.7.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 123451234513451245max 325232473438..116333z x x x x x x x x x x x x x x s t x x x x =+--+++++£ìï+-+£ïí-+-³ï 1231231231223max 3252244..346z x x x x x x x x x s t x x x x =-++-£ìï++£ïï+£íï+£ïï=四.K-T 条件条件1.利用库恩-塔克（K-T ）条件求解以下问题（共）条件求解以下问题（共 15 分）分）22121122121212max ()104446..418,0f X x x x x x x x x s t x x x x =+-+-+£ìï+£íï³î2.利用库恩-塔克（K-T ）条件求解以下非线性规划问题。

0-1模型例题

0-1模型例题
以下是一个简单的0-1规划模型例题：
问题描述：某公司生产某种产品，需要经过三个阶段，每个阶段都需要投入一定数量的资源。

目标是在满足市场需求的前提下，最小化总成本。

每个阶段都有一定的生产能力限制，同时市场需求也有限制。

决策变量：
•x1：第一阶段资源投入量（0或1）
•x2：第二阶段资源投入量（0或1）
•x3：第三阶段资源投入量（0或1）
约束条件：
1.第一阶段生产能力限制：x1 <= 1
2.第二阶段生产能力限制：x2 <= 1
3.第三阶段生产能力限制：x3 <= 1
4.市场需求限制：x1 + x2 + x3 >= 1
5.总成本限制：3x1 + 2x2 + x3 <= 10
目标函数：最小化总成本，即 3x1 + 2x2 + x3
这是一个简单的0-1规划问题，可以使用整数规划方法求解。

通过求解该问题，可以得到最优的资源投入组合，从而最小化总成本，满足市场需求。

0-1整数规划模型1专题培训课件

指派问题的数学模型为：
n
n
min Z
c ij x ij
i1 j1

n
x ij 1
( i 1 .2 . .n )
j1

n
x ij 1
( j 1 .2 . .n )
i1

x
ij
取
0或
1(
i,
j
Байду номын сангаас
1 .2 .
.n )

克尼格定理 : 如果从分配问题效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui，从每一列中分别减去(或加上)一个常数vj，得到一个新的效率矩阵[bij]，则以[bij]为效率矩阵的分配问题与以[aij]为效率矩阵的分配问题具有相同的最优解。
xij＝0或1
可见指派问题是0-1 型整数规划的特例。不难发现，指派问题也是运输问题的特例，其产地和销地数都为n，各产地的产量和各销地的销量都为1。
指派问题的求解，最简便易行的方法是匈牙利法。
匈牙利法基于下面的效率矩阵：
（cij）=
c11 c12 … c1n c21 c22 … c2n ……………….
第三步：用最少的直线覆盖所有0元素。 (1)给无◎的行打“√”； (2)给打√行中含有0元素的列打“√”； (3)给打√列中含有◎元素的行打“√”； (4)重复(2)、(3)，直到无新的“√”打出。 (5)给没有打√的行画横线，给打√的列画纵线。
第四步：变换系数矩阵，增加0元素。在未被画线覆盖的其它元素中找出最小元素，各打“√”行减去最小元素，各打“√”列加上最小元素，转第二步。
第一步：变换系数矩阵，使每行每列都出现0元素。 (1) 系数矩阵的各行分别减去各行中的最小元素； (2)所得系数矩阵的各列再分别减去各列中的最小元素。

用Lingo求解整数(0-1)规划模型.

Lingo 程序: max=2*x1+5*x2+3*x3+4*x4;
-4*x1+x2+x3+x4>=0; -2*x1+4*x2+2*x3+4*x4>=1; x1+x2-x3+x4>=1; @bin(x1);@bin(x2);@bin(x3);@bin(x4);
温州大学城市学院
例 2 用Lingo软件求解整数规划问题 min z 2 x1 5 x2 3 x3
温州大学城市学院
注意:
Lingo 默认变量的取值从0到正无穷大,
变量定界函数可以改变默认状态.
@free(x): 取消对变量x的限制(即x可取任意实数值)
例 4 求函数 z x 2 y 2 的最小值.
2 2
温州大学城市学院例 4 求函数 z x 2 y 2 的最小值.
,8
温州大学城市学院
温州大学城市学院
上机作业题
要求：
1、建立数学模型，
2、用lingo循环语句编写程序.
温州大学城市学院
上机作业题
人员安排问题
某城市的巡逻大队要求每天的各个时间段都有一定数量的警员值班, 以便随时处理突发事件, 每人连续工作6h, 中间不休息. 如表所示是一天8个班次所需值班警员的人数情况统计:
成绩甲乙丙丁自由泳 / s 56 63 57 55 蛙泳 / s 74 69 77 76 蝶泳 / s 61 65 63 62 仰泳 / s 63 71 67 62
甲, 乙, 丙, 丁四名队员各自游什么姿势 , 才最有可能取得好成绩?
温州大学城市学院

0-1型整数规划

最优结果为总支付报酬每周727.5元值班方案为：
学生代号 1 2 3 4 5 6 一 6 4 8 5 3 2 6 2 二三 6 6 5 2 6 四五 7
3
例B 清远市下设八个区，下表给出救护车从一个区至另一个区的车程时间（min）该市拟建救护中心，要求各区离救护中心的车程时间必须在8min之内，是为该市提供决策建议：至少建多少个救护中心，建于何处？
(x1,x2,x3) Z值 a
(0,0,0) (0,0,1) (0,1,0) (0,1,1)
0 5 -2 3
√ √
b √ √
c √ √
d 过滤条件 √ Z≥0 Z≥5 √
(1,0,0)
(1,0,1) (1,1,0) (1,1,1)
3 8 1
6
√
√
√
√
Z≥8
按目标函数中各变量系数的大小重新排列各变量最大化问题：由小到大最小化问题：由大到小
max z 5 x3 3 x1 2 x 2 x3 x1 2 x 2 2 ① x3 x1 4 x 2 4 ② st x1 x 2 3 ③ x 4 x 6 ④ 2 3 xi 0或1, i 1， 3 2，
2．相互排斥的约束条件
如果有m个互相排斥的约束条件（<=型）：
ai1 x1 ai 2 x2 ain xn bi
i 1, 2,, m
为了保证这个约束条件只有一个起作用，我们引
入m个0－1变量 yi i 1,2,..., m 和一个充分大的常数M，而下面这一组m+1个约束条件 ai1 x1 ai 2 x2 ain xn bi yi M i 1, 2,, m

整数线性规划及0-1规划

蝶泳仰泳蛙泳自由泳
甲 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)，但是其结果常依赖于初值的选择。实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。

奥鹏[北京交通大学]《管理运筹学》在线作业二-0001满分参考1

北交《管理运筹学》在线作业二-0001
若原问题是一标准型，则对偶问题的最优解值就等于原问题最优表中松弛变量的
（）
A:值
B:个数
C:机会费用
D:检验数
参考选项：C
在灵敏度分析中，某个非基变量的目标系数的改变，将引起某变量的检验数的变化，这个变量是（）
A:基变量
B:非基变量
C:决策变量
D:该非基变量自身
参考选项：D
求解0—1整数规划的方法是（）
A:割平面法
B:分枝定界法
C:隐枚举法
D:匈牙利法
参考选项：C
一般讲，对于某一问题的线性规划与该问题的整数规划可行域的关系存在（）A:前者大于后者
B:后者大于前者
C:二者相等
D:二者无关
参考选项：A
关于图论中的图，以下叙述不正确的是（）
A:图论中点表示研究对象，边或有向边表示研究对象之间的特定关系。

B:图论中的图，用点与点的相互位置，边的长短曲直来表示研究对象的相互关系。

C:图论中的边表示研究对象，点表示研究对象之间的特定关系。

D:图论中的图，可以改变点与点的相互位置。

只要不改变点与点的连接关系。

参考选项：C
对偶求目标函数最小值的线形规划问题，有m个变量n个约束条件，它的约束条件都是______不等式
A:小于
B:大于
C:小于等于
D:大于等于
参考选项：D
1。

运筹学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整数规划中，决策变量只能取0或1的整数值。

0-1整数规划是一类NP-hard问题，通常以优化问题的形式出现。

0-1整数规划在实际生活中有广泛的应用。

它可以用于资源分配、生产计划、物流运输等方面。

下面将通过一个具体的例子来说明0-1整数规划的应用：假设某公司生产两种产品A和B，分别需要使用两种原材料X和Y。

每个单位的产品A需要消耗1个单位的原材料X和3个单位的原材料Y；每个单位的产品B需要消耗2个单位的原材料X和2个单位的原材料Y。

该公司每天可以获得100个单位的原材料X和150个单位的原材料Y。

假设产品A的利润为5元，产品B的利润为8元。

问如何安排生产，使得利润最大化。

首先，我们定义决策变量：设产品A的生产数量为x，产品B 的生产数量为y，决策变量为整数。

则可以列出目标函数和约束条件。

目标函数：maximize 5x + 8y约束条件：1x + 2y ≤ 100 （原材料X的限制）3x + 2y ≤ 150 （原材料Y的限制）x，y为0或1的整数根据上述目标函数和约束条件，可以构建0-1整数规划模型。

然后，可以使用相应的算法求解该模型，确定最优的生产方案，使得利润最大化。

对于这个例子来说，通过计算可以得到最优解为x=25，y=37，即生产25个单位的产品A和37个单位的产品B时，利润最大，为325元。

总结起来，0-1整数规划是一种重要的优化工具，可以应用于各种实际问题中。

通过明确决策变量的整数限制，可以获得最优解，实现最大化或最小化的目标。

在实际应用中，需要结合具体问题的特点和约束条件，构建相应的数学模型，并运用适当的算法求解。

这样可以有效地解决实际问题，提高效率和经济效益。

0-1规划

6
3
6
5
然后划去所在的列的其他0元素，记作Ø。
5 2 0 3 10 8 2 0 5 0 0 0 7 0 2 0 2 4

9
Ø
6
3
6
5
从只有一个0元素的列开始，给这个0元素加圈，记
5 2

3 10 8
2 0 5 0
0 0 7 0
2 0 2 4

9
Ø
6
3
6
5
然后划去所在的行的其他0元素，记作Ø。
任务人员甲乙
E 2 10
J 15 4
G 13 14
R 4 15
丙
丁
9
7
14
8
16
11
13
9
匈牙利算法的步骤：
第一步：使分配问题的系数矩阵经变换，在各行各列中都出现0元素：从系数矩阵的每行元素减去该行的最小元素。再从所得系数矩阵的每列元素减去该列的最小元素。若某行已经有0元素，就不必再减了。
称为过滤性条件。初看起来，增加约束条件需增加计算量，实际减少了计算量。
最优解（1，0，1） Z=8
循环 1 2
(X1,X2,X3)
s.t. 0 0 5
s.t. s.t. s.t. s.t. 1 2 3 4 -1 1 1 0 2 1 5 1 2 6 1 1 0 1 0 1
满足 no yes
Z 值 5
注意：
改进过滤性条件，在计算过程中随时调整右边常数。
价值系数按递增排列。
以上两种方法可减少计算量。
循环 1 2
(X2,X1,X3) s.t. s.t. s.t s.t s.t 满
(0,0,0) (0,0,1)

0-1选址法例题

0-1选址法例题全文共四篇示例，供读者参考第一篇示例：0-1选址法是一种运用动态规划思想解决最优选址问题的方法。

它的基本思想是根据不同位置的成本和收益来选择最优的位置，从而使得整体收益最大化。

在实际应用中，0-1选址法被广泛应用于各种领域，如城市规划、生产布局等。

为了更好地理解0-1选址法的应用，下面我们来看一个例题。

假设有一个城市需要建设若干个服务站，且每个服务站的成本和收益都不相同。

现在要求选择其中的几个位置建设服务站，以达到整体收益最大化的目标。

给定的问题是：总共有n个潜在的服务站位置，每个位置的成本和收益分别为Ci和Pi。

现在需要选择k个位置建设服务站，求这k个位置的成本加上收益的总和的最大值。

为了解决这个问题，我们可以使用动态规划的思想进行求解。

具体的步骤如下：1. 定义状态：我们可以用dp[i][j]来表示在前i个位置选择j个位置建设服务站时，总成本加收益的最大值。

0<=i<=n，0<=j<=k。

2. 状态转移方程：对于dp[i][j]，我们可以分为两种情况来考虑：选择第i个位置建设服务站和不选择第i个位置建设服务站。

具体的转移方程如下：dp[i][j] = max{dp[i-1][j], dp[i-1][j-1]+Pi-Ci}Pi-Ci表示在第i个位置建设服务站的收益减去成本。

3. 边界条件：当i=0或j=0时，dp[i][j]都为0，即没有位置可选或建设的服务站数量为0时，总成本加收益为0。

通过以上步骤，我们可以得到在给定的n个位置中选择k个位置建设服务站时，总成本加收益的最大值。

这个问题可以通过动态规划的方式高效求解，对于大规模的问题也可以有效处理。

0-1选址法是一种非常实用的方法，能够帮助我们在实际应用中做出最优的选择。

通过以上例题的介绍，希望读者能更好地理解和掌握这种方法，进而在实际问题中灵活运用。

【2000字】第二篇示例：0-1选址法是一种常用的数学方法，用来解决一些优化问题，特别是在选址问题上。

0-1规划的应用案例

不考虑固定费用每种容器售出一只所得的利润分别为万元5万元6万元可使用的金属板有500吨劳动力有300人月机器有100台月此外不管每种容器制造的数量是多少都要支付一笔固定的费用
0-1规划的应用
一、投资场所的选择例1、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j＝1，2，3，…， 10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1 ， A2 ，A3 三个点至多选择两个；在西区由A4 ， A5 两个点中至少选一个；在南区由A6 ， A7 两个点中至少选一个；在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每 A A A A A A A A A A 年可获利润由于地点不投资额 100 120 150 80 70 90 80 140 160 180 同都是不一样的，预测利润 36 40 50 22 20 30 25 48 58 61 情况见右表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?
ቤተ መጻሕፍቲ ባይዱ
0-1规划的应用(4)
四、分布系统设计例6．某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在 A2 ， A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小? b) 如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?

整数规划

第五章
概念
整数规划
（整数线性规划）
分枝定界解法
0-1型整数规划指派问题应用
第一节概念
整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。
根据变量的取值性质，又可以分为纯整数规划，混合整数规划，0-1整数规划等。
整数规划是数学规划中一个较弱的分支，目前只能解中等规模的线性整数规划问题，而非线性整数规划问题，还没有好的办法。
第三节

0-1型整数规划
0-1变量的引入 1 采取方案j Xj＝
0
不采取方案j
例1：相互排斥的决策参量
某公司要建立门市部，有七个备选地点：东区：A1A2A3中至多选两个；西区：A4A5中至少选一个南区：A6A7中至少选一个若选用Aj，投资费为bj，年获利为cj，投资总额不超过B。如何定夺方案？
车运 5 4
船运 7 3 45
利润 20 10
乙
托运限制 24
0
y＝
采用车运
采用船运
1
5X1+4X2≤24+yM (1’) 7X1+3X2 ≤ 45+(1-y)M (2’) y＝0或1
当y＝0采用车运，(1’)＝ (1)；(2’)显然成立，是多余条件。当y＝1采用船运，(2’)＝ (2)；(1’)显然成立，是多余条件。
例2 背包问题( Knapsack
Problem)
一个旅行者,为了准备旅行的必须用品,要在背包内装一些最有用的东西,但有个限制,最多只能装b公斤的物品,而每件物品只能整个携带,这样旅行者给每件物品规定了一个“价值”以表示其有用的程度, 如果共有n件物品,第j件物品aj公斤,其价值为cj.问题变成:在携带的物品总重量不超过b公斤条件下,携带哪些物品,可使总价值最大?

0-1整数规划解法

人员
A
B
C
D
E
甲
7
5
9
8
11
乙
9
12
7
11
9
丙
8
5
4
6
8
丁
7
3
6
9
6
戊
4
6
7
5
11
指派问题与匈牙利法
解：1）变换系数矩阵，增加0元素。
7 5 9 8 11 5
9
12
7
11
9

7
8 5 4 6 9 4

7 3 6 9 6 3
4 6 7 5 11 4
11 6
3

8 14 17

6
4
5

3 2 1
5 9 10 0 0
11 6 3 0 0
8 14 17 0 0

6
4
5 0 0
3 2 1 0 0
当人数m小于工作数n时，加上n－m个人，例如
15 20 10 9

6
5
4
7

10 13 16 17
15 20 10 9

6
5
4
7

10 13 16 17

0
0
0
0

指派问题与匈牙利法
3. 一个人可做几件事的指派问题
若某人可做几件事，则将该人化作相同的几个“人”来接受指派，且费用系数取值相同。
例如：丙可以同时任职A和C工作，求最优指派方案。
6 7 11 2 2

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

整数线性规划及0-1规划

x1(x1 80) 0 x2 (x2 80) 0
x1, x2 , x3为非负整数
IP 结果输出
280x1+250x2+400x3< 60000 end
OBJECTIVE FUNCTION VALUE
1)
632.0000
VARIABLE VALUE REDUCED COST
X1
64.000000
-
2.000000
X2
168.000000
-
“gignin3 3”表示“前3个变量为整数”，等价于： gin x1 gin x2 gin x3
模型求解整数规划(Integer Programming,简记
Max z 2x1 3x2 4x3
IPIP可) 用LINDO直接求解
s. t. 1.5x1 3x2 5x3 600 280 x1 250 x2 400 x3 60000
max 2x1+3x2+4x3 st 1.5x1+3x2+5x3<600
模型建立
令xj表示对第j个发展项目的投资数量
n
Max z cj x j j 1 n
s. t. a j xj b j 1
xj 0或1(j=1,2, ,n)
整数线性规划 0－ 1模型 (IP)
整数线性规划及0－1规划
例1 汽车厂生产计划
汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。
x1,x2,, x3=0 或 80 方法1：分解为8个LP子模型
其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：

0-1型整数规划

货物
体积每箱（米3）重量每箱（百公斤）
利润每箱（百元）
甲
乙
托运限制
5 2
4 5
24 13
20 10
第五章：0 -1整数规划
互相排斥的约束条件： 5x1 4 x2 24 用车运的体积约束用船运的体积约束 7 x1 3x2 45
0 用车运 y 1 用船运
至从
2
3
4
5
6
7
8
1 2 3 4 5 6 7
8
9 10
11 12 7
13 13 7 8
14 11 8 7 8
8 17 12 10 14 10
15 14 10 9 16 7 12
解：先根据表整理出若救护中心建于该区时，救护车程 8min内所能覆盖的区，见于下表
救护中心设于该区救护车程8min内所能覆盖的区
不起作用
用船运时y 1 5 x1 4 x 2
7 x1 3x 2 45
不起作用
例：某公司有5个项目列入投资计划，各项目的投资额和期望的投资收益见下表：
项目投资额投资收益
1
2 3 4 5
210
300 150 130 260
160
210 60 80 180
该公司只有600万元可用于投资，由于技术上的原因，投资受到以下约束： 1.在项目1、2和3中必须只有一项被选中； 2.在项目3和4中只能选中一项； 3.项目5选中的前提是项目1必须被选中。如何在上述条件下选择一个最好的投资方案，是投资收益最大？
4 3 6 200 12
300 200
解：设xj是第j种产品的产量，j=1，2，3；再设 1, 若生产第j种产品（即xj>0） j=1，2，3 y 0, 若不生产第j种产品（即xj=0）则问题的模型为

0-1型整数规划习题

合集下载

用Lingo求解整数(0-1)规划模型

运筹学 0-1整数规划

运筹学与最优化方法习题集

0-1模型例题

0-1整数规划模型1专题培训课件

用Lingo求解整数(0-1)规划模型.

0-1型整数规划

整数线性规划及0-1规划

奥鹏[北京交通大学]《管理运筹学》在线作业二-0001满分参考1

运筹学01整数规划

0-1整数规划

0-1规划

0-1选址法例题

0-1规划的应用案例

整数规划

0-1整数规划解法

0—1 型整数规划

整数线性规划及0-1规划

0-1型整数规划

文档推荐

最新文档