第九章 最优化方法本章主要介绍线性规划、0-1规划、非线性规划等问题的MATLAB 求解。

9.1 线性规划（Linear Programming ，简写为LP ）问题线性规划问题就是求多变量线性函数在线性约束条件下的最优值。

满足约束条件的解称为可行解，所有可行解构成的集合称为可行域，满足目标式的可行解称为最优解。

MATLAB 解决的线性规划问题的标准形式为：min z f x ¢=? ..A x b s t Aeq x beq lb x ubì祝ïïï?íïï＃ïïî 其中,,,,,f x b beq lb ub 为列向量，,A Aeq 为矩阵。

其它形式的线性规划问题都可经过适当变换化为此标准形式。

在MATLAB 中求解线性规划问题函数为linprog ，其使用格式为：[x, fval, exitflag, output, lambda] = linprog(f, A, b, Aeq, beq, lb, ub) 输入部分：其中各符号对应线性规划问题标准形式中的向量和矩阵，如果约束条件中有缺少，则其相应位置用空矩阵[]代替。

输出部分：其中x 为最优解，用列向量表示；fval 为最优值；exitflag 为退出标志，若exitflag=1表示函数有最优解，若exitflag=0表示超过设定的迭代最大次数，若exitflag=-2，表示约束区域不可行，若exitflag=-3，表示问题无解，若exitflag=-4，表示执行迭代算法时遇到NaN ，若exitflag=-5，表示原问题和对偶问题均不可行，若exitflag=-7，表示搜索方向太小，不能继续前进；output 表明算法和迭代情况；lambda 表示存储情况。

例1 用linprog 函数求下面的线性规划问题12312312312123min 54620324423230.. 0,00x x x x x x x x x x x s t x x x ---ì-+?ïïïï++?ïïï+?ïïíï£ïïï£ïïïï£ïî 输入如下： >> f = [-5, -4,-6]; A = [1 -1 1; 3 2 4; 3 2 0]; b = [20; 42; 30]; lb = zeros(3,1);[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb)注意：由于该问题没有等式约束，所以输入格式中相应的位置用[]代替，变量没有上限约束，所以ub 也用[]代替，但由于其在最后，可以不写。

输出结果如下： Optimization terminated. x = % 最优解 0.0000 15.0000 3.0000 fval = %最优值 -78.0000exitflag = %函数收敛于解 1 output = iterations: 6algorithm: 'large-scale: interior point' cgiterations: 0message: 'Optimization terminated.' lambda =ineqlin: [3x1 double] eqlin: [0x1 double] upper: [3x1 double] lower: [3x1 double]例2 一家家具公司生产桌子和椅子，用于生产的全部劳动力共计450个工时，原料是400个单位的木材。

每张桌子使用15个工时的劳动力，20个单位的木材，售价为80元。

每张椅子使用10个工时，用料5个单位，售价45元。

问为达到最大效益，应如何安排生产？解 设生产桌子x 个，椅子y 个，建立如下模型：max 80452054001510450.. 00x yx y x y s t x y +ì+?ïïïï+?ïíï³ïïï³ïî 输入如下： >> f = [-80,-45]; A = [20, 5; 15, 10]; b = [400, 450]; lb = zeros(2,1);[x, fval, exitflag] = linprog(f,A,b,[],[],lb) 结果如下：Optimization terminated. x = 14.0000 24.0000 fval = -2.2000e+003 exitflag = 1注意：由于linprog 是求目标函数的最小值，如求目标函数f 的最大值，可先求出f -的最小值fval ，则-fval 就是f 的最大值。

本例只输出最优解、最优值和退出标志，可见生产14个桌子，24个椅子，可获得最大利润2200元。

9.2 0-1规划0-1规划是一种特殊形式的整数规划，它的决策变量仅取值0或1.一般用0表示放弃，1表示选取，故0-1规划可以用来处理选址问题、指派问题、装箱问题、项目评价、资金分配、生产计划安排等问题。

在MATALB 中求解0-1规划问题函数为bintprog ，其针对下述0-1规划：min z f x ¢=? .. 0/1,1,2,,i A x b s t Aeq x beq x i nL ì祝ïïï?íïï==ïïî其中,,,f x b beq 为列向量，,A Aeq 为矩阵。

使用格式为：[x, fval, exitflag, output] = bintprog(f, A, b, Aeq, beq)输入部分：其中各符号对应0-1规划问题标准形式中的向量和矩阵，如果约束条件中有缺少，则其相应位置用空矩阵[]代替。

输出部分：其中x 为最优解，用列向量表示；fval 为最优值；exitflag 为退出标志，若exitflag=1表示函数有最优解，若exitflag=-1表示超过设定的迭代最大次数，若exitflag=-2，表示问题不可行，若exitflag=-4，表示搜索节点数超过了设定的搜索节点最大个数，若exitflag=-5，表示搜索时间超过了设定的指令运行的最大秒数，若exitflag=-6，表示LP 求解器在某节点处求解LP 松弛问题时的迭代次数超过了设定的迭代次数；output 包含使用算法、迭代次数、搜索过的节点数、算法执行时间、算法终止原因。

例3 求解下述0-1规划问题。

123451234512345max 22643225.. 2422501(1,2,,5)i z x x x x x x x x x x s t x x x x x x i =++--+-++≤⎧⎪+---≤⎨⎪==⎩L 或 利用bintprog 函数求解如下： >> f=-[1;2;2;-6;-4];A=[3,2,-1,4,2; 2,4, -2,-1,-2]; b=[5;5] ;[x,fval,exit,output]=bintprog(f,A,b) 输出结果：Optimization terminated. x = 1 1 1 0 0 fval = -5 exit = 1 output =iterations: 4 nodes: 1 time: 0.0781algorithm: 'LP-based branch-and-bound' branchStrategy: 'maximum integer infeasibility' nodeSrchStrategy: 'best node search' message: 'Optimization terminated.这表明，当123451,1,1,0,0x x x x x =====时，目标函数取最大值5。

例4 资金分配问题，某企业在今后3年内有5个工程考虑开工，每项工程的期望收入和年度费用如表所示。

假定每一项已经批准的工程要在整3年内完成。

企业应如何选择工程，使企业总收入最大？解 设决策变量为12345,,,,x x x x x ：其中01i x =或，0i x =表示放弃第i 项工程，1i x =表示选择第i 项工程。

该问题的数学模型为：12345123451234512345max 20402015305437825794625.. 8102102510(i=1,2,3,4,5)=++++++++≤⎧⎪++++≤⎪⎨++++≤⎪⎪=⎩或i z x x x x x x x x x x x x x x x s t x x x x x x利用bintprog 函数求解如下： f=-[20;40;20;15;30];A=[5,4,3,7,8;1,7,9,4,6;8,10,2,1,10]; b=[25;25;25];[x,fv,exit]=bintprog(f,A,b) 输出结果如下： Optimization terminated. x = 1 1 1 1 0 fv = -95 exit = 1上述结果表明，该企业选择第1，第2，第3，第4项工程，可以获得最大利润95千元。

指派问题：设有n 项工作分配给n 个人去做，每人做一项，由于个人的工作效率不同，因而完成同一工作所需时间也不同，设人员i 完成工作j 所需时间为ij C （称为效率矩阵），问如何分配工作，使得完成所有工作所用的总时间最少？这类问题称为指派问题（Assignment Problem ），也称最优匹配问题，它是一类典型的0-1规划问题。

例5 有4个工人被分派做4项工作，每项工作只能一人做，每人只能做一项工作。

现设每个工人做每项工作的耗时如表所示，求总耗时最少的分配方案。

表1时间表 时间单位：小时解 设决策变量为(,1,2,3,4)ij x i j =，只取0或1。

1ij x =表示工人i 完成工作j ；0ij x =表示工人i 不做工作j 。

于是，上述问题的数学模型如下：11121314212223243132333441424344min 15182124192322182617161919212317z x x x x x x x x x x x x x x x x =+++++++++++++++111,1,2,3,4.. 1,1,2,3,4nij j nij i x i s t x j ==⎧==⎪⎪⎨⎪==⎪⎩∑∑ 下面给出Matlab 计算程序。