




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
线性规划数学建模实验实验目的实验内容2、掌握用数学软件包求解线性规划问题。1、了解线性规划的基本内容。*2线性规划的基本算法。3用数学软件包求解线性规划问题。1两个引例。问题一:
任务分配问题:某车间有甲、乙两台机床,可用于加工三种工件。假定这两台车床的可用台时数分别为800和900,三种工件的数量分别为400、600和500,且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务,才能既满足加工工件的要求,又使加工费用最低?两个引例解
设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3,在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型:
解答问题二:
某厂每日8小时的产量不低于1800件。为了进行质量控制,计划聘请两种不同水平的检验员。一级检验员的标准为:速度25件/小时,正确率98%,计时工资4元/小时;二级检验员的标准为:速度15件/小时,正确率95%,计时工资3元/小时。检验员每错检一次,工厂要损失2元。为使总检验费用最省,该工厂应聘一级、二级检验员各几名?解设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为:因检验员错检而造成的损失为:故目标函数为:约束条件为:线性规划模型:解答返回1.线性规划的一般形式:用单纯法求解时,常将标准形式化为:2.线性规划的基本算法——单纯形法线性规划的基本算法——单纯形法引入松弛变量x3,x4,x5,将不等式化为等式,即单纯形标准形:显然A的秩ran(A)=3,任取3个线性无关的列向量,如P3P4P5称为一组基,记为B.其余列向量称为非基,记为N.于是f=cBxB+cNxN,Ax=BxB+NxN=b,
则xB=B-1b-B-1NxN,f=cBB-1b+(cN–cBB-1N)xN
若可行基进一步满足:
cN–cBB-1N≥0,即:cBB-1N-cN≤0则对一切可行解x,必有f(x)≥cBB-1b,此时称基可行解x=(B-1b,0)T为最优解.3.最优解的存在性定理将A的列向量重排次序成A=(B,N),相应x=(xB,xN)T,c=(cB,cN)基对应的变量xB称为基变量,非基对应的变量xN称为非基变量.定理1如果线性规划(1)有可行解,那么一定有基可行解.定理2如果线性规划(1)有最优解,那么一定存在一个基可行解是最优解.4.基可行解是最优解的判定准则因为f=cBB-1b+(cN–cBB-1N)xN,即f-0•xB+(cBB-1N-cN)xN=cBB-1b5.基可行解的改进改进方法:返回用MATLAB优化工具箱解线性规划minz=cX
1、模型:命令:x=linprog(c,A,b)
2、模型:minz=cX
命令:x=linprog(c,A,b,Aeq,beq)注意:若没有不等式:存在,则令A=[],b=[].3、模型:minz=cX
VLB≤X≤VUB命令:[1]x=linprog(c,A,b,Aeq,beq,VLB,VUB)
[2]x=linprog(c,A,b,Aeq,beq,VLB,VUB,X0)
注意:[1]若没有等式约束:,则令Aeq=[],beq=[].[2]其中X0表示初始点4、命令:[x,fval]=linprog(…)返回最优解x及x处的目标函数值fval.解编写M文件xxgh1.m如下:c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];Aeq=[];beq=[];vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)
D:/MATLAB6p1/bin/win32/matlab.exeMatlab(xxgh1)解:编写M文件xxgh2.m如下:c=[634];A=[010];b=[50];Aeq=[111];beq=[120];vlb=[30,0,20];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh2)S.t.改写为:例3问题一的解答编写M文件xxgh3.m如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];vlb=zeros(6,1);vub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh3)结果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3,可在满足条件的情况下使总加工费最小为13800。例2问题二的解答
问题改写为:编写M文件xxgh4.m如下:c=[40;36];A=[-5-3];b=[-45];Aeq=[];beq=[];vlb=zeros(2,1);vub=[9;15];%调用linprog函数:[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh4)结果为:x=9.00000.0000fval=360即只需聘用9个一级检验员。
注:本问题应还有一个约束条件:x1、x2取整数。故它是一个整数线性规划问题。这里把它当成一个线性规划来解,求得其最优解刚好是整数:x1=9,x2=0,故它就是该整数规划的最优解。若用线性规划解法求得的最优解不是整数,将其取整后不一定是相应整数规划的最优解,这样的整数规划应用专门的方法求解。返回用Mathematica软件包解线性规划问题LinearProgramming[c,m,b]findsthevectorxwhichminimizesthequantityc.x
subjecttotheconstraintsm.x≥bandx≥0.例:In[1]:=LinearProgramming[{2,-3},{{-1,-1},{1,-1},{1,0}},{-10,2,1}]Out[1]={6,4}ConstrainedMin[f,{inequalities},{x,y,…}]findstheglobalminimumoffinthedomainspecifiedbytheinequalities.Thevariablesx,y,…areallassumedtobenon-negative.例In[2]:=ConstrainedMin[2x-3y,{x+y<10,x-y>2,x>1},{x,y}]Out[2]={0,{x->6,y->4}}ConstrainedMax[f,{inequalities},{x,y,…}]findstheglobalmaximumoffinthedomainspecifiedbytheinequalities.Thevariablesx,y,…areallassumedtobenon-negative.例In[2]:=ConstrainedMax[x+3y+7z,{x-3y<7,2x+3z>=5,x+y+z<=10},{x,y,z}]Out[2]={70,{x->0,y->0,z->10}实验作业
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 【正版授权】 ISO/IEC 14888-4:2024 EN Information security - Digital signatures with appendix - Part 4: Stateful hash-based mechanisms
- 2025年充电桩充电设备生产许可证申请与审批合同
- 2025年度新能源汽车充电桩建设与运营服务合同-@-3
- 2024 年度中国汽车行业争议解决报告
- 2025年度小时工维修养护服务合同范本
- 2025年度知识产权保险产品代理与服务合同
- 2025年心电遥测监护仪项目合作计划书
- 英语-黑龙江省大庆市实验中学2024-2025学年高一上学期阶段考试
- 2025年沥青试验仪器项目合作计划书
- 2025年度走读生户外活动安全责任承诺协议范本
- 预防接种工作规范(2023年版)解读课件
- (2024年1月)广西各市房屋工程造价指标
- 渝水区良山分散式风电项目环评报告
- 2023夏季广东广州期货交易所招聘历年高频难易度、易错点模拟试题(共500题)附带答案详解
- 《人事管理》课件
- 【非正式组织对企业人力资源管理的影响8700字(论文)】
- 铅锑合金生产工艺技术规范
- 2024拳击比赛计划书
- PPAP-测量系统分析研究模板
- 管道直饮水系统技术和方案
- 培养幼儿的时间观念
评论
0/150
提交评论