线性规划模型及matlab程序求解(共28页).doc
精选优质文档-倾情为你奉上§1 线性规划模型一、线性规划课题： 实例1：生产计划问题 假设某厂计划生产甲、乙两种产品，现库存主要材料有A类3600公斤，B类2000公斤，C类3000公斤。每件甲产品需用材料A类9公斤，B类4公斤，C类3公斤。每件乙产品，需用材料A类4公斤，B类5公斤，C类10公斤。甲单位产品的利润70元，乙单位产品的利润120元。问如何安排生产，才能使该厂所获的利润最大。建立数学模型：设x1、x2分别为生产甲、乙产品的件数。f为该厂所获总润。 max f=70x1+120x2 s.t 9x1+4x23600 4x1+5x22000 3x1+10x23000 x1,x20归结出规划问题：目标函数和约束条件都是变量x的线性函数。形如： (1) min f T X s.t A Xb Aeq X =beqlbXub 其中X为n维未知向量，f T=f1,f2,fn为目标函数系数向量，小于等于约束系数矩阵A为m×n矩阵，b为其右端m维列向量，Aeq为等式约束系数矩阵，beq为等式约束右端常数列向量。lb,ub为自变量取值上界与下界约束的n维常数向量。二线性规划问题求最优解函数： 调用格式： x=linprog(f,A,b) x=linprog(f,A,b,Aeq,beq) x=linprog(f,A,b,Aeq,beq,lb,ub) x=linprog(f,A,b,Aeq,beq,lb,ub,x0) x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) x,fval=linprog() x, fval, exitflag=linprog() x, fval, exitflag, output=linprog() x, fval, exitflag, output, lambda=linprog() 说明：x=linprog(f,A,b)返回值x为最优解向量。 x=linprog(f,A,b,Aeq,beq) 作有等式约束的问题。若没有不等式约束，则令A= 、b= 。 x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options) 中lb ,ub为变量x的下界和上界，x0为初值点，options为指定优化参数进行最小化。Options的参数描述：Display 显示水平。 选择off 不显示输出；选择iter显示每一 步迭代过程的输出；选择final 显示最终结果。MaxFunEvals 函数评价的最大允许次数Maxiter 最大允许迭代次数TolX x处的终止容限 x,fval=linprog() 左端 fval 返回解x处的目标函数值。x,fval,exitflag,output,lambda=linprog(f,A,b, Aeq,beq,lb,ub,x0) 的输出部分： exitflag 描述函数计算的退出条件：若为正值，表示目标函数收敛于解x处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。output 返回优化信息：output.iterations表示迭代次数；output.algorithm表示所采用的算法；outprt.funcCount表示函数评价次数。lambda 返回x处的拉格朗日乘子。它有以下属性： lambda.lower-lambda的下界； lambda.upper-lambda的上界； lambda.ineqlin-lambda的线性不等式； lambda.eqlin-lambda的线性等式。三 举例例1：求解线性规划问题： max f=2x1+5x2 s.t x14 x23 x1+x28 x1,x20先将目标函数转化成最小值问题：min(-f)=- 2x1-5x2程序： f=-2 -5; A=1 0;0 1;1 1; b=4;3;8; x,fval=linprog(f,A,b) f=fval*(-1) 结果： x = 2 3 fval = -19.0000maxf = 19例2：minf=5x1-x2+2x3+3x4-8x5s.t 2x1+x2-x3+x4-3x56 2x1+x2-x3+4x4+x57 0xj15 j=1,2,3,4,5 程序： f=5 -1 2 3 -8; A=-2 1 -1 1 -3;2 1 -1 4 1; b=6;7; lb=0 0 0 0 0; ub=15 15 15 15 15; x,fval=linprog(f,A,b,lb,ub) 结果：x = 0.0000 0.0000 8.0000 0.0000 15.0000minf = -104例3：求解线性规划问题： min f=5x1+x2+2x3+3x4+x5s.t 2x1+x2-x3+x4-3x51 2x1+3x2-x3+2x4+x5-2 0xj1 j=1,2,3,4,5程序： f=5 1 2 3 1; A=-2 1 -1 1 -3;2 3 -1 2 1; b=1;-2; lb=0 0 0 0 0; ub=1 1 1 1 1; x,fval,exitflag,output,lambda=linprog(f,A,b,lb,ub) 运行结果： Exiting: One or more of the residuals, duality gap, or total relative error has grown times greater than its minimum value so far: the primal appears to be infeasible (and the dual unbounded). (The dual residual < TolFun=1.00e-008.)x = 0.0000 0.0000 1.1987 0.0000 0.0000fval = 2.3975exitflag = -1output = iterations: 7 cgiterations: 0 algorithm: 'lipsol'lambda = ineqlin: 2x1 double eqlin: 0x1 double upper: 5x1 double lower: 5x1 double 显示的信息表明该问题无可行解。所给出的是对约束破坏最小的解。 例4：求解实例1的生产计划问题建立数学模型： 设x1、x2分别为生产甲、乙产品的件数。f为该厂所获总润。 max f=70x1+120x2 s.t 9x1+4x23600 4x1+5x22000 3x1+10x23000 x1,x20将其转换为标准形式：min f=-70x1-120x2 s.t 9x1+4x23600 4x1+5x22000 3x1+10x23000 x1,x20 程序： f=-70 -120; A=9 4 ;4 5;3 10 ; b=3600;2000;3000; lb=0 0; ub=; x,fval,exitflag=linprog(f,A,b,lb,ub) maxf=-fval 结果： x = 200.0000 240.0000fval = -4.2800e+004exitflag = 1maxf = 4.2800e+004 例5：求解实例2 建立数学模型：max f=0.15x1+0.1x2+0.08 x3+0.12 x4 s.t x1-x2- x3- x40 x2+ x3- x40 x1+x2+x3+ x4=1 xj0 j=1,2,3,4 将其转换为标准形式：min z=-0.15x1-0.1x2-0.08 x3-0.12 x4 s.t x1-x2- x3- x40 -x2- x3+ x40 x1+x2+x3+ x4=1 xj0 j=1,2,3,4 程序： f = -0.15;-0.1;-0.08;-0.12; A = 1 -1 -1 -1 0 -1 -1 1; b = 0; 0; Aeq=1 1 1 1; beq=1; lb = zeros(4,1); x,fval,exitflag = linprog(f,A,b,Aeq,beq,lb) f=-fval 结果：x = 0.5000 0.2500 0.0000 0.2500fval = -0.1300exitflag = 1f =0.1300 即4个项目的投资百分数分别为50%，25%，0, 25%时可使该公司获得最大的收益，其最大收益可到达13%。过程正常收敛。MATLAB的语言特点一种语言之所以能如此迅速地普及，显示出如此旺盛的生命力，是由于它有着不同于其他语言的特点，正如同FORTRAN和C等高级语言使人们摆脱了需要直接对计算机硬件资源进行操作一样，被称作为第四代计算机语言的MATLAB，利用其丰富的函数资源，使编程人员从繁琐的程序代码中解放出来。MATLAB最突出的特点就是简洁。MATLAB用更直观的，符合人们思维习惯的代码，代替了C和FORTRAN语言的冗长代码。MATLAB给用户带来的是最直观，最简洁的程序开发环境。以下简单介绍一下MATLAB的主要特点。1）。语言简洁紧凑，使用方便灵活，库函数极其丰富。MATLAB程序书写形式自由，利用起丰富的库函数避开繁杂的子程序编程任务，压缩了一切不必要的编程工作。由于库函数都由本领域的专家编写，用户不必担心函数的可靠性。可以说，用MATLAB进行科技开发是站在专家的肩膀上。具有FORTRAN和C等高级语言知识的读者可能已经注意到，如果用FORTRAN或C语言去编写程序，尤其当涉及矩阵运算和画图时，编程会很麻烦。例如，如果用户想求解一个线性代数方程，就得编写一个程序块读入数据，然后再使用一种求解线性方程的算法（例如追赶法）编写一个程序块来求解方程，最后再输出计算结果。在求解过程中，最麻烦的要算第二部分。解线性方程的麻烦在于要对矩阵的元素作循环，选择稳定的算法以及代码的调试动不容易。即使有部分源代码，用户也会感到麻烦，且不能保证运算的稳定性。解线性方程的程序用FORTRAN和C这样的高级语言编写，至少需要四百多行，调试这种几百行的计算程序可以说很困难。以下用MATLAB编写以上两个小程序的具体过程。MATLAB求解下列方程，并求解矩阵A的特征值。Ax=b,其中：A= 32 13 45 67 23 79 85 12 43 23 54 65 98 34 71 35b= 1 2 3 4解为：x=Ab;设A的特征值组成的向量e，e=eig（A）。可见，MATLAB的程序极其简短。更为难能可贵的是，MATLAB甚至具有一定的智能水平，比如上面的解方程，MATLAB会根据矩阵的特性选择方程的求解方法，所以用户根本不用怀疑MATLAB的准确性。2）运算符丰富。由于MATLAB是用C语言编写的，MATLAB提供了和C语言几乎一样多的运算符，灵活使用MATLAB的运算符将使程序变得极为简短。3）MATLAB既具有结构化的控制语句（如for循环，while循环，break语句和if语句），又有面向对象编程的特性。4）程序限制不严格，程序设计自由度大。例如，在MATLAB里，用户无需对矩阵预定义就可使用。5）程序的可移植性很好，基本上不做修改就可以在各种型号的计算机和操作系统上运行。6）MATLAB的图形功能强大。在FORTRAN和C语言里，绘图都很不容易，但在MATLAB里，数据的可视化非常简单。MATLAB还具有较强的编辑图形界面的能力。7）MATLAB的缺点是，它和其他高级程序相比，程序的执行速度较慢。由于MATLAB的程序不用编译等预处理，也不生成可执行文件，程序为解释执行，所以速度较慢。8）功能强大的工具箱是MATLAB的另一特色。MATLAB包含两个部分：核心部分和各种可选的工具箱。核心部分中有数百个核心内部函数。其工具箱又分为两类：功能性工具箱和学科性工具箱。功能性工具箱主要用来扩充其符号计算功能，图示建模仿真功能，文字处理功能以及与硬件实时交互功能。功能性工具箱用于多种学科。而学科性工具箱是专业性比较强的，如control,toolbox,signl proceessing toolbox,commumnication toolbox等。这些工具箱都是由该领域内学术水平很高的专家编写的，所以用户无需编写自己学科范围内的基础程序，而直接进行高，精，尖的研究。9）源程序的开放性。开放性也许是MATLAB最受人们欢迎的特点。除内部函数以外，所有MATLAB的核心文件和工具箱文件都是可读可改的源文件，用户可通过对源文件的修改以及加入自己的文件构成新的工具箱。MATLAB入门教程1MATLAB的基本知识1-1、基本运算与函数 在MATLAB下进行基本数学运算，只需将运算式直接打入提示号（>>）之後，并按入Enter键即可。例如： >> (5*2+1.3-0.8)*10/25 ans =4.2000 MATLAB会将运算结果直接存入一变数ans，代表MATLAB运算後的答案（Answer）并显示其数值於萤幕上。小提示： ">>"是MATLAB的提示符号（Prompt），但在PC中文视窗系统下，由於编码方式不同，此提示符号常会消失不见，但这并不会影响到MATLAB的运算结果。 我们也可将上述运算式的结果设定给另一个变数x： x = (5*2+1.3-0.8)*102/25 x = 42 此时MATLAB会直接显示x的值。由上例可知，MATLAB认识所有一般常用到的加（+）、减（-）、乘（*）、除（/）的数学运算符号，以及幂次运算（）。 小提示： MATLAB将所有变数均存成double的形式，所以不需经过变数宣告（Variable declaration）。MATLAB同时也会自动进行记忆体的使用和回收，而不必像C语言,必须由使用者一一指定.这些功能使的MATLAB易学易用，使用者可专心致力於撰写程式，而不必被软体枝节问题所干扰。 若不想让MATLAB每次都显示运算结果，只需在运算式最後加上分号（；）即可，如下例： y = sin(10)*exp(-0.3*42); 若要显示变数y的值，直接键入y即可： >>y y =-0.0045 在上例中，sin是正弦函数，exp是指数函数，这些都是MATLAB常用到的数学函数。下表即为MATLAB常用的基本数学函数及三角函数： 小整理：MATLAB常用的基本数学函数 abs(x)：纯量的绝对值或向量的长度 angle(z)：复 数z的相角(Phase angle) sqrt(x)：开平方 real(z)：复数z的实部 imag(z)：复数z的虚 部 conj(z)：复数z的共轭复数 round(x)：四舍五入至最近整数 fix(x)：无论正负，舍去小数至最近整数 floor(x)：地板函数，即舍去正小数至最近整数 ceil(x)：天花板函数，即加入正小数至最近整数 rat(x)：将实数x化为分数表示 rats(x)：将实数x化为多项分数展开 sign(x)：符号函数 (Signum function)。 当x<0时，sign(x)=-1； 当x=0时，sign(x)=0; 当x>0时，sign(x)=1。 > 小整理：MATLAB常用的三角函数 sin(x)：正弦函数 cos(x)：馀弦函数 tan(x)：正切函数 asin(x)：反正弦函数 acos(x)：反馀弦函数 atan(x)：反正切函数 atan2(x,y)：四象限的反正切函数 sinh(x)：超越正弦函数 cosh(x)：超越馀弦函数 tanh(x)：超越正切函数 asinh(x)：反超越正弦函数 acosh(x)：反超越馀弦函数 atanh(x)：反超越正切函数 变数也可用来存放向量或矩阵，并进行各种运算，如下例的列向量（Row vector）运算： x = 1 3 5 2; y = 2*x+1 y = 3 7 11 5 小提示：变数命名的规则 1.第一个字母必须是英文字母 2.字母间不可留空格 3.最多只能有19个字母，MATLAB会忽略多馀字母 我们可以随意更改、增加或删除向量的元素： y(3) = 2 % 更改第三个元素 y =3 7 2 5 y(6) = 10 % 加入第六个元素 y = 3 7 2 5 0 10 y(4) = % 删除第四个元素， y = 3 7 2 0 10 在上例中，MATLAB会忽略所有在百分比符号（%）之後的文字，因此百分比之後的文字均可视为程式的注解（Comments）。MATLAB亦可取出向量的一个元素或一部份来做运算： x(2)*3+y(4) % 取出x的第二个元素和y的第四个元素来做运算 ans = 9 y(2:4)-1 % 取出y的第二至第四个元素来做运算 ans = 6 1 -1 在上例中，2:4代表一个由2、3、4组成的向量 若对MATLAB函数用法有疑问，可随时使用help来寻求线上支援（on-line help）：help linspace 小整理：MATLAB的查询命令 help：用来查询已知命令的用法。例如已知inv是用来计算反矩阵，键入help inv即可得知有关inv命令的用法。（键入help help则显示help的用法，请试看看！） lookfor：用来寻找未知的命令。例如要寻找计算反矩阵的命令，可键入 lookfor inverse，MATLAB即会列出所有和关键字inverse相关的指令。找到所需的命令後 ，即可用help进一步找出其用法。（lookfor事实上是对所有在搜寻路径下的M档案进行关键字对第一注解行的比对，详见後叙。） 将列向量转置（Transpose）後，即可得到行向量（Column vector）： z = x' z = 4.0000 5.2000 6.4000 7.6000 8.8000 10.0000 不论是行向量或列向量，我们均可用相同的函数找出其元素个数、最大值、最小值等： length(z) % z的元素个数 ans = 6 max(z) % z的最大值 ans = 10 min(z) % z的最小值 ans = 4 小整理：适用於向量的常用函数有： min(x): 向量x的元素的最小值 max(x): 向量x的元素的最大值 mean(x): 向量x的元素的平均值 median(x): 向量x的元素的中位数 std(x): 向量x的元素的标准差 diff(x): 向量x的相邻元素的差 sort(x): 对向量x的元素进行排序（Sorting） length(x): 向量x的元素个数 norm(x): 向量x的欧氏（Euclidean）长度 sum(x): 向量x的元素总和 prod(x): 向量x的元素总乘积 cumsum(x): 向量x的累计元素总和 cumprod(x): 向量x的累计元素总乘积 dot(x, y): 向量x和y的内 积 cross(x, y): 向量x和y的外积 （大部份的向量函数也可适用於矩阵，详见下述。） 若要输入矩阵，则必须在每一列结尾加上分号（；），如下例： A = 1 2 3 4; 5 6 7 8; 9 10 11 12; A = 1 2 3 4 5 6 7 8 9 10 11 12 同样地，我们可以对矩阵进行各种处理： A(2,3) = 5 % 改变位於第二列，第三行的元素值 A = 1 2 3 4 5 6 5 8 9 10 11 12 B = A(2,1:3) % 取出部份矩阵B B = 5 6 5 A = A B' % 将B转置後以行向量并入A A = 1 2 3 4 5 5 6 5 8 6 9 10 11 12 5 A(:, 2) = % 删除第二行（：代表所有列） A = 1 3 4 5 5 5 8 6 9 11 12 5 A = A; 4 3 2 1 % 加入第四列 A = 1 3 4 5 5 5 8 6 9 11 12 5 4 3 2 1 A(1 4, :) = % 删除第一和第四列（：代表所有行） A = 5 5 8 6 9 11 12 5 这几种矩阵处理的方式可以相互叠代运用，产生各种意想不到的效果，就看各位的巧思和创意。 小提示：在MATLAB的内部资料结构中,每一个矩阵都是一个以行为主（Column-oriented ）的阵列（Array）因此对於矩阵元素的存取，我们可用一维或二维的索引（Index）来定址。举例来说，在上述矩阵A中，位於第二列、第三行的元素可写为A(2,3) （二维索引）或A(6)（一维索引，即将所有直行进行堆叠後的第六个元素）。 此外，若要重新安排矩阵的形状，可用reshape命令： B = reshape(A, 4, 2) % 4是新矩阵的列数，2是新矩阵的行数 B = 5 8 9 12 5 6 11 5 小提示： A(:)就是将矩阵A每一列堆叠起来，成为一个行向量，而这也是MATLAB变数的内部储存方式。以前例而言，reshape(A, 8, 1)和A(:)同样都会产生一个8x1的矩阵。 MATLAB可在同时执行数个命令，只要以逗号或分号将命令隔开： x = sin(pi/3); y = x2; z = y*10,z = 7.5000 若一个数学运算是太长，可用三个句点将其延伸到下一行： z = 10*sin(pi/3)* . sin(pi/3); 若要检视现存於工作空间（Workspace）的变数，可键入who： who Your variables are: testfile x 这些是由使用者定义的变数。若要知道这些变数的详细资料，可键入： whos Name Size Bytes Class A 2x4 64 double array B 4x2 64 double array ans 1x1 8 double array x 1x1 8 double array y 1x1 8 double array z 1x1 8 double array Grand total is 20 elements using 160 bytes 使用clear可以删除工作空间的变数： clear A A ? Undefined function or variable 'A'. 另外MATLAB有些永久常数（Permanent constants），虽然在工作空间中看不 到，但使用者可直接取用，例如： pi ans = 3.1416 下表即为MATLAB常用到的永久常数。 小整理：MATLAB的永久常数 i或j：基本虚数单位eps：系统的浮点（Floating-point）精确度 inf：无限大， 例如1/0 nan或NaN：非数值（Not a number） ，例如0/0 pi：圆周率 p（= 3.） realmax：系统所能表示的最大数值 realmin：系统所能表示的最小数值 nargin: 函数的输入引数个数 nargin: 函数的输出引数个数 1-2、重复命令 最简单的重复命令是for圈（for-loop），其基本形式为： for 变数 = 矩阵； 运算式； end 其中变数的值会被依次设定为矩阵的每一行，来执行介於for和end之间的运算式。因此,若无意外情况，运算式执行的次数会等於矩阵的行数。 举例来说，下列命令会产生一个长度为6的调和数列（Harmonic sequence）： x = zeros(1,6); % x是一个16的零矩阵 for i = 1:6, x(i) = 1/i; end 在上例中，矩阵x最初是一个16的零矩阵，在for圈中，变数i的值依次是1到6，因此矩阵x的第i个元素的值依次被设为1/i。我们可用分数来显示此数列： format rat % 使用分数来表示数值 disp(x) 1 1/2 1/3 1/4 1/5 1/6 for圈可以是多层的，下例产生一个16的Hilbert矩阵h，其中为於第i列、第j行的元素为 h = zeros(6); for i = 1:6, for j = 1:6, h(i,j) = 1/(i+j-1); end end disp(h) 1 1/2 1/3 1/4 1/5 1/6 1/2 1/3 1/4 1/5 1/6 1/7 1/3 1/4 1/5 1/6 1/7 1/8 1/4 1/5 1/6 1/7 1/8 1/9 1/5 1/6 1/7 1/8 1/9 1/10 1/6 1/7 1/8 1/9 1/10 1/11 小提示：预先配置矩阵 在上面的例子，我们使用zeros来预先配置（Allocate）了一个适当大小的矩阵。若不预先配置矩阵，程式仍可执行，但此时MATLAB需要动态地增加（或减小）矩阵的大小，因而降低程式的执行效率。所以在使用一个矩阵时，若能在事前知道其大小，则最好先使用zeros或ones等命令来预先配置所需的记忆体（即矩阵）大小。 在下例中，for圈列出先前产生的Hilbert矩阵的每一行的平方和： for i = h, disp(norm(i)2); % 印出每一行的平方和 end 1299/871 282/551 650/2343 524/2933 559/4431 831/8801 在上例中，每一次i的值就是矩阵h的一行，所以写出来的命令特别简洁。 令一个常用到的重复命令是while圈，其基本形式为： while 条件式； 运算式； end 也就是说，只要条件示成立，运算式就会一再被执行。例如先前产生调和数列的例子，我们可用while圈改写如下： x = zeros(1,6); % x是一个16的零矩阵 i = 1; while i <= 6, x(i) = 1/i; i = i+1; end format short 1-3、逻辑命令 最简单的逻辑命令是if, ., end，其基本形式为： if 条件式； 运算式； end if rand(1,1) > 0.5, disp('Given random number is greater than 0.5.'); end Given random number is greater than 0.5. 1-4、集合多个命令於一个M档案 若要一次执行大量的MATLAB命令，可将这些命令存放於一个副档名为m的档案，并在 MATLAB提示号下键入此档案的主档名即可。此种包含MATLAB命令的档案都以m为副档名，因此通称M档案（M-files）。例如一个名为test.m的M档案，包含一连串的MATLAB命令，那麽只要直接键入test，即可执行其所包含的命令： pwd % 显示现在的目录 ans = D:MATLAB5bin cd c:datamlbook % 进入test.m所在的目录 type test.m % 显示test.m的内容 % This is my first test M-file. % Roger Jang, March 3, 1997 fprintf('Start of test.m!n'); for i = 1:3, fprintf('i = %d -> i3 = %dn', i, i3); end fprintf('End of test.m!n'); test % 执行test.m Start of test.m! i = 1 -> i3 = 1 i = 2 -> i3 = 8 i = 3 -> i3 = 27 End of test.m! 小提示：第一注解行（H1 help line） test.m的前两行是注解，可以使程式易於了解与管理。特别要说明的是，第一注解行通常用来简短说明此M档案的功能，以便lookfor能以关键字比对的方式来找出此M档案。举例来说，test.m的第一注解行包含test这个字，因此如果键入lookfor test，MATLAB即可列出所有在第一注解行包含test的M档案，因而test.m也会被列名在内。 严格来说，M档案可再细分为命令集（Scripts）及函数（Functions）。前述的test.m即为命令集，其效用和将命令逐一输入完全一样，因此若在命令集可以直接使用工作空间的变数，而且在命令集中设定的变数，也都在工作空间中看得到。函数
