当前位置：文档之家 › 运筹学 第三章 0-1规划

运筹学 第三章 0-1规划

  • 格式：ppt
  • 大小：403.00 KB
  • 文档页数：21

下载文档原格式

  / 21

合集下载

运筹学 第3章 线性规划问题的计算机求解

运筹学 第3章 线性规划问题的计算机求解
• 百分之一百法则
• 50
74
• 100
78
• 允许增加量是指该系数在上限范围内的 最大增加量。
• 允许减少量是指该系数在下限范围内的 最大减少量。
c • x1系数的上限为100，故 1的允许增加量为
•
上限-现在值=100-50=50
x c • 而 2的下限为50，故 2的允许减少量为
•
现在值-下限=100-50=50
管理运筹学
朱晓辉 管理科学与工程
第三章 线性规划问题的计算机求解
• 3.1 “管理运筹学软件的操作方法
3.2 “管理运筹学”软件的输出信息分析
• 相差值提供的数值表示相应的决策变量的目 标系数需要改进的数量，使得该决策变量有可能 取正数值，当决策变量已取正数值时相差值为零。
• 在目标函数系数范围一栏中，所谓的上限与 下限是指目标函数的决策变量的系数在此范围内 变化时，其线性规划的最优解不变。
c • 其中bj的允许增加（减少）百分比的定义同 i
的允许增加（减少）百分比一样，为bj的增加量 （减少量）除以bj的允许增加量（减少量）所得
到的值。
• 在使用百分之一百法则进行灵敏度分析时，要 注意以下三点：
• （1）当允许增加量（减少量）为无穷大时，则 对于任一个增加量（减少量），其允许增加（减 少）百分比都看成零。
• 在常数项数范围一栏中，所谓上限与下限是指 当约束条件中的常数项在此范围内变化时，与其 对应的约束条件的对偶价格不变。
• 以上讨论计算机输出的关于目标函数系 数及约束条件中常数项的灵敏度分析都是 基于这样一个重要假设：当一个系数发生 变化时，其他系数保持不变。
• 两个或更多的系数发生变化时，怎么来 进行灵敏度分析？

运筹学知识点总结

运筹学知识点总结

运筹学：应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

第一章、线性规划的图解法1.基本概念线性规划：是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。

线性规划的三要素：变量或决策变量、目标函数、约束条件。

目标函数：是变量的线性函数。

约束条件：变量的线性等式或不等式。

可行解：满足所有约束条件的解称为该线性规划的可行解。

可行域：可行解的集合称为可行域。

最优解：使得目标函数值最大的可行解称为该线性规划的最优解。

唯一最优解、无穷最优解、无界解（可行域无界）或无可行解（可行域为空域）。

凸集：要求集合中任意两点的连线段落在这个集合中。

等值线：目标函数z，对于z的某一取值所得的直线上的每一点都具有相同的目标函数值，故称之为等值线。

松弛变量：对于“≤”约束条件，可增加一些代表没使用的资源或能力的变量，称之为松弛变量。

剩余变量：对于“≥”约束条件，可增加一些代表最低限约束的超过量的变量，称之为剩余变量。

2.线性规划的标准形式约束条件为等式（=）约束条件的常数项非负（b j≥0）决策变量非负（x j≥0）3.灵敏度分析：是在建立数学模型和求得最优解之后，研究线性规划的一些系数的变化对最优解产生什么影响。

4.目标函数中的系数c i的灵敏度分析目标函数的斜率在形成最优解顶点的两条直线的斜率之间变化时，最优解不变。

5.约束条件中常数项b i的灵敏度分析对偶价格：约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量。

当某约束条件中的松弛变量（或剩余变量）不为零时，这个约束条件的对偶价格为零。

第二章、线性规划问题在工商管理中的应用1.人力资源分配问题（P41）设x i为第i班次开始上班的人数。

2.生产计划问题（P44）3.套材下料问题（P48）下料方案表（P48）设x i为按各下料方式下料的原材料数量。

4.配料问题（P49）设x ij为第i种产品需要第j种原料的量。

北京科技大学运筹学课件第3章

北京科技大学运筹学课件第3章

x2
D
x1
(39) 的最优表为
5 2 x2 74 x1 3 4
x1 x2 u1
0 0 0 12 1 34
u2
1 2 1 4 1 4
A( 3 , 7 ) 最优解： 4 4
不是整数解
x1
3 7 10 A( , ) Z 4 4 4
C ( 1 ,1 )
S
0 1
最优整数解
x1
3 1 1 u1 u 2 4 4 4 7 3 1 1 0 14 x 2 u1 u 2 4 4 4 (3 在( 2 9) 9)的约束方程中 , x1 , x 2的系数是整数 , 右侧常数项也 是整数， 若 x1 , x 2 取整数 , 则 u1 , u2也一定是整数 .
max z x1 x 2
s .t .
x 2 2或x 2 3
1
2
3
x1
61 14
x1 2 x2 3
9 51 x2 14 14 (3 2) 1 2 x1 x 2 3 x1
max z x1 x 2
s .t .
3 10 29 A( , ) Z 2 3 6 7 23 10 41 C ( 1 , ) B ( 2 , ) Z Z 3 9 3 9 33 D( ,2) 14 61
则((3-2) 2 2)的最优解中, x2应满足 : x2 2或x2 3
( 2 x 2 3不符合整数条件 )
9 51 x1 x2 14 14 (3 4) 1 2 x1 x 2 3
max z x1 x 2
x1 2 0 x2 2
9 51 x2 S5 空集 14 14 (35) 1 2 x1 x 2 3 x1

运筹学基础-整数规划(3)

运筹学基础-整数规划(3)

【例如】某约束为 2x1+5x2-x3≤2或3 2x1+5x2-x3≤2y1+3y2 引入辅助变量y1,y2, 约束化为 y1+y2=1 y1，y2只取0或1
3
整数规划
3、两组条件满足其中一组
若x1≤4,则 x2≥1；否则（即x1>4时）， x2≤3
引入变量定义为：
1 yi 0
第i组条件不起作用 第i组条件起作用
整数规划
【解】
设： xij为学生i在周j值班时间，aij代表学生i在周j 最多值班时间， ci代表学生i的报酬。 安排学生i在周j值排 1 6 5 yij min z ci xij 否则 i 1 j 1 0 2 yij xij aij yij i 1, ,6; j 1, ,5 不超过安排
i 1， 2
又M为任意大的数，则问题可表达为
x1 4 y1M x 1 y M 1 2 x1 4 y2 M x2 3 y 2 M y1 y2 1 y1 , y2只取0或1
4
整数规划
4、用以表示含固定费用的函数
用xj代表产品j的生产量，其生产费用函数通常可表示为：
n j 1
0 x j Myi yi yi 0或1
可以看出当xj=0时，yi=0；而如果yi=1，则必有xj>0
5
整数规划
【应用1】
工厂的各种产品所需要的机时、人工工时、原材料的资源数量 及可用资源的总量、产品的售价和各种资源的价格等因素。有关信 息在下表中给出。
产品A 产品B 资源总量 资源价格（元／单位） 机器（时） 6 8 120 ５ 人工（时） 10 5 100 20 原材料(公斤) 11 8 130 1 产品售价（元） 600 400

运筹学 第三章

运筹学 第三章
st.
中
运用
8
8
现有一批每根长度为L的圆钢，需要截取n种不同长度的零件毛坯，长度为a 的毛坯需要
有m （1,2,….n）段。为了方便，每根圆钢只截取一种长度的毛坯。应当怎样截取，才能使动用的圆钢数目最少？
设使用 根L米长的圆钢来截取 米长的毛坯（1,2,……n）。
设s 为每根L米长的圆钢用来截取 米长毛坯时可以得到的最多段数。
max z=7x +9 x
st.
最优解z=55, x =4, x =3;
用割平面法求解下列整数规划问题
max z=4x +5 x
st.
最优解z=13, x =2, x =1;
用割平面法求解下列整数规划问题
max z=4x +6 x +2 x
st.
最优解z=26, x =2, x =1,x =6;
用割平面法求解下列整数规划问题
设在A 处建住宅x 幢（j=1，2…..n）。
数学模型为
11180302
某公司今后三年内有五项工程可以考虑投资
设
求最优解和投资的最大收益
最优解X＝(1,1,1,0,1)，Z=110万元。
用分枝定界法求解下列整数规划问题
max z=3x +2 x
st.
最优解z=14, x =4, x =1;
用分枝定界法求解下列整数规划问题
-1/2
1
0
1/2
5/2
z
x1
x2
x3
x4
RHS
z
1
0
0
3/35
1/5
89/5
x1
0
1
0
1/35
-3/5

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

运筹学课件第四节0—1型整数规划
T (1,1,...,1) T , 选择（ A1,...An） ( x1 ,...x n ) T : T (1,1,...,0 ) T , 选择（ A1,...A n）
例：固定费用问题 有三种产品被用于生产三种产品，资源量、产品单件费用、 资源消耗量以及生产产品的固定费用。要求制定一个生产计 划，总收益最大。
,先加工某种产品 0 yj （ j 1 ,2 ,3 ,4 ） 1 ，先加工另外产品 机床1:x11+a11≤x21+My1 ; x21+a21≤x11+M(1-y1) 机床2:x22+a22≤x32+My2 ; x32+a32≤x22+M(1-y2) 机床3:x13+a13≤x33 +My3 ; x33+a33≤x13+M(1-y3) 机床4:x14+a14≤x24 +My4 ; x24+a24≤x14+M(1-y4) 当y1=0,表示机床1先加工产品1,后加工产品2;当y1=1,表示机床1先 加工产品2,后加工产品1.
4 求解： 7 C 6 6 6
8
7
9 17 9 12 7 14 9 12
15 12 14 10 8 7 6 10 10 6
第一步 造0 各行各列减其最小元素
0 0 0 0 0
4 3 2 10 3 1 3 6 8 6
11 7 2 0 4
第四节
0—1型整数规划
一、0-1变量及其应用 某些特殊问题，只做是非选择，故变量设置简化为0或1， 1代表选择，0代表不选择。
选取某个特定方案 1, 当决策选取方案 x 0 , 当决策不选取方案 问题含有较多的要素， 每项要素有 2 种选择，用 0 1变量描述。 有限要素 E1, E 2 ,...E n , 每项 E j 有两种选择 A j , A j 1, E j 选择 A j xj 0 , E j 选择 A j

《运筹学》教案-目标规划数学模型

《运筹学》教案-目标规划数学模型第一章：目标规划概述1.1 目标规划的定义与意义1.2 目标规划与其他规划方法的区别1.3 目标规划的应用领域1.4 目标规划的发展历程第二章：目标规划的基本原理2.1 目标规划的基本假设2.2 目标规划的数学模型2.3 目标规划的求解方法2.4 目标规划的评估与决策第三章：目标规划的数学模型3.1 单一目标规划模型3.2 多目标规划模型3.3 带约束的目标规划模型3.4 动态目标规划模型第四章：目标规划的求解方法4.1 线性规划求解方法4.2 非线性规划求解方法4.3 整数规划求解方法4.4 遗传算法求解方法第五章：目标规划的应用案例5.1 生产计划目标规划案例5.2 人力资源规划目标规划案例5.3 投资组合目标规划案例5.4 物流配送目标规划案例第六章：目标规划的高级应用6.1 目标规划在供应链管理中的应用6.2 目标规划在项目管理中的应用6.3 目标规划在金融管理中的应用6.4 目标规划在能源管理中的应用第七章：目标规划的软件工具7.1 目标规划软件工具的介绍7.2 常用目标规划软件工具的操作与应用7.3 目标规划软件工具的选择与评估7.4 目标规划软件工具的发展趋势第八章：目标规划在实际问题中的应用8.1 目标规划在制造业中的应用案例8.2 目标规划在服务业中的应用案例8.3 目标规划在政府决策中的应用案例8.4 目标规划在其他领域的应用案例第九章：目标规划的局限性与挑战9.1 目标规划的局限性分析9.2 目标规划在实际应用中遇到的问题9.3 目标规划的发展趋势与展望9.4 目标规划的未来研究方向10.1 目标规划的意义与价值10.2 目标规划在国内外的发展现状10.3 目标规划在未来的发展方向10.4 对运筹学领域的发展展望重点和难点解析重点环节一：目标规划的数学模型补充和说明：在讲解目标规划的数学模型时，重点关注单一目标规划模型和多目标规划模型的构建。

运筹学——第3章_线性规划问题的计算机求解


变量 下限 当前值 上限
x1
0
50
100
x2
50
100 无上限
从上面可知目标函数中X1的系数的上限为100，故C1
允许增加量为： 上限-现在值=100-50=50；
而X2的下限为50，故C2的允许减少量为： 现在值-下限=100-50=50。
定义Ci 的允许增加(减少)百分比为：Ci 的增加量 (减少量)除以Ci 的允许增加量(允许减少量)的值。
在上题中C1 的允许增加百分比与C2 的允许减 少百分比之和为92％不超过100％，所以当每件产 品Ⅰ利润从50元增加到74元，每件产品Ⅱ利润从 100元减少到78元时，此线性规划最优解仍然为Ⅰ 产品生产50件， Ⅱ产品生产250件(即x1= 50， x2=250)，此时有最大利润为:
74× 50+78× 250=3700＋19500=23200(元)。
为50元，即增加了一个台时数就可使总利润增加50元；
原料A还有50千克没有使用，原料A的对偶价格当然为零，
即增加1千克A原料不会使总利润有所增加；原料B全部使
用完，原料B的对偶价格为50元，即增加一千克原料B就
可使总利润增加50元。
在目标函数系数范围一栏中，所谓的当前值是指在目标函数 中决策变量的当前系数值。如x1的系数值为50，x2的系数值为100。 所谓的上限与下限值是指目标函数的决策变量的系数（其它决策 变量的系数固定在当前值）在此范围内变化时，其线性规划的最 优解不变。例如当c1= 80时，因为0≤80≤100，在x1的系数变化范 围内，所以其最优解不变（此时要固定c2=100)，也即当x1=50， x2=250时，有最大利润。当然由于产品Ⅰ的单位利润由50变为80 了，其最大利润也增加了(最优值变了)，

运筹学-第三章-整数规划


于是，对原问题增加两个新约束条件，将原问题分为两个 子问题，即有
max z 40x1 90x2
max z 40x1 90x2
9x1 7x2 56
s.t
7 x1
20 x2
70
x1 4
x1, x2 0
（LP1）
9x1 7x2 56
和
s.t
7
x1
20
x2
70
（LP2）
x1 5
表 3.1
货物 体积（米 3/箱） 重量（百公斤/箱） 利润（百元/箱）
甲
5
2
20
乙
4
5
10
托运限制 24 米 3
13 百公斤
解： 设x1，x2 分别为甲、乙两种货物的托运箱数，则数 学模型可以表示为：
max z 20x1 10x2
5x1 4x2 24 2x1 5x2 13 x1, x2 0, x1, x2整数
其中，目标函数表示追求最大的卫星实验价值；第1,2个约
束条件表示体积和重量的限制；第3-5个约束条件表示特定的卫
星装载要求,该问题的决策变量是0-1整数变量。
3.2.3隐枚举法 从上面两个例子可以看出，此类型问题是整数规划中的特
殊情形，其中决策变量 xi 的取值只能为0或1，此时变量 xi 称 为0-1变量，这类问题被称为0-1整数规划。对于 xi 的取值的 0-1约束，可以转化成下述整数约束条件：xi 1, xi 0, xi Z
目前对于整数规划问题的求解主要有两种方法：分支 定解法和割平面法。本章仅介绍分枝定界法，该方法在上 世纪60年代由Land Doig和Dakin等人提出，其具有灵活 且便于计算机求解的优点，所以现在已成为解决整数规划 问题的重要方法。下面通过例子说明分支定界方法的算法 思想和步骤。

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

例2 求解0-1规划
编号
max z 3 x1 2 x2 5 x3
s.t. x1 2 x2 x3 2
①
x1 4 x2 x3 2 x1 2 x2 3
② ③
4x2 x3 6
④
xi 0 or 1, i 1,2,3
算法过程：1. 先找出一个可行解，比如（1，0，0）.相应
cnn
称为指派问题 的效益矩阵。
？
定理：将指派问题的效益矩阵的行(列)分别减去该行(列) 的最小元素，得到的新指派问题和原问题的最优解相同. 意义：根据定理,对指派问题可以化简,使 最优值呢? 得其效益矩阵中每一行至少有一个0元素.
这种简化对于求解有何帮助？
任务 A
B
C
D
人员
甲
2
15
13
4
乙
10
在海淀区，由A6,A7中至少选一个. 假设选用Ai点，设备投资估计为bi元，每年获利估计ci元， 但是总投资额不超过B元。问应该选择哪几个点可以使年 利润最大？
➢分析问题
如图，如何确定选择哪些点？有多少种可能？
试一试
枚举 法
A7
A6
海淀区
共有多少情形？
A5 A4
西城区 专门的解法研究 ——隐枚举法.
安排n个人完成n项工作，使总效率最高的问题称为指 派问题或者分派问题(Assignment problem).
例 甲、乙、丙、丁四人去完成A、B、C、D四项工作. 要求每个人只能完成一项工作，每个工作只能一人完成，
他们所需费用如下表，应如何安排工作，使所需总费用最
少？
任务 A
B
C
D
人员
甲
2
10
9
7
乙
任务 A B C D
例 已知效益矩阵
如下，求指派问题 的最小解.
人员 甲 乙 丙
2
10
9
7
15
4
14
8
13
14
16
11
丁
4
15 13
9
00 1 0
0603
最优解
xij= 0 1 0 0 00 0 1
13 0 5 4 4 30 0
10 0 0
0 923
即最优解：甲-C，乙-B，丙-D，丁-A
最优值：28
15
4
14
8
丙
13
14
16
11
丁
4
15
13
9
试利用0-1规划建立数学模型.
任务 A
B
C
D
人员 甲
2
10
9
记
7
为cij
乙
15
4
14
8
丙
13
14
16
11
丁
4
15
13
9
设
1， 当 指 派 第i个 人 完 成 第j项 任 务 xij 0，当不指派第i个人完成第j项任务
矩阵(xij) 44有何特点？
每行(列)有且只有一个为1，其他为0.
练习：已知效益矩阵如下，求指派问题的最小解.
任务 A B C D
人员
甲
15 18 21 24
乙
19 23 22 18
丙
26
17
16
19
丁
19 21 23 17
练习： 求解0-1规划
min z 4x1 3x2 2x3
s.t.
2x1 5x2 3x3 4 4x1 x2 3x3 3
x2 x3 1
xi 0 or 1,i 1,2,3
预习第五章
x6 x7 1
模型综合形式
max z c1 x1 c2 x2 ... c7 x7 s.t. b1 x1 b2 x2 ... b7 x7 B
x1 x2 x3
2
x4 x5 1
x6 x7 1
xi 0或者1, i 1,2,...,7
如何求解？
➢解决问题——隐枚举法
(1)对没有圈的行打∨；对已有∨的行中所有的0元列打∨号； 在对有∨号的列中的0元行打∨号，重复.
(2) 无∨号的行画横线，有∨号的列画纵线(这样得到了覆 盖全部0元的最少直线数).
(3) 找出没有覆盖的最小元，有∨号的行减去最小元，有 ∨号的列加上最小元，得新的效益矩阵.
75
0
2
42
3
0
0
180
53
的目标函数值为3.
➢解决问题——隐枚举法
算法过程：2. 增加约束条件，得到新问题.
max z 3x1 2x2 5x3
s.t .
3 x1
x1 x1
2x2
2x2 4x2
5x3 3
x3 2 x3 2
x1 2x2 3
4x2 x3 6
xi 0 or 1, i 1,2,3
A1
A2
A3
东城区
➢建立模型
设
xi
1,
0,
当点Ai 被选用 当 点Ai 没 被 选 用
i
1,2,...,7
目标函数
max z c1 x1 c2 x2 ... c7 x7
资金限制 三条规定
b1 x1 b2 x2 ... b7 x7 B
x1 x2 x3 2 x4 x5 1
任务 A
B
C
D
E
人员
甲
5
0
2
0
2
乙
2
3
0
0
0
丙
0
10
5
7
2
丁
9
8
0
0
4
戊
0
6
3
6
5
step2：试指派寻找最小解：从只有一个0元的行(列)开始， 给这个0加标志，之后划掉本列(行)中其他的0元.直到所 有的0元都加标志或者划掉.
此时独立0元个数小于矩阵阶数，没有发现最优解.
step3：缩减效益矩阵，增加0元素.
min z
i
cij xij
j
s.t .
xij 1, j 1,2,...,n
i
➢指派问题算法：匈牙利算法思路
xij 1, i 1,2,...,n
j
xij 0 or 1
效益矩阵：将目标函数系数cij排列成矩阵形式
c11 (cij ) ...
cn1
... c1n ... ...
➢建立模型
min z
i
cij xij
j
s.t .
xij 1, j 1,2,3,4
i
xij 1, i 1,2,3,4
j
xij 0 or 1
0-1规划广泛见于生活问题，也是运筹学算法研究
的一个重点。0-1问题大致可以划分为互斥的计划、
互斥的约束条件，固定费用和分派问题等。比如
刚才的经营选址问题就是互斥的计划问题,经典的 背包问题是固定费用问题.
4
14
15
丙
9
14
16
13
丁
7
8
11
9
任务 A
B
C
D
人员
甲
0
13
171
20
乙
6
0
160
191
丙
0
5
73
42
丁
0
1
40
20
从表中就可以发现最优解：甲D，乙B，丙A，丁C. 最优值：28
任务 A
B
C
D
人员
甲
0
13
7
0
乙
6
0
6
9
丙
0
5
3
2
丁
0
1
0
0
结论：如果可以在化简后的效益矩阵中找到n个不同 行不同列的0元（称为独立0元） ，便可容易得到最 优解和最优值.
编号
△ ① ② ③ ④
3. 重复上述的过程，注意随时改进约束条件. （可 在表格上进行）
4. 最优解（1，0，1），最优值8.
➢隐枚举法的改进
重新编排变量顺序，以降低运算量.
max z 3 x1 2 x2 5 x3
s.t. x1 2 x2 x3 2
x1 4 x2 x3 2 x1 2 x2 3
当效益矩阵很大时，观察的方法寻找不同行不 同列的0元不太容易.
化简后的效益矩阵未必恰好存在n个独立0元.
例 已知效益矩阵如下，求指派问题的最小解.
任务 A
B
C
D
E
人员
甲
12
7
9
7
9
乙
8
9
6
6
6
丙
7
17
12
14
9
丁
15
14
6
6
10
戊
4
10
7
10
9
练习：化简此效益矩阵，并判断是否能找到最小解.
step1：化简效益矩阵得.
4x2 x3 6
xi 0 or 1, i 1,2,3
max z 2x2 3x1 5x3
s.t. 2 x2 x1 x3 2
4x2 x1 x3 2 2x2 x1 3
4x2 x3 6
xi 0 or 1, i 1,2,3
这样做有什么好处？ 最小化问题呢？
2 指派问题及其算法
第三章 特殊的整数规划——0-1规划
本次课解决如下问题：
1、0-1规划模型及隐枚举法； 2、指派问题及匈牙利算法.
1 0-1规划模型
例1 某公司拟在市东城、西城、海淀三区建立营业网点。 拟议中有7个位置(点)Ai(i=1,2,…,7)可供选择。规定