当前位置：文档之家 › 运筹学 第4章 整数规划与分配问题

运筹学 第4章 整数规划与分配问题

  • 格式：ppt
  • 大小：916.00 KB
  • 文档页数：40

下载文档原格式

  / 40

合集下载

运筹学-整数规划与分配问题PPT

运筹学-整数规划与分配问题PPT

但 z=13 不是最优。实际问题的
最优解为（4 , 1）这时 z*= 14。
逻辑（0-1）变量在建立数学模型中的作用
1. m 个约束条件中只有 k 个起作用
设 m 个约束条件可以表示为：
n
aijxj bi (i1, ,m)
j1
定义逻辑变量
1，假定第 i 个约束条件不起作用 yi 0，假定第 i 个约束条件起作用
第四章 整数规划与分配问题
整数规划的特点及作用 分配问题与匈牙利法 分枝定界法 割平面法 应用举例
1 整数规划的特点及应用
在实际问题中，全部或部分变量取值必须是整数。比如人 或机器是不可分割的，选择地点可以设置逻辑变量等。
在一个线性规划问题中要求全部变量取整数值的，称纯整
数线性规划或简称纯整数规划；只要求一部分变量取整 数值的，称为混合整数规划。
如果完成任务的效率表现为资源消耗，考虑的是如何分配 任务使得目标极小化；如果完成任务的效率表现为生产效 率的高低，则考虑的是如何分配使得目标函数极大化。
在分配问题中，利用不同资源完成不同计划活动的效率常
用表格形式表示为效率表，表格中数字组成效率矩阵。
例2. 有一份说明书，要分别翻译成英、日、德、俄 四种文字，交甲、乙、丙、丁四个人去完成。因各人专长 不同，使这四个人分别完成四项任务总的时间为最小。效 率表如下：
又设 M 为任意大的正数，则约束条件可以改写为：
n
aijxj
bi Myi
j1
y1 y2 ym mk
2. 约束条件的右端项可能是 r 个值中的某一个
n
即
aijxj b1或b2或或br
j1
定义逻辑变量：
yi 10， ，假 其定 它约束右端项b为 i

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

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

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元。 问：应如何选址，可使年利润为最大？
第一步：找出每 行的最小元素， 每行对应减去这 个元素。

运筹第四章整数规划与分配问题

运筹第四章整数规划与分配问题
x1 ≤ 4 + y1 M x2 ≥ 1 − y1 M x1 > 4 − y2 M x ≤ 3+ y M 2 2 y1 + y2 = 1
i=1,2
则问题可以表示为
4 用以表示含固定费用的函数 总费用
K j + c j x j ( x j > 0) Cj(xj ) = ( x j = 0) 0
则上述条件可以表示成
r n ∑ aij x j ≤ ∑ b; y + ... + y = 1 m 2 1
3、 两组条件中满足其中的一组 、
若 x1 ≤ 4, 则 x2 ≥ 1
若 x1 > 4, 则 x2 ≤ 3
定义
1 第i组条件不起作用 yi = 0 第i 组 条件 起作 用
0 0 X = 1 0 0 0 1 1 0 0 0 0 0 0 1 0
用矩阵形式表示为: 用矩阵形式表示为: 解矩阵
一般分配问题 设有n项任务 需有n个人去完成 项任务， 个人去完成， 设有 项任务，需有 个人去完成，每个人只能完成一 项任务，每项任务只能由一个人去完成，设第i人完成 项任务，每项任务只能由一个人去完成，设第 人完成 项任务需要的时间是a 第j 项任务需要的时间是 ij , 问如何分配才能使完成任 务的总时间最少？ 务的总时间最少？ 设
2. 整数规划问题的特征与性质
特征—变 特征 变量整数性要求 来源 问题本身的要求 引入的逻辑变量的需要 性质—可 性质—可行域是离散集合
3. 整数规划的分类
纯整数规划 要求全部决策变量的取值都为整数, 要求全部决策变量的取值都为整数 则称为纯整数规划 (All IP)； ； 混合整数规划 仅要求部分决策变量的取值为整数，则称为混合整数规 仅要求部分决策变量的取值为整数， 划(Mixed IP)； ； 0-1整数规划 整数规划 要求决策变量只能取0或 值 则称为0-1规划 规划(0-1 要求决策变量只能取 或1值，则称为 规划 Programming)。 。

运筹学--第四章 整数规划与分配问题

运筹学--第四章 整数规划与分配问题

一、整数线性规划问题的提出
引例：生产组织计划问题与选址问题 例4-1（生产组织计划问题）某工厂在一个计划期 内拟生产甲、乙两种大型设备。除了A、B两种部件 需要外部供应且供应受到严格限制之外，该厂有充 分的能力来加工制造这两种设备所需的其余零件， 并且所需原材料和能源也可满足供应。每种设备所 用部件数量和部件的供应限额以及设备的利润由表 3-1-1给出。问该厂在本计划期内如何安排甲、乙 设备的生产数量，才能获取最大利润？
例4-3某人有一背包可以装10公斤重、0.025m3的物
品。他准备用来装甲、乙两种物品，每件物品的重 量、体积和价值如表4-3-1所示。问两种物品各装 多少件，所装物品的总价值最大？
表4-3-1 物品 甲 乙 重量 （公斤/每件） 1.2 0.8 体积 （m3/每件） 0.002 0.0025 价值 (元/每件) 4 3
应寻找仅检查可行的整数组合的一部分，就能定出 分支定界法可用于解纯整数或混合整数线性规划问
最优的整数解的方法。分支定界解法就是其中之一。
题。
–20世纪60年代初由Land Doig和Dakin等提出，是 解整数线性规划的重要方法之一。
–由于这方法灵活且便于用计算机求解，所以现在
它已是解整数规划的重要方法。
了。 但这常常是不行的，因为化整后不见得是可行解； 或虽是可行解，但不一定是最优解。 因此，对求最优整数解的问题，有必要另行研究。
例4-4 说明整数规划问题的求解不能直接在单纯形
法最优解的基础上四舍五入 求下述整数规划问题的最优解（P105）
max z 3x1 2 x2 2 x1 3x2 14 s.t. x1 0.5 x2 4.5 x , x 0, 且均取整数值 1 2

运筹学(第4章 整数规划与分配问题)(1)

运筹学(第4章 整数规划与分配问题)(1)
运筹学基础及应用 ( Operations Research )
主讲：杨启明
第4章 整数规划与分配问题1Fra bibliotek2 3
整数规划的特点及应用
分配问题与匈牙利法
分枝定界法 割平面法 解0-1规划问题的隐枚举法
4
5




4.1.1 整数规划的模型分类 纯整数规划模型 0-1整数规划模型 混合整数规划模型 4.1.2 实例 投资决策问题 背包问题 4.1.3 解整数线性规划的困难性 4.1.4 逻辑变量在建模中的作用
令
x11 x23 x32 1其余的xij=0
问题： 如何产生并寻找这组位于不同行不同列的零元素？
匈牙利数学家克尼格(Konig)
基础： 两个基本定理 如果从分配问题效率矩阵[aij]的每一行元素中分别 减去(或加上)一个常数ui(被称为该行的位势), 从每一列分 别减去(或加上)一个常数vj(被称为该列的位势), 得到一个 新的效率矩阵[bij], 若其中bij=aij-ui-vj , 则[bij]的最优解等价 于[aij]的最优解 作用：
用图解法求出最优解为： x1＝3/2, x2 = 10/3，且有Z = 29/6
现求整数解(最优解):如用舍 入取整法可得到4个点即(1， 3),(2，3),(1，4),(2，4)。显然， 它们都不可能是整数规划的最优 解。 按整数规划约束条件，其可行 解肯定在线性规划问题的可行域 内且为整数点。故整数规划问题 的可行解集是一个有限集，如右 图所示。其中(2,2),(3,1)点的目 标函数值最大，即为Z=4。
xij 1(i 1,, m) 第i人完成
m
x1j

x2j
xi1 xi2 xij xi m-1 xim

运筹学基础及应用第4章-整数规划与分配问题

运筹学基础及应用第4章-整数规划与分配问题

整数规划的特点及应用
解：对每个投资项目都有被选择和不被选择两种可能，因此 分别用0和1表示，令xj表示第j个项目的决策选择，记为：
j投 资 1 对 项 目 xj ( j 1,2,..., n) j不 投 资 0 对 项 目
投资问题可以表示为：
max z
c
j 1
n
j
xj
n a j x j B j 1 x2 x1 s .t x 3 x4 1 x5 x6 x7 2 ） x j 0或者1 （j 1, 2, L n
B1 B2 B3 B4 年生产能力
A1
A2 A3 A4 年需求量
2
8 7 4 350
9
3 6 5 400
3
5 1 2 300
4
7 2 5 150
400
600 200 200
工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。 现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。
0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划。
整数规划的特点及应用
整数规划的典型例子
例4.1 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要 再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地 有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各 需求地的单位物资运费cij，见下表：
例4.3 设整数规划问题如下
max Z x1 x 2 14x1 9 x 2 51 6 x1 3 x 2 1 x , x 0且 为 整 数 1 2
首先不考虑整数约束，得到线性规划问题（一般称为松弛问 题）。

管理运筹学第四章整数规划与指派问题 ppt课件


资源
小号容器
金属板（张）
2
劳动力（个）
2
机时（小时）
1
中号容器 大号容器 资源拥有量
4
8
500
3
4
300
2
3
100
利润
4
5
6
11
解：设x1 , x2 , x3分别表示小、中、大号容器的生产数量， M为很大的正数，z表示总利润
引入逻 辑变量
yj 10,,
xj 0 xj 0
j1,2,3
m ax z 4 x1 5 x2 6 x3 100 y1 150 y2 200 y3
32
分枝的方法
max z CX
AX b
s.t.
X
0,
X为整数
m ax z CX
AX b
s .t . x r b r
X
0,
X为
整
数
m ax z CX
AX b
s .t . x r b r
X
0, X 为 整 数
33
定界的方法
当前得到的最好整数解的目标函数值 分枝后计算放松的线性规划的最优解
.t
.
X
0
如果最优解x
i中某个分量
x
0 i
非整
max z CX
AX b
s.t
.
X 0
X为整数向量
xi [ xi0 ]
max z CX
AX b
s.t
.
X 0
X为整数向量
xi [ xi0 ] 1
26
分枝定界法的两个要点：分枝和定界 ☺如何定界？ • 整数规划ILP的最优解不会优于松弛LP的最优解； • 对极大化问题来说，松弛 LP 的目标函数最优值是原

运筹学基础及应用_(第四章_整数规划与分配问题)

号与7号必须同时开采；
（d） 8
（e）1号、
4号、6号、9号开采时不能超过两个，试表示上
述约束条件。
Next
基础教研室
（a）当x8=1 当x8=0 ∴ x8 x6
x6=1，x6≠0 x6=1，x6=0
（b）当x5 =1 当x5 =0 ∴ x5 + x3 1
x3=0， x3 ≠1 x3=0， x3 =1
基础教研室
【例1】求下述整数规划的最优解
Max z= 3x1 + 2x2 st . 2x1 + 3x2 14 x1 + 0.5x2 4.5 x10，x20，且为整数
基础教研室
x2 x1+0.5x2=4.5
4
(3.25, 2.5) 2 2x1+3x2=14
2
4
6
x1
3x1+2x2=6
二、整数规划的求解方法
1 －选择电网供应 设 y1 0 －不选择电网供应
10 d j x j f (1 y1 ) M j 1 10 0.3d j x j p (1 y2 ) M j 1 y1 y2 1 y1 , y2 0或1
基础教研室
【例3】投资决策问题 某公司准备1000万元资金在10个地点中选择若干个建立 工厂（工厂名称用地点名来命名），有关数据如下：
由于各个工厂之间有配套和协作关系，因此必须满足条件： 1、 建工厂1就必须同时建工厂2； 2、 若建工厂2就不允许建工厂3； 3、 工厂4和工厂5至少建一个； 4、 工厂6，7，8恰好建2个； 5、 工厂8，9，10最多建2个； 6、 建工厂4或者建工厂6，就不能建工厂8，反过来也一样； 7、 条件2，3，5最多满足2个。 问选择哪几个地点建厂最有利？ Next

运筹学第四章--整数规划和分配问题(新)aPPT课件


-
1
整数线性规划的一般形式: n max(或min)z cj xj j 1
n
aij xj ( 或 ）bi (i 1,2,...m)
j 1
xj 0( j 1,2,...n),且部分或全部取整数
例1.求下述整数规划问题的最优解
max z 3x1 2x2
2x1 3x2 14 x1 0.5x2 4.5
先不考虑整数解的限制，用单纯形法求 解其松弛问题，如果求得的解恰好是整数解， 则得整数规划最优解，停止计算。否则，将 松弛问题分解为两个子问题（也称后继问 题），每个子问题都是在原松弛问题的基础 上增加一个变量取整数的约束条件，这样就 缩小了原来的可行域，然后用单纯形法求解， 直至得到最终结果。
-
21
-
23
例.用分枝定界法求下述数整规划问题的最优
maxz 3x1 2x2
2x1 3x2 14 x1 0.5x2 4.5 x1, x2 0,且均取整数值
-
24
-
25
-
26
-
27
-
28
-
29
第四节 割平面法 一、割平面法的基本思想
先不考虑整数条件，用单纯形法求解其 松弛问题，若得整数解，即得整数规划最优 解。否则，增加线性约束条件（称为割平面 方程），将原问题的可行域切割掉一部分， 被切割掉的都是非整数解，再用单纯形法求 解新的线性规划问题，依次进行下去，直到 使问题的最优解恰好在可行域的某个具有整 数坐标的顶点上得到。
0.5 + 0.4 x4 + 0.4 x5≥ 1
-
35
2. 借助单纯形表法
对求解整数规划问题的松弛问题（LP问题）得到
最优单纯形表，设xi=bi 是最优解中取分数值（分数 部分最大）的基变量，则有

第4章 整数规划与分配问题 管理运筹学 重庆三峡学院


某厂拟用集装箱托运甲、乙两种货物，每箱的体积、质量、可获得的利 润以及托运所受到的限制如表所示。问怎样安排托运计划，可使利润最 大？
货物
甲 乙 托运 限制
每箱体积 (m3) 3 8
40
每箱质量 (50kg)
4 3
24
每箱利润 (百元)
5 6
设 x1,x2表示两种货物装载数量(整 数)，依题意有如下数学模型：
0-1规划的数学模型为：
max(min)z CX
AX ≥ (,≤)b
s.t.
X
取0或1
4.2.2 隐枚举法简介
管理运筹学 第4章 整数规划与分配问题
1.化成标准形式 (1)目标函数:min ,cj>0。目标若 max,目标系数改变符号,变为
min; (2)若cj<0,令yj=1-xj使其变正; (3)目标函数中,变量按目标系数 从小到大排列,约束条件中也跟 着相应改变.
4.1.3 图解法
管理运筹学 第4章 整数规划与分配问题 0 1 2 3 4 5 6 7 8 x2
（1）建立直角坐标系， 图示约束条件，确定 可行域。
（2）图示目标函数一 根基线，按目标要求 平行移动，直到与可 行域相交。
（3）求出交点坐标与 目标值。
【例4.1】 用图解法求解整数规划
max z 5x1 6x2
生产过程的种类
甲 乙 丙
固定投资(元)
1 000 2 000 3 000
生产成本(元/千克)
5 4 3
最大日产量(千克)
2 000 3 000 4 000
4.2.4 0-1变量在数学建模中的应用
管理运筹学 第4章 整数规划与分配问题
解 设：
生产 固定投资 生产成本 过程 (元) (元/千克)
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

匈牙利法思路：若能在 [Cij] 中找出 n 个位于
不同行不同列的0元素(称为独立0元素)，则
令解矩阵[xij]中对应这n个独立0元素的元素
取值为 1 ，其他元素取值为 0 ，则它对应目
标函数zb=0是最小的。这就是以[Cij]为系数
矩阵分配问题的最优解，也得原问题的最
优解。
定理1 若从分配问题效率矩阵[cij]的每一行元素中分别减去 (或加上)一个常数ui(称为该行的位势)，从每一列分别减去 (或加上)一个常数vj(称为该列的位势)，得到一个新效率矩阵 [bij]，若其中bij=cij-ui-vj，则[bij]的最优解等价于[cij]的最优解
第1步：找出效率矩阵每行的最小元素，并分别从每行
中减去。
第2步：再找出矩阵每列的最小元素，并分别从各列中 减去。
2 10 9 7 2 15 4 14 8 4 13 14 16 11 11 4 15 13 9 4
0 8 7 5 11 0 10 4 0 3 5 0 0 11 9 5
表明m个约束条件中有(m-k)个的右端项为( bi+M )，不起约 束作用，因而，只有k个约束条件起作用。 ② 约束条件的右端项可能是r个值b1 , b2 ,, br 中的某一个 即： 定义：
n
aij x j b1 或b2或或br
j 1
1 假定约束右端项为 bi yi 否则 0
现用下例来说明： max z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1，x2≥0 x1，x2整数 ① ② ③ ④ ⑤
解：先不考虑条件⑤，即解相应的线性规划B,①～④(见图5-2)， 得最优解x1=4.81，x2=1.82，z0=356
z z
可见它不符合整数条件⑤。 这时 z0 是问题 A 的最优目标函 数值z*的上界，记作z0= z 。 当 x1=0 ， x2=0 ，是问题 A 的一 个整数可行解，这时 z=0 ，是 z*的一个下界，记作 z =0，即 0≤z*≤356。
b x M c x
n n n n i 1 j 1 ij ij i 1 j 1 n n ij n i 1 j 1
ij n
M xij cij xij
i 1 j 1
nM cij xij
i 1 j 1
n
n
故所得最小解就是原问题的最大解。
证明：略。
下面以实例说明匈牙利法的解题步骤：
例2 有一份中文说明书，需译成英、日、德、俄四种文字， 现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同 语种说明书所需时间如表4-2所示。问应指派何人去完成 何工作，使所需总时间最少? 表4-2
人 员 任务 英文 日文 德文 俄文 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9
重复(1)、(2)两步，可能出现三种情况：
① 效率矩阵每行都有一个打( )号的0元素，此时，令对应 打( )号0元素的xij=1，得到最优解。 ② 打( )号的0元素个数小于m，但未被划去的0元素之间存 在闭回路，这时可顺着闭回路的走向，对每个间隔的0元 素打一( )号，然后对所有打( )号的0元素，或所在行，或 所在列画一条直线。 ③ 矩阵中所有0元素或被划去，或打上( )，但打上( )号的 0元素个数小于m
0 0 5 0
0 8 11 0 2 3 0 11
2 5 0 4
5 4 0 5
第3步：若找出n个独立0元素，就以这些元素对应解矩阵[xij] 中的元素为1，余为0，得最优解。否则，按下列步骤解决 (1) 从第一行开始，若该行只有一个0元素，就对这个元素打 上( )号，对打上( )号0元素所在列画一条直线。若该行没 有0元素或有两个以上0元素(已划去的不计在内)，则转下 一行，依次进行到最后一行。 (2) 从第一列开始，若该列只有一个0元素，就对这个元素打 上( )号，对打上( )号0元素所在行画一条直线。若该列没 有0元素或有两个以上0元素(已划去的不计在内)，则转下 一列，依次进行到最后一列。
分枝定界法思路：对求解最大化的整数规划问题 A ，从 解与它相应的线性规划问题 B 开始，若其最优解不是整 数，那么B的最优目标函数必是A的最优目标函数 的上 z 界，记作 ； A 的任意可行解的目标函数值将是 的一 z z 个下界 。分枝定界法是将 B的可行域分许多子区域 (称 z 为分枝)的方法，逐步减小 和增大 ，最终求得 。 z z z
第4步：为设法使每一行都有一个打( )号的0元素，需要对 矩阵变换。 (1) 从矩阵未被直线覆盖的数字中找出一个最小的数k;
(2) 对矩阵的每行，当该行有直线覆盖时，令 i 0 ,无 直线覆盖的，令 i k ； (3) 对矩阵中有直线覆盖的列，令v j k ，对无直线覆盖
的列，令 v j 0 ;
2 5 0 4
5 4 0 5
0 8 2 5 11 0 5 4 2 3 0 0 0 11 4 5
0 8 0 11 4 5 0 11
0 3 0 2
3 2
0
3

0 0 1 0 0 1 0 0 可见最优解为 xij 0 0 0 1 1 0 0 0 这表示：指定甲译成俄文，乙译成日文，丙译成英文，丁译 成德文，所需总时间最少。
2、逻辑变量在数学模型中的作用
① m个约束条件中只有k个起作用
设m个约束条件可表为：
aij x j bi
j 1
n
i 1, 2, , m
定义
1 假定第i个约束条件不起作用 yi 0 假定第i个约束条件起作用
令M 为任意大的正数，则
n aij x j bi Myi j 1 y1 y2 ym m k
证明：将从[bij]中得到的解代入目标函数
z bij xij cij i v j xij
n n n n i 1 j 1
n n
i 1 j 1
cij xij i xij v j xij
i 1 j 1 i 1 j 1 j 1 i 1
max z cij xij
i 1 j 1 m m
可令 bij=M-cij，其中M是足够大的常数(如选cij中最大元 素为M即可)，这时效率矩阵变换为B=(bij)，bij≥0，符合 匈牙利法条件。
目标函数变换后，即解
min z bij xij
i 1 j 1 n n
因为：
n r aij x j bi yi i 1 j 1 y1 y 2 y r 1
上述约束条件可表示为：
§2 分配问题与匈牙利法
2-1 问题的提出与数学模型 某单位需完成 n项任务，恰好有 n个人可承担这些任务。 由于每人的专长不同，完成任务不同，效率也不同。 于是产生应指派哪个人去完成哪项任务，使完成n项任 务的总效率最高(或所需总时间最小)。这类问题称为分 配问题或指派问题(assignment problem)。 设：用[cij]表示分配问题的效率矩阵，令
1 分配第i个人去完成第 j项任务 xij 0 不分配第i个人去完成第 j项任务
i 1, 2, , n; j 1, 2, , n
当问题要求极小化时，数学模型j 1
n
n
n j 1, 2, , n xij 1 1 i n i 1, 2, , n xij 1 j 1 xij 0 或 1 指派问题是运输问题的特例，即n=m, aj=bi=1。可用 运输问题的解法去求解。根据分配问题的特点，下面给 出匈牙利法。
(4) 从原矩阵的每个元素cij中分别减去 i 和 v j ，得到一个 新的矩阵。 第5步：回到第3步，反复进行，直到矩阵每一行都有一 个打( )号的0元素为止，即找到了最优分配方案。
2 0 8 2 5 2 11 0 5 4 2 3 0 0 0 0 11 4 5 2 2 0 0 2
第4章 整数线性规划
• • • • • §1 整数规划的特点及作用 §2 分配问题与匈牙利法 §3 分枝定界法 §4 割平面法 §5 应用举例
§1 整数规划的特点及作用
1、整数规划的特点 线性规划问题的最优解通常是非整数，但对某些具 体问题，要求解必须是整数。例如，所求解是机器的台 数、完成工作人数等问题，非整数解就不合要求。将非 整数解通过“舍入化整”，不见得是可行解，或虽是可 行解，但不一定是最优解。
因此，求整数最优解问题，有必要另行研究。我们 称此问题为整数线性规划(integer linear programming)， 简称ILP。
整数线性规划中如果所有的变量都限制为(非负)整数， 就称为纯整数线性规划(pure integer linear programming)或称为全整数线性规划(all integer linear programming)； 如果仅一部分变量限制为整数，则称为混合整数规划 (mixed integer linear programming)。
n
n
n
n
cij xij i v j
i 1 j 1 i 1 j 1
n
n
n
n
第一项是[cij]解的目标函数 z，后两项是常数，因而，当 z 达到最小值时，相应地 z 也达到最小值。
定理2 若矩阵A的元素可分成“0”与非“0”两部 分，则覆盖“0”元素的最少直线数等于位于不同 行不同列的“0”元素的最大个数。