数学模型培训讲稿1线性规划

数学模型培训讲稿1-线性规划2024/3/24数学模型培训讲稿1线性规划

运筹学是一门新兴的应用学科.由于它所研究的对象极其广泛有着许多不同的定义.

1978年联邦德国的科学词典上定义:“运筹学是从事决策模型的数学解法的一门学科”.

1976年美国运筹学会定义:“运筹学是研究用科学方法来决定在资源不充分的情况下如何最好地设计人一机系统,并使之最好地运行的一门学科”.

前者着重于处理实际问题,而对于“科学方法”则未加说明,后者强调数字解,而注重数学方法.运筹学简介

数学模型培训讲稿1线性规划运筹学一词的英文名词为operationsresearch可直译为“运用研究”和“作用研究”.早在1938年英国空军就有了飞机定位和控制系统,并在沿海有几个雷达站,可以用来发现敌机,但在一次防空大演习中发现,由这些雷达送来的(常常是互相矛盾的)信息,需要加以协调和关联,以改进作战效果,这一任务的提出即产生“运筹学”一词,英国空军成立了运筹学小组,主要从事警报和控制系统的研究.

运筹学简介

数学模型培训讲稿1线性规划

我国运筹学的先驱者从《史记.高祖本记》:“夫运筹帷幄之中,决胜于千里之外”一语摘取“运筹”二字作为这门科学的名称,既显示其军事的起源,也表明其萌芽早已出现在我国.释义筹：计谋、谋划；帷幄：古代军中帐幕。指拟定作战策略。引申为筹划、指挥。运筹学简介

数学模型培训讲稿1线性规划运筹学研究的基本特征是：系统的整体观念、多学科的综合、应用模型技术。数学模型是最为抽象的模型，当你看到数学模型时，往往看不出它所代表的现实是什么，如Y=kX。正是由于数学模型的抽象性，所以数学模型有其广泛的适应性。数学模型中的参数和变量最容易改变，运用起来也最为方便。如：参数k:m、v、R、P；变量Y:F、S、V、C；变量X:a、t、I、Q

运筹学中用的模型主要是数学模型，数学模型是运筹学的核心，可以说，没有数学模型，就没有运筹学。运筹学简介

数学模型培训讲稿1线性规划运筹学应用的步骤示意图：分析与表述问题建立模型

对模型和由模型导出的解进行检验建立起对解的有效控制对问题求解

方案实施不满意满意运筹学简介

数学模型培训讲稿1线性规划

运筹学的主要分支：1.线性规划2.非线性规划3.动态规划4.图论与网络分析5.存贮论6.排队论7.对策论8.决策论运筹学简介

数学模型培训讲稿1线性规划一.线性规划模型的建立线性规划模型

数学模型培训讲稿1线性规划建立数学模型：线性规划模型

数学模型培训讲稿1线性规划模型的特点：线性规划模型

数学模型培训讲稿1线性规划线性规划模型

数学模型培训讲稿1线性规划线性规划模型

数学模型培训讲稿1线性规划线性规划模型

数学模型培训讲稿1线性规划线性规划模型的求解----图解法

在此讨论线性规划问题的解，以下面的LP问题为例：数学模型培训讲稿1线性规划课题的来源及意义

线性规划模型的求解----图解法

数学模型培训讲稿1线性规划用Matlab求解线性规划问题命令:simpleMthd调用格式：[x,minf]=simpleMthd(A,c,b,baseVector)其中,A:约束矩阵c:目标函数系数向量b:约束右端向量baseVector:初始基向量x:目标函数取最小值时的自变量值minf:目标函数的最小值线性规划模型的求解----计算机的实现

数学模型培训讲稿1线性规划例1：用单纯形法求解线性规划问题线性规划模型的求解----计算机的实现

数学模型培训讲稿1线性规划化成标准型：线性规划模型的求解----计算机的实现

数学模型培训讲稿1线性规划输入命令：A=[-12100;23010;1-1001];C=[-4-1000];b=[4;12;3];[x,minf]=simpleMthd(A,c,b,[345])所得结果：X=4.20001.20000Minf=-18线性规划模型的求解----计算机的实现

数学模型培训讲稿1线性规划例2：用大M法求解线性规划问题线性规划模型的求解----计算机的实现

数学模型培训讲稿1线性规划化成标准型：线性规划模型的求解----计算机的实现

数学模型培训讲稿1线性规划输入命令：A=[1-211000;-4120-110;-2010001];C=[-3110010001000];b=[11;3;1];[x,mf]=simpleMthd(A,c,b,[467])所得结果：X=4.00001.00009.0000mf=-2线性规划模型的求解----计算机的实现

数学模型培训讲稿1线性规划其中,A:不等式约束的系数矩阵，Aeq：等式约束的系数矩阵beq:等式约束右端向量b:不等式约束右端向量Lb，ub:自变量的上下范围在MatlabR2008b求解线性规划问题的函数:linprog求解对象是：线性规划模型的求解----计算机的实现

数学模型培训讲稿1线性规划调用格式：1）x=linprog(f,A,b),要求线性规划只存在不等式约束。2）x=linprog(f,A,b，Aeq,beq),要求线性规划存在不等式和等式约束。3）x=linprog(f,A,b，Aeq,beq,lb,ub),一般格式4）x=linprog(f,A,b，Aeq,beq,lb,ub，x0),x0为设定的初始值。5）x=linprog(f,A,b，Aeq,beq,lb,ub，x0，options),x0为设定的初始值,options来指定优化参数线性规划模型的求解----计算机的实现

数学模型培训讲稿1线性规划例3：linprog函数求解线性规划问题线性规划模型的求解----计算机的实现

数学模型培训讲稿1线性规划输入命令：f=[-4;-1];A=[-12；23；1-1；];b=[4;12;3];[x,fval,exitflag,output,lamda]=linprog(f,A,b,[],[],zeros(2,1))所得结果：Optimizationterminated.X=4.20001.20000fval=-18.0000exitflag=1output=iterations:5algorithm:`large-scale`:interiorpointcgiterations:0message：’Optimizationterminated‘线性规划模型的求解----计算机的实现

数学模型培训讲稿1线性规划线性规划建模举例数学模型培训讲稿1线性规划线性规划建模举例数学模型培训讲稿1线性规划线性规划建模举例数学模型培训讲稿1线性规划线性规划建模举例数学模型培训讲稿1线性规划线性规划建模举例数学模型培训讲稿1线性规划线性规划建模举例数学模型培训讲稿1线性规划线性规划建模举例数学模型培训讲稿1线性规划灵敏度分析举例数学模型培训讲稿1线性规划灵敏度分析举例数学模型培训讲稿1线性规划灵敏度分析举例数学模型培训讲稿1线性规划灵敏度分析举例数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划课题的来源及意义

特殊的线性规划模型----运输问题

数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。但具体计算和术语有所不同。可归纳为：(1)找出初始基可行解。即初始调运方案(2)进行最优检验，判别是否最优(3)若不是最优，对方案进行调整和改进，直到最优。运输问题的求解----表上作业法

数学模型培训讲稿1线性规划

例1某公司经销甲产品。它下设三个加工厂。

每日的产量分别是：A1为8吨，A2为5吨，A3为11吨。

该公司把这些产品分别运往四个销售点。各销售点每日销量为：B1为4吨，B2为7吨，B3为6吨，B4为7吨。

已知从各工厂到各销售点的单位产品的运价为表3-2所示。

问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。

运输问题的求解----表上作业法

数学模型培训讲稿1线性规划问该公司应如何调运产品，在满足各销点的需要量的前提下，使总运费为最少。运输问题的求解----表上作业法

数学模型培训讲稿1线性规划运输问题的求解----表上作业法

数学模型培训讲稿1线性规划P2数学模型培训讲稿1线性规划求解（P2）：

1.给出初始调运方案

两种方法来确定初始方案

（1）最小元素法和沃格尔法

这方法的基本思想是按单位运价的大小决定供应的先后，优先满足单价运价最小者的供销要求(1)找出初始基可行解。即初始调运方案(2)进行最优检验，判别是否最优(3)若不是最优，对方案进行调整和改进，直到最优。运输问题的求解----表上作业法

数学模型培训讲稿1线性规划运输问题的求解----表上作业法

数学模型培训讲稿1线性规划运输问题的求解----表上作业法

数学模型培训讲稿1线性规划用最小元素法给出的初始解是运输问题的基可行解，其理由为：(1)用最小元素法给出的初始解，是从单位运价表中逐次地挑选最小元素.并比较产量和销量。当产大于销，划去该元素所在列。当产小于销，划去该元素所在行。然后在未划去的元素中再找最小元素，再确定供应关系。运输问题的求解----表上作业法

数学模型培训讲稿1线性规划用最小元素法给出的初始解是运输问题的基可行解，其理由为：这样在产销平衡表上每填入一个数字，在运价表上就划去一行或一列。表中共有m行n列，总共可划(n+m)条直线。但当表中只剩一个元素时，这时当在产销平衡表上填这个数字时，而在运价表上同时划去一行和一列。此时把单价表上所有元素都划去了，相应地在产销平衡表上填了(m+n-1)个数字。即给出了(m+n-1)个基变量的值。数学模型培训讲稿1线性规划

用最小元素法给出初始解时，有可能在产销平衡表上填入一个数字后，在单位运价表上同时划去一行和一列。这时就出现退化。关于退化时的处理将后面加以讲述。

运输问题的求解----表上作业法

数学模型培训讲稿1线性规划2.方案的最优检验和改进---闭回路法和位势法（1）闭回路法在给出调运方案的计算表上，如表1，数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划从每一空格出发找一条闭回路。它是以某空格为起点。用水平或垂直线向前划，当碰到一数字格时可以转90°后，继续前进，直到回到起始空格为止。闭回路如图的(a),(b),(c)等所示。数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划闭回路法的特点：1.闭回路的其余三个顶点均应由填有数字的格组成2.每一个空格都存在唯一一条这样的闭回路3.闭回路的形状不一定是简单的矩形数学模型培训讲稿1线性规划最优检验标准：1.观察各个空格的检验数，若存在负检验数，说明运费还可以减少。2.若同时存在几个负检验数时，通常以绝对值最大者对应的变量为引入变量3.若存在非基变量的检验数为零，则说明最优方案不唯一。数学模型培训讲稿1线性规划4.确定引入变量后，对其闭回路上各顶点的运量作尽可能多的调整，使其中某个数字格的运量变为0，这个格对应的变量就是退出变量。数学模型培训讲稿1线性规划4.当同时有几个变量为0时，就发生退化，选取其中一个为退出变量，其余的需在对应格中填入0，以保持填有数字的格的个数为m+n-1个。数学模型培训讲稿1线性规划新方案的总运费为：122元对这一方案进行最优检验。最优方案数学模型培训讲稿1线性规划前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。就需要把产销不平衡的问题化成产销平衡的问题。1.当产大于销产销不平衡的运输问题及其求解方法数学模型培训讲稿1线性规划前面所讲表上作业法，都是以产销平衡为前提条件的；但是实际问题中产销往往是不平衡的。就需要把产销不平衡的问题化成产销平衡的问题。1.当产大于销产销不平衡的运输问题及其求解方法数学模型培训讲稿1线性规划运输问题的数学模型可写成(P4)

数学模型培训讲稿1线性规划增加一个假想的销地j=n+1(实际上是储存)，该销地总需要量为而在单位运价表中从各产地到假想销地的单位运为，就转化成一个产销平衡的运输问题

数学模型培训讲稿1线性规划所以这是一个产销平衡的运输问题。

此时数学模型为：数学模型培训讲稿1线性规划

2.当销大于产时，

可以在产销平衡表中增加一个假想的产地i=m+1，该地产量为

在单位运价表上令从该假想产地到各销地的运价，同样可以转化为一个产销平衡的运输问题.。

数学模型培训讲稿1线性规划产销平衡的运输问题数学模型培训讲稿1线性规划例3某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，作出使该厂全年生产(包括储存、维护)费用最小的决策

产销不平衡的运输问题应用举例数学模型培训讲稿1线性规划解由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的用于第j季度交货的柴油机数。根据合同要求，必须满足

产销不平衡的运输问题应用举例数学模型培训讲稿1线性规划又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：

产销不平衡的运输问题应用举例数学模型培训讲稿1线性规划

第i季度生产的用于j季度交货的每台柴油机的实际成本cij应该是该季度单位成本加上储存、维护等费用。cij的具体数值见

产销不平衡的运输问题应用举例数学模型培训讲稿1线性规划设用ai表示该厂第i季度的生产能力，bj表示第i季度的合同供应量，则问题可写成：

目标函数：满足产销不平衡的运输问题应用举例数学模型培训讲稿1线性规划显然，这是一个产大于销的运输问题模型。注意到这个问题中当i＞j时，xij=0，所以应令对应的cij=M，再加上一个假想的需求D，就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表(合在一起，数学模型培训讲稿1线性规划经用表上作业法求解，可得多个最优方案，表3-32中列出最优方案之一。即第Ⅰ季度生产25台，10台当季交货，15台Ⅱ季度交货；Ⅱ季度生产5台，用于Ⅲ季度交货；Ⅲ季度生产30台，其中20台于当季交货，10台于Ⅳ季度交货。Ⅳ季度生产10台，于当季交货。按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元。数学模型培训讲稿1线性规划1.若全部变量取整数，称为全整数规划（AllIntegerProgramming）或纯整数规划（PureIntegerProgramming）2.若部分变量取整数，称为混合整数规划（MixedIntegerProgramming）3.若变量只取0或者1，称为0-1规划1）什么是整数规划特殊的线性规划模型----整数规划

数学模型培训讲稿1线性规划2）整数规划的实际背景整数规划是数学规划的一个重要分枝，有广泛的应用背景，如指派问题、背包问题、生产调度等都是整数规划问题；整数规划又是最难求解的问题之一，至今还没有找到有效算法3)整数规划与线性规划的关系整数规划=相关的线性规划+整数约束整数规划是约束得更紧的问题,它的可行域是其相关线性规划问题可行域的一个子集；整数解的数目远少于线性规划的解，只要可行域有界，整数解的数目有限；整数规划的求解难度远大于线性规划。特殊的线性规划模型----整数规划

数学模型培训讲稿1线性规划

分支定界法可用于解纯整数或混合的整数线性规划问题。在20世纪60年代初由LandDoig和Dakin等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数线性规划的重要方法。

思想：设有最大化的整数线性规划问题A，与它相应的线性规划为问题B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作；而A的任意可行解的目标函数值将是z*的一个下界。分支定界法就是将B的可行域分成子区域(称为分解)的方法，逐步减小和增大，最终求到z*。现举例说明：整数规划的求解---分支定界法

数学模型培训讲稿1线性规划例：求解如下整数规划问题：整数规划的求解---分支定界法

数学模型培训讲稿1线性规划

解先不考虑条件⑤，即解相应的松弛问题：

1.舍弃整数条件得原问题（A）的松弛问题(B)整数规划的求解---分支定界法

数学模型培训讲稿1线性规划可得(B)的最优解为x1=4.81，x2=1.82，z0=356整数规划的求解---分支定界法

数学模型培训讲稿1线性规划

可见它不符合整数条件⑤。这时z0是问题A的最优目标函数值z*的上界，记作z0=。而在x1=0，x2=0时，显然是问题A的一个整数可行解，这时z=0，是z*的一个下界，记作=0，即0≤z*≤356可得(B)的最优解为x1=4.81，x2=1.82，z0=356数学模型培训讲稿1线性规划

首先注意其中一个非整数变量的解，如x1，在问题B的解中x1=4.81。于是对原问题增加两个约束条件x1≤4，x1≥5可将原问题分解为两个子问题B1和B2(即两支)，给每支增加一个约束条件，如图所示。这并不影响问题A的可行域.x1≤4，x1≥5(B)的最优解为x1=4.81，x2=1.82，z0=356数学模型培训讲稿1线性规划松弛问题(B)问题B的解中x1=4.81。于是对原问题增加两个约束条件x1≤4，x1≥5可得(B)的最优解为x1=4.81，x2=1.82，z0=356定界：0≤z*≤356，z*为原问题最优解分支数学模型培训讲稿1线性规划松弛问题(B1)松弛问题(B2)整数规划的求解---分支定界法

数学模型培训讲稿1线性规划显然没有得到全部变量是整数的解。因z1＞z2，故将改为349，那么必存在最优整数解，得到z*，并且0≤z*≤349继续对问题B1和B2进行分支因z1＞z2，故先分解B1为两支。增加条件x2≤2者，称为问题B3；增加条件x2≥3者称为问题B4。第一次迭代0≤z*≤356整数规划的求解---分支定界法

数学模型培训讲稿1线性规划分支比较，剪支第一次迭代（定界）0≤z*≤349数学模型培训讲稿1线性规划（定界）340≤z*≤341第二次迭代数学模型培训讲稿1线性规划分支剪支第二次迭代时（定界）340≤z*≤341剪支数学模型培训讲稿1线性规划第三次迭代时（定界）340≤z*≤340数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划从以上解题过程可得到，用分支定界法求解整数线性规划(最大化)问题的步骤为：

将要求解的整数线性规划问题称为问题A，将与它相应的松弛问题称为问题B。(1)解问题B，可能得到以下情况之一。①B没有可行解，这时A也没有可行解，则停止。②B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。③B有最优解，但不符合问题A的整数条件，记它的目标函数值为整数规划的求解---分支定界法

数学模型培训讲稿1线性规划（3）分支，在B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以［bj］表示小于bj的最大整数。构造两个约束条件xj≤［bj］和xj≥［bj］+1

2)用观察法找问题A的一个整数可行解，一般可取xj=0，j=1，…，n，试探，求得其目标函数值，并记作。

以z*表示问题A的最优目标函数值；这时有将这两个约束条件，分别加入问题B，求两个衍生问题B1和B2。不考虑整数条件求解这两个衍生问题的松弛问题。整数规划的求解---分支定界法

数学模型培训讲稿1线性规划定界，1)以每个松弛问题为一分支标明求解的结果，与其他问题的解的结果中，找出最优目标函数值最大者作为新的上界。2)从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界，若无可行解，令

3)各分支的最优目标函数中若有小于者，则剪掉这支(用打×表示)，即以后不再考虑了。若大于，且不符合整数条件，则重复第一步骤。一直到最后得到z*为止，得最优整数解xj*，j=1，…，n。整数规划的求解---分支定界法

数学模型培训讲稿1线性规划

用分支定界法可解纯整数线性规划问题和混合整数线性规划问题。它比穷举法优越。因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。整数规划的求解---分支定界法

数学模型培训讲稿1线性规划1）先不考虑整数条件求解松弛问题，记原问题为p2）用单纯形法求解松弛问题（p1）得其最优解为3）若解均为分数，故不是最优解，采用割平面（建立割平面）

方法：a）考虑基变量（值为分数）所在的约束方程b)将这个方程中的系数和右侧常数分成整数和非负真分数。c)将带整数系数的部分移至等号右侧d)根据非负要求可得到割平面方程，用不是添加的变量表示出来4）将割平面方程作为新的约束条件添加到（p1）中，得到新的线性规划问题（p2）。5)用单纯形法求解（p2）,检查是否最优，是，停止；否则，返回3）。整数规划的求解---割平面法

数学模型培训讲稿1线性规划整数规划的求解---割平面法

数学模型培训讲稿1线性规划数学模型培训讲稿1线性规划整数规划的Matlab的实现：

1.分枝定界法调用格式：[intx,intf]=IntProgFZ(f,A,b,Aeq,beq,lb,ub)2.割平面法。调用格式[intx,intf]=DividePlane(A,c,b,basevector)整数规划的求解---计算机的实现

数学模型培训讲稿1线性规划0-1型整数线性规划:在整数线性规划中，如果它的变量xi仅取值0或1。此时xi称为0-1变量，或布尔变量.它和一般整数线性规划的约束条件形式是一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。在本节我们先介绍引入0-1变量的实际问题，再研究解法。一.什么是0-1规划特殊的整数规划-----0-1规划

数学模型培训讲稿1线性规划用Matlab工具箱中函数bintprog来求解0-1整数规划例1.目标函数maxz=3x1-2x2+5x5约束条件：x1+2x2-x3≤2①x1+4x2+x3≤4②(5-17)x1+x2≤3③4x1+x3≤6④x1，x2，x3=0或1⑤输入：A=[12-1;141;110;041]f=[-3;2;-5]b=[2;4;3;6][xm,fv]=bintprog(f,A,b)运行结果：Optimizationterminated.xm=101fv=-8特殊的整数规划-----0-1规划

数学模型培训讲稿1线性规划在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。这类问题称为指派问题或分派问题(assignmentproblem)。特殊的整数规划-----分派问题

数学模型培训讲稿1线性规划

价值系数矩阵例有5个工人，要分派他们分别完成5项工作，每人做各项工作所消耗的时间表如下所示，问应分派哪个人去完成哪项工作，可使总的消耗时间为最小？特殊的整数规划-----分派问题

数学模型培训讲稿1线性规划特殊的整数规划-----分派问题

数学模型培训讲稿1线性规划类似有：有n项加工任务，怎样指派到n台机床上分别完成的问题；有n条航线，怎样指定n艘船去航行问题……。对应每个指派问题，需有类似表那样的数表，称为效率矩阵或系数矩阵，其元素cij＞0(i,j=1,2，…，n)表示指派第i人去完成第j项任务时的效率(或时间、成本等)。解题时需引入变量xij；其取值只能是1或0。并令

特殊的整数规划-----分派问题

数学模型培训讲稿1线性规划

当问题要求极小化时数学模型是：

①②③④特殊的整数规划-----分派问题

数学模型培训讲稿1线性规划分派问题是0-1规划的特例，也是运输问题的特例；即n=m,aj=bi=1当然可用整数线性规划，0-1规划或运输问题的解法去求解，这就如同用单纯形法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法。特殊的整数规划-----分派问题

数学模型培训讲稿1线性规划分派问题的最优解有这样性质，性质：若从系数矩阵(cij)的某一行(或某一列)各元素中分别减去该行(列)的最小元素，得到新矩阵(bij)，那么以(bij)为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。特殊的整数规划-----分派问题

数学模型培训讲稿1线性规划

利用这个性质，可使原系数矩阵变换为含有很多0元素的新系数矩阵，而最优解保持不变，在系数矩阵(bij)中，我们关心位于不同行不同列的0元素，以下简称为独立的0元素。若能在系数矩阵(bij)中找出n个独立的0元素；则令解矩阵(xij)中对应这n个独立的0元素的元素取值为1，其他元素取值为0。将其代入目标函数中得到zb=0，它一定是最小。这就是以(bij)为系数矩阵的指派问题的最优解。也就得到了原问题的最优解。特殊的整数规划-----分派问题

数学模型培训讲稿1线性规划问题的关键：在于寻找产生这组位于不同行不同列的零元素的方法---匈牙利数学家（konig)发展并证明了这种方法。设已给定一个初始的价值系数矩阵，运用匈牙利法求最优分派的步骤如下：1.找出每行（或每列）的最小元素，将的每行（或每列）的所有元素都减去该行（或该列）的最小元素，然后转下一步。2.找出每列（或每行）的最小元素，若它们均等于零，转下一步。否则，以其每列（或每行）的所有元素减去其最小元素。至此所得价值系数矩阵的各行和各列均含有零元素，并称其为简约化的价值系数矩阵。数学模型培训讲稿1线性规划3.以最少的m条直线（水平的或竖直的）去覆盖（或说划去）简约化价值系数矩阵中的所有零元4.若m=n，停止；可从上述简约化的价值系数矩阵的零元中找到一组位于不同行且不同列的零元，令对应于这组零元位置的变量，其余变量。就得到了一个最优解。若m<n，从未被m条直线覆盖的元素中找出最小元素，从所有未被覆盖的元素中将它减去，并将这个最小元素加在所有位于水平覆盖线和竖直覆盖线相交处的元素上，而其它被覆盖的覆盖的元素保持不变。这样得到一个新简约化价值系数矩阵，转第3步

特殊的整数规划-----分派问题

数学模型培训讲稿1线性规划注：当价值系数矩阵较大时，由简约化价值系数矩阵中的零元确定分配方案时，遵循：如