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

补充 线性规划与整数规划1第一节 线性规划与图解法1一、线性规划的实例与定义1二、线性规划问题解的概念2三、线性规划的图解法3第二节 单纯形法4一、问题概述4二、单纯形法的主要思路6三、使用单纯形表法进行系数演算7第三节 整数规划概述11一、问题的提出11二、整数规划的分类11三、应用举例12第四节 整数规划常用解法简介14一、分支定界法14二、割平面法14三、隐枚举法14第五节 分配问题解法-匈牙利法16一、分配问题的数学模型16二、匈牙利法的基本思想16三、匈牙利法的步骤及举例17四、特殊情况的处理最大值问题19补充 线性规划与整数规划第一节 线性规划与图解法在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。一、线性规划的实例与定义例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为机器10小时、机器8小时和机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？求解上述问题：设该厂生产台甲机床和乙机床时总利润最大，可将问题列表如下：机器A机器B机器C利润产品 甲= x12 h1 h0 h4000产品 乙= x21 h1 h1 h300010 h 8 7列出上述问题的数学模型，则应满足：（目标函数） (1)s.t.（约束条件） （2）这里变量称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选取适当的决策变量，是我们建立有效模型的关键之一。 上述例题，虽然有着不同的实际意义，但它们具有以下的共同特性： 1求一组变量的值，它是决策者可以控制的一组变量，这组变量称为决策变量。决策变量每取定一组值就表示一个具体的方案，而这个方案是可供决策者选择的若干个方案中的一个。通常要求决策变量的取值是非负的。 2决策变量要满足一定的限制条件，正因为有了这些限制条件，才约束了方案的任意性；这组限制条件称为约束条件。约束条件往往是由各决策变量之间存在的相互关系来表达，要求这种相互关系能够表示为决策变量的线性不等式或线性等式。 3决策者都有一个明确的目标，如总运费、总利润等达到最小值或最大值，并且这个目标可以表示为决策变量的线性函数，称为目标函数。 具有上述共同特性的问题称为线性规划问题。因此，一般线性规划问题是具有下述形式的数学问题： 求决策变量(自定义自变量)：x1，x2，xn满足约束条件：使目标函数 以矩阵形式描述：目标函数：max(min)Z=CX约束条件：AX=BX0二、线性规划问题解的概念一般线性规划问题的标准型为 (3) (4) 1可行解：满足线性规划问题约束条件(包括非负约束)的一组值X(x1，x2，xn)T称为线性规划问题的可行解。可行域 全体可行解的集合，称为线性规划问题的可行集或可行域，记为。 2最优解：使目标函数Z取得最大(小)值的可行解，称为最优解。最优解对应的目标函数值，称为最优值。 3基、基变量、非基变量：系数矩阵A中任意一个非奇异m阶子矩阵B，称为线性规划问题的一个基。如果决策变量xj所对应的系数列向量P, 包含在B中，则称xj为基变量；否则，称xj为非基变量。显然，当基改变时，相应的基变量，非基变量也随之改变。 4基本解：对于有n个决策变量和m个约束方程的线性方程组，在取定基的情况下，令n-m个非基变量等于零，求得方程组的解，称这个解为线性规划问题的基本解。 5基本可行解：满足非负约束的基本解，称为基本可行解。对应于基本可行解的基B，称为可行基。 显然，一个线性规划问题的基本解的个数不超过个，因此，基本可行解的个数，一般说来要小于个。即基本可行解的个数要小于基本解的个数，最多是相等，而且每个基本可行解的非零分量个数不大于系数矩阵A的秩m。 6退化解：非零分量的个数小于m（约束）的基本可行解，称为退化解。三、线性规划的图解法图解法简单直观，有助于了解线性规划问题求解的基本原理。我们先应用图解法来求解例1。如上图所示，阴影区域即为LP问题的可行域R。对于每一固定的值，使目标函数值等于的点构成的直线称为目标函数等位线，当变动时，我们得到一族平行直线。让等位线沿目标函数值减小的方向移动，直到等位线与可行域有交点的最后位置，此时的交点（一个或多个）即为LP的最优解。对于例1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为，最优目标值。第二节 单纯形法单纯形法的基本思路是：从一个基本可行解出发，转移到另一个基本可行解，每一次转移都使目标函数值得到改善，这在数学上称为从一个基本可行解到另一个基本可行解的迭代。因为基本可行解反映在几何上就是可行域的一个顶点，而可行域的顶点个数是有限的，因此，经过有限次迭代后，就可取得最优解。一、问题概述当m和n很大时, 顶点数目会很大, 例 n=100, m=50时, 顶点数目可达1029.问题: 从一个容易找到的顶点出发, 能否经过有限的几步, 最快找到最优解对应的顶点?如：约束条件: 原料限制: 工时限制: 非负条件：x1, x2 , x3, x40令 得p5可用pi(i=1,4) 的线性组合表示。xi视为系数, 存在无穷组xi可使上式成立。现在的目标是为找到使目标函数有最优值的最优组xi：因p5是二维向量, 可用两个线性无关的向量的线性组合表示, 则系数xi是唯一确定的, 对应于基本解 (注: 基本解和基本可行解的关系).例: 得 这里 定义为基变量, 定义为基向量.单纯形法的基本原理: 不断地更换基变量和基向量(对应于不断地更换顶点). 这种变换是在对应于可行区域顶点的各组基本可行解中找出最优解. 寻找起始点:做为基向量, 基本矩阵为易得 以及 对应于A点, 目标值 z/=-z=-6x1-4x2=0 (即两种产品均未安排生产).目标是通过选xi(i=1,4) 使z增长(或使-z减少)最快，x1增加一个单位, 使-z减少6个单位，x2增加一个单位, 使-z减少4个单位, 所以选择x1，使其从0增大(即使x1进基)。x1的增大受到限制，因为当x2=0, x1=100/2=50时, 使 x3=0 (原料剩余量, 用完).当x2=0, x1=120/4=30时, 使 x4=0 (工时剩余量, 用完).所以, x1=30时, 已使x4=0, x1进基增长, x4离基减少。由约束条件, 得 (1)回顾: (2)消去x1, 得 (3)目标函数 z/+6x1+4x2=0 (注z/=-z) (4) (4)中消去x1, 得 z/+ x2- x4= -180 (5)即当x1=30, x2=0, z/=-180 (即 z=180) 注: 现从A点移至D点. 问题: 能否进一步减少z?由(5)式得知, 因为x2的系数为正, 则x2由0增大, 会使z进一步减少。由(3)式和(1)式可得x2增大受到限制,当x2=40/2=20时, 使x3=0, (注x4已经为零 )当x2=30/(1/2)=60时, 使x1=0, 所以x2只能增大到20.由(3)式得, (6)考虑 (1)式, 消去x2, 得 (7)由(5)式减去(6)式可得, (8)由(7)式, 基变量, 非基变量, z/=-200。由于(8)式中x的系数均为负, z/无法再减少, 所以z/=-200, 即z=200。二、单纯形法的主要思路1) 先找出初始基本可行解, 通常选个决策变量为零, 而松弛变量等于约束方程右边值作为初始解. 2) 改进目标值进行换基. 选择目标方程中系数为正而且绝对值最大的那一项对应的变量x作为基变量. 再计算当它增加时, 将原来的首先减为零的变量做为离基变量. 然后将方程进行交换, 使进基变量在这一方程中的系数为1, 在其余方程(包括目标方程)中的系数为零(以利于迅速求得基变量值). 这是目标值将得到改善. 3) 然后进一步查看目标值能否再减少. 若目标方程中变量x的系数仍有正数, 则选最大的一项进行换基, 直到所有系数为负, 目标值无法再进一步改进为止。三、使用单纯形表法进行系数演算(一) 单纯形法思路例2-5 求解线性规划问题：(1)先化为标准型： (2)求一组基本可行解：令xlx20，得X(0)(0, 0, 10, 8)T，x3，x4为基变量。 (3)判定是否达到最优：这时Z-3x1-2x20，如非基向量x1，x2不为0，则Z还可减小。因为min(-3，-2)-3，选换入变量xl，可使目标函数改善更快些；每次只换入一个，所以保持x20。(4)改进，确定x3或x4为换出变量：由原约束方程整理得到当x20，x3，x40，则x1可能达到的最大值：min(5，8)5。这时x30，即x3为换出变量。将x2x30，x15代入约束方程，得x4=3。即得到另组基本可行解X(1)(5，0，0，3)T, Z-15。 (5)判定是否达到最优：以非基向量x2，x3代入目标函数： 可见，选x2为换入变量，仍可使目标函数改善。保持x30，重复(4)，整理后得 所以取x26，x40。代入约束方程得一组基本可行解X(2)(2，6，0，0)T，Z-18。重复(5)，得到Z-18+x3+x4，可见，x3, x4换入不能使目标函数改善。Z已达最优值。所以原问题的解为: 对应图解法可见，基本可行解从顶点(0，0)变换到(5，0)，最终在(2，6)达到Z的最优值。(二)单纯形表解法（由康托洛维奇和希奇柯克两人独立地提出，简称康-希表上作业法）。 将以上计算过程表格化，使其更简单明了，便于程序化。下而仍结合上例介绍单纯形表解法的计算过程。 (1)建立初始单纯形表。将标准型 min ZCX，AXb(X0)按顺序列入式内：将上例标准型代入：令x1x20，得X(0)(0，0，10，8)T，Z0。 进行最优性检验：-C所在行(0行)称为检验行，若所有-cj0，则对应解为最优解。否则，选列s，以确定换入变量：max(-cj)所在列，且-cj0；再选行r，以确定换出变量： ，按规则，选最小的非负比值所在行为r行。 确定主元：以r行，s列所在元素为主元，用()表示。 本例，s1，rl，主元为2。 (2)以为中心旋转运算(行初等变换)，使主元l，主元所在列其它元素变为0(实际上是进行基变量与非基变量的互换)。 上式T(B0)中，主元所在第一行所有元素除以2，使=1。然后第一行各元素(-1)后，分别加到第二行各元素上去；第一行各元素(-3)后，分别加到第0行各元素上去。进行初等变换得到：得X(1) = (5, 0, 0, 3)T，Z = -15。重复(1)中的最优性检验，可见0行元素只有c21/20，选列s=2；选行r： ，所以主元素=1/2。重复(2)旋转运算：，这时所有-cj0，因此得最优解： X(2)=(2, 6, 0, 0)T, min Z=-18。小结：单纯型表解法计算过程就是不断地寻找主元的过程(找新基变量)，然后检验是否己达到最优。 (1)选列s：max(-cj)0； (2)选行r：，若所有0，则无解； (3)作初等变换(旋转运算)，使主元1，主元所在列其余行=0，当所有-cj0，即已得到最优解。 *此方法使用前提条件是：原线性规划问题必须是“”约束。这样可使标准化后的初始单纯型表中基变量对应价值系数cj=0，且基变量对应的系数矩阵恰为单位矩阵，因此可直接得出一组初始解。若原线性规划问题为其它类型约束，则要采用别的方法。(三)举例某养鸡场养鸡10000只，用大豆和谷物饲料混合饲养，每天每只鸡平均吃混合饲料05kg，其中应至少含有01kg蛋白质和0002kg钙。巳知1kg大豆中含50蛋白质和05的钙，价格是100元kg，1kg谷物中含存10的蛋白质和04的钙，价格是030元kg，粮食部门每周只保证供应谷物饲料25000kg，大豆供应量不限,问应如何搭配两种饲料，才能使喂养成本最低?试建立该问题的数学模型。问题列表：大豆谷物用量/kg饲料量/kgx1x20.5蛋白质/kg0.50.10.1钙/kg0.50.0040.002价格/元/kg1.00.3Zmin供应量/kg25000/10000/7设：每只鸡每天成本为Z，饲养每只鸡每天用大豆x1kg，谷物x2kg，则：目标函数：Z = 1.0x1 + 0.3x2 min约束条件s.t.：饲料量 x1 + x2 0.5蛋白质 0.5x1 + 0.1 x2 0.1钙 0.5x1 + 0.1x2 0.002供应量 x2 25000/10000/7非负 x1, x2 0第三节 整数规划概述一、问题的提出 在线性规划数学模型中，决策变量都是连续性变量，可以取分数值或小数值。可是，在许多实际问题中，这种取值方式往往是不符合要求的。例如：代表人(劳动力)的决策变量及其他不可分割物体(集装箱、设备、建筑物等)的决策变量必须要求取整数值才有实际意义。从直观上看，为了得到整数值的解，只要对用单纯形法求出约分数(或小数)形式的最优解进行“舍入化整”的办法即可。但这是不可行的，一则是因为化整后不能保证解的可行性，二是因为化整后即使是可行解但却不能保证它的最优性。 例如，对整数规划问题： 不考虑整数条件，用单纯形法可求得最优解及最优值为： x14.8， x20， maxZ96 为了得到整数最优解，若直接对上面的解凑成整数解x15, x20，则成为非可行解(不满足第一个条件)。若凑成整数解x14，x20，虽然是可行解，但不是最优解(此时Z80，因为若令x14，x21，则有Z9080)。再如，若某问题的线性规划最优解是x11.5，x23.7，若采取“舍入取整”的方法求整数解，则必须找出与上述x1，x2相近的整数解的组合，即1，3，1，4, 2，3，2，4，取其中可行的并且使目标函数值最大的整数解作为近似的整数最优解。如果问题有10个取小数值的变量，为求整数解就得计算比较2101024个整数解组合。即使如此，也不一定能保证真正找到问题的整数最优解。因此，将其相应的线性规划的最优解进行“舍入”求整数最优解的方法是不能满足要求的。对求最优整数解的问题需要另行研究，这个问题就称为整数规划问题。二、整数规划的分类我们可以用下面的关系来说明整数规划的分类：所谓纯整数规划就是指问题的所有变量都要求取整数值的整数规划。它的一种特殊情况就是要求问题的所有变量都取0或1，这类问题称为纯0-l规划。 所谓混合整数规划就是指问题中只要求一部分变量取整数值，而其余变量可取连续值的整数规划，它的一种特殊情况就是要求问题一部分变量取值为0或1，而其余变量可取连续值，这类问题称为混合0-1规划。 显然0-1规划是整数规划的一种特殊形式。三、应用举例 例1 投资问题。 有N个投资项目，需连续投资M年，某大型企业要制定M年的投资规划。每年可投资金额为Bi(i1，2，M)，由N个投资项目可供选择，当j项目被选中时，其各年的投资额为aij(i1，2，M; j1，2，N。已知各个项目在M年内的净现值分别为Pj(j=1，2，N)，求使所有项目净现值总额最大的投资方案(只列模型)。解 令：则其数学模型为：这是一个纯0-l规划问题。例2 固定费用问题。为生产某种产品，可采用M种方式，每一方式的最大产量及固定费用分别为Ai和Fi(i1，2，,M)，产品供给N个用户，每一用户的需求量分别为Bj(j1，2，N)，设cij为用第i种方式生产出来供给第j个用户的单位产品费用(含运费)，试决定既满足供需要求，又使总费用最低的生产方式。 解 令xij为用第i种方式生产后给j用户的供应量： 则其数学模型为： 这是一个混合0-1规划问题。 若对某一i有xij0，则由第二类约束(产量约束)yi必须为1; 否则，xij0(jl，2，N)，则第二类约束(产量约束)成为多余约束，又由于是求Z的最小值，故必有yi0。 例3 互相排斥的约束条件。 在一台车床上同时加工两种零件是不可能的，这种情况可以用约束条件来描述。设x1，x2分别为加工零件1和零件2的开始时间，a1，a2分别是零件1和零件2的加工时间长度，则两种零件互不影响的加工过程可表示为：x1+ a1x2或x2+ a2x1 对一个数学模型而言，上面的约束条件是不能同时放入模型的，为了解决这个问题，我们可考虑引入0-1变量y12将上面的约束条件改写为如下形式：x1+ a1x2+M y12x2+ a2x1+M(1- y12) 这里M为充分大正数，若y120，则第一个约束成为实际约束(即零件1先于零件2加工)，第二个约束成为多余约束。若y121，则相反。 若有m个约束条件，其中只有K个(Km)约束必须同时满足，则上述要求可用0-1变量来表示： 另一种特殊情况是，某约束条件的右端常数项只能在r个值中取其中一个，这时可表示为：第四节 整数规划常用解法简介一、分支定界法 一舱情况下，假定整数规划问题的解都是有界的(上界或下界)，因此，直观上讲，若将变量的所有可行的整数组合都找出来，然后比较它们的目标函数值，就可以求出整数规划的最优解。这是一种穷举法的思想，当问题的变量较少时，这种方法是可以考虑采用的，但是当问题变量较多时实际问题常常如此，这种方法由于计算量太大往往行不通。 分支定界法可用于求解纯整数或混合的整数规划问题，它的基本思想是：先不考虑整数解的限制，将问题当成一般的线性规划问题求最优解。如果求得的解恰好是整数解，则该解就是整数规划问题的最优解，停止计算。否则，就将问题分解成两部分，每一部分都增加一个约束条件，这样就缩小了原来的可行域，然后再用单纯形法求解。由于整数规划是在相应的线性规划中增加了变量为整数的条件，所以可行域的范围要缩小。这说明对求最大值问题的整数规划而言，其相应的线性规划的最优值就是整数规划目标函数值的上界。二、割平面法 割平面法的基本思想是先不考虑整数条件，用单纯形法求解相应的线性规划问题，若最优解为整数解即得原问题的最优解。否则，增加线性约束条件(称为割平面)将原问题的可形域切割掉一部分，被切割掉的都是非整数解，再用单纯形法求解新的线性规划问题，依次进行下去，直到使切割后最终得到达样一个可行解：它使问题的最优解恰好在某个具有整数坐标的顶点上得到。三、隐枚举法 隐枚举法是用来求解纯0-1规划的有效方法。由于每个变量只有两个可能取值0或1，则当有n个变量时，就有2n个取值组合。隐枚举法就是一种通过检查和计算一部分变量取值来求问题最优解及最优值的方法。隐枚举法的基本思想是首先令所有整数变量都取0值，然后使某些变量取值为1，直到获得一个可行解。将这第一个可行解作为临时最优解，再继续试探某些变量的取值，若可找到另一个可行解优于临时最优解，则将新的可行解作为临时最优解，以此类推。检查整数变量等于0或1的各种组合，不断寻求新的临时最优解，直到获得问题的最优解为止。由于有许多结果不如临时最优解的可行解组合不必去计算、比较，故该法称为隐枚举法。举例 0-1 整数规划数学模型Max Z = 3x1 - 2x2 + 5x3s.t. x1 + 2x2 - x3 2 x1 + 4x2 + x3 4 x1 + x2 3 4x2 + x3 6 x1,x2,x3 = 0或1求解：一、枚举法计算2n = 23 = 8个解 4 = 32步。序号解(x1,x2,x3)约束条件是否满意Z值12345678(0,0,0)(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)0-121103201451256001111220145014505-2338max16二、隐枚举法以（1，0，0）代入目标函数得z=3，则增加约束条件3x1-2x2+5x33, 只需要计算24步得到最优值，见下表。以（0，0，1）代入目标函数得z=5，则增加约束条件3x1-2x2+5x35, 只需要计算13步得到最优值。序号解(x1,x2,x3)约束条件是否满意Z值12345678(0,0,0)(0,0,1)(0,1,0)(0,1,1)(1,0,0)(1,0,1)(1,1,0)(1,1,1)05-233816-1110215126011101538max第五节 分配问题解法-匈牙利法（又称指派问题Assignment Problem） 匈牙利法是专门用来求解分配问题的一种有效方法。在实际工作中我们常遇到这样的问题：有n项任务，恰好有n个人可以分别去完成其中每一项。但由于任务的性质和每个人的专长或工作效率不同，就要考虑应指派哪个人去完成哪项任务才能使总的效率为最高，或花费的总时间最少。这一类问题就是分配问题。一、分配问题的数学模型 设有n项工作，由n个人去完成，每个人只能完成其中一项工作，而每项工作只能由一个人完成，又知第i个人完成第j项工作的效率(如时间、成本等)为cij。我们先引入0-1变量，令： xij =1 (当派第i个人去完成第j项任务时) xij0 (当不派第i个人去完成第j项任务时)若研究求最小值问题，则分配问题的数学模型可写成： 从数学模型可以看出，它类似于运输问题的数学模型，当然可以用表上作业法进行求解。但是由于它的约束条件系数矩阵的特殊性，我们可以寻求更简单、更有效的方法来解决这一类问题就像我们使用表上作业法而不是单纯行法求解运输问题一样。这就是匈牙利法。二、匈牙利法的基本思想在分配问题的数学模型中，目标函数系数cij可以写成一个nn的矩阵C，该矩阵称为效率矩阵，匈牙利法要求所有cij0。 匈牙利法是从这样一个明显的事实出发的，如果效率矩阵的所有元素cij0，而其中又存在一组(n个)位于不同行、不同列的零元索，则只要令对应于这些零元素位置的xij1，其余xij=0，就可得最优分配方案。此时，最优值即为： 但是，一般分配问题给出的效率矩阵中是没有或很少有零元素的。因此，就要用一定的方法来产生并寻找这一组位于不同行、不同列的零元素。 下而我们先来介绍一个定理，这是匈牙利数学家克尼格首先发现的，它为解决上面的问题奠定了基础，故由此而建立起来的求解分配问题的计算方法就称为匈牙利法。 定理 如果从效率矩阵（cij）中的每一行元素中分别减去一个数ui，从每一列元素中分别减去一个数vj，得到一个新的效率矩阵(cij)，其中每个元素cijcij(ui十vj)，则(cij)的最优解和(cij)的最优解相同。 推论 如果从效率矩阵(cij)的每一行(或每一列)各元素分别减去该行(或该列)的最小元素，得一新效率矩阵(cij)，则(cij)的最优解和(cij)的最优解相同。 下面我们就根据上述基本思想及