当前位置：文档之家 › 线性规划和匈牙利法.doc

线性规划和匈牙利法.doc

  • 格式：doc
  • 大小：139.00 KB
  • 文档页数：6

一、线性规划

l线性规划的含义和数学模型的建立

线性规划(Linear Programming)就是在一定的约束条件下，寻求某一个目标函数的最大

值或最小值，以求取最优方案的一种规划方法。

在生产管理中运用线性规划时，首先要把所要解决的实际问题．如投资问题、计划安排问题、下料问题、运输问题、库存问题等，经过归纳和整理，建立数学模型，然后用相应的方法求出模型的最优解。线性规划模型由两部分组成：目标函数和约束条件。 建立模型的步骤是：首先明确目标函数，即确定该生产问题所追求的目标，如利润、产量、成本等，和它所对应的决策变量，建立以决策变量表示的线性函数式。当追求的目标是经济效果时，在函数式前冠以max，这就是极大化问题；当追求的目标是资源消耗时，在函数式前冠以min，这就是极小化问题。其次建立为实现目标函数所需满足的各种约束条件，如设备、原材料、劳动力、能源的使用限制等，并以线性等式或不等式表示。

现举例说明线性规划模型的建立。

例 经市场调查研究，某工厂决定生产A、B两种产品，它们的生产条件、经济指标如表3-1所示，求工厂取得最大利润的生产方案。

解：设该工厂生产A、B两种产品的计划产量分别为x1、x2件，它们必须满足约束条件：钢材的限制情况30021xx；人力的限制情况400221xx；预测市场销售限制情况2502x；x1和x2必须为非负。其目标函数式可表达为：max z=50x1+100x2。经整理上述的线性规划问题可建立如下的数学模型

目标函数 max z=50x1+100x2

约束条件0,25040030021221212xxxxxxx

2.线性规划的图解法

对于一个仅含两个决策变量的线性规划问题，可用图解法求出其最优解。现仍用上侧介绍具体求法。

首先，在平面图形上建立以x1为横轴、x2为纵轴的直角坐标系，因为线性规划数学模型中要求所有变量为非负数，因此只有在直角坐标系的第一象限的坐标点才有实际意义。按方程

250,400,300221212xxxxx在图上作三条直线。由解析几何知道，不仅三条直线上所有点满足各约束条件的要求，而且三条直线的各左下半平面所有坐标点，也均满足各约束的要求，由此可知同时满足约束的区域是凸多边形的0ABCD，见图3-7a中的阴影部分，因为该区域的坐标点均满足约束条件，故称可行解．整个区域称为可行域。

然后，可把目标函数xxz2110050改写为1002112zxx，在坐标图上这是以z为参数、斜率为21的一族平行直线。在图3-7b中容易看出，这族平行线中，离0点越远的直线，z的值越大，要确定一条直线使它尽可能远离0点．又至少与凸多边形0ABCD有一个交点。显然，由图可见，当直线通过B点时，与可行域相切，此点即为最优解，目标函数在此点达到最大值，对应于B点的甲、乙两种产品的产量为：甲产品501x件，乙产品2502x件，工厂获得最大利润为z=27500元。

3.单纯形法的计算

当两个以上变量的线性规划求解时，运用单纯形法更为筒捷。它的基本原理是先确定一个基本可行解，再通过数学选代过程逐步达到最优解。

这里仍以上题为例，介绍单形法求解的基本步骤。

（1） 将上述模型变为标准式

目标函数 xxxxxz5432100010050max 约束条件

为松弛变量xxxxxxxxxxxxjj54352421321,,)5,4,3,2,1(02504002300

（2） 建立初始单纯表，如表3-2所示，进行迭代，求得最优解。

解单纯形表的步骤：先计算初始表的检验数CCCBajjj，并找出关键列(↑)。关键列应找检验数行绝对值最大的值数。从本例初始表中看出，x2是关键列，x2应调人到xB栏（基本变量栏)的变量。再找出关键行(←)。关键行由常数项列与关键列数值的最小比值（Q）决定。见表右端。关键行上的变量就是调出的变量，从本倒初始表中看出x5是应调出的变量。经迭代，在极大化问题中，当检验数行的数值均为零或正值；在极小化问题中，当检验数行的数值均为零或负值，表明最优解已找到，本倒经过二次迭代，得最优解501x，2502x，最优目标函数值z=27500 (元)。

二、 生产任务分配的匈牙利法

在实际的生产管理工作中，常会遇到这样的问题，就是如何根据生产作业汁划将不同任务在不同的工人(或班组)之间分配，使完成任务总的消耗时间或费用最小。解决这类问题的简便而有效的方法是匈牙利法，它是由匈牙利数学家D. Konig所提出。

例 有4项任务A、B、C、D，分别由甲、乙、丙、丁4个人去完成，规定每人承担其中一项任务，不同的人完成同一任务所花时间(h)不同，见表3-3，求如何分配，使完成这4项任务的总时间最小。

匈牙利法求解此问题的步骤是：

1） 按表3-3列出矩阵

2) 将矩阵作行、列约简：首先进行行约简。在矩阵的每一行中选取最小元素，然后将该行的各元素都减去此数，得到如下新矩阵

行约简是比较一名工人担任不同任务时所花的时间，各行中减去最小值后的时间表示该工人担任其它任务时，所多花费的时间，每行中的“0”表示该工人承担这项任务最有利。

然后将经过行约筒后的矩阵中没有“0”的列再进行约简，即从该列中选出最小元素，并将其它元素减去此数，得到新矩阵

列约简是比较一项任务有不同工人承担所托时间，各列中减去最小值后的时间表示任务由其他工人担任时，所多花费的时间，每列中的“0”表示这项任务由该工人承担最有利。

3) 检验是否已得最优分配方案；作零的覆盖线，即对有“0”的行和列，划上一条覆盖线，能覆盖所有零元素的最少覆盖线数称为维数，当覆盖线的维数等于矩阵阶数时，可知已得最优分配方案，若维数小于阶数，再作调整。本例可用三条覆盖线覆盖住所有零元素，维数是3，矩阵的阶数是4，维数不等于阶数，因此矩阵还必须调整。

4) 矩阵的调整。在上述矩阵中．有三种元素，一种是无线覆盖元素，另一种是单线覆盖元素，还有一种是双线覆盖元素。在无线覆荒元素中找出最小值，本例为“1”，将无线覆盖得元素都减去“1”，而双线覆盖的元素加上“1”，单线覆盖的元素不变。这样得到新矩阵

5) 再检验——作覆盖线，方法与步骤3相同。现在的最少覆盖线数为4，与矩阵阶数相等，可知已能进行最优分配。

6) 确定最优分配方案。进行具体分配时，可以对只有一个零元素的列(行)先分配(记√号)，分配后，划去与该零元素同行(列)的其他零元素(记×号)这样依改做完各列(行)，得到分配结果。如果矩阵能通过直接观察找到位于不同行不同列的零元素，那么就可以直接确定分配方案。

最优分配方案：甲——D，乙——B，丙——A，丁——C。

总消耗工时为：Z=7+5+4+5=21 (h)。

合集下载

指派模型【数学建模】

指派模型【数学建模】

指派模型 宋海洲 一：指派问题 设有n个人被分配去做n件工作，规定每个人只做一件工作，每件工作只由一个人做。已知第i个人做第j件工作的效率（时间或费用)为 ，并假设 。 ?问：应如何分配才能使总效率（总时间或总费用）最高？ 引进变量 设 建立模型 分析 这是线性规划模型； 也是整数规划模型；0-1规划模型； 更是运输模型。 共有n*n个变量，实际上只需找n个变量为1即可，因此这是高度退化的线性规划模型。 例1 设有5个人被分配去做5件工作，规定每个人只做一件工作，每件工作只由一个人做。已知第i个人做第j件工作的费用如下表所示。问：应如何分配工作才能使总费用最省？ 二：匈牙利法 定义：指派问题的效益矩阵：

效益矩阵的性质 定理1：从效益矩阵C的第k行（或第k列）的每一个元素中减去一个常数a得到的矩阵C’所表示的指派问题具有相同的最优解。（ C’称缩减效益矩阵） 定义：如果这些0元素分布在效益矩阵的不同的行和不同的列上，则称这些0元素为独立的0元素。 定理2：若方阵的一部分元素为0，一部分元素不为0，则覆盖方阵内所有0元素的最少直线数，等于矩阵中独立的0元素的最多个数（匈牙利：konig） 积和式 定义： 积和式的性质 按行展开性； 转置不变性； 换行不变性； 倍法变换增倍性； 单行可加性； Laplace法则。 补矩阵 定义： 匈牙利法解指派模型算法 第一步：将原指派问题的效益矩阵C进行变换得矩阵CC，使得CC的各行各列均出现0元素，其方法是： （1）从效益矩阵C的每行元素减去该行最小元素； （2）在从所得的效益矩阵的每列元素减去该列最小元素。 第二步：计算CC的补矩阵D,计算D的积和式per(D)。 判断per(D)是否不等于0，如果per(D)不等于0，转第五步； 如果per(D)等于0，转第三步。 第三步： （1）在CC中找0元素最少的一排（行或列），选中其中一个0，记为0，将该0所在的行及列划去。 （2）对上述划去一行及一列的矩阵，重复（1）的做法。 „„. 一共得到m个0 。(m n) 记下这m个0 所在的行号i1,i2,„,im及列号j1,j2,„,jm. (则CC所有的0或0必在i1,i2,„,im行中或在j1,j2,„,jm中） (3)①：在 CC中找出不在i1,i2,„,im行的0，记下他们的列号r1,r2,„;并将这些列划竖线； ②：在划去竖线的CC中找出不含0的列的0，记下他们的行号s1,s2,„;并将这些列划横线； 重复① ②，则这些直线构成覆盖方阵CC内所有零元素的最少直线。 第四步：调整CC ,使之增加一些0，为此按如下方法进行： （1）在没有直线覆盖的元素中，找出最小元素x; （2）在未划线的行减去最小元素x； （3）在划线的列加上最小元素x；

线性规划

线性规划

-1- 第二章 线性规划

线性规划（linear programming，简称LP）是运筹学的一个重要分支，研究得比较早，尤其自1947年丹捷格（G.B.Dantzig）提出了单纯形法之后，线性规划在理论上趋向成熟．线性规划研究的对象大体可分为两大类：一类是在现有的人、财、物等资源的条件下，研究如何合理地计划、安排，可使得某一目标达到最大，如产量、利润目标等；另一类是在任务确定后，如何计划、安排，使用最低限度的人、财等资源，去实现该任务，如使生产成本、费用最小等．这两类问题从本质上说是相同的，即都在一组约束条件下，去实现某一个目标的最优（最大或最小）．线性规划研究的问题要求目标与约束条件函数均是线性的，而目标函数只能是一个．在经济管理问题中，大量的问题是线性的，有的可以转化为线性的，从而使线性规划有极大的应用价值．据美国《财富》杂志对全美500家大公司的调查，线性规划的应用名列前茅，有85%左右的公司频繁地使用线性规划．

第一节 线性规划问题及其数学模型

一、线性规划问题的数学模型

在生产实践和日常生活中，经常会遇到如何合理地使用有限资源（如资金、劳力、材料、机器、仪器设备、时间等），以获得最大效益的问题．

例2-1 某制药厂在计划期内要安排生产Ⅰ、Ⅱ两种药品，这些药品分别需要在DCBA、、、四种不同的设备上加工．按工艺规定，每千克药品Ⅰ和Ⅱ在各台设备上所需要的加工台时数如表2-1．已知各设备在计划期内有效台时数（1台设备工作1小时称为1台时）分别是12、8、16和12．该制药厂每生产1千克药品Ⅰ可得利润200元，每生产1千克药品Ⅱ可得利润300元．问应如何安排生产计划，才能使制药厂利润最大？

表2-1 BA、两种药品每千克在各台设备上所需的加工台时数

药品 A B C D

Ⅰ 2 1 4 0 -2- Ⅱ 2 2 0 4

这是一个资源有限，但需利润最大的线性规划问题．

解 设1x，2x分别表示在计划期内药品Ⅰ和Ⅱ的产量（千克），Z表示这个期间的制药厂利润．则计划期内生产Ⅰ、Ⅱ两种药品的利润总额为21300200xxZ（元）．但是生产Ⅰ、Ⅱ两种药品在A设备上的加工台时数必须满足122221xx；在B设备上的加工台时数必须满足8221xx；在C设备上的加工台时数必须满足1641x；在D设备上的加工台时数必须满足1242x；生产Ⅰ、Ⅱ两种药品的数量应是非负的数，即0,21xx．于是上述的问题归结为：

数字集合匹配

数字集合匹配

数字集合匹配

在数学中，数字集合匹配指的是将两个集合之间的对应关系建立起来，即将两个集合的元素一一对应，每个元素仅与另一个集合中的一个元素对应。本文将从数字集合匹配的概念、应用、方法等方面详细讲述。

一、概念

数字集合匹配是指，在两个集合 A 和 B 中，满足以下条件的对应关系：

1. A 中的每个元素都恰好和 B 中的一个元素对应；

2. B 中的每个元素都恰好和 A 中的一个元素对应；

3. 两个元素之间的对应关系是唯一的。

二、应用

1. 数学建模

数字集合匹配是数学建模中常用的概念，它可以应用于各个领域的建模中。比如在货车调度问题中，要求将若干个货车按照最优的方式分配到各个目的地，这就需要使用数字集合匹配的方法。

2. 信息处理 数字集合匹配在信息处理中也有着广泛的应用。比如在计算机视觉领域中，可以用数字集合匹配的方法将图像中的特征点与模板中的特征点进行匹配，以确定图像中物体的位置和姿态等信息。

3. 人工智能

数字集合匹配在人工智能中也有着重要的应用。在机器学习领域中，可以利用数字集合匹配的方法来训练神经网络，从而实现更精确的分类和识别任务。

三、方法

数字集合匹配有多种方法，常见的有以下三种：

1. 匈牙利算法

匈牙利算法是一种经典的数字集合匹配算法，其时间复杂度为

O(n^3)。该算法的基本思想是将数字集合匹配问题转化为最大权匹配问题，并利用增广路的方法求解。

2. KM 算法

KM 算法是一种更高效的数字集合匹配算法，其时间复杂度为

O(n^2logn)。该算法的基本思想是在求解最大权匹配问题的同时，不断地优化边权的阈值，从而加速算法的收敛。

3. 线性规划 线性规划是一种更为通用的数字集合匹配方法，其时间复杂度可以达到 O(n^3)。该方法将数字集合匹配问题转化为线性规划问题，并通过对偶问题求解实现。

总之，在实际的应用中，选择不同的数字集合匹配方法，需要考虑到时间复杂度、计算效率以及问题本身的特点等因素，并进行适当的对比和分析。

线性规划知识点

线性规划知识点

线性规划知识点

一、概述

线性规划是数学规划的一种重要方法，用于解决线性约束条件下的最优化问题。它的基本思想是在一组线性约束条件下，找到使目标函数达到最大或者最小值的变量取值。

二、基本概念

1. 目标函数：线性规划的目标是最大化或者最小化一个线性函数，称为目标函数。通常用字母 Z 表示。

2. 约束条件：线性规划的变量需要满足一组线性不等式或者等式，称为约束条件。通常用字母 Ai 表示。

3. 变量：线性规划的问题中，需要确定的变量称为决策变量。通常用字母 Xi

表示。

三、标准形式

线性规划问题通常可以转化为标准形式，以便于求解。标准形式的线性规划问题包括以下要素：

1. 目标函数：目标函数是一个线性函数，需要最大化或者最小化。

2. 约束条件：约束条件是一组线性不等式或者等式。

3. 变量的非负性：变量需要满足非负性约束，即变量的取值不能为负数。

四、线性规划求解方法

线性规划问题可以通过以下方法求解： 1. 图形法：对于二维线性规划问题，可以通过绘制约束条件的直线和目标函数的等高线，找到最优解的位置。

2. 单纯形法：单纯形法是一种常用的求解线性规划问题的算法。它通过迭代计算，逐步接近最优解。

3. 整数规划法：当决策变量需要取整数值时，可以使用整数规划方法求解。整数规划问题相对于线性规划问题更加复杂，通常需要使用分支定界等方法求解。

五、线性规划的应用

线性规划在实际问题中有广泛的应用，包括但不限于以下领域：

1. 生产计划：线性规划可以匡助确定最优的生产计划，使得生产成本最低或者产量最高。

2. 运输问题：线性规划可以用于解决货物运输的最优路径问题，以降低运输成本。

3. 金融投资：线性规划可以用于确定最优的投资组合，以最大化收益或者最小化风险。

4. 资源分配：线性规划可以匡助确定资源的最优分配方案，以满足需求并最大化效益。

5. 排产问题：线性规划可以用于解决生产设备的排产问题，以最大化生产效率。