当前位置：文档之家 › 运筹学——.整数规划和分配问题

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

  • 格式：ppt
  • 大小：1.08 MB
  • 文档页数：104

下载文档原格式

  / 104

合集下载

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

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

1
整数规划问题的提出
0 xj 1 表示项目j不被选中 表示项目j被选中 ( j 1,2,3,4,5)
解：决策变量：设
目标函数：期望收益最大
max z 10 x1 8 x 2 7 x3 6 x 4 9 x5
约束条件：投资额限制条件 6x1+4x2+2x3+4x4+5x515 项目A、C、E之间必须且只需选择一项：x1+x3+x5=1 项目B、D之间必须且只需选择一项：x2+x4=1 项目C的实施要以项目D的实施为前提条件： x3 x4 归纳起来，其数学模型为：
n
(i 1,2, , m) ( j 1,2, , n)
2
整数规划问题的分类
根据变量取整数的情况，将整数规划分为：
（1）纯整数规划，所有变量都取整数.
（2）混合整数规划，一部分变量取整数,一部分变量取实数 （3）0-1整数规划 ,所有变量均取0或1
2
整数规划问题的求解思考
1
整数规划问题与其松弛问题
2
匈牙利法
例：用匈牙利法求解下列指派问题，已知效率矩阵分别如下：
任务 A 2 10 9 7 B 15 4 14 8 C 13 14 16 11 D 4 15 13 9
人员
甲 乙 丙 丁
2
匈牙利法
2 10 9 7
15 4 14 8
13 14 16 11
4 15 13 9
例：其中（2，2）（3，1）点为最大值，Z=4。常用的求解整数规划的方法有： 割平面法和
分支定界法，对于0－1规划问题采用隐枚举法和匈牙利法。
3
分派问题与匈牙利法
1

运筹学-整数规划与分配问题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

运筹学的基本名词解释汇总

运筹学的基本名词解释汇总

运筹学的基本名词解释汇总运筹学是一门研究如何在有限资源下做出最优决策的学科。

它涵盖了多个子领域，包括线性规划、整数规划、动态规划、网络优化、排队论、决策分析等等。

在本篇文章中，我将深入解释其中一些基本的运筹学名词。

一、线性规划线性规划是运筹学中最常用的方法之一。

它用于解决在给定的约束条件下，如何最大化或最小化一个线性目标函数的问题。

具体来说，线性规划问题可以用如下形式表示：Maximize（或Minimize）：C₁X₁ + C₂X₂ + ... + CnXnSubject to：A₁₁X₁ + A₁₂X₂ + ... + A₁nXn ≤ b₁A₂₁X₁ + A₂₂X₂ + ... + A₂nXn ≤ b₂...An₁X₁ + An₂X₂ + ... + AnnXn ≤ bnX₁, X₂, ..., Xn ≥ 0其中，C₁，C₂，...，Cn为目标函数的系数，X₁，X₂，...，Xn为决策变量，Aij为约束条件的系数，bi为约束条件的右手边。

线性规划在供应链管理、资源分配、生产计划等各个领域都有广泛的应用。

二、整数规划整数规划是线性规划的一个扩展。

在整数规划中，决策变量被限制为整数值，而不仅仅是非负实数。

这在某些情况下更符合实际问题的特点。

整数规划可以用于解决许多实际问题，例如旅行商问题、资源分配问题等。

整数规划的形式与线性规划相似，只是添加了一个约束条件：X₁, X₂, ..., Xn为整数整数规划是一个NP难问题，在实际应用中通常通过割平面法、分支定界法等方法来求解。

三、动态规划动态规划是一种解决多阶段决策问题的方法。

在动态规划中，问题被分解为一系列阶段，每个阶段都有一组决策变量。

每个阶段的决策都基于之前阶段的决策结果，从而达到最优解。

动态规划可以用于解决诸如背包问题、最短路径问题等在实际问题中普遍存在的多阶段决策问题。

四、网络优化网络优化是研究在网络结构下如何优化资源分配和信息流动的方法。

运筹学中的整数规划问题分析

运筹学中的整数规划问题分析

运筹学中的整数规划问题分析运筹学是运用数学和定量分析方法，通过对系统的建模和优化，来解决实际问题的学科。

其中整数规划是运筹学中的一个重要分支，它在许多实际情况中得到广泛应用。

本文将对整数规划问题进行分析，并探讨其解决方法与应用领域。

一、整数规划问题定义及特点整数规划是一类线性规划问题的扩展，其目标函数和约束条件中的变量取值限定为整数。

通常，整数规划问题可以形式化表示为：Max/Min Z = c₁x₁ + c₂x₂ + ... + cₙxₙs.t.a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + a₂₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ∈ Z其中，Z为目标函数值，x₁, x₂, ..., xₙ为待求解的整数变量，c₁, c₂, ..., cₙ为目标函数的系数，aᵢₙ为约束条件的系数，b₁, b₂, ..., bₙ为约束条件的右端常数。

整数规划问题的特点在于整数约束条件的引入，使其解空间变得有限，增加了问题的复杂性。

与线性规划问题相比，整数规划问题更接近实际情况，能够更准确地描述和解决很多实际问题。

二、整数规划问题的解决方法解决整数规划问题的方法主要有以下几种：穷举法、剪枝法、分支定界法、动态规划法等。

具体使用哪种方法需要根据问题的规模和特点来确定。

1. 穷举法是最简单直观的方法，通过枚举搜索整数解空间中的每一个可能解来寻找最优解。

然而，由于整数解空间往往非常大，这种方法在实际问题中往往是不可行的。

2. 剪枝法是一种通过对解空间进行剪枝操作，减少搜索空间的方法。

通过合理选择剪枝条件，可以避免对明显无解的解空间进行搜索，从而提高求解效率。

3. 分支定界法是一种将整数规划问题不断分解为子问题，并对子问题进行界定的方法。

通过不断缩小问题规模，并计算上下界确定最优解的位置，可以有效地求解整数规划问题。

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

运筹第四章整数规划与分配问题
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章-整数规划与分配问题

运筹学基础及应用第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
首先不考虑整数约束，得到线性规划问题（一般称为松弛问 题）。

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


【例 2 】求解 0-1 规划最优解
minZ= 4x1+3x2 +2x3 2x1 -5x2+3x3 ≤4 (1) 4x1 + x2+3x3 ≥3 (2) x2+x3 ≥1 (3) x1 , x2 , x3 =0或 1
解： 先将问题化为如下的标准问题
minZ= 4x1+3x2 +2x3 2x1 － 5x2+3x3 ≤4 (1) － 4x1 － x2 － 3x3 ≤－3 (2) (3) － x2 － x3 ≤ － 1 x1 , x2 , x3 =0或 1
0 13 aij－列min 6 (0) 0 (0) 5 0 0 1 (0) 7 0 6 9 3 2 0 (0) 0 2 15 10 4 9 14 7 8 13 14 16 11 4 15 13 9
（a）从行开始，对只有一个的零元素，打上（），用直线划去所在列 （b）再从列开始，对只有一个的零元素，打上（），用直线划去所在行
∑ ∑
指派问题的解法－－匈牙利法 指派问题的解法－－匈牙利法 －－
从时间表（效率表）出发构建效率矩阵 效率矩阵。 效率矩阵
时间表
任务 人员 甲 乙 丙 丁 E 2 10 9 7 J 15 4 14 8 G 13 14 16 11 R 4 15 13 9
2 15 10 4 9 14 7 8
13 14 16 11
分配表
任务 人员 甲 乙 丙 丁
合计
E x11 x21 x31 x41 1
i
J x12 x22 x32 x42 1
G x13 x23 x33 x43 1
ij x ij
R x14 x24 x34 x44 1
合计
1 1 1 1

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

号与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

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


匈牙利法思路：若能在 [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

运筹学习题解答(chap4 整数规划与分配问题)

第四章 整数规划与分配问题一、建立下列问题的数学模型1、P143, 4.1 利用0－1变量对下列各题分别表示成一般线性约束条件 (a) 221≤+x x 或53221≥+x x ； (b) x 取值0,3,5,7中的一个； (c) 变量x 或等于0，或50≥； (d) 若21≤x ，则12≥x ，否则42≤x ； (e) 以下四个约束条件中至少满足两个：6225433121≥+≥≤≤+x x x x x x ，，，。

解：(a) 设⎩⎨⎧=否则。

，个条件起作用；第1i ,0y i （i=1,2）,M 为任意大正数。

则有 ⎪⎩⎪⎨⎧=+≥++≤+1y y My -5x 3x 2My 2x x 21221121(b) 设⎩⎨⎧=≠=ix i x y i ,1,0，7,5,3,0=i ，则原条件可表示为⎩⎨⎧=++++++=1753075307530y y y y y y y y x(c) 设⎩⎨⎧≥==50,10,0x x y ，则原条件可表示为⎪⎩⎪⎨⎧≥--≥≤0)1(50x M y x yM x(d)⎩⎨⎧=否则。

，组条件起作用；第1i ,0y i （i=1,2）,M 为任意大正数。

则有⎪⎪⎪⎩⎪⎪⎪⎨⎧=++≤->-≥+≤.1,4,2,1,22122211211y y My x My x My x My x (e)设⎩⎨⎧=个条件不成立第个条件成立第i ,1i ,0y i ，4,3,2,1i =，则原条件可表示为：⎪⎪⎪⎩⎪⎪⎪⎨⎧≤+++-≥+-≥+≤+≤+2y y y y My 6x x My 2x M y 2x M y 5x x 43214433321121 2、P143, 4.2 某钻井队要从以下10个可供选择的井位确定5个钻井探油，目的是使得总的钻探费用最小。

若10个井位代号为101S ,...,S ，相应的钻探费用为101C ,...,C ，并且井位的选择要满足下列条件：（1）或选择1S 和7S ，或选择8S ；（2）选择了3S 或4S 就不能选择5S ，反过来也一样； （3）在10962S ,S ,S ,S 中最多只能选两个。

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

二、分配问题与匈牙利法
2.4 匈牙利法实例(8)
第五步：回到第三步，迭代运算，直到矩阵的每一行都有 一个打() 的零元素为止。
最优分配方案为：甲译俄文，乙译日文，丙译英文，丁译 德文。所需时间为：4 + 4 + 9 + 11 = 28h
二、分配问题与匈牙利法
2.5 人数和任务数不相等的分配问题
有四项工作分配给六个人去完成，每个人分别完成各 项工作的时间如下，依然规定每个人完成一项工作。 每项工作只交给一个人去完成。即六个人中挑选哪四 个人去完成，花费时间最少。
一、整数规划的特点及作用
1.2 0-1整数规划
1 解：设x j 0 选Ai 不选Ai
MaxZ c1 x1 c 2 x 2 c7 x7 b1 x1 b2 x 2 b7 x7 B x x x 2 1 2 3 ST : x 4 x5 1 x x 1 7 6 x j 1或0, ( j 1, ,7)
这时，分数或小数的解就不合要求，我们称这
样的问题为整数规划。
例：某厂拟用集装箱托运甲乙两种货物，每箱的体积、 重量、可获利润以及托运所受限制如下表： 问两种货物各托运多少箱，可使获得的利润为最大？
货物
甲 乙 托运 限制 体积 米 3/箱 重量 利润 百斤/箱 百元/箱
MaxZ 20x1 10x 2 ST : 5 x1 4 x 2 24 2 x1 5 x 2 13 x ，x 0，且为整数 1 2
主要内容
一、整数规划的特点及作用 二、分配问题与匈牙利法 三、分枝定界法 四、应用举例
第四章 整数规划及分配问题
第一节 整数规划的特点及作用
一、整数规划的特点及作用
1.1 整数规划的概念
整数规划(Integer Programming) ：决策变 量要求取整数的线性规划。
如果所有的决策变量、技术系数和右端项都 是非负整数，就称为纯整数规划。 如果所有的决策变量都是非负整数，技术系 数和右端项为有理数，称为全整数规划。 如果仅一部分决策变量为整数，则称为混合 整数规划。 如果变量取值仅限于0或1，称为0-1整数规划。
i 1 j 1 某项任务只能由1人完成； m 某人只能完成1项任务。 xij 1 (i 1,, m)
j 1 建立整数规划模型 m 分配问题是0-1整数规划的 xij 1 ( j 1,, m) i 1 特例，也是运输问题的特 xij 0 或 1 (i 1,, m; j 1,, m) 例； n = m, aj = bj = 1。 二、分配 Nhomakorabea题与匈牙利法
2.2 分配问题实例(1)
例：有一份中文说明书，需要译成英、日、德、 俄四种文字。现有甲、乙、丙、丁四人，他们 将中文说明书译成不同语种的说明书所需时间 如下，问应指派何人去完成工作，使所需总时 间最少? 人员
任务 译成英文 译成日文 译成德文 译成俄文 甲 乙 丙 丁 7 8 11 9 2 15 13 4 10 4 14 15 9 14 16 13
例：某线性规划问题最优解为(x1, x2) = (4.6, 5.5)，用凑整法需要比较与上述数据最接近的 几种组合：(4, 5), (4, 6), (5, 5), (5, 6)， 共四种组合。若问题中有10个整数变量，则解 组合达到210 = 1024个整数组合。且最优解未 必在这些组合中。
例：求整数规划问题的最优解 max z 3 x1 2 x2 2 x1 3 x2 14 x1 0.5 x2 4.5 x , x 0, 且均取整数值 1 2
2.4 匈牙利法实例(2)
第二步：找出矩阵每列的最小元素，再分别从各列中减去。
必定满足：bij = aij–ui–vj
0 11 2 0 0
8 0 3 11 0
7 5 0 10 4 11 2 5 0 9 5 0 5 0
8 2 5 0 5 4 3 0 0 11 4 5
第一步：找出每 行的最小元素， 每行对应减去这 个元素。
2 15 13 4
10 4 14 15
9 14 16 13
7 2 0 8 4 11 11 11 2 9 4 0
8 0 3 11
7 10 5 9
5 4 0 5
二、分配问题与匈牙利法
二、分配问题与匈牙利法
2.4 匈牙利法实例(3)
第三步：从第一行开始，若该行只有一个零元素，对零元 素打上()括号，表示行所代表的任务已指派。用直线划去 其所在列；若该行没有零元素或有两个以上零元素(已划 去的不计在内)，则转下一行，依次进行到最后一行为止。
二、分配问题与匈牙利法
2.4 匈牙利法实例(4)
二、分配问题与匈牙利法
2.4 匈牙利法实例(6)
顺着闭回路的走向，对每个间隔的零元素打 ()，然后对 所有打()的零元素或所在行或所在列画一条直线，同样得 到最优解。
二、分配问题与匈牙利法
2.4 匈牙利法实例(7)
第四步：继续按照定理1，对矩阵进行变换。
从矩阵未被直线覆盖的数字中找出一个最小的数k；对矩 阵的每行，当该行有直线覆盖时，令ui=0，无直线覆盖的， 令ui=k；对矩阵中有直线覆盖的列，令vj= -k，对无直线覆 盖的列，令vj=0。 只有一条直线 覆盖的元素保 持不变
5 4 24
2 5 13
20 10
能否先不考虑对变量的整数约束，作为一般线性 规划来求解，当解为非整数的时候可以用“四舍 五入”或“凑整”方法寻找最优解？
对于变量取值很大时，用上述方法得到的解 与最优解差别不大；但当变量取值较小时，得 到的解就可能与实际整数最优解差别很大。 当问题规模较大（决策变量较多）时，用 “凑整”方法来算工作量很大。
二、分配问题与匈牙利法
2.3 匈牙利法的基本思想
如果效率矩阵的所有元素aij≥0, 而其中存在一组位于不 同行不同列的零元素，则只要令对应于这些零元素位 置的xij = 1，其余的xij= 0，则所得到的可行解就是问 题的最优解。
0 9 23 7
14 20 0 12
9 0 3 14
二、分配问题与匈牙利法
2.2 分配问题实例(2)
人员 任务 译成英文 译成日文 译成德文 译成俄文
甲 乙 丙 丁
2 15 13 4
10 4 14 15
9 14 16 13
7 8 11 9
2 10 9 7 15 4 14 8 [aij ] 13 14 16 11 4 15 13 9
效率矩阵用[aij]表示。aij > 0 ( i,j = 1,2,…,n )表示 指派第j人去完成第i项任务时的效率(时间、成 本等)。
二、分配问题与匈牙利法
2.2 分配问题实例(3)
1，分配第 i 个人去完成第 j 项任务 xij 0，不分配第 i 个人去完成第 j 项任务 m m （i 1, , m；j 1,, m） min z aij xij
0-1整数规划的一般形式:
MaxZ C T X Ax b ST : x j 1或0, ( j 1, , n)
0-1整数规划一般都 是纯整数规划。
一、整数规划的特点及作用
1.3 整数规划的作用
0-1整数规划在管理领域具有重要作用
1. m个约束条件中只有k个起作用； 2. 约束条件的右端项可能是r个值(b1, b2, … br) 中的某一个； 3. 两组条件中满足一组； 4. 用以表示含固定费用的函数。
二、分配问题与匈牙利法
2.1 分配问题(2)
如果完成任务的效率表现为资源消耗，考 虑的是如何分配任务使得目标函数极小化； 如果完成任务的效率表现为生产效率的高 低，则考虑的是如何分配使得目标函数最 大化。 在分配问题中，利用不同资源完成不同计 划活动的效率，通常用表格形式表示为效 率表，表格中数字组成效率矩阵。
第四章 整数规划及分配问题
第二节 分配问题与匈牙利法
二、分配问题与匈牙利法
2.1 分配问题(1)
指派n个人去完成n项任务，使完成 n项任 务的总效率最高(或所需总时间最少)，这 类问题称为指派问题或分配问题。
安排工作（派工）：有n项加工任务，怎样 指派到n台机床上完成； 有n条航线，怎样指定n艘船去航行的； ……
3 23 8 0
显然令 x11=1, x23=1, x32=1, x44=1，即 将第一项工作分配给甲，第二项给丙， 第三项给乙，第四项给丁。这时完成 总工作的时间为最少。 如何寻找这组位于不同行不同列的零 元素？
二、分配问题与匈牙利法
2.3 匈牙利法的基本定理
定理1 如果从分配问题效率矩阵[aij]的每一行 元素中分别减去(或加上)一个常数ui(被称为该 行的位势)，从每一列分别减去(或加上)一个常 数vj(被称为该列的位势)，得到一个新的效率矩 阵[bij]，若其中bij = aij –ui–vj，则[bij]的最 优解等价于[aij]的最优解。 定理2 若矩阵A的元素可分为“0”和非“0”两 部分，则覆盖“0”元素的最少直线数等于位于 不同行不同列的“0”元素的最大个数。
一、整数规划的特点及作用
1.2 0-1整数规划
某公司拟在市东、西、南三区建立门市部。拟 议中有7个位置（点）Ai供选择。规定
在东区，由A1，A2，A3三个点中至多选两个； 在西区，由A4，A5两个点中至少选一个； 在南区，由A6，A7两个点中至少选一个。
如选用Ai点，设备投资估计为bi元，每年可获利 润估计为ci元，但投资总额不能超过B元。 问：应如何选址，可使年利润为最大？
二、分配问题与匈牙利法
2.4 匈牙利法实例(1)
人员 任务 译成英文 译成日文 译成德文 译成俄文 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9