关 键 词：

MATLAB 算法 大全

资源描述：

MATLAB算法大全,MATLAB,算法,大全

内容简介：

-1- 第一章第一章 线性规划线性规划 1 线性规划 在人们的生产实践中， 经常会遇到如何利用现有资源来安排生产， 以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支数学规划，而线性规划(Linear Programming 简记 LP)则是数学规划的一个重要分支。自从 1947 年 G. B. Dantzig 提出求解线性规划的单纯形方法以来， 线性规划在理论上趋向成熟， 在实用中日益广泛与深入。 特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后， 线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例 1 某机床厂生产甲、 乙两种机床， 每台销售后的利润分别为 4000 元与 3000 元。生产甲机床需用BA、机器加工，加工时间分别为每台 2 小时和 1 小时；生产乙机床需用CBA、三种机器加工， 加工时间为每台各一小时。 若每天可用于加工的机器时数分别为A机器 10 小时、B机器 8 小时和C机器 7 小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型： 设该厂生产1x台甲机床和2x乙机床时总利润最大， 则21,xx应满足 （目标函数）2134maxxxz+= (1) s.t.（约束条件）+0,781022122121xxxxxxx （2） 这里变量21,xx称之为决策变量， （1）式被称为问题的目标函数， （2）中的几个不等式是问题的约束条件，记为 s.t.(即 subject to)。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。 总之， 线性规划问题是在一组线性约束条件的限制下， 求一线性目标函数最大或最小的问题。 在解决实际问题时， 把问题归结成一个线性规划数学模型是很重要的一步， 但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选适当的决策变量，是我们建立有效模型的关键之一。 1.2 线性规划的 Matlab 标准形式 线性规划的目标函数可以是求最大值， 也可以是求最小值， 约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为 xcxT min s.t. =ubxlbbeqxAeqbAx 其中c和x为n维列向量，A、Aeq为适当维数的矩阵，b、beq为适当维数的列向量。 -2- 例如线性规划 bAxxcxT s.t. max 的 Matlab 标准型为 bAxxcxT s.t. min 1.3 线性规划问题的解的概念 一般线性规划问题的（数学）标准型为 =njjjxcz1max (3) s.t. =njxmibxajnjijij, 2 , 10, 2 , 11LL (4) 可行解可行解 满足约束条件 （4） 的解),(21nxxxxL=， 称为线性规划问题的可行解，而使目标函数（3）达到最大值的可行解叫最优解。 可行域可行域 所有可行解构成的集合称为问题的可行域，记为R。 1.4 线性规划的图解法 024681 001234567891 0x 2 = 72 x 1 + x 2 = 1 0x 1 + x 2 = 8z = 1 2(2 ,6 ) 图 1 线性规划的图解示意图 图解法简单直观， 有助于了解线性规划问题求解的基本原理。 我们先应用图解法来求解例 1。对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线，当z变动时，我们得到一族平行直线。对于例 1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为Tx)6 , 2(*=，最优目标值26*=z。 从上面的图解过程可以看出并不难证明以下断言： （1）可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时， 它必定是若干个半平面的交集 （除非遇到空间维数的退化） 。R既可能是有界区域，也可能是无界区域。 （2） 在R非空时， 线性规划既可以存在有限最优解， 也可以不存在有限最优解 （其目标函数值无界） 。 -3- （3） 若线性规划存在有限最优解， 则必可找到具有最优目标函数值的可行域R的“顶点” 。 上述论断可以推广到一般的线性规划问题， 区别只在于空间的维数。 在一般的n维空间中，满足一线性等式=niiibxa1的点集被称为一个超平面，而满足一线性不等式=niiibxa1（或=niiibxa1）的点集被称为一个半空间（其中),(1naaL为一n维行向量，b为一实数） 。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域必为多胞形（为统一起见，空集也被视为多胞形） 。 在一般n维空间中，要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点可以看成为边界直线的交点， 但这一几何概念的推广在一般n维空间中的几何意义并不十分直观。为此，我们将采用另一途径来定义它。 定义定义 1 称n维空间中的区域R为一凸集，若Rxx21,及) 1 , 0(，有Rxx+21)1 (。 定义定义 2 设R为n维空间中的一个凸集，R中的点x被称为R的一个极点，若不存在Rxx21、及) 1 , 0(，使得21)1 (xxx+=。 定义 1 说明凸集中任意两点的连线必在此凸集中；而定义 2 说明，若x是凸集R的一个极点，则x不能位于R中任意两点的连线上。不难证明，多胞形必为凸集。同样也不难证明，二维空间中可行域R的顶点均为R的极点（R也没有其它的极点） 。 1.5 求解线性规划的 Matlab 解法 单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不介绍单纯形法， 有兴趣的读者可以参看其它线性规划书籍。 下面我们介绍线性规划的 Matlab解法。 Matlab 中线性规划的标准型为 xcxT min s.t. =ubxlbbeqxAeqbAx 基本函数形式为 linprog(c,A,b)， 它的返回值是向量x的值。 还有其它的一些函数调用形式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式） ，如： x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS) 这里 fval 返回目标函数的值， LB 和 UB 分别是变量x的下界和上界，0x是x的初始值，OPTIONS 是控制参数。 例 2 求解下列线性规划问题 321532max xxxz+= s.t. 7321=+xxx 1052321+xxx 123321+xxx 0,321xxx -4- 解 （i）编写 M 文件 c=2;3;-5; a=-2,5,-1;1,3,1; b=-10;12; aeq=1,1,1; beq=7; x=linprog(-c,a,b,aeq,beq,zeros(3,1) value=c*x （ii）将M文件存盘，并命名为example1.m。 （iii）在Matlab指令窗运行example1即可得所求结果。 例3 求解线性规划问题 32132 minxxxz+= +0,62382432121321xxxxxxxx 解 编写Matlab程序如下： c=2;3;1; a=1,4,2;3,2,0; b=8;6; x,y=linprog(c,-a,-b,zeros(3,1) 1.6 可以转化为线性规划的问题 很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决。如： 例4 规划问题为 bAxxxxn+ t.s.|min21L 其中Tnxxx1L=，A和b为相应维数的矩阵和向量。 要把上面的问题变换成线性规划问题，只要注意到事实：对任意的ix，存在0,iivu满足 iiivux=，iiivux+= | 事实上，我们只要取2|iiixxu+=，2|iiixxv=就可以满足上面的条件。 这样，记Tnuuu1L=，Tnvvv1L=，从而我们可以把上面的问题变成 =+niiivu1)(min 0,)( t.s.vubvuA 例 5 |maxminiyxii 其中iiiyx =。 对于这个问题，如果我们取|max0iyix=，这样，上面的问题就变换成 -5- 0minx 0011, t.s.xyxxyxnnL 此即我们通常的线性规划问题。 2 运输问题(产销平衡) 例 6 某商品有m个产地、n个销地，各产地的产量分别为maa,1L，各销地的需求量分别为nbb,1L。若该商品由i产地运到j销地的单位运价为ijc，问应该如何调运才能使总运费最省？ 解：引入变量ijx，其取值为由i产地运往j销地的该商品数量，数学模型为 =minjijijxc11min s.t. =0, 2 , 1, 1,11ijmijijnjiijxnjbxmiaxLL 显然是一个线性规划问题，当然可以用单纯形法求解。 对产销平衡的运输问题，由于有以下关系式存在： =miinjnjmiijminjijjaxxb111111 其约束条件的系数矩阵相当特殊， 可用比较简单的计算方法， 习惯上称为表上作业法 （由康托洛维奇和希奇柯克两人独立地提出，简称康希表上作业法） 。 3 指派问题 3.1 指派问题的数学模型 例 7 拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需花费ijc单位时间，问应如何分配工作才能使工人花费的总时间最少？ 容易看出，要给出一个指派问题的实例，只需给出矩阵)(ijcC =，C被称为指派问题的系数矩阵。 引入变量ijx，若分配i干j工作，则取1=ijx，否则取0=ijx。上述指派问题的数学模型为 =ninjijijxc11min s.t. =njijx11 -6- =niijx11 1 0或=ijx 上述指派问题的可行解可以用一个矩阵表示，其每行每列均有且只有一个元素为1，其余元素均为 0；可以用n, 1L中的一个置换表示。 问题中的变量只能取 0 或 1，从而是一个 0-1 规划问题。一般的 0-1 规划问题求解极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵， 其各阶非零子式均为1） ， 其非负可行解的分量只能取 0 或 1， 故约束10或=ijx可改写为0ijx而不改变其解。此时，指派问题被转化为一个特殊的运输问题，其中nm =，1=jiba。 3.2 求解指派问题的匈牙利算法 由于指派问题的特殊性，又存在着由匈牙利数学家 Konig 提出的更为简便的解法匈牙利算法。算法主要依据以下事实：如果系数矩阵)(ijcC=一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵)(ijbB= ，则以C或B为系数矩阵的指派问题具有相同的最优指派。 例 8 求解指派问题，其系数矩阵为 =16221917171822241819211722191516C 解 将第一行元素减去此行中的最小元素 15，同样，第二行元素减去 17，第三行元素减去 17，最后一行的元素减去 16，得 =06310157124074011B 再将第 3 列元素各减去 1，得 =*20531005711407301B 以2B为系数矩阵的指派问题有最优指派 43124321 由等价性，它也是例 7 的最优指派。 有时问题会稍复杂一些。 例 9 求解系数矩阵C的指派问题 -7- =61071041066141512141217766698979712C 解：先作等价变换如下 2636040*08957510*00*0032202*056107104106614151214121776669897971246767 容易看出， 从变换后的矩阵中只能选出四个位于不同行不同列的零元素， 但5=n，最优指派还无法看出。此时等价变换还可进行下去。步骤如下： (1) 对未选出 0 元素的行打； (2) 对行中 0 元素所在列打； (3) 对列中选中的 0 元素所在行打； 重复（2） 、 （3）直到无法再打为止。 可以证明，若用直线划没有打的行与打的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令行元素减去此数，列元素加上此数，则原先选中的 0 元素不变，而未覆盖元素中至少有一个已转变为 0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足够的 0 元素为止。例如，对例 5 变换后的矩阵再变换，第三行、第五行元素减去 2，第一列元素加上 2，得 04140400811353800003420207 现在已可看出，最优指派为5314254321。 4 对偶理论与灵敏度分析 4.1 原始问题和对偶问题 考虑下列一对线性规划模型： xcTmax s.t. 0,xbAx (P) 和 ybTmin s.t. 0,ycyAT (D) -8- 称（P）为原始问题， （D）为它的对偶问题。 不太严谨地说，对偶问题可被看作是原始问题的“行列转置” ： （1） 原始问题中的第j列系数与其对偶问题中的第j行的系数相同； （2） 原始目标函数的各个系数行与其对偶问题右侧的各常数列相同； （3） 原始问题右侧的各常数列与其对偶目标函数的各个系数行相同； （4） 在这一对问题中，不等式方向和优化方向相反。 考虑线性规划： 0,s.t.min=xbAxxcT 把其中的等式约束变成不等式约束，可得 0, s.t. minxbbxAAxcT 它的对偶问题是 cyyAAyybbTTTT2121 s.t.max 其中1y和2y分别表示对应于约束bAx 和bAx的对偶变量组。 令21yyy=，则上式又可写成 cyAybTT s.t. max 原问题和对偶的对偶约束之间的关系： min max 无限制变量00 =000行约束 =000行约束 无限制变量00 4.2 对偶问题的基本性质 1o 对称性：对偶问题的对偶是原问题。 2o 弱对偶性：若x是原问题的可行解，y是对偶问题的可行解。则存在ybxcTT。 3o 无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。 4o 可行解是最优解时的性质：设x是原问题的可行解，y 是对偶问题的可行解，当ybxcTT=时，yx , 是最优解。 5o 对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相同。 6o 互补松弛性：若yx, 分别是原问题和对偶问题的最优解，则 0)(, 0)(=cyAxbxAyTTT 例 10 已知线性规划问题 5432132532minxxxxx+= s.t. 43254321+xxxxx -9- 33254321+xxxxx 5 , 2 , 1, 0L=jxj 已知其对偶问题的最优解为5;53,54*2*1=zyy。试用对偶理论找出原问题的最优解。 解 先写出它的对偶问题 2134maxyyz+= 2221+yy 321 yy 53231+ yy 221+ yy 3321+ yy 0,21yy 将*2*1, yy的值代入约束条件，得，为严格不等式；由互补松弛性得0*4*3*2=xxx。因 0,*2*1yy；原问题的两个约束条件应取等式，故有 43*5*1=+ xx 32*5*1=+ xx 求解后得到1, 1*5*1=xx；故原问题的最优解为 5;10001 *=X 。 4.3 灵敏度分析 在以前讨论线性规划问题时， 假定jiijcba,都是常数。 但实际上这些系数往往是估计值和预测值。如市场条件一变，jc值就会变化；ija往往是因工艺条件的改变而改变；ib是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这些系数有一个或几个发生变化时， 已求得的线性规划问题的最优解会有什么变化； 或者这些系数在什么范围内变化时， 线性规划问题的最优解或最优基不变。 这里我们就不讨论了。 4.4 参数线性规划 参数线性规划是研究jiijcba,这些参数中某一参数连续变化时， 使最优解发生变化的各临界点的值。 即把某一参数作为参变量， 而目标函数在某区间内是这参变量的线性函数， 含这参变量的约束条件是线性等式或不等式。 因此仍可用单纯形法和对偶单纯形法进行分析参数线性规划问题。 5 投资的收益和风险 5.1 问题提出 市场上有n种资产is（ni, 2 , 1L=）可以选择，现用数额为M的相当大的资金作一个时期的投资。 这n种资产在这一时期内购买is的平均收益率为ir， 风险损失率为iq，投资越分散，总的风险越少，总体风险可用投资的is中最大的一个风险来度量。 -10- 购买is时要付交易费， （费率ip） ，当购买额不超过给定值iu时，交易费按购买iu计算。另外，假定同期银行存款利率是0r，既无交易费又无风险。 （%50=r） 已知4=n时相关数据如表 1。 表 1 is ir(%) iq ip(%) iu(元) 1s 28 2.5 1 103 2s 21 1.5 2 198 3s 23 5.5 4.5 52 4s 25 2.6 6.5 40 试给该公司设计一种投资组合方案，即用给定资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小。 5.2 符号规定和基本假设 符号规定： is：第i种投资项目，如股票，债券 iiiqpr,：分别为is的平均收益率，交易费率，风险损失率 iu：is的交易定额 0r：同期银行利率 ix：投资项目is的资金 a：投资风险度 Q：总体收益 基本假设： 1 投资数额M相当大，为了便于计算，假设1=M； 2 投资越分散，总的风险越小； 3 总体风险用投资项目is中最大的一个风险来度量； 4 n种资产is之间是相互独立的； 5 在投资的这一时期内，iiiqpr,，0r为定值，不受意外因素影响； 6 净收益和总体风险只受iiiqpr,影响，不受其它因素干扰。 5.3 模型的分析与建立 1 总体风险用所投资的is中最大的一个风险来衡量，即 , 2 , 1|maxnixqiiL= 2购买is所付交易费是一个分段函数，即 交易费=iiiiiiiiuxupuxxp, 而题目所给定的定值iu（单位：元）相对总投资M很少，iiup更小，可以忽略不计，这样购买is的净收益为iiixpr)( 。 3 要使净收益尽可能大，总体风险尽可能小，这是一个多目标规划模型： -11- 目标函数为 =maxmin)(max0iiniiiixqxpr 约束条件为 =+=nixMxpiniii, 1 , 0, 0)1 (0L 4 模型简化 a) 在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险aMxqii， 可找到相应的投资方案。 这样把多目标规划变成一个目标的线性规划。 模型一 固定风险水平，优化收益 =niiiixpr0)(max s.t. =+=niiiiiinixMxpaMxq0, 1 , 0, 0,)1 (L b) 若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻求相应的投资组合。 模型二 固定盈利水平，极小化风险 maxminiixq s.t. =+=niiiiniiiinixMxpkxpr00, 1 , 0, 0,)1 ()(L c) 投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益分别赋予权重s（10 s）和)1 (s，s称为投资偏好系数。 模型三 =niiiiiixprsxqs0)()1 (maxmin s.t. =+niiiinixMxp0, 2 , 1 , 0, 0,)1 (L 5.4 模型一的求解 模型一为： Txxxxxf),)(185. 0,185. 0,19. 0,27. 0,05. 0(min43210= -12- s.t. =+)4 , 1 , 0(0026. 0055. 0015. 0025. 01065. 1045. 102. 101. 1432143210Lixaxaxaxaxxxxxxi 由于a是任意给定的风险度， 到底怎样没有一个准则， 不同的投资者有不同的风险度。我们从0=a开始，以步长001. 0=a进行循环搜索，编制程序如下： clc,clear a=0; hold on while a0.05 c=-0.05,-0.27,-0.19,-0.185,-0.185; A=zeros(4,1),diag(0.025,0.015,0.055,0.026); b=a*ones(4,1); Aeq=1,1.01,1.02,1.045,1.065; beq=1; LB=zeros(5,1); x,Q=linprog(c,A,b,Aeq,beq,LB); Q=-Q; plot(a,Q,*r); a=a+0.001; end xlabel(a),ylabel(Q) 5.5 结果分析 1. 风险大，收益也大。 2当投资越分散时，投资者承担的风险越小，这与题意一致。即： 冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。 3在006. 0=a附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是%6 . 0=a，%20=Q，所对应投资方案为： 风险度006. 0=a， 收益2019. 0=Q，00=x，24. 01=x，4 . 02=x，1091. 03=x，2212. 04=x。 习 题 一 1试将下述问题改写成线性规划问题： =miiinmiiimiiixxaxaxai11211,minmaxL =+mixxxxim, 1, 01st.21LL 2试将下列问题改写成线性规划问题： -13- =njjjxcz1|max =取值无约束jnjijijxmibxa1), 2 , 1(st.L 3线性回归是一种常用的数理统计方法，这个方法要求对图上的一系列点),( ,),(),(2211nnyxyxyxL选配一条合适的直线拟合。方法通常是先定直线方程为bxay+=，然后按某种准则求定ba,。通常这个准则为最小二乘法，但也可用其他准则。试根据以下准则建立这个问题的线性规划模型： =+niiibxay1| )(|min 4某厂生产三种产品 I，II，III。每种产品要经过BA,两道工序加工。设该厂有两种规格的设备能完成A工序，它们以21, AA表示；有三种规格的设备能完成B工序，它们以321,BBB表示。产品 I 可在BA,任何一种规格设备上加工。产品 II 可在任何规格的A设备上加工，但完成B工序时，只能在1B设备上加工；产品 III 只能在2A与2B设备上加工。已知在各种机床设备的单件工时，原材料费，产品销售价格，各种设备有效台时以及满负荷操作时机床设备的费用如表 2，求安排最优的生产计划，使该厂利润最大。 表 2 产 品 设备 I II III 设备有效台时 满负荷时的 设备费用(元) 1A 2A 1B 2B 3B 5 7 6 4 7 10 9 8 12 11 6000 10000 4000 7000 4000 300 321 250 783 200 原料费(元/件) 单 价(元/件) 0.25 1.25 0.35 2.00 0.50 2.80 5有四个工人，要指派他们分别完成 4 项工作，每人做各项工作所消耗的时间如表 3。 表 3 工作 工人 A B C D 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 问指派哪个人去完成哪项工作，可使总的消耗时间为最小？ -14- 6某战略轰炸机群奉命摧毁敌人军事目标。已知该目标有四个要害部位，只要摧毁其中之一即可达到目的。为完成此项任务的汽油消耗量限制为 48000 升、重型炸弹48 枚、轻型炸弹 32 枚。飞机携带重型炸弹时每升汽油可飞行 2 千米，带轻型炸弹时每升汽油可飞行 3 千米。 又知每架飞机每次只能装载一枚炸弹， 每出发轰炸一次除来回路程汽油消耗（空载时每升汽油可飞行 4 千米）外，起飞和降落每次各消耗 100 升。有关数据如表 4 所示。 表 4 摧毁可能性 要害部位 离机场距离 （千米） 每枚重型弹 每枚轻型弹 1 2 3 4 450 480 540 600 0.10 0.20 0.15 0.25 0.08 0.16 0.12 0.20 为了使摧毁敌方军事目标的可能性最大， 应如何确定飞机轰炸的方案， 要求建立这个问题的线性规划模型。 7用 Matlab 求解下列线性规划问题： 3213maxxxxz= s.t. =+0,1232411232131321321xxxxxxxxxxx 8用 Matlab 求解下列规划问题： |4|3|2|min4321xxxxz+= s.t. 04321=+xxxx 134321=+xxxx 21324321=+xxxx 9一架货机有三个货舱：前舱、中仓和后舱。三个货舱所能装载的货物的最大重量和体积有限制如表 5 所示。 并且为了飞机的平衡， 三个货舱装载的货物重量必须与其最大的容许量成比例。 表 5 货舱数据 前舱 中仓 后舱 重量限制（吨） 10 16 8 体积限制（立方米） 6800 8700 5300 现有四类货物用该货机进行装运，货物的规格以及装运后获得的利润如表 6。 表 6 货物规格及利润表 重量（吨） 空间（立方米/吨） 利润（元/吨） 货物 1 18 480 3100 货物 2 15 650 3800 货物 3 23 580 3500 货物 4 12 390 2850 -15- 假设： （1）每种货物可以无限细分； （2）每种货物可以分布在一个或者多个货舱内； （3）不同的货物可以放在同一个货舱内，并且可以保证不留空隙。 问应如何装运，使货机飞行利润最大？ -16- 第二章第二章 整数规划整数规划 1 概论 1.1 定义 规划中的变量 （部分或全部） 限制为整数时， 称为整数规划。 若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。 1.2 整数规划的分类 如不加特殊说明，一般指整数线性规划。对于整数线性规划模型大致可分为两类： 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 1.2 整数规划特点 （i） 原线性规划有最优解， 当自变量限制为整数后， 其整数规划解出现下述情况： 原线性规划最优解全是整数，则整数规划最优解与线性规划最优解一致。 整数规划无可行解。 例 1 原线性规划为 21minxxz+= 0, 0, 5422121=+xxxx 其最优实数解为：45min,45, 021=zxx。 有可行解（当然就存在最优解） ，但最优解值变差。 例 2 原线性规划为 21minxxz+= 0, 0, 6422121=+xxxx 其最优实数解为：23min,23, 021=zxx。 若限制整数得：2min, 1, 121=zxx。 （ii） 整数规划最优解不能按照实数最优解简单取整而获得。 1.3 求解方法分类： （i）分枝定界法可求纯或混合整数线性规划。 （ii）割平面法可求纯或混合整数线性规划。 （iii）隐枚举法求解“0-1”整数规划： 过滤隐枚举法； 分枝隐枚举法。 （iv）匈牙利法解决指派问题（ “0-1”规划特殊情形） 。 （v）蒙特卡洛法求解各种类型规划。 下面将简要介绍常用的几种求解整数规划的方法。 2 分枝定界法 对有约束条件的最优化问题 （其可行解为有限数） 的所有可行解空间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题） ，这称为定界。 在每次分枝后， 凡是界限超出已知可行解集目标值的那些子集不再进一步分枝， -17- 这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。 分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由 Land Doig 和 Dakin 等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。 设有最大化的整数规划问题A， 与它相应的线性规划为问题B， 从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数*z的上界，记作z；而A的任意可行解的目标函数值将是*z的一个下界z。分枝定界法就是将B的可行域分成子区域的方法。逐步减小z和增大z，最终求到*z。现用下例来说明： 例 3 求解下述整数规划 219040Maxxxz+= +且为整数0,702075679212121xxxxxx 解 （i）先不考虑整数限制，即解相应的线性规划B，得最优解为： 355.8779,8168. 1,8092. 421=zxx 可见它不符合整数条件。这时z是问题A的最优目标函数值*z的上界，记作z。而0, 021=xx显然是问题A的一个整数可行解， 这时0=z， 是*z的一个下界， 记作z，即3560* z。 （ii）因为21,xx当前均为非整数，故不满足整数要求，任选一个进行分枝。设选1x进行分枝，把可行集分成 2 个子集： 44.80921=x，514.80921=+x 因为 4 与 5 之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下： 问题1B： 219040Maxxxz+= +0, 40702075679212121xxxxxx 最优解为：349, 1 . 2, 0 . 4121=zxx。 问题2B： 219040Maxxxz+= +0, 5702075679212121xxxxxx 最优解为：4 .341,57. 1, 0 . 5121=zxx。 再定界：3490* z。 （iii）对问题1B再进行分枝得问题11B和12B，它们的最优解为 -18- 340, 2, 4:112111=zxxB 327.14,00. 3x1.43,:122112=zxB 再定界：341340* z，并将12B剪枝。 （iv）对问题2B再进行分枝得问题21B和22B，它们的最优解为 083,00. 1x5.44,:222121=zxB 22B无可行解。 将2221,BB剪枝。 于是可以断定原问题的最优解为： 340, 2, 4*21=zxx 从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为： 开始，将要求解的整数规划问题称为问题A，将与它相应的线性规划问题称为问题B。 （i）解问题B可能得到以下情况之一： （a）B没有可行解，这时A也没有可行解，则停止 （b）B有最优解，并符合问题A的整数条件，B的最优解即为A的最优解，则停止。 （c）B有最优解，但不符合问题A的整数条件，记它的目标函数值为z。 （ii）用观察法找问题A的一个整数可行解，一般可取njxj, 1, 0L=，试探，求得其目标函数值，并记作z。以*z表示问题A的最优目标函数值；这时有 zzz* 进行迭代。 第一步：分枝，在B的最优解中任选一个不符合整数条件的变量jx，其值为jb，以jb表示小于jb的最大整数。构造两个约束条件 jjbx 和 1+jjbx 将这两个约束条件，分别加入问题B，求两个后继规划问题1B和2B。不考虑整数条件求解这两个后继问题。 定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界z。 从已符合整数条件的各分支中， 找出目标函数值为最大者作为新的下界z，若无作用z不变。 第二步：比较与剪枝，各分枝的最优目标函数中若有小于z者，则剪掉这枝，即以后不再考虑了。若大于z，且不符合整数条件，则重复第一步骤。一直到最后得到zz =*为止。得最优整数解njxj, 1,*L=。 3 10型整数规划 10型整数规划是整数规划中的特殊情形，它的变量jx仅取值 0 或 1。这时jx称为10变量，或称二进制变量。jx仅取值 0 或 1 这个条件可由下述约束条件： 10jx，整数 -19- 所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入 10变量， 就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。 我们先介绍引入10变量的实际问题，再研究解法。 3.1 引入10变量的实际问题 3.1.1 投资场所的选定相互排斥的计划 例 4 某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置（点）)7 , 2 , 1(L=iAi可供选择。规定 在东区。由321,AAA三个点中至多选两个； 在西区。由54, AA两个点中至少选一个； 在南区，由76,AA两个点中至少选一个。 如选用iA点，设备投资估计为ib元，每年可获利润估计为ic元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？ 解题时先引入10变量)7 , 2 , 1(L=ixi 令 =.0, 1点没被选中当点被选中当，iAiAix 7 , 2 , 1L=i. 于是问题可列写成： iiixcz=71Max =+=10, 112765432171或iiiixxxxxxxxBxb 3.1.2 相互排斥的约束条件 有两个相互排斥的约束条件 244521+ xx 或 453721+ xx。 为了统一在一个问题中，引入10变量y，则上述约束条件可改写为： =+10)1 (453724452121或yMyxxyMxx 其中M是充分大的数。 约束条件 01=x 或 8005001 x 可改写为 =108005001或yyxy -20- 如果有m个互相排斥的约束条件： mibxaxainini, 2 , 111LL=+ 为了保证这m个约束条件只有一个起作用，我们引入m个10变量), 2 , 1(miyiL=和一个充分大的常数M，而下面这一组1+m个约束条件 miMybxaxaiinini, 2 , 111LL=+ （1） 11=+myymL （2） 就合于上述的要求。这是因为，由于（2） ，m个iy中只有一个能取 0 值，设0*=iy，代入（1） ，就只有*ii =的约束条件起作用，而别的式子都是多余的。 3.1.3 关于固定费用的问题（Fixed Cost Problem） 在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。 例 5 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备） ，由于产量大，因而分配到每件产品的变动成本就降低； 反之， 如选定的生产方式投资低， 将来分配到每件产品的变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择，令 jx表示采用第j种方式时的产量； jc表示采用第j种方式时每件产品的变动成本； jk表示采用第j种方式时的固定成本。 为了说明成本的特点， 暂不考虑其它约束条件。 采用各种生产方式的总成本分别为 =+= 0 , 00,jjjjjjxxxckP当当 3 , 2 , 1=j. 在构成目标函数时，为了统一在一个问题中讨论，现引入10变量jy，令 =.00, 0, 1时种生产方式，即当不采用第时，种生产方式，即当采用第jxjjxjjy （3） 于是目标函数 )()()(min333322221111xcykxcykxcykz+= （3）式这个规定可表为下述 3 个线性约束条件： 3 , 2 , 1,=jMyxyjjj （4） 其中是一个充分小的正常数，M是个充分大的正常数。 （4）式说明，当0jx时jy必须为 1；当0=jx时只有jy为 0 时才有意义，所以（4）式完全可以代替（3）式。 3.2 10型整数规划解法之一（过滤隐枚举法） 解10型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，即检查变量取值为 0 或 1 的每一种组合， 比较目标函数值以求得最优解， 这就需要检查变量取值的n2个组合。对于变量个数n较大（例如100n） ，这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法（Implicit Enumeration） ，分枝定界法也是一种隐枚举法。当然，对 -21- 有些问题隐枚举法并不适用，所以有时穷举法还是必要的。 下面举例说明一种解10型整数规划的隐枚举法。 例 6 321523Maxxxxz+= =+10,64344223213221321321或xxxxxxxxxxxxx 求解思路及改进措施： （i） 先试探性求一个可行解，易看出)0 , 0 , 1 (),(321=xxx满足约束条件，故为一个可行解，且3=z。 （ii） 因为是求极大值问题，故求最优解时，凡是目标值3z的解不必检验是否满足约束条件即可删除， 因它肯定不是最优解， 于是应增加一个约束条件 （目标值下界） ： （iii） 改进过滤条件。 （iv） 由于对每个组合首先计算目标值以验证过滤条件， 故应优先计算目标值z大的组合，这样可提前抬高过滤门槛，以减少计算量。 4 蒙特卡洛法（随机取样法） 前面介绍的常用的整数规划求解方法， 主要是针对线性整数规划而言， 而对于非线性整数规划目前尚未有一种成熟而准确的求解方法， 因为非线性规划本身的通用有效解法尚未找到，更何况是非线性整数规划。 然而， 尽管整数规划由于限制变量为整数而增加了难度； 然而又由于整数解是有限个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一定的计算量的情况下，完全可以得出一个满意解。 例 7 已知非线性整数规划为： 5432125242322212328 243Max xxxxxxxxxxz+= +=200520062800622400)5 , 1(9905433215432154321xxxxxxxxxxxxxxxxixiL 如果用显枚举法试探，共需计算10510)100(=个点，其计算量非常之大。然而应用蒙特卡洛去随机计算610个点，便可找到满意解，那么这种方法的可信度究竟怎样呢？ 下面就分析随机取样采集610个点计算时，应用概率理论来估计一下可信度。 不失一般性，假定一个整数规划的最优点不是孤立的奇点。 假设目标函数落在高值区的概率分别为 0.01，0.00001，则当计算610个点后，有 -22- 任一个点能落在高值区的概率分别为 多位）100(9999. 099. 011000000L， 999954602. 099999. 011000000。 解 （i）首先编写 M 文件 mente.m 定义目标函数 f 和约束向量函数 g，程序如下： function f,g=mengte(x); f=x(1)2+x(2)2+3*x(3)2+4*x(4)2+2*x(5)-8*x(1)-2*x(2)-3*x(3)-. x(4)-2*x(5); g=sum(x)-400 x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800 2*x(1)+x(2)+6*x(3)-200 x(3)+x(4)+5*x(5)-200; （ii）编写M文件mainint.m如下求问题的解： rand(state,sum(clock); p0=0; tic for i=1:106 x=99*rand(5,1); x1=floor(x);x2=ceil(x); f,g=mengte(x1); if sum(g=0)=4 if p0=f x0=x1;p0=f; end end f,g=mengte(x2); if sum(g=0)=4 if p0=f x0=x2;p0=f; end end end x0,p0 toc 本题可以使用LINGO软件求得精确的全局最有解，程序如下： model: sets: row/1.4/:b; col/1.5/:c1,c2,x; link(row,col):a; endsets data: c1=1,1,3,4,2; c2=-8,-2,-3,-1,-2; a=1 1 1 1 1 1 2 2 1 6 2 1 6 0 0 -23- 0 0 1 1 5; b=400,800,200,200; enddata max=sum(col:c1*x2+c2*x); for(row(i):sum(col(j):a(i,j)*x(j)x，这个条件可以表示为 0)500(21=xx （15） 同理，只有当以 8 千元/吨的价格购买5002=x（吨）时，才能以 6 千元/吨的价格购买)0(3x，于是 0)500(32=xx （16） 此外，321,xxx的取值范围是 500,0321xxx （17） 由于有非线性约束（15） 、 （16） ，因而（7）（17）构成非线性规划模型。将该模型输入 LINGO 软件如下： model: sets: var1/1.4/:y; !这里y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22; var2/1.3/:x,c; endsets max=4.8*(y(1)+y(2)+5.6*(y(3)+y(4)-sum(var2:c*x); y(1)+y(3)sum(var2:x)+500; y(2)+y(4)0; 0.4*y(3)-0.6*y(4)0; (x(1)-500)*x(2)=0; (x(2)-500)*x(3)=0; for(var2:bnd(0,x,500); data: c=10 8 6; enddata end 可以用菜单命令“LINGO|Options”在“Global Solver”选项卡上启动全局优化选型，并运行上述程序求得全局最有解：购买 1000 吨原油A，与库存的 500 吨原油A和1000 吨原油B一起，共生产 2500 吨汽油乙，利润为 5000（千元） 。 （2）解法二 引入 01 变量将（15）和（16）转化为线性约束。 令11=z，12=z，13=z分别表示以 10 千元/吨、8 千元/吨、6 千元/吨的价格采购原油A，则约束（15）和（16）可以替换为 -26- 112500500zxz， （18） 223500500zxz， （19） 33500zx ， （20） 0,321=zzz或 1 （21） 式（7）（14） ，式（17）（21）构成混合整数线性规划模型，将它输入 LINGO 软件如下： model: sets: var1/1.4/:y; !这里y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22; var2/1.3/:x,z,c; endsets max=4.8*(y(1)+y(2)+5.6*(y(3)+y(4)-sum(var2:c*x); y(1)+y(3)sum(var2:x)+500; y(2)+y(4)0; 0.4*y(3)-0.6*y(4)0; for(var1(i)|i #lt# 3:500*z(i+1)x(i);x(i)500*z(i); x(3)500*z(3); for(var2:bin(z); for(var2:bnd(0,x,500); data: c=10 8 6; enddata end （3）解法三 直接处理分段线性函数)(xc。式（5）表示的函数)(xc如图 1 所示。 记x轴上的分点为01=b，5002=b，10003=b。当x属于第 1 个小区间,21bb时，记2211bwbwx+=，121=+ ww，0,21ww，因为)(xc在,21bb上是线性的， 图 1 分段线性函数)(xc图形 所 以)()()(2211bcwbcwxc+=。 同 样 ， 当x属 于 第 2 个 小 区 间,32bb时 ，3322bwbwx+=，132=+ ww，0,32ww，)()()(3322bcwbcwxc+=。当x属于第3个 小 区 间,43bb时 ，4433bwbwx+=，143=+ ww，0,43ww，)()()(4433bcwbcwxc+=。为了表示x在哪个小区间，引入 0-1 变量)3 , 2 , 1( =kzk，当x在第k个小区间时，1=kz，否则，0=kz。这样，3214321,zzzwwww应满 -27- 足 11zw ，212zzw+，323zzw+，34zw （22） 14321=+wwww，0kw（4 , 3 , 2 , 1=k） （23） 1321=+zzz，10,321或=zzz （24） 此时x和)(xc可以统一地表示为 4324433221115001000500wwwbwbwbwbwx+=+= （25） )()()()()(44332211bcwbcwbcwbcwxc+= 4321200090005000www+= （26） 式（6）（13） ，式（22）（26）也构成一个混合整数线性规划模型，可以用LINGO 求解。输入的 LINGO 模型如下： model: sets: var/1.4/:b,c,y,z,w; !这里y(1)=x11,y(2)=x21,y(3)=x12,y(4)=x22 端点数为4，即分段数为3; endsets data: b=0,500,1000,1500; c=0,5000,9000,12000; z=,0; !增加的虚拟变量z(4)=0; enddata max=4.8*(y(1)+y(2)+5.6*(y(3)+y(4)-sum(var:c*w); y(1)+y(3)sum(var:b*w)+500; y(2)+y(4)0; 0.4*y(3)-0.6*y(4)0; w(1)z(1); for(var(i)|i #ne# 1:w(i)z(i-1)+z(i); sum(var:z)=1; sum(var:w)=1; for(var:bin(z); End 注：这个问题的关键是处理分段线性函数，我们推荐化为整数线性规划模型的第2和第3种解法，第3种解法更具一般性，其做法如下。 设一个n段线性函数)(xf的分点为11+nnbbbL，引入kw将x和)(xf表示为 +=11nkkkbwx +=11)()(nkkkkbfwxf kw和0-1变量kz满足 11zw ，212zzw+，nnnzzw+1，nnzw+1 （27） -28- 121=+nzzzL，10或=kz （28） 1121=+nwwwL，0kw（1, 2 , 1+=nkL） （29） 习 题 二 1. 用分枝定界法解： 21Max xxz+= +整数21212121, 0,3121451149xxxxxxxx 2. 试将下述非线性的10规划问题转换成线性的10规划问题 3211maxxxxxz+= =+) 3 , 2 , 1(10332321jxxxxj，或 3. 某钻井队要从以下 10 个可供选择的井位中确定 5 个钻井探油，使总的钻探费用为最小。若 10 个井位的代号为1021,sssL，相应的钻探费用为1021,cccL，并且井位选择上要满足下列限制条件： （1） 或选择1s和7s，或选择钻探9s； （2） 选择了3s或4s就不能选5s，或反过来也一样； （3） 在8765,ssss中最多只能选两个；试建立这个问题的整数规划模型。 4有一条河流由于河床泥沙淤结，每当上游发生洪水时，就会破堤淹没两岸，造成人员和财产的损失，为减少总的损失，人们采取破堤泄洪的方法，图 2 是该河流一岸区域的信息示意图，在该区域边界上有很高的山，使该区域成为封闭区域。区域内又分成十五个小区，每个小区内标有三个数字，分别表示该区域的海拔高度)m(h、面积)km(2S和被完全淹没时土地、房屋和财产等损失总数k（百万元） ，我们假设 （a）各小区间有相对高度为 1.2m 的小堤相互隔离，例如第一区和第二区之间事实上有海拔 5.2m 小堤。 （b） 当洪水淹没一个小区且洪水高于该小区高度mp时， 该小区的损失),(pkf为该小区的k和p的函数： =1,10,),(pkpkppkf （c）假设决堤口，可选在大堤或小堤的任何地方，决堤口的数量不受限制，但已经决口，就不能再补合，从河流经大堤决口流入小区的洪水量按决口数成比例分配，如在小区之间小堤开一决口， 则假设该两小区之间的这段小堤不复存在， 若水位高过小堤，则将自动向邻近最低的小区泄洪，若这样的小区有多块时，则平均泄洪。 求 -29- （1）整个区域全部受损失的最小洪水量Q。 （2）当洪水量为6/Q，3/Q时，分别制定泄洪方案，使总损失最小（在一种方案中，决堤同时进行） ，并计算出该方案的损失数。 河 流 图 2 河流一岸区域示意图 表 1 校址选择数据 备选校址 1B 2B 3B 4B 5B 6B 覆盖的居民小区 751,AAA8521,AAAA531,AAA842,AAA63,AA 864,AAA 5某市为方便小学生上学，拟在新建的 8 个居民小区821,AAAL增设若干所H3.6 S6.1 K1.4 1 111H4.0 S8.4 K7.0 2 2H4.7 S7.0 K5.8 3 3H4.4 S9.3 K3.3 4 1H3.8 S4.8 K2.0 5 551H3.3 S3.6 K9.