当前位置：文档之家 › 0-1线性规划模型

0-1线性规划模型

  • 格式：ppt
  • 大小：446.50 KB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

第四讲 0 1整数线性规划要点

第四讲 0 1整数线性规划要点


? ??
x25 、? 项x1目3和4只能选中一项 x3i 、? 项0,1目5被i ?选1中,2,的? 前,5提是项目 1被选中;如何
在 满足上述条件下选择一个最好的投资
解：设 xi为决方策案变，量使（投i资? 1收,2益,?最,5大)
?1 投资第i个项目
xi ? ?
?0 不投资第i个项目
项目
1 2 3 4
整数规划建模举例
练习1 ：组合投资问题。
某财团有 B 万元的资金，经过其考察选中 n个投资
项目，其中第 j个项目需投资金额为 a j 万元，预
计获利 c j（ j ? 1,2..., n）万元，由于种种原因，
有两个附加条件：第一，项目 2和项目3至少选择一
个；第二项目 5，6，7恰好选择两个。问应如何选
例1：一个旅行者要到某地作两周的带包旅行 ,装背包时,他 发现除了已装的必需物件外,他还能再装5公斤重的东西.他 打算从下列4种东西中选取,使增加的重量不超过5公斤又 能使使用价值最大.这4种东西的重量和使用价值( 这里用打 分数的办法表示价值) 如下表所示,问旅行者应该选取哪些 物件为好？
解：建立模型为 max Z=6x 1 ? 7 x 2 ? 3 x3 ? 9 x4
在 满足上述条件下选择一个最好的投资
解：设 xi为决方策案变，量使（投i资? 1收,2益,?最,5大)
?1 投资第i个项目
xi ? ?
?0 不投资第i个项目
项目
1 2 3 4
投资额 （万元） 210 300 100 130
投资收益 （万元） 150 210 60 80
Z表示投资效益
5
260
180
max=150*x1+210*x2 +60*x3+80*x4+180* x5; 210*x1+300*x2+100 *x3+130*x4+260*x5 <=600; x1+x2+x3>=1; x3+x4=1; x5<=x1; @bin(x1); @bin(x2); @bin(x3); @bin(x4); @bin(x5);
运筹学-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规划问题中，分支定界法将问题分解为多个子问题，每个子问题对应一种指派 方案。算法通过不断排除不可能的解来缩小搜索范围，最终找到最优解。
0-1整数型线性规划在消防站布局中的应用

0-1整数型线性规划在消防站布局中的应用

ｌ ■
０１ — 整数型 线性 规划在 消 防站布局 中 的应用
宋江涛 杨艳军
河北 廊坊 ０５０ ） ６ ０ ０ （ 中国人民武装警察 部队学院
［ 要］ 摘 针对 目前我 国城 市现 有消防站数量少 ，责任面积面积大 ，资金短缺 等一系列 问题 ，结合消防站布局 的影响因素 ，运用整 数型线性规划理论 ，提 出一些
域 的边 界 ，结 合消 防站 的责 任面 积 划分 出不 同 的区域 ，使 消 防站所 在 区域 和 临近 区域 为其所 能达 到 的最大 责任面 积 。其优化 模 型如下 ：
｝ ｛ ｍｉＩ ： ￡ ｎ＋
∑ ≥， ， ｌ 】 ＝２ …
ｆ ０ ＝（ １ ， 溅 ０２１ ｉ ， ． ・ ＝Ｉ ＂ ２ ．， ， ＝１ ２ Ｓ
（ ）最 大覆盖 模 型 。对 于 一些老 城 区， 随着城 区 改造 工程 的进行 ， 二
已有 消 防站布 局 不均 匀 ，不 能满足 城市 消 防发 展 需求 的 问题 日益 严 重 ，这
就要 求我 们对 现 有消 防站 进行 改 建和搬 迁 ，重 新布 置 消防 力量 ， 以达 到 充 分利 用现 有 消防 站的 资源 ，使 其所 覆盖 的总的 责任 面积 最 大的 目的 。其优
一
其 中Ｓ 模 型 中消 防站 要覆 盖 的项 目， 即需要 有 消防 站 或临 近消 防站 为
的 区域 ：ｃ 是在 区域 ｊ 置 消防 站 的费用 ； 若在 区域 ｊ ｊ 设 设置 消 防站￣ ｘ＝ ， Ｊｊｌ 否Ｎ ｘ＝ ￣若 区域ｉ ｊ 邻或 者 ｉｊ Ｊｉ＝ ，否 ￣ａｊ ０ ｊ０ ，相 ＝ ，￣ａ ｊｌ ］ １ｉ＝ 。
在城 市 消防规 划过 程 中，消 防站布 局 是一项 非常 重要 的 内容 。我 国城 市 消 防 站 的布 局是 以接 警 起 ５ｉ 其 中ｌ ｉ为 接警 出车 ，４ ｉ为 行 驶 时 ｍ ｎ（ ｍｎ ｍｎ 间 ）内到达 责任 区 的最远 点为布 点依 据 的。 随着社 会 经济 和城 市规 模 的不 断 向前发展 ，我 国不少 城 区存在 的消 防站 布 局不合 理 、责 任 区面积 过 大等 状 况 目益突 出 ，如广州 市平 均一 个消 防站责 任 面积为 ２ｋ ０ ９ ｍ，而上海 市 竟达 到 １ｌｍ。消防 站布 局 的一 系列 问题 导致 在 火灾 发 生 时， 消防 人员 和 车辆 ２ｋ 不能及 时 到达 火灾现 场 ，贻 误 了战机 ，对 保 障城 市建 设和 人 民生命 财 产 的
用Lingo求解整数(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线性规划模型

0-1线性规划模型


思考题3:
在选课策略问题中如果一个学生在满 足学校有关选课规定条件下,希望毕 业时所学课程获得的学分数尽可能多, 试给出他(她)的一个选课方案.
选课策略问题②的数学模型
选课策略问题②的数学模型与选课策略问 题①的数学模型的约束条件完全一样; 只是目标函数不同.要求”选课门数少 而学分多”意味着同时要求两个决策目 标:
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0; 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1];
[x z]=bintprog(f,A,b,Aeq,beq)
用Matlab函数bintprog求解这个问题时,
与前面求解选课策略问题①时的 A,b,Aeq,beq数据完全一样,只需把f改为
f=-0.1[8 5 5 2 5 2 -1 -1 2];
后,再执行行命令bintprog=(f,A,b,Aeq,beq) 即可得出
最优解 x=[1 1 1 1 1 1 1 0 1], 目标函数最小值 z=-2.8.
所以,混合接力队的最优组合问题的数 学 模型是下列0-1线性规划问题: Min z=j=14i=15cijxij s.t. j=14xij1,i=1,…,5 i=15xij=1,j=1,…,4 xij{0,1},i=1,…,5,j=1,…,4
这类线性规划问题的特点是决策变量只 取值1或0,故称为0-1线性规划问题.
★我们可以证明 此问题恰有两个解.
证:如果我们再把x4=1作为约束条件(表 示为 -x4-1),求得最优解x=[1,1,1,1,1 1,1,0,0],但对应最优目标值已不是6, 而是7.说明,此解与上面二解不同,不 是选课策略问题①的最优解.再注意观 察:上面两个最优解恰有一个分量,第4 分量,同时为0,由此可见(没有第4分量 为1的最优解),选课策略问题①只有上 述两个解.
用Lingo求解整数(0-1)规划模型.

用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规划

整数线性规划及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)，但是其结果常依赖于初值的选择。 实践表明，本例仅当初值非常接近上面方法算出 的最优解时，才能得到正确的结果。
整数规划与01规划

整数规划与01规划


. y j
1, 0,
采用第 j种方式，即x j 0， 不采用第 j种方式，即x j 0
于是目标函数
min z (k1 y1 c1x1) (k2 y2 c2 x2 ) (k3 y3 c3x3 )
23
0-1型整数规划解法之一（过滤隐枚举法）
解0-1型整数规划最容易想到的方法，和一般整数规 划的情形一样，就是穷举法，即检查变量取值为0或1 的每一种组合，比较目标函数值以求得最优解，这就 需要检查变量取值的2n个组合。对于变量个数n较大 （例如n>10），这几乎是不可能的。因此常设计一些 方法，只检查变量取值的组合的一部分，就能求到问 题的最优解。这样的方法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然， 对有些问题隐枚举法并不适用，所以有时穷举法还是 必要的。
24
例6
Max
z 3x1 2x2 5x3
x1 2x2 x3 2
x1 x1
4x2 x2 , x3 0或1
求解思路及改进措施：
1.
先试探性求一个可行解，易看出
且相应的目标函数值为 z 3
(
x1,
x2
,
x3
)
(1,
0,
0)
满足约束条件，故为一个可行解，
z 为 。
14
小结（续）
z z ii）用观察法找问题A的一个整数可行解，一般可取 xj 0, j 1,L , n 试探，求得其目标函数值，并记作 。以 * 表示问题的最优目标 函数值；这时有 z z* z
其次，进行迭代。
第一步：分枝，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以[bj]
表示小于bj的最大整数。构造两个约束条件: x j [bj ] x j [bj ] 1
第2章 0-1规划

第2章 0-1规划


用自编函数itgm： [r1,r2,ex1,ex2]=itgm(g,a,b,aq,bq) 定出决策变量x1，x2，x3的取值范围： x1：0~3 x2：0~2 x3：0~2
下面用枚举法求解：
k=1; for x1=0:3 for x2=0:2 for x3=0:2 q=[x1 x2 x3]';p=a*q; if p<=b z(k)=f*q; v(k,:)=q'; k=k+1; end end end end [zm,mi]=max(z); x=v(mi,:); zv=[z',v];
解得： ex =1 fv =53
x= 0 1 0 1 0 0 0 0 1
则当x1=0，x2=1，x3=0，x4=1，x5=0， x6=0，x7=0，x8=0，x9=1时，目标函数取 得最小值53。
例2-4 新产品研制，某工厂计划试制4种新产品A1、A2、 A3、A4。现有科研经费40万元，科技人员60名。各新产 品的试制费用、所需科技人员及预期的年利润如表2-1所 示。如果研制产品A2必须先研制产品A1，但产品A1的研 制与产品A2无关。另外该厂想至少研制其中的两种新产 品。问决策者应如何决定研制计划，使该厂获得利润最 大？
表2-6
货物编号i
1
2
3
单位重量（t）
3
4
5
单位价值ci
4
5
6
解：设第i种货物装载件的数量为xi（i=1,2,3），则所述 问题可表为：
max z 4x1 5x2 6x3
s.t.
3x1 4x2 5x3 10
xi
0, xi为整数(i=1,2,3)
f=[4,5,6]; a=[3,4,5]; b=10;
第4章 线性整数规划

第4章 线性整数规划


线性整数规划的概念 例：用集装箱装运甲、乙两种货物，每种货物每包的体积、 重量和收益见下表。集装箱体积为 24m3 ，允许的最大 重量 14 吨，问每个集装箱应装两种货物各多少包才能
使收益最大?
货物 甲 乙 每包体积 (m3) 5 4 每包重量 (吨 ) 2 5 收益 (元/包) 1000 1500
线性整数规划的概念
二、线性整数规划的数学模型
在线性规划模型：
max S CX AX b s .t . X 0
中，若增加自变量取整数约束条件，则可得到线性整数 规划的数学模型：
max S CX AX b s.t . X 0且为整数
解：①解原问题的松弛问题P0： max S 40 x1 90 x2
9 x1 7 x2 56 s.t .7 x1 20 x2 70 x , x 0 1 2
分枝定界法 可用图解法求解。最优解为xl=4.809，x2=1.817，S=355.89 根据松弛问题的最优解可以确定原问题的目标函数值的 上界为S =355.89或 S =355，下界为 S =0（由于目标函数的 系数均为整数且大于0）。 ②将P0分解为两个子问题Pl和P2(分枝)
P3 的最优解为 x1=4 ， x2=2 ， S=340 ，因已得到一个整数 解，即原问题的一个可行解，故原问题目标函数下界 为：S=340。 P4的最优解为x1=1.428，x2=3，S＝327.12，S4 327
分枝定界法
因S4 S，故没有必要继续对 P4分枝，应将 P4剪掉(称为剪枝 )。
线性整数规划的概念
三、整数规划的解法概述
由于对变量的整数约束限制了通常的连续型方法的应 用，因此，人们在刚接触整数规划问题时，往往会产 生两种原始的求解设想： ①因为纯整数规划的可行解是有限的，因此，可采用一 一比较的方法(穷举法)找出最优解； ②先不考虑整数约束，解相应的连续型问题 ( 松弛问题 ) ， 然后用“四舍五入”的办法凑得一个较好的整数解作 为最优解。 这两种设想往往是行不通的。穷举法效率太低，只有 当可行解较少时才能行得通，当可行解很多时，需要 花很长的时间。凑整法不一定能得到问题的最优解。
0-1型整数线性规划模型理论

0-1型整数线性规划模型理论

0-1型整数线性规划模型理论(1) 0-1型整数线性规划0-1型整数线性规划是一类特殊的整数规划,它的变量仅取值0或1.其模型如下:T min ..01(1,2,,)j f s t x j n =⎧⎨=⎩c xAx =b 取或 其中()T 12,,,,n c c c =c ()T 12,,,,n x x x =x (),ij m na ⨯=A ()T 12,,,.mb b b =b 称此时的决策变量为0-1变量,或称二进制变量.在实际问题中,如果引进0-1变量,就可以把各种需要分别讨论的线性(或非线性)规划问题统一在一个问题中讨论了.(2) 求解0-1型整数线性规划的分支界定法Matlab 指令x = bintprog(f,A,b): 求解0-1型整数线性规划,用法类似于linprog.x = bintprog(f,A,b,Aeq,beq): 求解下述线性规划问题:T min ,z =f x ≤Ax b ,≤Ax b ,⋅≤Aeq x beq ,x 分量取0或1.x = bintprog(f,A,b,Aeq,beq,x0): 指迭代初值x0,如果没有不等式约束,可用[]代替A,b 表示默认,如果没有等式约束,可用[]代替Aeq 和beq 表示默认;用[x,fval]代替上述各命令行中左边的x,则可得到最优解处的函数值fval.例如：求解0-1型整数线性规划模型:1min ni i Z x ==∑()()()12345356894679123471256758129232200..20002001(1,2,,9)j x x x x 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 j ⎧-++++≤-⎪-++++≤-⎪⎪-+++≤-⎪⎪--+≤⎪-≤⎪⎨--+≤⎪⎪-≤⎪-+≤⎪⎪--+≤⎪⎪==⎩或用Matlab 软件编程可解得1236791x x x x x x ======,其他变量为0,共六门课,满足所给条件, Matlab程序代码如下：c = ones(1,9);a =[-1,-1,-1,-1,-1,0,0,0,0;0,0,-1,0,-1,-1,0,-1,-1;0,0,0,-1,0,-1,-1,0,-1;-1,-1,2,0,0,0,0,0,0;0,0,0,1,0,0,-1,0, 0;-1,-1,0,0,2,0,0,0,0;0,0,0,0,0,1,-1,0,0;0,0,0,0,-1,0,0,1,0;-1,-1,0,0,0,0,0,0,2];b = [-2;-3;-2;0;0;0;0;0;0];A = [5 4 4 3 4 3 2 2 3];x = bintprog(c,a,b)f = A*x运行结果：Optimization terminated.x =111111f =20。

第四节 0-1规划

max S ci xi
i 1 n
ai x i b i 1 xi 0 或 1
n
另例 某公司拟在市东、西、南三区建门市 部，拟议中有七个位置 Ai 可供选择，规定
1、在东区，A1 , A2 , A3 中至多选两个； 2、在西区，A4 , A5 中至少选一个； 3、在南区，A6 , A7 中至少选一个。
若选用Ai ，则设备投资估价 bi 元，每年可 获利 ci 元．三个区投资总额为 B 元，则选择 哪几个位置可使年利润最大？ 解
1 令 xi 0
，选择 Ai ，不选择 Ai
该问题的数学模型为如下的0-1规划问题：
max Z ci xi
i 1 7
7 bi xi B i 1 x1 x2 x3 2 s .t x4 x5 1 x6 x7 1 xi 0或1
求解0-1规划的方法
将变量的可能取值 显枚举法： 的全部组合一一列 举进行计算并比较 找出最优值
将变量的可能取值 隐枚举法： 的部分组合一一列
枚举(穷举)法
举进行计算并比较 找出最优值
例 求解0-1
规划问题
2 x1 3 x2 x3 2 4 x1 x2 +x3 4 x1 x2 1 x , x , x 0或1 1 2 3
x y1 3 y2 5 y3 7 y4 y y y y 1 2 3 4 1 y , y , y , y 0或1 1 2 3 4
（2）若 x1≤5，则 x2≥0，否则 x2≤8;
引入0-1变量y，并设M是充分大的数，则
x1 5 yM x 5 (1 y ) M 1 x 2 yM x 8 (1 y ) M 2 y 0或1

线性规划模型

研究模型中常数数据变动时解的变化。
（1）模型中常数数据不精确
（2）模型中常数数据可能发生变化
价值变动
min z cx s.t. Ax b x0
11/43
资源总量变动
敏感性分析
max z 60d 30t 20c 8d + 6t + c <=48 4d + 2t + 1.5c <= 20 d + 1.5t + 0.5c <=8 t <= 5
mn
满足约束条件的解称为可行解，所有可行解的集合 称为可行域 ，满足最优目标的解称为最优解 决策变量为整数时，称为整数线性规划
决策变量取0或1时，称为0-1线性规划
7/43
线性规划问题的解
线性规划问题的可行域是一个凸多边形；
线性规划问题如果存在最优解，则最优解必在可行域的
顶点处达到。
单纯形法:
约束条件右端变化一个单位时目标函数变化量，只对紧约 决策变量改变一个单位时目标函数的改变量，只有非基变 量有值 束有值
12/43
敏感性分析
Objective Coefficient Ranges Current Allowable Allowable Coefficient Increase Decrease 60.00000 0.0 8.000000 30.00000 60.00000 0.0 20.00000 2.500000 INFINITY Righthand Side Ranges Current Allowable Allowable RHS Increase Decrease 48.00000 INFINITY 2.000000 20.00000 1.333333 8.000000 8.000000 1.000000 3.000000 5.000000 INFINITY 2.000000

0-1规划


The Assignment Problem 指派问题
现实生活之中， 现实生活之中，我们经常遇到指派人员 做某项工作的情况。 做某项工作的情况。指派问题的许多应用都 用来帮助管理人员解决如何为一项将要开展 进行的工作指派人员的问题。 进行的工作指派人员的问题。其他的一些应 用如为一项任务指派机器、 用如为一项任务指派机器、设备或者是工厂
二、引入0-1变量的实际问题
1. 投资场所的选定——相互排斥的计划 例 某公司拟在市东、西、南三区建立门市部。拟议中有7个 位置(点)Ai (i=1，2，…，7)可供选择。规定： 在东区，由A1，A2，A3三个点中至多选两个； 在西区，由A4，A5两个点中至少选一个； 在南区，由A6，A7两个点中至少选一个。 如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元， 但投资总额不能超过B元。问应选择哪几个点可使年利润 为最大?
D）可能出现以下情况： ）可能出现以下情况： 每行均有（ ）元素，则在有（ ） ① 每行均有（0）元素，则在有（0）位置构成最 优解中x ； 优解中 ij=1； 所有0元素均有直线覆盖 但记（ ）的个数<m 元素均有直线覆盖， ② 所有 元素均有直线覆盖，但记（0）的个数 个，转⑶。 元素， ③多于两行和两列存在未被直线覆盖的0元素，即 多于两行和两列存在未被直线覆盖的 元素 存在0元素的闭回路 元素的闭回路， 存在 元素的闭回路， 则沿 回路顶点每间隔一个0记 回路顶点每间隔一个 记（ ） ，同时作直线覆盖该列的 元素； 元素；
解题时先引入0-1变量xi (=1,2，…，7)
1, 当Ai点被选用 令 xi = i = 1,2,⋯,7 0, 当Ai点没有被选用 7 于是问题可列成：
目标函数： max z = ∑ ci xi

运筹学课件第四节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求解工具

0-1整数规划

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

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

0—1型整数规划的的数学模型为：目标函数 n n x c x c x c z Min Max +++= 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型整数规划模型建立其相应的模型。

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整数规划是一种重要的优化工具，可以应用于各种实际问题中。

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

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

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

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

核对输入数据正确之后,键入下列行命令:
[x z]=bintprog(f,A,b,Aeq,beq)
由屏幕最后显示结果得:
最优解 x1=x2=x5=x6=x7=x8=1, x3=x4=x9=0 目标函数最小值 z=6 即应该选修微积分,线性代数,应用统计, 计算机模拟,计算机编程,预测理论等6 门课,最小选课门数是6.
Min z=j=19xi.
⑴
其次,某些课有先修课的要求,例如,数据 结构的先修课是计算机编程,这意味着 x4=1蕴涵x7=1,这个条件可表示为x4x7或 x4-x70. ⑸ 同理,最优化方法的先修课是微积分和线 性代数的条件可表示为x3x1,x3x2,此二 式可合并为一个不等式
2x3-x1-x20. 另外有 2x5-x1-x20 x 6-x 7 0 x8-x5 0 2x9-x1-x20 ⑹ ⑺ ⑻ ⑼ ⑽
Min z=j=19xi Max w=5x1+4x2+4x3+3x4+4x5+3x6+2x7+2x8+3x9
具有多个决策目标的规划称为多目标规划, 前面讲的只有一个目标的规划称为单目 标规划.所以,选课策略问题②的数学模 型是满足约束条件⑵-⑽并有双目标 Min z和 Max w 的0-1线性规划.
所以,选课策略问题①的数学模型就是:只 取值0或1的9个决策变量x1,…,x9,满足 约束条件⑵-⑽,并使目标函数⑴取最小 值的0-1线性规划模型.
选课策略问题①数学模型求解
首先,把约束条件⑵-⑷标准化为
-x1-x2-x3-x4-x5-2 -x3 -x5-x6 -x8-x9-3 -x4 -x6-x7 -x9-2 ⑵ ⑶ ⑷
0-1线性规划模型
在实际优化问题中存在一类所谓的分派 问题,其含义如下:有若干项任务,每项 任务必须有一人且只能有一人承担,每 人也只能承担其中一项,不同人员承担 不同任务的收益(或成本)不同.优化目 标是:怎样分派各项任务使总收益最大 (或总成本最小). 本节通过若干个实际的分派问题,说明 如何建立这类优化问题的数学模型,并 用Matlab求出最优解及对应的目标函数 最优值,同时对结果作一些分析.
函数linprog(f,A,b,Aeq,beq)使用方法
首先,(必要的话)改变z中所有系数的符 号把”Max z”化为”Min z”;把””化 为””. 其次,输入具体的f(=c),A,b,Aeq,beq. 最后执行行命令: [x z]=bintprog(f,A,b,A eq,beq) 则输出的x即为最优解;z(或-z)即为目 标函数最小(大)值.
思考题1:
在校运会报名时,发现队员b4的蛙泳 成绩有较大退步,只有115"2;而队员 b5训练努力自由泳有明显进步,达到 57"5.
问组成接力队的方案应作如何调整?
B 选课策略问题
问题:某大学规定,运筹学专业学生毕业时 必须至少修过2门数学课,3门运筹学课 和2门计算机课.这些课的编号及信息如 下表所示. ① 给出毕业时选课门数最少的一个方案. ② 给出毕业时选课门数少而学分多的一 个方案.

Min y=0.7z-0.3w =-0.1(8x1+5x2+5x3+2x4+5x5+2x6-x7-x8+2x9)
用Matlab函数bintprog求解这个问题时, 与前面求解选课策略问题①时的 A,b,Aeq,beq数据完全一样,只需把f改为
f=-0.1[8 5 5 2 5 2 -1 -1 2]; 后,再执行行命令bintprog=(f,A,b,Aeq,beq)

函数bintprog(f,A,b,Aeq,beq)使用范围

函数linprog(f,A,b,Aeq,beq)用来求解 一般的标准型0-1线性规划:
Min z=cTx s.t. Axb, Aeqx=beq x=0或1
其中,约束条件除若干不等式Axb外,还 有若干等式Aeqx=beq,A,b;Aeq,beq分别 代表二者的系数矩阵及右端向量.若置 A=[],b=[],则不等式全缺省;若置 Aeq=[],beq=[],则等式全缺省.
思考题3:
在选课策略问题中如果一个学生在满 足学校有关选课规定条件下,希望毕 业时所学课程获得的学分数尽可能多, 试给出他(她)的一个选课方案.
选课策略问题②的数学模型
选课策略问题②的数学模型与选课策略问 题①的数学模型的约束条件完全一样; 只是目标函数不同.要求”选课门数少 而学分多”意味着同时要求两个决策目 标:

A 混合接力队的最优组合问题
• 问题:某学院准备从5名游泳队员中选择4 人组成学院的接力队,参加校运动会的4 100混合泳接力赛.5名队员b1,…,b5的4种 泳姿(蝶,仰,蛙,自由)a1,…,a4的百米平 均成绩cij,i=1,…,5;j=1,…,4如下表所示. 应如何选择4人组成最优的接力队?
所以,混合接力队的最优组合问题的数 学 模型是下列0-1线性规划问题: Min z=j=14i=15cijxij s.t. j=14xij1,i=1,…,5 i=15xij=1,j=1,…,4 xij{0,1},i=1,…,5,j=1,…,4 这类线性规划问题的特点是决策变量只 取值1或0,故称为0-1线性规划问题. Matlab的函数bintprog专门用来求解01线性规划,下面介绍此函数的使用范围 及使用方法,其理论基础从略.
其次,输入数据
A=[-1 -1 -1 -1 -1 0 0 0 0;0 0 -1 0 -1 -1 0 -1 -1;0 0 0 -1 0 -1 -1 0 -1;-1 -1 2 0 0 0 0 0 0; 0 0 0 1 0 0 -1 0 0;-1 -1 0 0 2 0 0 0 0; 0 0 0 0 0 1 -1 0 0;0 0 0 0 -1 0 0 1 0; -1 -1 0 0 0 0 0 0 2]; b=[-2 -3 -2 0 0 0 0 0 0],Aeq=[];beq=[]; f=[1 1 1 1 1 1 1 1 1];
cij(秒) b1 b2 b3 b4 a1 66.8 75.6 87 58.6 a2 57.2 66 66.4 53 a3 78 67.8 84.6 59.4 a4 70 74.2 69.6 57.2 a5 67.4 71 83.8 62.4
问题分析
要求从5名队员选择4人,每人一种泳姿 且4人泳姿各不相同,使接力队成绩最好. 容易想到的办法是穷举法,组成接力队 的方案共5!=120种,逐一计算并作比较 即可找出最优方案.显然,这不是解决这 类问题的有效办法,随着问题规模变大, 穷举法的计算量将是无法接受的. 一个好的办法是:用0-1变量表示一个队 员是否入选接力队,从而建立这个问题 的0-1规划模型,再借助数学软件求解.
思考题2:
在选课策略问题①中,如果一个学生 因对最优化方法特有兴趣而把此课定 为必选,仍然希望毕业时所学课程门 数尽可能少,试给出他(她)的一个选 课方案.
关于解的唯一性

一般来说,线性规划问题,包括0-1线性 规划问题的解都不是唯一的,例如对选 课策略问题①,我们先求出一个最优解 x=[1,1,0,0,1,1,1,1,0]; 后又在思考题 5-5中求得另外一个最优解 x=[1,1,1,0,0 1,1,0,1],它们对应的最优目标函数值相 等(=6).说明对应选课策略问题①的0-1 线性规划至少有两个的解★,说明它的解 不唯一.
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0; 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1]; [x z]=bintprog(f,A,b,Aeq,beq)
即可得出 最优解 x=[1 1 1 1 1 1 1 0 1], 目标函数最小值 z=-2.8. 即选修除预测理论外的8门课,共计28学分.
思考题4:
在选课策略问题②中如果一个学生觉 得学分数和课程数是二五和七五开, 试给出他(她)的一个最优选课方案.
作业:请根据我校的选课政策,给出你专
业的一位同学的一个最优选课方案.

建立0-1线性规划模型
引入0-1变量xij,若队员bj参加泳姿ai的比 赛,记xij=1,否则记xij=0.根据组成接力 队的要求,应满足两个约束条件: ① 每人至多入选4种泳姿之一,应有 j=14xij1,i=1,…,5 ② 每种泳姿必须有一人入选 i=15xij=1,j=1,…,4 当队员bj入选泳姿ai时,其成绩为cijxij,于 是接力队的成绩可表为z= j=14i=15cijxij,这就是问题的xi=1(0)表示选修(不选)按上表中编号 顺序的9门课程的第i门课. 问题①决策目标为选修课程门数最少,即
其约束条件包括 首先,每人最少要选2门数学课,3门运筹学 课和2门计算机课,按表中课程类别划 分可将此约束表示为
x1+x2+x3+x4+x52 x3+x5+x6+x8+x93 x4+x6+x7+x92 ⑵ ⑶ ⑷
★我们可以证明
此问题恰有两个解.
证:如果我们再把x4=1作为约束条件(表 示为 -x4-1),求得最优解x=[1,1,1,1,1 1,1,0,0],但对应最优目标值已不是6, 而是7.说明,此解与上面二解不同,不 是选课策略问题①的最优解.再注意观 察:上面两个最优解恰有一个分量,第4 分量,同时为0,由此可见(没有第4分量 为1的最优解),选课策略问题①只有上 述两个解.
双目标规划的一种处理方法
把双目标归结为一个单目标,即令 y=z+(1-)w,为闭区间[0,1]中任一 数,并取决策目标为(Max w=Min(-w)) Min y=z-(1-)w 值的大小体现决策者对每个目标的重 视程度,例如,某同学觉得学分数和课程 数是三七开,故把取为0.7,决策目标 为