线性规划模型及matlab程序求解.docx
- 文档编号:17553870
- 上传时间:2023-07-26
- 格式:DOCX
- 页数:34
- 大小:33.18KB
线性规划模型及matlab程序求解.docx
《线性规划模型及matlab程序求解.docx》由会员分享,可在线阅读,更多相关《线性规划模型及matlab程序求解.docx(34页珍藏版)》请在冰点文库上搜索。
线性规划模型及matlab程序求解
§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为该厂所获总润。
maxf=70x1+120x2
s.t 9x1+4x2≤3600
4x1+5x2≤2000
3x1+10x2≤3000
x1,x2≥0
归结出规划问题:
目标函数和约束条件都是变量x的线性函数。
形如:
(1) minfTX
s.t AX≤b
AeqX=beq
lb≤X≤ub
其中X为n维未知向量,fT=[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:
求解线性规划问题:
maxf=2x1+5x2
s.t x1≤4
x2≤3
x1+x2≤8
x1,x2≥0
先将目标函数转化成最小值问题:
min(-f)=-2x1-5x2
程序:
f=[-2-5];
A=[10;01;11];
b=[4;3;8];
[x,fval]=linprog(f,A,b)
f=fval*(-1)
结果:
x=2
3
fval=-19.0000
maxf= 19
例2:
minf=5x1-x2+2x3+3x4-8x5
s.t –2x1+x2-x3+x4-3x5≤6
2x1+x2-x3+4x4+x5≤7
0≤xj≤15 j=1,2,3,4,5
程序:
f=[5-123-8];
A=[-21-11-3;21-141];
b=[6;7];
lb=[00000];
ub=[1515151515];
[x,fval]=linprog(f,A,b,[],[],lb,ub)
结果:
x=
0.0000
0.0000
8.0000
0.0000
15.0000
minf=
-104
例3:
求解线性规划问题:
minf=5x1+x2+2x3+3x4+x5
s.t –2x1+x2-x3+x4-3x5≤1
2x1+3x2-x3+2x4+x5≤-2
0≤xj≤1 j=1,2,3,4,5
程序:
f=[51231];
A=[-21-11-3;23-121];
b=[1;-2];
lb=[00000];
ub=[11111];
[x,fval,exitflag,output,lambda]=linprog(f,A,b,[],[],lb,ub) 运行结果:
Exiting:
Oneormoreoftheresiduals,dualitygap,ortotalrelativeerror
hasgrown100000timesgreaterthanitsminimumvaluesofar:
theprimalappearstobeinfeasible(andthedualunbounded).
(Thedualresidual x=0.0000 0.0000 1.1987 0.0000 0.0000 fval= 2.3975 exitflag= -1 output= iterations: 7 cgiterations: 0 algorithm: 'lipsol' lambda= ineqlin: [2x1double] eqlin: [0x1double] upper: [5x1double] lower: [5x1double] 显示的信息表明该问题无可行解。 所给出的是对约束破坏最小的解。 例4: 求解实例1的生产计划问题 建立数学模型: 设x1、x2分别为生产甲、乙产品的件数。 f为该厂所获总润。 maxf=70x1+120x2 s.t 9x1+4x2≤3600 4x1+5x2≤2000 3x1+10x2≤3000 x1,x2≥0 将其转换为标准形式: minf=-70x1-120x2 s.t 9x1+4x2≤3600 4x1+5x2≤2000 3x1+10x2≤3000 x1,x2≥0 程序: f=[-70-120]; A=[94;45;310]; b=[3600;2000;3000]; lb=[00]; ub=[]; [x,fval,exitflag]=linprog(f,A,b,[],[],lb,ub) maxf=-fval 结果: x= 200.0000 240.0000 fval= -4.2800e+004 exitflag= 1 maxf= 4.2800e+004 例5: 求解实例2 建立数学模型: maxf=0.15x1+0.1x2+0.08x3+0.12x4 s.t x1-x2-x3-x4≤0 x2+x3-x4≥0 x1+x2+x3+x4=1 xj≥0 j=1,2,3,4 将其转换为标准形式: minz=-0.15x1-0.1x2-0.08x3-0.12x4 s.t x1-x2-x3-x4≤0 -x2-x3+x4≤0 x1+x2+x3+x4=1 xj≥0 j=1,2,3,4 程序: f=[-0.15;-0.1;-0.08;-0.12]; A= [1-1-1-1 0-1-11]; b=[0;0]; Aeq=[1111]; 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.2500 fval= -0.1300 exitflag= 1 f= 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=32134567 23798512 43235465 98347135 b=1 2 3 4 解为: x=A\b;设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,signlproceessingtoolbox,commumnicationtoolbox等。 这些工具箱都是由该领域内学术水平很高的专家编写的,所以用户无需编写自己学科范围内的基础程序,而直接进行高,精,尖的研究。 9)源程序的开放性。 开放性也许是MATLAB最受人们欢迎的特点。 除内部函数以外,所有MATLAB的核心文件和工具箱文件都是可读可改的源文件,用户可通过对源文件的修改以及加入自己的文件构成新的工具箱。 MATLAB入门教程 1.MATLAB的基本知识 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)*10^2/25 x=42 此时MATLAB会直接显示x的值。 由上例可知,MATLAB认识所有一般常用到的加(+)、减(-)、乘(*)、除(/)的数学运算符号,以及幂次运算(^)。 小提示: MATLAB将所有变数均存成double的形式,所以不需经过变数宣告(Variabledeclaration)。 MATLAB同时也会自动进行记忆体的使用和回收,而不必像C语言,必须由使用者一一指定.这些功能使的MATLAB易学易用,使用者可专心致力於撰写程式,而不必被软体枝节问题所干扰。 若不想让MATLAB每次都显示运算结果,只需在运算式最後加上分号(;)即可,如下例: y=sin(10)*exp(-0.3*4^2); 若要显示变数y的值,直接键入y即可: >>y y=-0.0045 在上例中,sin是正弦函数,exp是指数函数,这些都是MATLAB常用到的数学函数。 下表即为MATLAB常用的基本数学函数及三角函数: 小整理: MATLAB常用的基本数学函数 abs(x): 纯量的绝对值或向量的长度 angle(z): 复数z的相角(Phaseangle) 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): 符号函数(Signumfunction)。 当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): 反超越正切函数 变数也可用来存放向量或矩阵,并进行各种运算,如下例的列向量(Rowvector)运算: x=[1352]; y=2*x+1 y=37115 小提示: 变数命名的规则 1.第一个字母必须是英文字母2.字母间不可留空格3.最多只能有19个字母,MATLAB会忽略多馀字母 我们可以随意更改、增加或删除向量的元素: y(3)=2%更改第三个元素 y=3725 y(6)=10%加入第六个元素 y=3725010 y(4)=[]%删除第四个元素, y=372010 在上例中,MATLAB会忽略所有在百分比符号(%)之後的文字,因此百分比之後的文字均可视为程式的注解(Comments)。 MATLAB亦可取出向量的一个元素或一部份来做运算: x (2)*3+y(4)%取出x的第二个元素和y的第四个元素来做运算 ans=9 y(2: 4)-1%取出y的第二至第四个元素来做运算 ans=61-1 在上例中,2: 4代表一个由2、3、4组成的向量 若对MATLAB函数用法有疑问,可随时使用help来寻求线上支援(on-linehelp): helplinspace 小整理: MATLAB的查询命令 help: 用来查询已知命令的用法。 例如已知inv是用来计算反矩阵,键入helpinv即可得知有关inv命令的用法。 (键入helphelp则显示help的用法,请试看看! )lookfor: 用来寻找未知的命令。 例如要寻找计算反矩阵的命令,可键入lookforinverse,MATLAB即会列出所有和关键字inverse相关的指令。 找到所需的命令後,即可用help进一步找出其用法。 (lookfor事实上是对所有在搜寻路径下的M档案进行关键字对第一注解行的比对,详见後叙。 ) 将列向量转置(Transpose)後,即可得到行向量(Columnvector): 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的元素总
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 模型 matlab 程序 求解