采矿系统工程 补充-线性规划与整数规划

《采矿系统工程 补充-线性规划与整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、补充线性规划与整数规划1第一节线性规划与图解法1一、线性规划的实例与定义1二、线性规划问题解的概念2三、线性规划的图解法3第二节单纯形法4一、问题概述4二、单纯形法的主要思路6三、使用单纯形表法进行系数演算7第三节整数规划概述11一、问题的提出11二、整数规划的分类11三、应用举例12第四节整数规划常用解法简介14一、分支定界法14二、割平面法14三、隐枚举法14第五节分配问题解法-匈牙利法16一、分配问题的数学模型16二、匈牙利法的基本思想16三、匈牙利法的步骤及举例17四、特殊情况的处理——最大值问题1920补充线性规划与整数规划第一节线性规划与

2、图解法在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支——数学规划，而线性规划(LinearProgramming简记LP)则是数学规划的一个重要分支。自从1947年G.B.Dantzig提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。一、线性规划的实例与定义例1某机床厂生产甲、乙两种机床，每台销售后的利润分别

3、为4000元与3000元。生产甲机床需用机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为机器10小时、机器8小时和机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？求解上述问题：设该厂生产台甲机床和乙机床时总利润最大，可将问题列表如下：机器A机器B机器C利润产品甲=x12h1h0h4000产品乙=x21h1h1h3000≤10h≤8≤7列出上述问题的数学模型，则应满足：（目标函数）(1)s.t.（约束条件）（2）这里变量称之为决策变量，（1）式被称为问题的目标函

4、数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subjectto)。上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。20在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选取适当的决策变量，是我们建立有效模型的关键之一。上述例题，虽然有着不同的实际意义，但它们具有以下的共同特性：1．求一组变量的值，它是决策者可以控制的一组变量，这

5、组变量称为决策变量。决策变量每取定一组值就表示一个具体的方案，而这个方案是可供决策者选择的若干个方案中的一个。通常要求决策变量的取值是非负的。2．决策变量要满足一定的限制条件，正因为有了这些限制条件，才约束了方案的任意性；这组限制条件称为约束条件。约束条件往往是由各决策变量之间存在的相互关系来表达，要求这种相互关系能够表示为决策变量的线性不等式或线性等式。3．决策者都有一个明确的目标，如总运费、总利润等达到最小值或最大值，并且这个目标可以表示为决策变量的线性函数，称为目标函数。具有上述共同特性的问题称为线性规划问题。因此，一般线性规划问题是具有下述形

6、式的数学问题：求决策变量(自定义自变量)：x1，x2，…，xn满足约束条件：使目标函数以矩阵形式描述：目标函数：max(min)Z=CX约束条件：AX=BX≥0二、线性规划问题解的概念一般线性规划问题的标准型为(3)(4)1．可行解：满足线性规划问题约束条件(包括非负约束)的一组值X＝(x1，x2，…，xn)T20称为线性规划问题的可行解。可行域全体可行解的集合，称为线性规划问题的可行集或可行域，记为。2．最优解：使目标函数Z取得最大(小)值的可行解，称为最优解。最优解对应的目标函数值，称为最优值。3．基、基变量、非基变量：系数矩阵A中任意一个非奇异

7、m阶子矩阵B，称为线性规划问题的一个基。如果决策变量xj所对应的系数列向量P,包含在B中，则称xj为基变量；否则，称xj为非基变量。显然，当基改变时，相应的基变量，非基变量也随之改变。4．基本解：对于有n个决策变量和m个约束方程的线性方程组，在取定基的情况下，令n-m个非基变量等于零，求得方程组的解，称这个解为线性规划问题的基本解。5．基本可行解：满足非负约束的基本解，称为基本可行解。对应于基本可行解的基B，称为可行基。显然，一个线性规划问题的基本解的个数不超过个，因此，基本可行解的个数，一般说来要小于个。即基本可行解的个数要小于基本解的个数，最多是

8、相等，而且每个基本可行解的非零分量个数不大于系数矩阵A的秩m。6．退化解：非零分量的个数小于m（约束）的基本