运筹学完整教案

1、第一章 线性规划与单纯形法1、教学计划第 1 次课 2 学时授课章节绪论；第一章第1节、第2节、第3节授课方式理论课 讨论课 实验课 习题课 其他课堂教学目的及要求了解线性规划模型的背景、掌握建模方法以及线性规划的标准形式。掌握两个决策变量线性规划问题可行域（凸集）、最优解的位置；了解无解（无界解、无可行解）、有解（唯一解、无穷多个解）的几何意义。课堂教学重点及难点重点：线性规划的数学模型及其标准形。在数学模型中，要求熟悉矩阵形式；在标准形中，要求学生掌握非标准形式的几种具体情形及其相应的标准化方法；如何用几何的方法求两个决策变量的线性规划问题的最优解。难点：线性规划的基本概念，例如基、基变量

2、、基解、基可行解和可行基；多个最优解如何表示。教学过程教学过程教学方法及手段引 言运筹学模型，运筹学发展历史与现状，研究方法；考核方法与教学大纲等。1.1 线性规划问题及其数学模型线性规划的数学模型：变量的确定、约束条件与目标函数。1.2 线性规划问题的标准形式线性规划的标准形式及非标准形式的标准化处理。1.3线性规划问题的解基、基变量、基解、基可行解和可行基。多媒体讲解实例讲解第 2 次课 2 学时授课章节第一章第4节授课方式理论课 讨论课 实验课 习题课 其他课堂教学目的及要求掌握单纯形法思想以及具体操作过程。课堂教学重点及难点重点：单纯形法迭代过程：（1）换入基变量的确定； （2）换出基

3、变量的确定；（3）判定当前解已经最优。难点：单纯形法思想。教学过程教学过程教学方法及手段1.4 单纯形法单纯形数表的构造，要注意代数形式和表格形式的一一对应性。单纯形法迭代过程：（1）换入基变量的确定； （2）换出基变量的确定；（3）判定当前解已经最优。多媒体讲解实例讲解第 3 次课 2 学时授课章节第一章第5节授课方式理论课 讨论课 实验课 习题课 其他课堂教学目的及要求掌握人工变量法的基本思想以及大M法和两阶段法的求解。课堂教学重点及难点重点：人工变量法的基本思想。难点：大M法和两阶段法的求解。教学过程教学过程教学方法及手段1.5单纯形法的进一步讨论及小结人工变量法的思想，大M法和两阶段法

4、的求解思路和步骤。单纯形法小结多媒体讲解实例讲解2、课件1.1线性规划问题及其数学模型线性规划模型的建立就是将现实问题用数学的语言表达出来。例1：某工厂要安排生产、两种产品，每单位产品生产所需的设备、材料消耗及其利润如下表所示。问应如何安排生产计划使工厂获利最多？设备128台时原材料A4016kg原材料B0412kg单位产品的利润（元）23解：设生产产品、的数量分别为和。首先，我们的目标是要获得最大利润，即其次，该生产计划受到一系列现实条件的约束，设备台时约束：生产所用的设备台时不得超过所拥有的设备台时，即原材料约束：生产所用的两种原材料A、B不得超过所用有的原材料总数，即非负约束：生产的产品

5、数必然为非负的，即由此可得该问题的数学规划模型：总结：线性规划的一般建模步骤如下：（1）确定决策变量确定决策变量就是将问题中的未知量用变量来表示，如例1中的和。确定决策变量是建立数学规划模型的关键所在。（2）确定目标函数确定目标函数就是将问题所追求的目标用决策变量的函数表示出来。（3）确定约束条件将现实的约束用数学公式表示出来。线性规划数学模型的特点（1）有一个追求的目标，该目标可表示为一组变量的线性函数，根据问题的不同，追求的目标可以是最大化，也可以是最小化。（2）问题中的约束条件表示现实的限制，可以用线性等式或不等式表示。（3）问题用一组决策变量表示一种方案，一般说来，问题有多种不同的备选

6、方案，线性规划模型正式要在这众多的方案中找到最优的决策方案（使目标函数最大或最小），从选择方案的角度看，这是规划问题，从目标函数最大或最小的角度看，这是最优化问题。1.2 线性规划问题的标准形式根据问题的性质，线性规划有多种形式，目标函数有要求最大化的，也有要求最小化的；约束条件可以是“”或“”的不等式，也可以是“=”；虽然决策变量一般是非负的，但也可是无约束的，即，可以在取值。为了分析问题的简化，一般规定如下的标准形式：非标准形式转化为标准形式：（1）若目标函数要求实现最小化，则可令，可将原问题的目标函数转化为即可。（2）若约束方程为“”，则可在“”的左边加上非负的松弛变量；若约束方程为“”

7、，则可在“”的左边减去非负的剩余变量。（3）若存在取值无约束的变量，则可令，其中，。例：将如下问题转化为标准形式：解：首先，用替换，其中，；其次，在第一个约束条件的左端加上非负的松弛变量；再次，在第二个约束条件的左端减去非负的剩余变量；最后，令，将求改为求。由此，可得标准形如下：1.3线性规划问题的解首先，将线性问题的标准形式用矩阵和向量形式表示如下：其中，；，1、可行解和最优解满足约束条件的所有解成为线性规划问题的可行解，其中，使目标函数达到最大的可行解成为最优解。2、基和基解设为约束方程组的维矩阵，其秩为。设为矩阵中的阶非奇异子矩阵（），则称为线性规划的一个基。不妨设前个变量的系数矩阵为线

8、性规划的一个基，则为对应于这个基的基变量。用高斯消去法可求得一个解该解得非零分量的数目不大于方程个数，称为基解。3、基可行解若基解满足非负约束，则称其为基可行解。4、可行基对应于基可行解的基，成为可行基。1.4 单纯形法一、单纯形表考察一种最简单的形式：目标函数最大化、所有约束条件均为“”。利用所有约束条件化为等号的方法，在每个约束条件的左端加一个松弛变量，并整理，重新对变量及系数矩阵进行编号，得将其与目标函数的变换形式组成个变量、个方程的方程组。若将看成不参与基变换的基变量，它与的系数构成一个基，利用初等变换将变为零，则可得据此，可设计如下的数表1000010列表示基变量，在这里为；列为基变

9、量对应的价值系数；列为约束方程的右端项；行为所有变量的价值系数；列的数字是在确定换入变量后，按规则计算后填入；最后一行为各变量的检验数，尤其要注意的是非基变量的检验数。例，求解 首先将其转换为标准形式，构造初始单纯形表如下：230000812100401640010-01204001323000由上表可得初始基可行解由于和的检验数大于零，表明上述解不是最优解，由于的检验数更大，所以，先以为换入变量。根据规则，可确定为换出变量，计算得新表如下：23000021010-1/220164001043301001/4-2000-3/4可得新解，目标函数取值。的检验数为2，换入。根据规则，可确定为换出变

10、量，计算得新表如下：23000221010-1/2-0800-41243301001/41200-201/4得新解，目标函数取值。的检验数为1/4，换入。根据规则，可确定为换出变量，计算得：23000241001/400400-21/2132011/2-1/8000-3/2-1/80得解，目标函数取值。由于所有的检验都小于零，达到最优。PS：如果目标函数是求最小化，则，检验数的最优准则为检验数大于零。1.5单纯形法的进一步讨论及小结一、人工变量法如果初始约束条件不全是小于等于号，则不能直接得到初始基（单位基）和初始基可行解，此时必须要构造人工变量。在迭代结束后，如果最后基变量中不再含有非零的人

11、工变量，表示原问题有解；反之，则表示无可行解。例：在第一个约束条件中加入松弛变量；在第二个约束条件中加入剩余变量和人工变量；在第三个约束条件中加入人工变量。（1）大M法：在一个线性规划问题的约束条件中加入人工变量后，要求人工变量对目标函数值不产生影响，可假定人工变量在目标函数中的系数为（-M）（M为很大的正数），这样在目标函数要实现最大化时，必须将人工变量从基变量中换出，否则目标函数不会实现最大化。对上例求解，加入人工变量后，规划问题变成然后，利用单纯形法求解，详见P33。（2）两阶段法第一阶段：不考虑原问题是否有基可行解；给原线性规划问题加上人工变量后，构造仅含人工变量的目标函数和要求实现最

12、小化；然后用单纯形法求解，若得到该规划的最优解为零，说明原问题存在基可行解，否则原问题无可行解，停止计算。第二阶段：将第一阶段的最重计算表出去人工变量，换回原目标函数的系数作为第二阶段计算的初始表，利用单纯形法求解。前一个例子的两阶段法求解如下：构造出第一阶段的数学模型如下：00000110111-2110001113-4120-1103/211-201000116-1-3010000000110103-20100-1-110100-11-2101-2010001-0-10010000000110123001-22-5-010100-11-2101-2010001-0000011得最优解。由于

13、人工变量，说明是原问题的基可行解，可进行第二阶段运算。利用单纯形法，从下表开始：-311000123001-2-110100-1111-20100-10001-31100-341001/3-2/3-110100-11190012/3-4/3-0001/31/3二、解的退化所有的检验数均1、基变量中有非零的人工变量，无可行解；2、某非基变量的检验数为零，有无穷多解；对于任一检验数，若对应的系数向量，则有无界解。单纯形法小结变量不需处理令；无约束令，约束条件不需处理约束条件两端同乘-1加松弛变量=加人工变量减剩余变量，加人工变量目标函数加入变量的系数松弛变量0人工变量第三章 运输问题1、教学计划第

14、 4 次课 2 学时授课章节第三章授课方式理论课 讨论课 实验课 习题课 其他课堂教学目的及要求掌握运输问题的模型特点；熟悉表上作业法的基本步骤如初始调运方案的确定，非基变量检验数的确定方法，当前解是否最优解的判断，闭回路调整方法；非平衡运输问题的求解。课堂教学重点及难点重点：初始调运方案的确定，非基变量检验数的确定，判断当前解是否最优解，闭回路调整方法，非平衡运输问题的求解方法。难点：初始基可行解的确定、判断，非平衡问题的求解思路。教学过程教学过程教学方法及手段3.1 运输问题的提出及其模型特征运输问题的提出背景及其模型特征3.2运输问题的求解：表上作业法表上作业法的思路和步骤如初始基可行解

15、的确定（最小元素法和伏格尔法），最优解的判断方法，闭回路调整方法。3.3产销不平衡的运输问题将不平衡问题转化为平衡问题。多媒体讲解实例讲解2、课件3.1 运输问题的提出及其模型特征1、背景大规模的物资调运，将物资从生产地点运往消费地点，要求在现有的交通网络下，制定出总费用最小的运输方案。2、模型特征销地产地12产量12.销量个变量，个约束方程，但由于总产量等于总销量的关系存在，所以，独立的约束方程为，因此，其可行解中的基变量个数必然是。系数矩阵：变量的系数向量除第个分量和第个为1外其余为零。3.2 运输问题的求解：表上作业法表上作业法实际上是单纯形法在求解运输问题时的一个简化，主要步骤：（1）

16、找出初始基可行解：最小元素法和伏格尔（Vogel）法最小元素法：优先满足运价最小的供销关系例： 销地产地B1B2B3B4产量（吨）A13113107A219284A3741059销量（吨）3656 销地产地B1B2B3B4产量（吨）A13113107A2（3）9284A3741059销量（吨）3656 销地产地B1B2B3B4产量（吨）A13113107A2（3）9（1）84A3741059销量（吨）3656 销地产地B1B2B3B4产量（吨）A1311（4）107A2（3）9（1）84A3741059销量（吨）3656 销地产地B1B2B3B4产量（吨）A1311（4）107A2（3）9（1

17、）84A37（6）1059销量（吨）3656 销地产地B1B2B3B4产量（吨）A1311（4）10（3）7A2（3）9（1）84A37（6）10（3）9销量（吨）3656 销地产地B1B2B3B4产量（吨）A1437A2314A3639销量（吨）3656伏格尔法：优先满足最小运价与次小运价差值最大的行、列中的最小运价所对应的供销关系。 销地产地B1B2B3B4行差A13113100A219281A371051列差2513（2）求各非基变量（空格）的检验数。闭回路法：首先找到与空格对应的闭回路，规则是从要检验空格出发用水平或垂直线向前滑，碰到数字格转90度（也可不转，空格处绝不转），最后回到出

18、发空格形成闭回路。然后，在该空格处试着增加1单位运量，并保持平衡，在闭回路作相应的调整，调整后回路的总运费相对于调整前的变动量就是该空格的检验数 销地产地B1B2B3B4产量（吨）A1437A2314A3639销量（吨）3656 销地产地B1B2B3B4产量（吨）A1437A2314A3639销量（吨）3656如空格A3B1的检验数：7*1-5*1+10*1-3*1+2*1-1*1=10空格A2B4的检验数：8*1-2*1+3*1-10*1=-1位势法：构造位势和；由基变量的检验数，可得；任取、其中之一为零，可求得其他、；最后，由可求得个非基变量（空格）的检验数。 销地产地B1B2B3B4Ui

19、A13- (-8+10)11 -(10-1)31010A219 -(9-1)28 -(9+0)9A37- (-8+5)410-(-7+5)55Vj-8-1-70（3）若存在检验数为负的空格，用闭回路法进行调整，检验数最小的空格优先调整。调整时，以相应的空格位调入格（以它对应的非基变量为换入变量），以相应的闭回路进行调整，调入量为闭回路中数字格中所能调出量的最小者。 销地产地B1B2B3B4产量（吨）A1437A2314A3639销量（吨）3656三、运输问题的特殊情况：1、多重解当非基变量的检验数为零时，会出现多重解。2、退化当在某空格处填入数值时，恰好该处供应量等于需求量，在此填入相应的数值

20、时须同时划去一行一列，此时，必须在划去的该行、该列的任意空格处添一个零。闭回路调整时，如出现两个或两个以上调出格的数值相等，此时只能选择其中一个作为调出格，另一个格中必须填零。3.3 产销不平衡的运输问题相对于标准形式的运输问题，产销不平衡问题的求解关键在于将其转化为标准形式的运输问题，即产销平衡问题。如果是产量大于销量，则可增加一个虚拟销地，任何运往虚拟销地的产量等同于就地储存，因此，所有产地运往虚拟销地的运费为0。如果是销量大于产量，则可增加一个虚拟产地，由虚拟产地运往各销地的运量实际上就是供给的缺口，表示现实中没有实际的供给，因此，由虚拟产地运往各销地的运费为0。产销不平衡问题转化为产销

21、平衡问题之后，利用表上作业法进行求解的思路和步骤和前一节的内容完全相同。 销地产地B1B2B3B4B5产量（吨）A131131007A2192804A37410509销量（吨）36533如果存在某些特定的约束，如某地存在一个最低的需求，则应注意该部分不能由虚拟产地供给，即，虚拟产地运往该地的单位运输费用应用是一个很大的正数M。需求地区化肥厂1234产量A1613221750B1413191560C192023M50D50最低需求3070010最高需求50703060需求地区化肥厂11”2344”产量A16161322171750B14141319151560C19192023MM50DM0M0

22、M050销量302070301050第四章 目标规划1、教学计划第 5 次课 2 学时授课章节第四章授课方式理论课 讨论课 实验课 习题课 其他课堂教学目的及要求了解目标规划的数学模型、目标规划的图解法，掌握目标规划数学模型的建立方法及其单纯形解法和灵敏度分析。课堂教学重点及难点重点：目标规划的数学模型特征，建立目标规划的数学模型，目标规划的单纯形法及其灵敏度分析。难点：目标规划数学模型的建立、单纯形解法及灵敏度分析。教学过程教学过程教学方法及手段4.1目标规划的数学模型目标规划数学模型的特征4.2目标规划的图解法两决策变量目标规划的图解法。4.3目标规划的单纯形解法及灵敏度分析目标规划的单纯

23、形法与灵敏度分析。多媒体讲解实例讲解2、课件4.1 目标规划的数学模型前面所讲的线性规划模型是在一种静态、理想环境中的最优决策行为。但现实决策的背景要复杂得多，某些约束条件、目标均是“软”的。目标规划数学模型具有下列特征：（1）对于决策目标来说，它允许一定的偏差，这直接表现为决策变量可以有某种偏差或；为正偏差变量，表示决策超过目标值的部分，为负偏差变量，表示决策未达到目标值的部分。考虑到决策值不可能超过同时又未达到目标值，所以，（2）绝对约束和目标约束绝对约束是指必须严格满足的等式约束和不等式约束，如线性规划中的约束，不能满足这些条件的即为非可行解。目标约束则可将右端项视为要达到的目标，但允许

24、发生证或负的偏差，因此在这些约束中加入正、负偏差变量。在线性规划的硬约束中加入正负偏差变量（加上负偏差变量、减去正偏差变量），将符号变为等号就转变为目标约束。（3）优先因子（优先等级）与权系数在现实的决策背景下，决策者往往具有多个目标，但这些目标是有主次轻重的不同。赋予优先因子，规定，表示级目标比级具有绝对的优先权，在优先保证级目标时可不考虑级目标。权系数可区别同级目标中两个目标的差异。（4）目标规划的目标函数目标规划的目标函数由各目标约束的正负偏差变量和赋予相应的优先因子构造而成。当每一目标给定后，决策者的要求是尽可能地缩小偏离目标值。因此，目标规划的目标函数只能是，其基本形式有三种： 要求

25、恰好达到目标值，即正负偏差都要求尽可能地小，此时要求不超过目标值，即允许达不到目标值，就是正偏差要尽可能地小，即要求超过目标值，即超过量不限，就是负偏差要尽可能地小，此时4.2 目标规划的图解法与线性规划相同，具有两变量的目标规划也可以用图解法进行求解。具体步骤与线性规划的图解法相似。4.3 目标规划的单纯形解法及灵敏度分析（1）目标规划的单纯形解法目标规划的单纯形解法与线性规划的单纯形解法基本相似，当然也具有一些独特之处：由于目标函数都市要求最小化，所以为最优准则；非基变量的检验数中含有不同等级的优先因子，即，由于，因此，检验数的正、负取决于其中所含最高优先因子的系数的正负。例略。（2）灵敏

26、度分析目标规划的灵敏度分析与线性规划也很相似，但还有优先因子的变化问题。当优先因子发生改变时，实际上就是将最终单纯形数表中各有优先因子对应的行向量交换位置即可，然后计算它们的检验数，看是否还需要进一步的处理。第五章 整数规划1、教学计划第 6 次课 2 学时授课章节第五章授课方式理论课 讨论课 实验课 习题课 其他课堂教学目的及要求掌握整数规划的数学模型、特点以及求解方法；用匈牙利法求解指派问题。课堂教学重点及难点重点：用匈牙利法求解指派问题。难点：用匈牙利法求解指派问题。教学过程教学过程教学方法及手段5.1整数规划问题的提出及一般求解方法整数规划的数学模型及特点，一般求解方法简介：分支定界法

27、和割平面法。5.2指派问题指派问题的匈牙利法求解。多媒体讲解实例讲解2、课件5.1 整数规划的数学模型的提出及一般求解方法要求一部分或全部决策变量必须取整数值得规划问题称为整数规划。其模型为： Max(或min)z=中部分或全部取整数 s.t若要求决策变量只能取值0或1的整数规划称为0-1型整数线性规划。对于一般的整数规划问题，可采用分支定界法和割平面法进行求解。5.2 指派问题及其应用一 指派问题的标准形式及数学模型在现实生活中，有各种性质的指派问题。例如，有若干项工作需要分配给若干人（或部门）来完成；有若干项合同需要选择若干个投标者来承包；有若干班级需要安排在各教室上课等等。诸如此类的问题

28、，它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。由于指派问题的多样性，有必要定义指派问题的标准形式。指派问题的标准形式（以人和事为例）是：有n个人和n件事，已知第i个人作第j件事的费用为，要求确定人和事之间的一一对应的指派方案，是完成这n件事的总费用最少。为了建立标准指派问题的数学模型，引入个0-1变量：若指派第i人作第j件事若不指派第i人作第j事i，j=1,2,n 这样，问题的数学模型可写成 （5.1）（5.4）（5.2） s.t （5.3）其中，（5.1）表示每件事必优且只有一个人去做，（5.2）表示每个人必做且只做一件事。注： 指派问题是产量（）、销量（）相等，且

29、=1，i，j=1,2,n的运输问题。 有时也称为第i个人完成第j件工作所需的资源数，称之为效率系数（或价值系数）。并称矩阵 C= = （5.5）为效率矩阵（或价值系数矩阵）。并称决策变量排成的n×n矩阵X= （5.6）为决策变量矩阵。(5.6)的特征是它有n个1，其它都是0。这n个1位于不同行、不同列。每一种情况为指派问题的一个可行解。共n!个解。其总的费用 z =CX 这里的表示两矩阵对应元素的积，然后相加。问题是：把这n个1放到X的个位置的什么地方可使耗费的总资源最少？（解最优）例1 已知效率矩阵 C= 则 X（1）= ， X（2）= 都是指派问题的最优解例12/P-149：某商

30、业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由5家建筑公司分别承建。已知建筑公司Ai（i=1，2，5）对新商店Bj（1，2，5）的建造费用的报价（万元）为（i，j=1,2,5）,见表5-9。商业公司应当对5家建筑公司怎样分派建筑任务，才能使总的建筑费用最少？表5-9B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106解：这是一标准的指派问题。若设0-1变量i,j=1,2,5当Ai不承建Bj时当Ai承建Bj时=则问题的数学模型为 Min z=4+8+10+6 s.t 若看成运输问题，且如上所述，则表5-9为商店公司B1B2B3

31、B4B5任务A1（4）（8）（7）（15）（12）1A2（7）(9)(17)(14)(10)1A3(6)(9)(12)(8)(7)1A4(6)(7)(14)(6)(10)1A5(6)(9)(12)(10)(6)1所选的公司数111115当然，第一行的1应放在（1，1）位置，此位置同时是第一列的费用最小。但一般情况下没有这么好。需找一适合一般的方法。二 匈牙利解法原理：虽然指派问题是一类特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题，因此，它可以用多种相应的解法来求解。但是，这些解法都没有充分利用指派问题的特殊性质，有效地减少计算量。1955年，库恩（W.W.Kuhn）提出了匈牙利

32、法。定理1：设指派问题的效率矩阵为C= ，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数t（t可正可负），得到新的效率矩阵，则以为效率矩阵的新的指派问题与原指派问题的最优解相同。但其最优解比原最优解之减少t.证明：设式（5.1）（5.4）为原指派问题。现在C矩阵的第k行个元素东减去同一常数t,记新的指派问题的目标函数为.则有=+=+ =+-t=-t·1=Z-t因此有 Min =min(Z-t)=minZ-t而新问题的约束方程同原指派问题。因此其最优解比相同，而最优解差一个常数。推论：若将指派问题的效率矩阵每一行即每一列分别减去各行及各列的最小元素，则得到新指派问题与原指派问题

33、有相同的最优解。证明：结论是显然的。只要反复运用定理1便可得证。当将效率矩阵的每一行都减去各行的最小元素，将所得的矩阵的每一列在减去当前列中最小元素，则最后得到新效率矩阵中必然出现一些零元素。设=0，从第i行来看，它表示第i个人去干第j项工作效率（相对）最好。而从第j列来看，这个0表示第j项工作以第i人来干效率(相对)最高。定义：在效率矩阵C中，有一组在不同行不同列的零元素，称为独立零元素组，此时每个元素称为独立零元素。例2: 已知 C= 则=0，=0，=0，=0是一个独立零元素组，=0，=0，=0，=0分别称为独立零元素。=0，=0，=0，=0也是一个独立零元素组，而=0，=0，=0，=0就

34、不是一个独立零元素组，因为=0与=0这两个零元素位于同一列中。根据以上对效率矩阵中零元素的分析，对效率矩阵C中出现的的独立零元素组中零元素所处的位置，在决策变量矩阵中令相应的=1，其余的=0。就可找到指派问题的一个最优解。就上例中 X（1）= ，就是一个最优解。同理 X（2）= 也是一个最优解。但是在有的问题中发现效率矩阵C中独立零元素的个数不够n个，这样就无法求出最优指派方案，需作进一步的分析。首先给出下述定理。定理2 效率矩阵C中独立零元素的最多个数等于能覆盖所有零元素的最少直线数。我们不证它，说一下意思：例3：已知矩阵C1= ，C2= ，C3= 分别用最少直线去覆盖各自矩阵中的零元素：C

35、1= ， C2= ， C3= 可见，C1最少需要4条线，C2最少需要4条线，C3最少需要5条线，方能划掉矩阵中所有的零。即它们独立零元素组中零元素最多分别为4，4，5。三 匈牙利法求解步骤：我们以例题来说明指派问题如何求解：例4 给定效率矩阵 C= 求解该指派问题。解：）变换效率矩阵，将各行各列都减去当前各行、各列中最小元素。min 列变换行变换7942C= = Min 0 0 4 2这样得到的新矩阵中，每行每列都必然出现零元素。）用圈0法求出新矩阵中独立零元素。（1）进行行检验对进行逐行检验，对每行只有一个未标记的零元素时，用记号将该零元素圈起。然后将被圈起的零元素所在的列的其它未标记的零元

36、素用记号×划去。如中第2行、第3行都只有一个未标记的零元素，用分别将它们圈起。然后用×划去第1列其它未被标记的零元素（第2列没有），见 =在第i行只有一个零元素=0时，表示第i人干第j件工作效率最好。因此优先指派第i人干第j项工作，而划去第j列其它未标记的零元素，表示第j项工作不再指派其它人去干（即使其它人干该项工作也相对有最好的效率）。重复行检验，直到每一行都没有未被标记的零元素或至少有两个未被标记的零元素时为止。本题中第1行此时也只有1个未被标记的零元素。因此圈起中第1行第4列的零元素，然后用×划去第4列中未被标记的零元素。这是第4行也只有一个未被标记的零元素

37、，再用圈起，见 =（2）进行列检验 与进行行检验相似，对进行了行检验的矩阵逐列进行检验，对每列只有一个未被标记的零元素，用记号将该元素圈起，然后技改元素所在行的其他未被标记的零元素打×。重复上述列检验，直到每一列都没有未被标记的零元素或有两个未被标记的零元素为止。这时可能出现以下三种情况：每一行均有圈0出现，圈0的个数m恰好等于n,即m=n.存在未标记的零元素，但他们所在的行和列中，为标记过的零元素均至少有两个。不存在未被标记过的零元素，当圈0的个数m< n.) 进行试指派若情况出现，则可进行试指派：令圈0为止的决策变量取值为1，其他决策变量取值均为零，得到一个最优指派方案，停

38、止计算。上例中得到后，出现了情况，可令=1，=1，=1，=1，其余=0。即为最优指派。若情况出现，则在对每行、每列的其它未被标记的零元素任选一个，加上标记，即圈上该零元素。然后给同行、同列的其它未被标记的零元素加标记×。然后再进行行、列检验，可能出现情况或，出现情况则由上述得到一最优指派，停止计算。若情况出现，则要转入下一步。）：做最少直线覆盖当前所有零元素。我们还以例12来说明过程：已知例12指派问题的系数矩阵为： 先对各行元素分别减去本行的最小元素，然后对各列也如此，即列变换行变换C =此时，中各行各列都已出现零元素。 为了确定中的独立零元素，对加圈，即=由于只有4个独立零元素，

39、少于系数矩阵阶数n=5,不能进行指派，为了增加独立零元素的个数，需要对矩阵作进一步的变换，变换步骤如下：（1）对中所有不含圈0元素的行打，如第3行。（2）对打的行中，所有零元素所在的列打，如第1列。（3）对所有打列中圈0元素所在行打，如第2行。（4）重复上述（2），（3）步，直到不能进一步打为止。（5）对未打的每一行划一直线，如第1，3，5行。对已打的每一列划一纵线，如第1列，既得到覆盖当前0元素的最少直线数。见。= =）：对矩阵作进一步变换，以增加0元素。在未被直线覆盖过的元素中找最小元素，将打行的各元素减去这个最小元素，将打裂的各元素加上这个最小元素（以避免打行中出现负元素），这样就增加了

40、零元素的个数。如中未被直线覆盖过的元素中，最小元素为=1，对打的第2，3行各元素都减去2，对打的第1列各元素都加上1，得到矩阵。 =）：回到步骤），对已增加了零元素的矩阵，再用圈0法找出独立零元素组。=中已有5个独立零元素，故可确定指派问题的最优方案。本例的最优解为承建X*=也就是说，最优指派方案是：让A1 B3 A2 B2 A3 B1 A4 B4 A5 B5这样按排能使总的建造费最少，为 z=79666=34（万元）四 一般的指派问题在实际应用中，常会遇到非标准形式，解决的思路是：先化成标准形式，然后再用匈牙利法求解。1 最大化的指派问题其一般形式为 s.t 处理办法：设最大化的指派问题的系

41、数矩阵为C=，m=max,令B=，则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同的最优解。例5：某工厂有4名工人A1，A2，A3，A4，分别操作4台车床B1，B2，B3，B4。每小时单产量如下表，求产值最大的分配方案。车床工人B1 B2 B3 B4A1A2A3A410 9 8 73 4 5 62 1 1 24 3 5 6解：C=，m=max10,9,8,7,5,6=10,B= =中的数=n=4, 所以 X= （5.7）即为最优解。从而产值最大的分配方案也为（5.7），最大产值为 Z=10615=222 人数和事数不等的指派问题。 若人数< 事数，添一些虚拟的“人

42、”，此时这些虚拟的“人”做各件事的费用系数取为0，理解为这些费用实际上不会发生。 若人数> 事数，添一些虚拟的“事”，此时这些虚拟的“事”被各个人做的费用系数同样也取为0。例6：现有4个人，5件工作。每人做每件工作所耗时间如下表：工作工人B1B2B3B4B5A11011428A2711101412A35691214A4131511107问指派那个人去完成哪项工作，可是总消耗最小？解：添加虚拟人A5，构造标准耗时阵：行变换C= =所圈0数=4< 5=n,下找最少覆盖0的直线。= 从未划去的元素中找最小者：4，3，7，5，1，4，7，9=1。未划去的行减去此最小者1，划去的列加上次最小

43、者1，得。=个数=n,从而的一最优指派：=从而最少耗时为 z=2767=223.一个人可做几件事的指派问题。若某人可作几件事，则可将该人化作相同的几个“人”来接受指派。这几个“人”做同一件事的费用系数当然一样。例6：对例12的指派问题，为了保证工程质量，经研究决定，舍弃建筑公司A4和A5，让技术力量较强的建筑公司A1、A2、A3来承建。根据实际情况，可以允许每家建筑公司承建一家或两家商店。求使总费用最少的指派方案。B1 B2 B3 B4 B5解：反映投标费用的系数矩阵为：A1A2A3 B1 B2 B3 B4 B5由于每家建筑公司最多可承建两家新商店，因此，把每家建筑公司化作相同的两家建筑公司（

44、和，i=1，2，3）。这样，系数矩阵变为： 上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚拟事，使之成为标准的指派问题，其系数矩阵为： B1 B2 B3 B4 B5 B6C= 列变换C =的数=5< 6=n,下找0元素的最少直线覆盖。 -1 -1= =从而得一最优指派：B4B5A3B2B6=A2B1B3A1承建商店公司 = 总费用为z=74978=35(万元)4某事不能由某人去做的指派问题某事不能由某人去做，可将此人做此时的费用取作足够大的M。例7：分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每人完成各项任务的时间如下表。由于任务重，人数少，考虑：a). 任务E必须完成，其它4项任务可选3项完成。但甲不能做A项工作。b) 其中有一人完成两项，其他人每人完成一项。试分别确定最优分