当前位置：文档之家 › 0-1整数规划

0-1整数规划

  • 格式：ppt
  • 大小：1.42 MB
  • 文档页数：41

下载文档原格式

  / 41

合集下载

0-1规划

0-1规划

0-1规划0-1规划是决策变量仅取值0或1的一类特殊的整数规划。

在处理经济管理中某些规划问题时，若决策变量采用 0-1变量即逻辑变量，可把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。

目录简介应用范围隐枚举法简介应用范围隐枚举法展开简介0-1规划0-1 Programming一种特殊形式的整数规划。

这种规划的决策变量仅取值0或1，故称为0-1变量或二进制变量，因为一个非负整数都可以用二进制记数法用若干个0-1变量表示。

0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件，因此0-1规划非常适合描述和解决如线路设计、工厂选址、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们所关心的多种问题。

实际上，凡是有界变量的整数规划都可以转化为0-1规划来处理。

由于0-1规划具有深刻的背景和广泛的应用，几十年来一直受到人们的重视。

求解0-1规划的方法主要是隐枚举法（如分枝定界法）。

对一些特殊问题还有一些更加有效的方法，例如对指派问题，用D.柯尼希发明的匈牙利法求解更显方便有效。

应用范围0-1规划主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和分派问题等方面。

互斥计划问题如确定投资项目，选定投资场所，决定投产产品等。

设有几种产品，各产品投产后获得的利润为c j，投资限额为B，规定决策变量xj的取值为1则此0-1规划的数学模型为23式中max表示求极大值；s.t.表示“受约束于”；z是目标函数；aj是各种产品的投资额。

约束条件互斥问题设有m个互相排斥的约束条件（≤型）ai1x1＋ai2x2＋…＋ainxn≤bi(i＝1，2，…，m)为了保证这m个约束条件中只有一个起作用,引入m个0-1变量y i和一个足够大的常数M，构造m＋1个约束条件ai1x1＋ai2x2＋…＋ainxn≤bi＋yiMy1＋y2＋…＋ym＝m－1因为m个yi中只有一个能取0值，所以只有一个约束条件能起作用。

第四讲 0-1整数线性规划

第四讲 0-1整数线性规划
枚举法： 检验可行解： 32次运算 计算目标 函数值：8次
√ √
√ √
√ √
√ √
Z≥0 Z≥5
（1 0 0） 3 （ 1 0 1） 1
（ 1 1 0） 8 （ 0 1 1） 3 （ 1 1 1） 6
× √ √ √ √
最优解： x1 1 ，x2 1 ，x3 1 最优值 Z 6
三
指派问题
1 投资第i个项目 xi 0 不投资第i个项目
1 3 4 5 210 100 130 260 150 60 80 180
2
300
210
Z表示投资效益
投资项目模型： 例1 （投资问题）华美公司有5个项目被列入投资计 划，每个项目的投资额和期望的投资收益见下表： max Z 150 x1 210 x2 60 x3 80 x4 180 x5 该公司只有 600 万资金可用于投资，由于技术上的 300 x2 100 x3 130 x4 260 x5 600 210 x1 x1 x2 x3 1 原因，投资受到以下约束： s.t x1 x4 1 1、2和3中必须有一项被选中 3 、在项目 x2 x1 5 、项目 3和4只能选中一项 i 1,2,,5 x3 i 0,1 、项目5被选中的前提是项目1被选中;如何 在 满足上述条件下选择一个最好的投资 项目 投资额 投资收益 （万元） （万元） 方 案，使投资收益最大 解：设 xi为决策变量（ i 1,2,,5)
当n=4时， 有16变量， 8个约束方程
练习2：现有4份工作，4个人应聘，由于各 Z表示总费用 人技术专长不同，他们承担各项工作所 max Z 3x11 5x12 4 x13 5x14 需费用如下表所示，且规定每人只能做 6 x21 7 x22 6 x23 8x24 一项工作，每一项工作只能由一人承担， 8x31 9 x32 8x33 10 x34 试求使总费用最小的分派方案。 10 x41 10 x42 9 x43 11x44 工作 1 2 3 4 x11 x12 x13 x14 1 人 x21 x22 x23 x24 1 1 3 5 4 5 6 7 6 8 2 x31 x32 x33 x34 1 8 9 8 10 3 x41 x42 x43 x44 1 10 10 9 11 x x x x 1 4 21 31 41 11 s.t x12 x22 x32 x42 1 解： 第i人做第j 件事 xij 1 0 x13 x23 x33 x43 1 x14 x24 x34 x44 1 第i人不做第j 件事 xij 0,1 i=1,2, 3,4; i 1,2, , n j=1,2, 3,4 j 1,2, , n

运筹学 0-1整数规划

运筹学 0-1整数规划

– 一般地，在建立数学模型时，若需从p个约束条件 一般地，在建立数学模型时，若需从 个约束条件 中选择q个约束条件 则可以引入p个 变量 个约束条件， 中选择 个约束条件，则可以引入 个0-1变量
0, yi = 1,
若选择第i个约束 若不选择第i个约束
i = 1,..., p
那么约束条件组
max z = 4 x1 + 5 x 2 + 6 x3 2 x1 + 4 x 2 + 8 x3 <= 500 2 x + 3 x + 4 x <= 300 1 2 3 s.t . x1 + 2 x 2 + 3 x3 <= 100 x1 , x 2 , x3 >= 0
若考虑固定费用就必须引入0—1变量： 变量： 若考虑固定费用就必须引入 变量
第四节 0－1整数规划
一、相互排斥的计划 某公司拟在市东、 南三区中建立门市部， – 例4.6 某公司拟在市东、西、南三区中建立门市部， 有例7个点 个点A ＝ ， ， ， ）可供选择， 有例 个点 i（i＝1，2，…，7）可供选择，要求满 足以下条件： 足以下条件： 1) 在东区，在A1，A2，A3三个点中至多选两个； 在东区， 三个点中至多选两个； 2) 在西区，A4，A5两个点中至少选一个； 在西区， 两个点中至少选一个； 3) 在南区，A6，A7两个点为互斥点。 在南区， 两个点为互斥点。 4) 选A2点必选 5点。 点必选A – 若Ai点投资为 i万元，每年可获利润为 i万元，投资 点投资为b 万元，每年可获利润为c 万元， 总额为B万元 试建立利润最大化的0－ 规划模型 万元， 规划模型。 总额为 万元，试建立利润最大化的 －1规划模型。

0-1整数规划解法

0-1整数规划解法

指派问题与匈牙利法
Ø0 Ø0 3 ◎0 3
1
6
0Ø
2
◎0

3 2 0◎ 0Ø 3


2 0◎ 2 3 Ø0
0◎ 4 4 0Ø 6
总费用为=8+9+4+3+4=28
指派问题与匈牙利法
2. 不平衡的指派问题
当人数m大于工作数n时，加上m－n项虚拟工作，例如：
5 9 10
2 0 4 3 6 2 5 0 4 2 4 1 0 2 5 4 0 3 6 3 0 2 3 1 7
-1 -2
指派问题与匈牙利法
2）试指派（找独立0元素）
2 0 4 2 4 2 5 0 3 0 4 1 0 1 3 4 0 3 5 1 0 2 3 0 5
从只有一个0元素的列开始（画Ø的不计在内），给该列中的0 元素加圈，记作◎；然后划去◎ 所在行的0元素，记作Ø ，表 示此人已有任务，不再为其指派其他任务了。依次进行到最后一 列。
若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，比 较这行各0元素所在列中0元素的数目，选择0元素少这个0元素 加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同 列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为 止。
所有0元素的最少直线数 l 。
注：l 应等于m，若不相等，说明试指派过程有误，回到第2步，另行试 指派；若 l＝m < n，表示还不能确定最优指派方案，须再变换当前的系 数矩阵，以找到n个独立的0元素，为此转第4步。
指派问题与匈牙利法
4) 变换矩阵(bij)以增加0元素
在没有被直线通过的所有元素中找出最小值，没有被直线通过 的所有元素减去这个最小元素；直线交点处的元素加上这个最小 值。新系数矩阵的最优解和原问题仍相同。转回第2步。

整数0-1规划

整数0-1规划

′=x 1=1,
x3′=0 x5′=0 x4′=0
z=4, 可行 z=1 z=-2
z=10,不可行
x2=0 z=6,不可行 x3′=0 x5′=0 z=5,不可行 x4′=0 z=3,不可行 x1=0 z=2,不可行
最优解为x2=0 ， x3′=0 ， x5′=1 ， x4′=1， x1=1 。 于是， 原 问 题 的 最 优 解 为 z*=4 ， x1*=1，x2*=0，x3*= 1-0=1， x4*=1-1=0，x5*=1-1=0
令 x3′=1-x3, x4′=1-x4, x5′=1-x5，得 Max z=2x2+4x3′+5x5′+7x4′+8x1-16 3x2- x3′- 3x5′- 2x4′+3x1≤-2 ① 3x2+2x3′- x5′+ x4′+5x1≤6 ② x2, x3′,x5′,x4′,x1 =0或1
z=8,不可行 x2 =x3′=x5′ = x4
x1 , x2 , x3 0或1
求解0-1型整数规划，可使用分枝定界法。下面 用实例说明： 例 求解0-1型整数规划问题 Max z=8x1+2x2-4x3-7x4-5x5 3x1+3x2+x3+2x4+3x5≤4 5x1+3x2-2x3-x4+ x5≤4 xj=0或1，j=1,2,…,5 变成标准型，要求如下：⑴目标函数求极大化。 对于目标函数为Min z的极小化问题，令z′=-z，使其 变为目标函数为Max z′的极大化问题。⑵目标函数中 所有变量的系数都为正数。如果目标函数中变量xj的 系数为负数，令xj′=1-xj，把模型中的xj用xj′代换。⑶ 变量的排列顺序按变量在目标函数中的系数值从小到 大排列。

0-1型整数规划

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, y 0,
若生产第j种产品（即xj>0） 若不生产第j种产品（即xj=0）
j=1，2，3
应用举例
例A 东方大学计算机实验室聘用4名大学生（代号1、2、 3、4）和2名研究生（代号5、6）值班答疑。已知每人从 周一至周五每天最多可安排的值班时间及每人每h值班的报 酬如下表
在东区，由A1，A2，A 三个点中至多选两个； x3 4 x5 1 在西区，由A4，A5两个点中至少选一个； x x 1
6 7
st.
在南区，由A6，A7两个点中至少选一个。 x 0或1
i

i 1

7
如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元， 但投资总额不能超过B元。问应选择哪个点可使年利润最大？
该公司只有600万元可用于投资，由于技术上的原因， 投资受到以下约束： 1.在项目1、2和3中必须只有一项被选中； 2.在项目3和4中只能选中一项； 3.项目5选中的前提是项目1必须被选中。 如何在上述条件下选择一个最好的投资方案，是投资收益 最大？
解：设
1，项目i被选中 xi 0, 项目i未被选中 只有600万元可用于投资 i 1,2,3,4,5
货物ቤተ መጻሕፍቲ ባይዱ
体 积 每箱（米3） 重 量 每箱（百公斤）
利 润 每箱（百元）
甲
乙
托运限制
5 2
4 5
24 13
20 10
第五章：0 -1整数规划
5 x1 4 x 2 24
7 x1 3x 2 45
0 用车运 y 1 用船运
5 x1 4 x 2 24 yM 7 x1 3x 2 45 (1 y ) M 5 x1 4 x 2 24 yM 7 x1 3x 2 45 (1 y ) M

0-1型整数规划


1
解：引入 0 1变量
令xi 10，，当当AA第i点i点四被没选被节用选用 0- 1整i 1数,2, 规,7划
0-1规划的实际问题： 7
MaxZ cixi i1
建模如下：
1、投资场所的选定－－7 相bi互xi排斥B的计划
例：某公司拟在市东、i1西、南三区建立门市部，拟议中有7个
MaxZ 20x1 10x2
例51x1.某 4厂x拟2 用24集+装(1箱-y托)M运 st.甲的润右72x1、体以表xx,11x乙积及所2 53两、托示xx022种重运。 1货量所问435物、受两+，可限种yM每获制货箱利如物
各得xy托利为1, x0运润2为多为1变整少最量数箱大，？可使获
210x1 300x2 150x3 130x4 260x5 600
s.t.
x1 x3

x2 x4
x3 1
1
在项目3和4中只能选中一项

x5

x1
项目5选中的前提是项目1必须被选中
xi 0或1，i 1,2,3,4,5
7
3 固定费用问题
例 有三种资源被用于生产三种产品，资源量、产品单件可变 费用及售价、资源单耗量及组织三种产品生产的固定费用如 表。要求制定一个生产计划，使总收益最大
2．相互排斥的约束条件
如果有m个互相排斥的约束条件（<=型）： ai1x1 ai2 x2 ain xn bi i 1, 2, , m
为了保证这个约束条件只有一个起作用，我们引
入m个0－1变量 yi i 1,2,.和.., 一m个充分大的常数M，
而下面这一组m+1个约束条件 ai1x1 ai2 x2 ain xn bi yiM i 1, 2, , m y1 y2 ym m 1

0-1整数规划

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型整数规划模型建立其相应的模型。

§5.4 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 M i n M a x+++= 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型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量n x x x , , ,21 的每一个0或1值，均比较其目标函数值的大小，以从中求出最优解。

这种方法一般适用于决策变量个数n 较小的情况，当n 较大时，由于n 个0、1的可能组合数为n2，故此时即便用计算机进行穷举来求最优解，也几乎是不可能的。

隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。

此时，就只能用穷举法了。

3. 应用实例例1 工程上马的决策问题1）问题的提出某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示：假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大。

2）模型分析与变量的假设这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别对应二进制数中的1、0，大凡这样的实际背景所对应的工程问题，大都可考虑用0—1型整数规划模型建立其相应的模型。

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

-1 -2
2）试指派（找独立0元素）
2 2 4 4 0
0 5 1 0 2
4 0 0 3 3
2 3 1 5 0
4 0 3 1 5
2 2 4 4 0 ◎
◎ 4 0
2
5 1
0 Ø 3
◎ 0
1 5
Ø 0
Ø 3 0
2
3
4 0 ◎ 3 1 5
匈牙利法基于下面的效率矩阵： c11 c12 … c1n （cij）= c21 c22 … c2n ………………. cn1 cn2 … cnn
指派问题的求解步骤：
1) 变换指派问题的系数矩阵(cij)为(bij)，使在(bij)的各行各列 中都出现0元素，即 从(cij)的每行元素都减去该行的最小元素； 再从所得新系数矩阵的每列元素中减去该列的最小元素。
任务 人员 甲 乙
A
2 10
B
15 4
C
13 14
D
4 15
丙
丁
9
7
14
8
16
11
13
9
解：1）变换系数矩阵，增加0元素。
2 15 13 4 2 10 4 14 15 4 9 14 16 13 9 7 8 11 9 7
0 6 0 0 13 0 5 1 11 10 7 4 2 11 4 2
0 Ø 6 0 ◎ Ø 0
13
7 ◎ 0 ◎ 6 9 0 5 3 2 1 ◎ Ø 0 0
例6 已知五人分别完成五项工作耗费如下 表，求最优分配方案。
任务 人员 甲 A 7 B 5 C 9 D 8 E 11
乙
丙 丁 戊
9
8 7 4
12
5 3 6
7
4 6 7
11
6 9 5
x 解： i
不在第i个地区建站 s.t i=1,2, …,6 Z表示全区消防站总数
0
x1 x 2 x 6 1 x3 x 4 1 x3 x 4 x5 1 x 2 x5 x6 1
x i 0 ,1
i 1, 2 , , 6
◎ 0
3
Ø 0
◎ 0
1 3 1 4
Ø 0
6 2
Ø 0
2 3
√
3
√
3 √ ◎ √ 0 3 √ Ø √ 0 5
√
l =m=4 < n=5
选择直线外最小元素为1， 直线外元素减1，直线交 点元素加1，其他保持不 变，得到新的系数矩阵。
Ø 0 1 3 2 ◎ 0
投资项目模型： 例1（投资问题）华美公司有5个项目被列入投资计 划，每个项目的投资额和期望的投资收益见下表： max Z 150 x1 210 x2 60 x3 80 x4 180 x5 该公司只有600万资金可用于投资，由于技术上的 210 x1 300 x2 100 x3 130 x4 260 x5 600 原因，投资受到以下约束： x1 x2 x3 1 1、在项目1、2和3中必须有一项被选中 s.t x3 x4 1 x2、项目3和4只能选中一项 5 x1 x3、项目5被选中的前提是项目1被选中;如何 i 1,2,,5 i 0,1 在 满足上述条件下选择一个最好的投资 方 案，使投资收益最大
二、指派问题
例3 有一份说明书，需译 任务 成英、日、德、俄四种文字。 E J G R 现有甲、乙、丙、丁四个人， 人员 甲 2 15 13 4 他们将说明书译成不同文字 乙 10 4 14 15 所需的时间如下表。问应指 丙 9 14 16 13 派哪个人完成哪项工作，使 丁 7 8 11 9 所需的总时间最少？ 一般地，有n项任务、n个完成人，第i人完成第j 项任务的代价为cij（i,j＝1,2,…,n）。为了求得总 代价最小的指派方案，引入0-1型变量xij，并令 1 指派第i人去完成第j项任务 xij＝ 0 不指派第i人去完成第j项任务
6 4 ( c ij ) 3 5 7 5 1 9 11 9 10 8 2 8 4 2 2 4 1 2
4 0 2 3 5 1 0 7 9 5 9 6 0 4 3 0
4 0 2 3 5 1 0 7 4 0 4 1 0 4 3 0
独立零元素的个数m等于最少 直线数l，即l＝m=3<n=4；
√
4）没有被直线通过的元素中选择最小值为1，变换系数矩 阵，将没有被直线通过的所有元素减去这个最小元素；直 线交点处的元素加上这个最小值。得到新的矩阵，重复2） 步进行试指派
3 0 2 2
4 1
0
3
0
4
0
6
0 5 4 0
2）试指派（找独立0元素）
－5
4 ◎ 2 3
4 ◎ 1 Ø 4 ◎ 4 3 7 1 Ø 5
找到 3 个独立零元素 但m=3<n=4
3）作最少的直线覆盖所有0元素
4 5 4 ◎ √ Ø 4 ◎ 1 2 ◎ 4 3 Ø √ 3 7 1
0-1整数规划
主讲人：陈元安 商丘职业技术学院基础部
一、决策问题与0-1变量
决策变量 x i 是否做第 i 件事 i 1, 2 , , n
xi
1 0
做第i件事 不做第i件事
n件事中必须做k件并只做k件事 x1 x 2 x n k n件事中最多做k件事 x1 x 2 x n k n件事中至少做k件事 x1 x 2 x n k 做第i件事的充要条件是做第j件事 x i x j 做第i件事的充要条件是不做第j件事 x i 1 x j 只在做了第i件事前提下才考虑是否做第j件事 x j x i
解：设 x i为决策变量（ i 1, 2 , ,5 )
1 xi 0
项目 1 投资额 投资收益 （万元） （万元） 210 150
投资第i个项目
2
3 4 5
300
100 130 260
210
60 80 180
不投资第i个项目 Z表示投资效益
例2（布点问题）某城市共有6个 地 1 2 3 4 5 6 区，每个区都可以建消防站。 区 1 0 10 16 28 27 20 市政府希望设置的消防站最少， 10 0 24 32 17 10 2 但必须满足在城市任何地区发 3 16 24 0 12 27 21 最优解 生火火警时，消防车要在15分 4 28 32 12 0 15 25 x2=1, x4=1 钟内赶到现场。据实地测定， 5 27 17 27 15 0 14 6 20 10 21 25 14 0 各区之间消防车行驶的时间见 右表。 请为该市制定一个 布点问题模型： min Z x1 x 2 x 3 x 4 x 5 x 6 最优值 最节省的计划 x x2 1 在第i个地区建站 1Z=2 1
2) 进行试指派，以寻求最优解。
在(bij)中找尽可能多的独立0元素，若能找出n个独立0元 素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余 为0，这就得到最优解。
找独立0元素，常用的步骤为：
从只有一个0元素的行开始，给该行中的0元素加圈，记作◎ 。 然后划去◎ 所在列的其它0元素，记作Ø ；这表示该列所代表的 任务已指派完，不必再考虑别人了。依次进行到最后一行。 从只有一个0元素的列开始（画Ø的不计在内），给该列中的0 元素加圈，记作◎；然后划去◎ 所在行的0元素，记作Ø ，表示 此人已有任务，不再为其指派其他任务了。依次进行到最后一列。 若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，比 较这行各0元素所在列中0元素的数目，选择0元素少这个0元素加 圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列 的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。
总费用为=7+9+4+3+5=28
0 Ø 1 3 2 ◎ 0
Ø 0
3
Ø 0
◎ 0
◎
0 2
Ø 0
6 2
◎
0 4
2 4
3
Ø 0
ห้องสมุดไป่ตู้
9
8 6 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
2 2 4 4 0 0 5 1 0 2 4 0 0 3 3 3 4 2 6 1 6 2 5 3 7
所有0元素的最少直线数 l 。
注：l 应等于m，若不相等，说明试指派过程有误，回到第2步，另行试 指派；若 l＝m < n，表示还不能确定最优指派方案，须再变换当前的系 数矩阵，以找到n个独立的0元素，为此转第4步。
4) 变换矩阵(bij)以增加0元素 在没有被直线通过的所有元素中找出最小值， 没有被直线通过的所有元素减去这个最小元素； 直线交点处的元素加上这个最小值。新系数矩 阵的最优解和原问题仍相同。转回第2步。
◎ 0
3
◎ 0
6 2
Ø 0
0 Ø 2 4
4
0 3 Ø 2 Ø 0 ◎ 0 3 3 ◎ 0 Ø 0 6
总费用为 =5+7+6+6+4=28
注：此问题有多个最优解
◎ 0 1 3 2 0 Ø
Ø 0
3
Ø 0
◎ 0
Ø 0
6 2
◎
2
Ø 0
0 4
2 4
3
◎ 0