下载

3下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 Matlab数学建模算法全收录

Matlab数学建模算法全收录.pdf

Matlab数学建模算法全收录

挑战极限
2011-03-07 0人阅读 举报 0 0 暂无简介

简介:本文档为《Matlab数学建模算法全收录pdf》,可适用于人文社科领域

本人精通MATLAB等编程语言可以提供以下方向的帮助MATLABGUISIMULINKCVC编程问题线性与非线性控制、智能控制、模糊控制数值计算问题、小波分析算法、有限元问题电机控制、电力系统、机器人路径优化、机器人控制粒子群算法、神经网络、模拟退火算法等智能优化算法图像处理、信号处理、语音信号处理、电子通信等方向有问题的朋友可以将问题直接发到我的邮箱小时内给您答复!非常欢迎大家加我为QQ好友欢迎访问我的空间!联系方式:QQ:邮箱:qqcomQQ空间:http:qzoneqqcom声明:本资料来源于网络切勿用做商业用途!请您支持正版图书!第一章线性规划§线性规划在人们的生产实践中经常会遇到如何利用现有资源来安排生产以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支数学规划而线性规划(LinearProgramming简记LP)则是数学规划的一个重要分支。自从年GBDantzig提出求解线性规划的单纯形方法以来线性规划在理论上趋向成熟在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后线性规划的适用领域更为广泛了已成为现代管理中经常采用的基本方法之一。线性规划的实例与定义例某机床厂生产甲、乙两种机床每台销售后的利润分别为元与元。生产甲机床需用BA、机器加工加工时间分别为每台小时和小时生产乙机床需用CBA、、三种机器加工加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器小时、B机器小时和C机器小时问该厂应生产甲、乙机床各几台才能使总利润最大?上述问题的数学模型:设该厂生产x台甲机床和x乙机床时总利润最大则,xx应满足(目标函数)maxxxz=()st(约束条件)⎪⎪⎩⎪⎪⎨⎧≥≤≤≤,xxxxxxx()这里变量,xx称之为决策变量()式被称为问题的目标函数()中的几个不等式是问题的约束条件记为st(即subjectto)。由于上面的目标函数及约束条件均为线性函数故被称为线性规划问题。总之线性规划问题是在一组线性约束条件的限制下求一线性目标函数最大或最小的问题。在解决实际问题时把问题归结成一个线性规划数学模型是很重要的一步但往往也是困难的一步模型建立得是否恰当直接影响到求解。而选适当的决策变量是我们建立有效模型的关键之一。线性规划的Matlab标准形式线性规划的目标函数可以是求最大值也可以是求最小值约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便Matlab中规定线性规划的标准形式为xcxTminst⎪⎩⎪⎨⎧≤≤=⋅≤ubxlbbeqxAeqbAx其中c和x为n维列向量A、Aeq为适当维数的矩阵b、beq为适当维数的列向量。例如线性规划bAxxcxT≥stmax的Matlab标准型为bAxxcxT−≤−−stmin线性规划问题的解的概念一般线性规划问题的(数学)标准型为∑==njjjxczmax()st⎪⎩⎪⎨⎧=≥==∑=njxmibxajnjijij,,,,,,LL()可行解满足约束条件()的解),,,(nxxxxL=称为线性规划问题的可行解而使目标函数()达到最大值的可行解叫最优解。可行域所有可行解构成的集合称为问题的可行域记为R。线性规划的图解法x=xx=xx=z=(,)图线性规划的图解示意图图解法简单直观有助于了解线性规划问题求解的基本原理。我们先应用图解法来求解例。对于每一固定的值z使目标函数值等于z的点构成的直线称为目标函数等位线当z变动时我们得到一族平行直线。对于例显然等位线越趋于右上方其上的点具有越大的目标函数值。不难看出本例的最优解为Tx),(*=最优目标值*=z。从上面的图解过程可以看出并不难证明以下断言:()可行域R可能会出现多种情况。R可能是空集也可能是非空集合当R非空时它必定是若干个半平面的交集(除非遇到空间维数的退化)。R既可能是有界区域也可能是无界区域。()在R非空时线性规划既可以存在有限最优解也可以不存在有限最优解(其目标函数值无界)。()若线性规划存在有限最优解则必可找到具有最优目标函数值的可行域R的“顶点”。上述论断可以推广到一般的线性规划问题区别只在于空间的维数。在一般的n维空间中满足一线性等式∑==niiibxa的点集被称为一个超平面而满足一线性不等式∑=≤niiibxa(或∑=≥niiibxa)的点集被称为一个半空间(其中),,(naaL为一n维行向量b为一实数)。若干个半空间的交集被称为多胞形有界的多胞形又被称为多面体。易见线性规划的可行域必为多胞形(为统一起见空集Φ也被视为多胞形)。在一般n维空间中要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点可以看成为边界直线的交点但这一几何概念的推广在一般n维空间中的几何意义并不十分直观。为此我们将采用另一途径来定义它。定义称n维空间中的区域R为一凸集若Rxx∈∀,及),(∈∀λ有Rxx∈−)(λλ。定义设R为n维空间中的一个凸集R中的点x被称为R的一个极点若不存在Rxx∈、及),(∈λ使得)(xxxλλ−=。定义说明凸集中任意两点的连线必在此凸集中而定义说明若x是凸集R的一个极点则x不能位于R中任意两点的连线上。不难证明多胞形必为凸集。同样也不难证明二维空间中可行域R的顶点均为R的极点(R也没有其它的极点)。求解线性规划的Matlab解法单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不介绍单纯形法有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的Matlab解法。Matlab中线性规划的标准型为xcxTminst⎪⎩⎪⎨⎧≤≤=⋅≤ubxlbbeqxAeqbAx基本函数形式为linprog(c,A,b)它的返回值是向量x的值。还有其它的一些函数调用形式(在Matlab指令窗运行helplinprog可以看到所有的函数调用形式)如:x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X,OPTIONS)这里fval返回目标函数的值LB和UB分别是变量x的下界和上界x是x的初始值OPTIONS是控制参数。例求解下列线性规划问题maxxxxz−=st=xxx≥−xxx≤xxx,,≥xxx解(i)编写M文件c=a=,,,,b=aeq=,,beq=x=linprog(c,a,b,aeq,beq,zeros(,))value=c'*x(ii)将M文件存盘并命名为examplem。(iii)在Matlab指令窗运行example即可得所求结果。例求解线性规划问题minxxxz=⎪⎩⎪⎨⎧≥≥≥,,xxxxxxxx解编写Matlab程序如下:c=a=,,,,b=x,y=linprog(c,a,b,,,zeros(,))可以转化为线性规划的问题很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决。如:例规划问题为bAxxxxn≤ts||||||minL其中TnxxxL=A和b为相应维数的矩阵和向量。要把上面的问题变换成线性规划问题只要注意到事实:对任意的ix存在,>iivu满足iiivux−=iiivux=||事实上我们只要取||iiixxu=||iiixxv−=就可以满足上面的条件。这样记TnuuuL=TnvvvL=从而我们可以把上面的问题变成∑=niiivu)(min⎩⎨⎧≥≤−,)(tsvubvuA例|}|max{miniyxiiε其中iiiyx−=ε。对于这个问题如果我们取||maxiyixε=这样上面的问题就变换成minx,,tsxyxxyxnn≤−≤−L此即我们通常的线性规划问题。§运输问题(产销平衡)例某商品有m个产地、n个销地各产地的产量分别为maa,,L各销地的需求量分别为nbb,,L。若该商品由i产地运到j销地的单位运价为ijc问应该如何调运才能使总运费最省?解:引入变量ijx其取值为由i产地运往j销地的该商品数量数学模型为∑∑==minjijijxcminst⎪⎪⎪⎩⎪⎪⎪⎨⎧≥====∑∑==,,,,,,,ijmijijnjiijxnjbxmiaxLL显然是一个线性规划问题当然可以用单纯形法求解。对产销平衡的运输问题由于有以下关系式存在:∑∑∑∑∑∑=======⎟⎠⎞⎜⎝⎛=⎟⎟⎠⎞⎜⎜⎝⎛=miinjnjmiijminjijjaxxb其约束条件的系数矩阵相当特殊可用比较简单的计算方法习惯上称为表上作业法(由康托洛维奇和希奇柯克两人独立地提出简称康希表上作业法)。§指派问题指派问题的数学模型例拟分配n人去干n项工作每人干且仅干一项工作若分配第i人去干第j项工作需花费ijc单位时间问应如何分配工作才能使工人花费的总时间最少?容易看出要给出一个指派问题的实例只需给出矩阵)(ijcC=C被称为指派问题的系数矩阵。引入变量ijx若分配i干j工作则取=ijx否则取=ijx。上述指派问题的数学模型为∑∑==ninjijijxcminst∑==njijx∑==niijx或=ijx上述指派问题的可行解可以用一个矩阵表示其每行每列均有且只有一个元素为其余元素均为可以用n,,L中的一个置换表示。问题中的变量只能取或从而是一个规划问题。一般的规划问题求解极为困难。但指派问题并不难解其约束方程组的系数矩阵十分特殊(被称为全单位模矩阵其各阶非零子式均为±)其非负可行解的分量只能取或故约束或=ijx可改写为≥ijx而不改变其解。此时指派问题被转化为一个特殊的运输问题其中nm===jiba。求解指派问题的匈牙利算法由于指派问题的特殊性又存在着由匈牙利数学家Konig提出的更为简便的解法匈牙利算法。算法主要依据以下事实:如果系数矩阵)(ijcC=一行(或一列)中每一元素都加上或减去同一个数得到一个新矩阵)(ijbB=则以C或B为系数矩阵的指派问题具有相同的最优指派。例求解指派问题其系数矩阵为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=C解将第一行元素减去此行中的最小元素同样第二行元素减去第三行元素减去最后一行的元素减去得⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=B再将第列元素各减去得⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=****B以B为系数矩阵的指派问题有最优指派⎟⎟⎠⎞⎜⎜⎝⎛由等价性它也是例的最优指派。有时问题会稍复杂一些。例求解系数矩阵C的指派问题⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=C解:先作等价变换如下∨∨∨⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡→⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡−−−−−****容易看出从变换后的矩阵中只能选出四个位于不同行不同列的零元素但=n最优指派还无法看出。此时等价变换还可进行下去。步骤如下:()对未选出元素的行打∨()对∨行中元素所在列打∨()对∨列中选中的元素所在行打∨重复()、()直到无法再打∨为止。可以证明若用直线划没有打∨的行与打∨的列就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合找出未覆盖的元素中的最小者令∨行元素减去此数∨列元素加上此数则原先选中的元素不变而未覆盖元素中至少有一个已转变为且新矩阵的指派问题与原问题也等价。上述过程可反复采用直到能选取出足够的元素为止。例如对例变换后的矩阵再变换第三行、第五行元素减去第一列元素加上得⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡现在已可看出最优指派为⎟⎟⎠⎞⎜⎜⎝⎛。§对偶理论与灵敏度分析原始问题和对偶问题考虑下列一对线性规划模型:xcTmaxst,≥≤xbAx(P)和ybTminst,≥≥ycyAT(D)称(P)为原始问题(D)为它的对偶问题。不太严谨地说对偶问题可被看作是原始问题的“行列转置”:()原始问题中的第j列系数与其对偶问题中的第j行的系数相同()原始目标函数的各个系数行与其对偶问题右侧的各常数列相同()原始问题右侧的各常数列与其对偶目标函数的各个系数行相同()在这一对问题中不等式方向和优化方向相反。考虑线性规划:,stmin≥=xbAxxcT把其中的等式约束变成不等式约束可得,stmin≥⎥⎦⎤⎢⎣⎡−≥⎥⎦⎤⎢⎣⎡−xbbxAAxcT它的对偶问题是cyyAAyybbTTTT≤⎥⎦⎤⎢⎣⎡−⎥⎦⎤⎢⎣⎡−stmax其中y和y分别表示对应于约束bAx≥和bAx−≥−的对偶变量组。令yyy−=则上式又可写成cyAybTT≤stmax原问题和对偶的对偶约束之间的关系:minmax⎪⎩⎪⎨⎧≤≥无限制变量⎪⎩⎪⎨⎧=≥≤行约束⎪⎩⎪⎨⎧=≤≥行约束⎪⎩⎪⎨⎧≤≥无限制变量对偶问题的基本性质o对称性:对偶问题的对偶是原问题。o弱对偶性:若x是原问题的可行解y是对偶问题的可行解。则存在ybxcTT≤。o无界性:若原问题(对偶问题)为无界解则其对偶问题(原问题)无可行解。o可行解是最优解时的性质:设xˆ是原问题的可行解yˆ是对偶问题的可行解当ybxcTTˆˆ=时yxˆ,ˆ是最优解。o对偶定理:若原问题有最优解那么对偶问题也有最优解且目标函数值相同。o互补松弛性:若yxˆ,ˆ分别是原问题和对偶问题的最优解则)ˆ(ˆ,)ˆ(ˆ=−=−cyAxbxAyTTT例已知线性规划问题minxxxxx=ωst≥xxxxx≥−xxxxx,,,,L=≥jxj已知其对偶问题的最优解为,**===zyy。试用对偶理论找出原问题的最优解。解先写出它的对偶问题maxyyz=≤yy①≤−yy②≤yy③≤yy④≤yy⑤,≥yy将**,yy的值代入约束条件得②③④为严格不等式由互补松弛性得***===xxx。因,**>yy原问题的两个约束条件应取等式故有**=xx**=xx求解后得到,**==xx故原问题的最优解为'**==ωX。灵敏度分析在以前讨论线性规划问题时假定jiijcba,,都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变jc值就会变化ija往往是因工艺条件的改变而改变ib是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题:当这些系数有一个或几个发生变化时已求得的线性规划问题的最优解会有什么变化或者这些系数在什么范围内变化时线性规划问题的最优解或最优基不变。这里我们就不讨论了。参数线性规划参数线性规划是研究jiijcba,,这些参数中某一参数连续变化时使最优解发生变化的各临界点的值。即把某一参数作为参变量而目标函数在某区间内是这参变量的线性函数含这参变量的约束条件是线性等式或不等式。因此仍可用单纯形法和对偶单纯形法进行分析参数线性规划问题。§投资的收益和风险问题提出市场上有n种资产is(ni,,,L=)可以选择现用数额为M的相当大的资金作一个时期的投资。这n种资产在这一时期内购买is的平均收益率为ir风险损失率为iq投资越分散总的风险越少总体风险可用投资的is中最大的一个风险来度量。购买is时要付交易费(费率ip)当购买额不超过给定值iu时交易费按购买iu计算。另外假定同期银行存款利率是r既无交易费又无风险。(=r)已知=n时相关数据如表。表isir()iqip()iu(元)ssss试给该公司设计一种投资组合方案即用给定资金M有选择地购买若干种资产或存银行生息使净收益尽可能大使总体风险尽可能小。符号规定和基本假设符号规定:is:第i种投资项目如股票债券iiiqpr,,:分别为is的平均收益率交易费率风险损失率iu:is的交易定额r:同期银行利率ix:投资项目is的资金a:投资风险度Q:总体收益基本假设:.投资数额M相当大为了便于计算假设=M.投资越分散总的风险越小.总体风险用投资项目is中最大的一个风险来度量.n种资产is之间是相互独立的.在投资的这一时期内iiiqpr,,r为定值不受意外因素影响.净收益和总体风险只受iiiqpr,,影响不受其它因素干扰。模型的分析与建立.总体风险用所投资的is中最大的一个风险来衡量即},,,|max{nixqiiL=.购买is所付交易费是一个分段函数即交易费⎩⎨⎧≤>=iiiiiiiiuxupuxxp,,而题目所给定的定值iu(单位:元)相对总投资M很少iiup更小可以忽略不计这样购买is的净收益为iiixpr)(−。.要使净收益尽可能大总体风险尽可能小这是一个多目标规划模型:目标函数为⎪⎩⎪⎨⎧−∑=}max{min)(maxiiniiiixqxpr约束条件为⎪⎩⎪⎨⎧=≥=∑=nixMxpiniii,,,,)(L.模型简化a)在实际投资中投资者承受风险的程度不一样若给定风险一个界限a使最大的一个风险aMxqii≤可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。模型一固定风险水平优化收益∑=−niiiixpr)(maxst⎪⎪⎩⎪⎪⎨⎧=≥=≤∑=niiiiiinixMxpaMxq,,,,,)(Lb)若投资者希望总盈利至少达到水平k以上在风险最小的情况下寻求相应的投资组合。模型二固定盈利水平极小化风险}}{{maxminiixqst⎪⎪⎩⎪⎪⎨⎧=≥=≥−∑∑==niiiiniiiinixMxpkxpr,,,,,)()(Lc)投资者在权衡资产风险和预期收益两方面时希望选择一个令自己满意的投资组合。因此对风险、收益分别赋予权重s(≤<s)和)(s−s称为投资偏好系数。模型三∑=−−−niiiiiixprsxqs)()(}}{max{minst∑==≥=niiiinixMxp,,,,,,)(L模型一的求解模型一为:Txxxxxf),,,,)(,,,,(min−−−−−=st⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥≤≤≤≤=),,,(Lixaxaxaxaxxxxxxi由于a是任意给定的风险度到底怎样没有一个准则不同的投资者有不同的风险度。我们从=a开始以步长=Δa进行循环搜索编制程序如下:clc,cleara=holdonwhilea<c=,,,,A=zeros(,),diag(,,,)b=a*ones(,)Aeq=,,,,beq=LB=zeros(,)x,Q=linprog(c,A,b,Aeq,beq,LB)Q=Qplot(a,Q,'*r')a=aendxlabel('a'),ylabel('Q')结果分析风险大收益也大。.当投资越分散时投资者承担的风险越小这与题意一致。即:冒险的投资者会出现集中投资的情况保守的投资者则尽量分散投资。.在=a附近有一个转折点在这一点左边风险增加很少时利润增长很快。在这一点右边风险增加很大时利润增长很缓慢所以对于风险和收益没有特殊偏好的投资者来说应该选择曲线的拐点作为最优投资组合大约是=a=Q所对应投资方案为:风险度=a收益=Q=x=x=x=x=x。习题一.试将下述问题改写成线性规划问题:⎭⎬⎫⎩⎨⎧⎟⎠⎞⎜⎝⎛∑∑∑===miiinmiiimiiixxaxaxai,,,minmaxL⎩⎨⎧=≥=mixxxxim,,,stLL.试将下列问题改写成线性规划问题:∑==njjjxcz||max⎪⎩⎪⎨⎧==∑=取值无约束jnjijijxmibxa),,,(stL.线性回归是一种常用的数理统计方法这个方法要求对图上的一系列点),(,),,(),,(nnyxyxyxL选配一条合适的直线拟合。方法通常是先定直线方程为bxay=然后按某种准则求定ba,。通常这个准则为最小二乘法但也可用其他准则。试根据以下准则建立这个问题的线性规划模型:∑=−niiibxay|)(|min.某厂生产三种产品IIIIII。每种产品要经过BA,两道工序加工。设该厂有两种规格的设备能完成A工序它们以,AA表示有三种规格的设备能完成B工序它们以,,BBB表示。产品I可在BA,任何一种规格设备上加工。产品II可在任何规格的A设备上加工但完成B工序时只能在B设备上加工产品III只能在A与B设备上加工。已知在各种机床设备的单件工时原材料费产品销售价格各种设备有效台时以及满负荷操作时机床设备的费用如表求安排最优的生产计划使该厂利润最大。表产品设备IIIIII设备有效台时满负荷时的设备费用(元)AABBB原料费(元件)单价(元件).有四个工人要指派他们分别完成项工作每人做各项工作所消耗的时间如表。表工作工人ABCD甲乙丙丁问指派哪个人去完成哪项工作可使总的消耗时间为最小?.某战略轰炸机群奉命摧毁敌人军事目标。已知该目标有四个要害部位只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为升、重型炸弹枚、轻型炸弹枚。飞机携带重型炸弹时每升汽油可飞行千米带轻型炸弹时每升汽油可飞行千米。又知每架飞机每次只能装载一枚炸弹每出发轰炸一次除来回路程汽油消耗(空载时每升汽油可飞行千米)外起飞和降落每次各消耗升。有关数据如表所示。表摧毁可能性要害部位离机场距离(千米)每枚重型弹每枚轻型弹为了使摧毁敌方军事目标的可能性最大应如何确定飞机轰炸的方案要求建立这个问题的线性规划模型。.用Matlab求解下列线性规划问题:maxxxxz−−=st⎪⎪⎩⎪⎪⎨⎧≥=−≥−≤−,,xxxxxxxxxxx.用Matlab求解下列规划问题:||||||||minxxxxz=st=−−xxxx=−−xxxx−=−−xxxx.一架货机有三个货舱:前舱、中仓和后舱。三个货舱所能装载的货物的最大重量和体积有限制如表所示。并且为了飞机的平衡三个货舱装载的货物重量必须与其最大的容许量成比例。表货舱数据前舱中仓后舱重量限制(吨)体积限制(立方米)现有四类货物用该货机进行装运货物的规格以及装运后获得的利润如表。表货物规格及利润表重量(吨)空间(立方米吨)利润(元吨)货物货物货物货物假设:()每种货物可以无限细分()每种货物可以分布在一个或者多个货舱内()不同的货物可以放在同一个货舱内并且可以保证不留空隙。问应如何装运使货机飞行利润最大?第二章整数规划§概论定义规划中的变量(部分或全部)限制为整数时称为整数规划。若在线性规划模型中变量限制为整数则称为整数线性规划。目前所流行的求解整数规划的方法往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。整数规划的分类如不加特殊说明一般指整数线性规划。对于整数线性规划模型大致可分为两类:o变量全限制为整数时称纯(完全)整数规划。o变量部分限制为整数的称混合整数规划。整数规划特点(i)原线性规划有最优解当自变量限制为整数后其整数规划解出现下述情况:①原线性规划最优解全是整数则整数规划最优解与线性规划最优解一致。②整数规划无可行解。例原线性规划为minxxz=,,≥≥=xxxx其最优实数解为:min,,===zxx。③有可行解(当然就存在最优解)但最优解值变差。例原线性规划为minxxz=,,≥≥=xxxx其最优实数解为:min,,===zxx。若限制整数得:min,,===zxx。(ii)整数规划最优解不能按照实数最优解简单取整而获得。求解方法分类:(i)分枝定界法可求纯或混合整数线性规划。(ii)割平面法可求纯或混合整数线性规划。(iii)隐枚举法求解“”整数规划:①过滤隐枚举法②分枝隐枚举法。(iv)匈牙利法解决指派问题(“”规划特殊情形)。(v)蒙特卡洛法求解各种类型规划。下面将简要介绍常用的几种求解整数规划的方法。§分枝定界法对有约束条件的最优化问题(其可行解为有限数)的所有可行解空间恰当地进行系统搜索这就是分枝与定界内容。通常把全部可行解空间反复地分割为越来越小的子集称为分枝并且对每个子集内的解集计算一个目标下界(对于最小值问题)这称为定界。在每次分枝后凡是界限超出已知可行解集目标值的那些子集不再进一步分枝这样许多子集可不予考虑这称剪枝。这就是分枝定界法的主要思路。分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由LandDoig和Dakin等人提出的。由于这方法灵活且便于用计算机求解所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。设有最大化的整数规划问题A与它相应的线性规划为问题B从解问题B开始若其最优解不符合A的整数条件那么B的最优目标函数必是A的最优目标函数*z的上界记作z而A的任意可行解的目标函数值将是*z的一个下界z。分枝定界法就是将B的可行域分成子区域的方法。逐步减小z和增大z最终求到*z。现用下例来说明:例求解下述整数规划Maxxxz=⎪⎩⎪⎨⎧≥≤≤且为整数,xxxxxx解(i)先不考虑整数限制即解相应的线性规划B得最优解为:,,===zxx可见它不符合整数条件。这时z是问题A的最优目标函数值*z的上界记作z。而,==xx显然是问题A的一个整数可行解这时=z是*z的一个下界记作z即*≤≤z。(ii)因为,xx当前均为非整数故不满足整数要求任选一个进行分枝。设选x进行分枝把可行集分成个子集:=≤x=≥x因为与之间无整数故这两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下:问题B:Maxxxz=⎪⎩⎪⎨⎧≥≤≤≤≤,xxxxxx最优解为:,,===zxx。问题B:Maxxxz=⎪⎩⎪⎨⎧≥≥≤≤,xxxxxx最优解为:,,===zxx。再定界:*≤≤z。(iii)对问题B再进行分枝得问题B和B它们的最优解为,,:===zxxB,x,:===zxB再定界:*≤≤z并将B剪枝。(iv)对问题B再进行分枝得问题B和B它们的最优解为,x,:===zxBB无可行解。将,BB剪枝。于是可以断定原问题的最优解为:,,*===zxx从以上解题过程可得用分枝定界法求解整数规划(最大化)问题的步骤为:开始将要求解的整数规划问题称为问题A将与它相应的线性规划问题称为问题B。(i)解问题B可能得到以下情况之一:(a)B没有可行解这时A也没有可行解则停止.(b)B有最优解并符合问题A的整数条件B的最优解即为A的最优解则停止。(c)B有最优解但不符合问题A的整数条件记它的目标函数值为z。(ii)用观察法找问题A的一个整数可行解一般可取njxj,,,L==试探求得其目标函数值并记作z。以*z表示问题A的最优目标函数值这时有zzz≤≤*进行迭代。第一步:分枝在B的最优解中任选一个不符合整数条件的变量jx其值为jb以jb表示小于jb的最大整数。构造两个约束条件jjbx≤和≥jjbx将这两个约束条件分别加入问题B求两个后继规划问题B和B。不考虑整数条件求解这两个后继问题。定界以每个后继问题为一分枝标明求解的结果与其它问题的解的结果中找出最优目标函数值最大者作为新的上界z。从已符合整数条件的各分支中找出目标函数值为最大者作为新的下界z若无作用z不变。第二步:比较与剪枝各分枝的最优目标函数中若有小于z者则剪掉这枝即以后不再考虑了。若大于z且不符合整数条件则重复第一步骤。一直到最后得到zz=*为止。得最优整数解njxj,,,*L=。§−型整数规划−型整数规划是整数规划中的特殊情形它的变量jx仅取值或。这时jx称为−变量或称二进制变量。jx仅取值或这个条件可由下述约束条件:≤≤jx整数所代替是和一般整数规划的约束条件形式一致的。在实际问题中如果引入−变量就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们先介绍引入−变量的实际问题再研究解法。引入−变量的实际问题投资场所的选定相互排斥的计划例某公司拟在市东、西、南三区建立门市部。拟议中有个位置(点)),,,(L=iAi可供选择。规定在东区。由,,AAA三个点中至多选两个在西区。由,AA两个点中至少选一个在南区由,AA两个点中至少选一个。如选用iA点设备投资估计为ib元每年可获利润估计为ic元但投资总额不能超过B元。问应选择哪几个点可使年利润为最大?解题时先引入−变量),,,(L=ixi令⎩⎨⎧=,点没被选中当点被选中当iAiAix,,,L=i于是问题可列写成:iiixcz∑==Max⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≥≤≤∑=,或iiiixxxxxxxxBxb相互排斥的约束条件有两个相互排斥的约束条件≤xx或≤xx。为了统一在一个问题中引入−变量y则上述约束条件可改写为:⎪⎩⎪⎨⎧=−≤≤)(或yMyxxyMxx其中M是充分大的数。约束条件=x或≤≤x可改写为⎩⎨⎧=≤≤或yyxy如

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/800

Matlab数学建模算法全收录

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利