运筹学-0-1规划-指派问题

第五章整数规划1．整数规划的基本概念2．分枝定界法解整数规划3．０－１规划4.指派问题及其解法☞1ppt课件1.整数规划的基本概念2.分枝定界法解整数规划纯整数规划、混整数规划分枝定界法分三步：第一步放宽第二步分枝第三步定界2ppt课件

具体作法是：首先，删去整数条件，把原整数规划化成相应线性规划。其次，求解相应线性规划。最后，如果相应线性规划的最优解也是原整数规划的最优解，那么整个计算过程即告结束；否则，便转入第二步。第一步放宽3ppt课件具体作法是：从相应线性规划的最优解中，任意选择一个不满足原整数规划整数条件的决策变量xj=bj。以使相应线性规划增加一个约束条件；xj小于bj的最大整数（或xj大于bj的最小整数），因而得到两枝新的线性规划，然后计算每枝的最优解和最优值。第二步

分枝4ppt课件

具体做法为：进行定界（由各枝的最优值中选最大值），找出界枝。若界枝的最优解就是原整数规划的最优解，则计算过程便告结束；否则，回到第二步。第三步定界返回5ppt课件第四节0-1规划一、0-1规划的概念二、隐枚举法6ppt课件

例9

在暑假期间，某同学准备徒步回家探亲。他把要带的物品装进包后，觉得还能多放5个单位重量的东西。为此，他列出了拟放物品的清单，见表2-11。他认为：应使所增加的物品总价值为最大。基于以上的考虑，他到底还要带哪些东西呢？一、0-1规划的概念7ppt课件y为增加的物品总价值编号名称重量价值1书籍562诱饵233电筒114食物35表2-11解：设例9的数模为：8ppt课件只取0或1的变量,称为0-1变量。若纯整数规划的决策变量都是0-1变量，则称为0-1规划。在讨论线性规划时，如果研究对象可以归结为互相对立的两种可能情况，那么依靠引入0-1变量，就能够将它进一步化成0-1规划。9ppt课件如果0-1规划模型不是标准型，总可以通过适当的变换，使其化为标准型.称下面形式的数学模型为0-1规划的标准型：返回10ppt课件二、隐枚举法

从理论上讲，求解0—1规划，可用枚举法。这时，一旦有n个决策变量x1，x2，…，xn，就必须逐一地检查（x1，x2，…，xn）的2n种取值（不仅仅指可行解）。但是，当n＞10时，即使经历漫长的计算过程找到了最优解，也会由于时过境迁而失去实用价值。隐枚举法是0-1规划的常用解法，它只须检查（x1，x2，…，xn）取值的一部分，即可找到最优解。11ppt课件例10

利用隐枚举法求解例9。试探的方法这是一个求y的最大值问题，当然可以认为ymax≥6这个新的约束条件具有滤掉非最优解的功能，称为过滤条件。解：（1）找出一个可行解并计算出相应的目标函数值：（x1，x2，x3，x4）=（1，0，0，0），y=6；（2）将不等式6x1+3x2+x3+5x4≥6加到约束条件中；（3）把6x1+3x2+x3+5x4≥6和5x1+2x2+x3+3x4≤5

依次记作（0）和（1），把它们的左边分别写成（0）´和（1）´。12ppt课件本0-1规划包含4个决策变量。所以（x1，x2，x3，x4）共有24种不同的取值。见表2-12。其中：（x1，x2，x3，x4）是24种取值；（0）´和（1）´是将（x1，x2，x3，x4）取值代入后的计算结果。考查它们是否满足（0）和（1）：当不满足某个约束条件时，同行以下的各项就不再考虑，这表明（x1，x2，x3，x4）不是可行解；当满足全部约束条件时，这表明（x1，x2，x3，x4）是可行解。☞13ppt课件（x1，x2，

x3，

x4）(0)’(1)’是(√)否(×)y（0,0,0,0）0×

(0,0,0,1)5×

(0,0,1,0)1×

(0,0,1,1)64√6(0,1,0,0)3×

(0,1,0,1)85√8(0,1,1,0)4×

(0,1,1,1)96×

(1,0,0,0)6(5)√6(1,0,0,1)118×

(1,0,1,0)76×

(1,0,1,1)129×

(1,1,0,0)97×

(1,1,0,1)1410×

(1,1,1,0)108×

(1,1,1,1)1511×

小于上面的目标值8，所以此解非最优。最优解☞14ppt课件求出这些可行解对应的目标函数的最大值：Max{6,8}=8。于是，本0-1规划的最优值ymax=8最优解（x1，x2，x3，x4）=（0，1，0，1）。这表明，该同学还要带诱饵和食物。15ppt课件从提高隐枚举法的效率着想，当求解最大（小）化0-1规划时，若遇到y值大（小）于（0）的右边，应随即让（0）的右边改取这个y值。求解0-1规划，不要墨守成规，应视具体情况选择适当的解法，以期收到事半功倍的效果。16ppt课件例3-3

求下面0-1规划的解.它满足约束条件（1）到（4），且对应的目标函数值y=3．于是过滤条件为：解

首先用试探的方法找一个可行解:17ppt课件表3-13隐枚举法计算表(0)（1）（2）（3）（4）满足√否则×y(0,0,0)0

×

(0,0,1)5-1101√5(0,1,0)-2

×

(0,1,1)3

×

(1,0,0)3

×

(1,0,1)80211√8(1,1,0)1

×

(1,1,1)6

×

18ppt课件用全部枚举法，3个变量共有23=8个解，原来4个约束条件共需32次运算，现在用隐枚举法，将5个约束条件按（0）~（4）顺序排好（见表3-13），对每个解依次代入约束条件左侧，求出数值，看是否适合不等式条件，如某一条件不适合，同行以下各条件可不必再检查，因而就减少了运算次数.本例实际只作18次运算．最优解:返回19ppt课件第五节

指派问题一、指派问题的概念二、最小化指派问题三、最大化指派问题20ppt课件指派问题就是人员和设备的任务安排问题。但是，运筹学当前所涉及的指派问题，并不是泛指一切指派问题，而是把它局限于某种特殊情况。这种特殊情况的一个典型事例是：有n个人分别完成n项任务中的其中一项。因工作性质和个人专长的差异，每个人完成各项工作的时间也就有所不同。于是便提出这样的问题：指派哪个人完成哪项工作，可使他们总的工作时间最短？指派问题有最小化和最大化之分，二者的解法大同小异。一、指派问题的概念返回21ppt课件

例11

某医院的四名化验员（甲、乙、丙、丁）完成四项化验工作（A、B、C、D）所消耗的时间见表2-13。哪个化验员担当哪项化验工作，可使他们总的消耗时间最短？二、

最小化指派问题22ppt课件表1-13

ABCD

消耗时间（分）

甲37.743.433.329.2

乙32.933.128.526.4

丙33.842.238.929.6

丁37.034.730.428.5建立其数学模型。设：

i=1,2,3,4分别表示甲，乙，丙，丁；

j=1,2,3,4分别表示A，B，C，D；

bij

表示i完成j的消耗时间；23ppt课件

y表示四名化验员总的消耗时间，于是数学模型为：例11称为最小化指派问题。24ppt课件一般地，最小化指派问题的数学模型是：其中[bij]称为效率矩阵。25ppt课件定理2.1

若效率矩阵[bij]第i行元素的最小值为bi

,则效率矩阵分别为[bij]和[bij-bi]的最小化指派问题具有相同的最优解。把“第i行”换成“第j列”，“bi”换成“bj”后，依然成立。最小化指派问题的求解步骤如下：第一步：在效率矩阵[bij]中，让每行（列）元素减去该行（列）元素的最小值，从而得到矩阵[Cij]。26ppt课件每行减去该行的最小元素每列减去该列的最小元素每行每列都有零27ppt课件第二步：在矩阵[Cij]中，首先找出含0最少的行，并且把其中的一个0括起来，即（0）；然后划掉与前提下，相继完成其它各行。（0）同行或同列的0，即。在不得再括的()()()28ppt课件第三步：在矩阵[Cij]中，若不能得到m个（0），则进行第四步；若能得到m个（0），则令[Cij]中与（0）相对应的xij=1，其余的决策变量等于0。这时，[xij]便是最优解。将最优解代入目标函数y的表达式，即得最优值。()()()没有得到4个(0)转入第四步29ppt课件第四步：遵循下列程序，在[Cij]中画出直线：（一）在没有（0）的行，标上“√”；（三）在标上“√”的列中（0）所在的行，标上“√”；（四）在没有标上“√”的行或已经标上“√”的列，都画上一条直线；（二）在标上“√”的行中所在的列，标上“√”；（五）去掉“√”，而且将（0）和重新写成0。√

√

√

()()()30ppt课件第五步：从[Cij]未画上直线的元素中找出最小值。让画上直线的列中元素都加上该最小值，未画上直线的行中元素都减去该最小值，随即去掉各行各列上的直线，并转入第二步。31ppt课件最小元素0.2新产生的0元素32ppt课件()()()()已得到4个（0），则令[Cij]中与（0）相对应的xij=1，其余的决策变量等于0。这时，[xij]便是最优解。将最优解代入目标函数y的表达式，即得最优值ymin=126.2(分)。转入第二步,重新括0元素:返回这表明，让化验员甲、乙、丙、丁分别担当化验工作D、C、A、B，可使他们总的消耗时间最短，只消126.2分，就能完成四项化验工作。33ppt课件三、

最大化指派问题

例12

某卫生防疫站准备选拔防疫科、食品科、总务科的三名科长。几经筛选，仅剩下赵、钱、孙三名候选人。根据民主评议的统计结果,他们主持各个科的工作能力（以得分多少来衡量）如表2-14所示。试从工作能力出发，确定最优选择科长方案。防疫食品总务工作能力（分）赵353027钱373529孙382832表2－1434ppt课件

建立数学模型设：

i=1,2,3分别表示赵，钱，孙；j=1,2,3分别表示防疫科，食品科，总务科；

aij

表示i

担任j

科长的工作能力；y表示三名科长总的工作能力。于是所求数学模型是：35ppt课件例12称为最大化指派问题。

36ppt课件

一般地，最大化指派问题的数学模型是：其中[aij]称为效率矩阵。37ppt课件最大化指派问题的求解步骤如下：第一步：将最大化指派问题的效率矩阵[aij]化成[a－aij]，a=max{aij

∣i,j=1,2,…,m}第二步：求出效率矩阵为[a－aij]的最小化指派问题的最优解，以其作为最大化指派问题的最优解。第三步：把最优解代入最大化指派问题的目标函数的表达式，求出最优解。定理2.2

若效率矩阵[aij]各元素的最大值是a,则效率矩阵为[aij]的最大化指派问题与效率矩阵为[a－aij]的最小化指派问题具有相同的最优解。38ppt课件确定例12的最优选拔科长方案a=max{aij｜i,j=1,2,3}=38得：第一步：由39ppt课件

第二步：因为3811