信息与计算机文献实习Word格式.docx
《信息与计算机文献实习Word格式.docx》由会员分享,可在线阅读,更多相关《信息与计算机文献实习Word格式.docx(18页珍藏版)》请在冰点文库上搜索。
![信息与计算机文献实习Word格式.docx](https://file1.bingdoc.com/fileroot1/2023-5/6/1e974677-a481-4b7e-866d-ae9a17c7bc83/1e974677-a481-4b7e-866d-ae9a17c7bc831.gif)
2操作步骤--------------------------------------------------------------------------------------------------------3
2.2万方数据库---------------------------------------------------------------------------------------------------4
1内容要求--------------------------------------------------------------------------------------------------------4
2操作步骤--------------------------------------------------------------------------------------------------------4
2.3维普信息资源系统------------------------------------------------------------------------------------------5
1内容要求--------------------------------------------------------------------------------------------------------5
2操作步骤--------------------------------------------------------------------------------------------------------5
2.4超星数字图书馆-------------------------------------------------------------------------------------------7
1内容要求--------------------------------------------------------------------------------------------------------7
2操作步骤----------------------------------------------------------------------------------------------------7
2.5Springer-Verlag全文数据库---------------------------------------------------------------------------8
1内容要求------------------------------------------------------------------------------------------------8
2操作步骤-------------------------------------------------------------------------------------------------8
2.6文献撰写---------------------------------------------------------------------------------------------------9
1内容要求-------------------------------------------------------------------------------------------------9
三、实习心得---------------------------------------------------------------------------------------------------14
一、实习目的
通过本课程的学习,使学生掌握计算机信息检索的基础知识、基本方法,文献信息资源该款、网络学术信息资源类型和检索方法,熟练掌握获得科技文献的能力,具备初步获得外文文献的能力,为后续专业课程和毕业论文服务。
着重考察学生分析信息需求主体和选择计算机检索工具的能力,并对检索结果进行及时评价和反馈的能力。
根据所给的相关课题和内容能正确选择检索刊物和数据库。
能够快速、准确的检索到所需的一次文献。
二、实习内容
2.1中国知网系列数据库
1.内容要求
了解并介绍通过校图书馆访问、检索“中国期刊全文数据库”、“中国优秀硕士学位论文全文数据库”的方法。
掌握采用不同的检索途径如作者、关键系、出版机构(刊名)、中文摘要等进行文献检索。
2.操作步骤
A、打开“青岛农业大学主页”,找到“中国知网系列数据库”,点击进入。
B、点击中国知网左边的“数据库导航”,可分别进入“中国期刊全文数据库”、“中国优秀硕士学位论文全文数据库”的界面。
C、用关键词进行搜索,输入“线性规划单纯形法”,搜索到文章后,点击查看或者下载保存即可。
2.2万方数据资源系统
1.内.容要求
了解并介绍通过校图书馆访问、检索“万方数据资源系统”的方法。
2.操作步骤
A、打开“青岛农业大学主页”,找到“万方数据资源系统”,点击进入。
B、点击万方数据资源系统的访问路径中的任意一个,进入访问网页。
C、用关键字进行搜索,搜索到相关文章点击查看或者下载即可。
2.3维普信息资源系统
1.内.容要求
了解并介绍通过校图书馆访问、检索“维普信息资源系统”的方法。
A、打开“青岛农业大学主页”,找到“维普信息资源系统”,点击进入。
B、在页面点击链接地址:
进入“维普期刊资源整合服务平台”。
C、用关键字进行搜索,搜索到相关文章查看或者下载即可。
2.4超星数字图书馆
了解并介绍通过校图书馆访问、检索“超星数字图书馆”的方法。
A、打开“青岛农业大学主页”,找到“超星数字图书馆”,点击进入。
B、在页面点击镜像网站链接地址。
C、用全文检索进行搜索,搜索到相关文章查看或者下载即可。
2.5Springer-Verlag全文数据库
1.内.容要求
了解并介绍通过校图书馆访问、检索“Springer-Verlag全文数据库”的方法。
掌握采用不同的检索途径如作者、关键系、出版机构(刊名)、外文摘要等进行文献检索。
A、打开“青岛农业大学主页”,找到“Springer-Verlag全文数据库”,点击进入。
输入“LinearProgramming”
2.6文献撰写
通过检索校图书馆国内外重要的数据库和外文文献库,根据你感兴趣的某一个方向,撰写一篇综述性的论文,包括论文题目、摘要、关键词、正文、参考文献,其中题目、摘要和关键词要翻译成英文,并放在中文关键词和正文之间,或者放在正文之后。
关于单纯形法新思路的探讨
信息与计算科学专业寇燕华
指导教师陈秀荣
摘要:
通过对单纯形求解法的实质的分析和认识,提出了基于矩阵初等变换初始可行基的获得方法,进而得到基于单纯形法的求解线性规划模型的直接方法,省略了以往为选择解法而进行的分析判断,使单纯形法的运甩简便明了。
借鉴两阶段法的求解思路,在用单纯形法求解线性规划问题时,对大M法进行改进,提出一种新的算法。
这种改进后的算法可以有效克服原来两种算法的不足,既能降低理解难度,又能提高算法的效率,保证算法的全局收敛性。
关键词:
线性规划初始可行基初等行变换单纯形法大M法两阶段法
Discussiononthenewmethodofsimplexmethod
InformationandComputingScienceYanhuaKou
TutorXiurongChen
Abstract:
Anassociationbetweentheelementarytransformationofmatrixandtheconceptofinitialfeasiblebasisisestablished,andthen,adeterminationwayforinitialfeasiblebasisoflinearprogrammingispresentedAdirectwayofthesimplexmethodforsolvingalinearprogrammingproblemispresented,thisschemeisconcisely,convenienceandmakingthesolvingprocedureclearlyinpractice.Referringtothetwo-phasesolvingmethod,thebig-Mmethodisimprovedbysolvinglinearprogrammingprob-lemsusingthesimplexmethod,andanewalgorithmispresented.Theimprovedalgorithmcaneffectivelyovercomethelackofthetwooriginalalgorithms,andnotonlyreducethedificultyofunderstanding,butalsoimprovetheefficiencyofthealgorithmtoensure
globalconvergenceofthealgorithm.
Keywords:
linearprogramming;
initialfeasiblebasis;
elementaryrowIransformationofmatrix;
simplexmethod;
big-Mmethod;
two-phasemethod
前言
众所周知,由美国数学家于1947年提出的求解线性规划的单纯形法虽然不是多项式算法,却至今仍然是行之有效的而被广泛应用的最基本方法。
通常,求解LP模型时,常用基本单纯形法、大M法、两阶段法等。
根据对模型中是否存在单位基矩阵、存在怎么样的基矩阵等特征的判断来选择方法或判断解的存在与否等情况。
这就是说,在求解线性规划的单纯形法中,初始基矩阵的确定是一个基本问题。
通常使用大M法和两阶段法,通过人工构造,人为地在系数矩阵中形成一个单位矩阵作为初始基矩阵,再进行单纯形法的迭代。
这样往往无意中扰乱了思想主线,增加了计算量,特别对于人工计算显得运算操作繁杂而偏离了主体,在理解的过程中常常带来不便。
单纯形法求解线性规划问题时,需先确定一个初始基本可行解。
在无明显的初始基本可行解时,通常要借助人工变量来构造一个“初始可行基”,即在线性规划标准型(本文提到的线性规划标准型均为目标极小化模型)的约束条件中引入非负人工变量,构造一个单位矩阵,再改变最初的目标函数,用两阶段法或大M法来求解。
两阶段法,在第一阶段引入人工变量、建立目标函数求解原问题的初始基本可行解;
第二阶段从这一初始基本可行解出发,用单纯形法求解原问题。
两阶段法的优点是在任何情况下,第一阶段的目标函数都一样,目的就是迫使人工变量退出基变量。
若做不到这一点(第一阶段结束时人工变量不全为0),则原问题无解(原问题的允许解域是空集)。
否则,就可将目标函数恢复为原问题的目标函数,继续求解。
大M法,在约束中引入人工变量X的同时,在原目标函数中减去惩罚项Mx。
迭代过程中迫使人工变量退出基变量,取得原问题的最优解。
若不能实现(迭代结束时人工变量不全为0),则原问题无解。
大M法的优点是在大M选择得当(足够大)时,可以不分阶段地计算到底。
但选择大M,一般而言,并无公式可搬。
通过比较不难得出大M法的缺点在于大M始终参与计算使迭代过程非常繁琐;
而两阶段法的缺点是两个阶段中的目标函数不一致。
一、关于人工变量的改进方法
1.1方法理论基础
为了思路清晰,对线性规划模型的系数矩阵不作模型标准性特征以外的任何要求。
设线性规划模型为:
(1)
其中C=(c1,c2,...,cn)X=(x1,x2,...,xn)Tb=(b1,b2,...,bm)
在求解
(1)的单纯形法的思想是通过可行域D={X|AX=b,X>
0}中的基本可行解出发,依次转化到另外一个基本可行解而使得某目标函数值不断得到改善。
从而求得目标函数的最优解或判断其无最优解。
每一个基本可行解对应于一个基本可行基,方法进行的出发点就是从一个初始基得到相应的基本可行解,这个基本可行基就是系数矩阵A的一个非奇异子矩阵。
只要单纯形法运算的实质与矩阵的初等变化的关系,可以利用矩阵的初等行变换,在保持资源向量非负的前提下对线性规划的模型的系数增广矩阵化简为包含单位矩阵为其子矩阵的形式,从而得到线性规划问题的初始可行基。
所给出的方法的思想理论基础是:
定理:
若矩阵A经过有限次初等行变换成矩阵B,则A的行向量组与B的行向量组等价,而A得任意K个列向量与B中对应的K歌列向量有相同的线性相关性。
也就是说,矩阵的初等变换不改变矩阵的秩,r(A)=r(B)。
所以,可以通过限定只用初等行变换把任意的m×
n阶矩阵变换为行阶梯型矩阵,其非零行向量的个数就是矩阵的秩r。
若在这种行阶梯型矩阵上再进行初等行变换,就可以把这个矩阵化为行最简形:
非零行向量的第一个非零元素为1,且含这个元素的列的其他元素都为零。
这就是说,可以通过有限次的初等行变换把任意一个m×
n阶矩阵化简为包含有r×
r阶单位矩阵的一个等价矩阵。
而单纯形法程序的出发点是要在系数矩阵中寻求单位矩阵作为初始可行基。
这样,就可以得到一种线性规划初始可行基的确定方法:
对线性规划模型
(1)的系数增广矩阵进行初等行变换,在始终保持资源向量非负的前提下将这个增广矩阵化简为行最简形,便得到了r×
r阶的初始可行基,并且r表示模型
(1)中独立约束的个数。
1.2方法步骤
利用这种初始可行基的方法求解线性规划时,首先,对线性规划模型
(1)的系数增广矩阵进行上述的初等行变换而得到r×
r阶的初始可行基,接着,将所得初始可行基安排入单纯形表,然后,进行单纯形表的表上作业程序。
这样做的优点不仅在于可以给出初始可行基,而且可以方便的发现不独立的约束,并将其提前剔除,以减少单纯形法的计算量。
具体步骤为:
步骤1:
对增广矩阵B实行一系列的初等行变换,并始终保持可行性(即:
b列非负),直到B中含有单位矩阵;
这里需要注意的是当变换到可以使某一行元素全部为0时,说明约束方程组不独立,B可以降维为(m一1)x(n+1),那么,所得到的单位矩阵也就是(m一1)x(n+1)阶的.并非一定要得到B的m×
m阶的单位矩阵作为基。
步骤2:
将步骤1的结果安排到一个单纯形表中,并以B中的单位矩阵的列所相应的变量为基变量而得到初始单纯形表。
步攘3:
在步骤2的所得的单纯形表上按照通常的单纯形表上作业法进行求解。
1.3几点强调
需要说明的是,在步骤1中完全可以不用第一类初等行变换(交换任两行的位置),而只用第二、三类初等行变换就可以实现。
该方法的优势在于思想清晰,方法简明.计算量减小。
有了初始可行基。
就可从这个可行基相应的基本可行解出发进行换基迭代,从而,求得目标函数的最优解或判断其无最优解。
1.4结束语
给出方法的优势在于思路清晰,方法简明.在运用单纯形法时不需要判断选择两阶段法或大M法等,只要借助于线性代数的初等行变换及在以单位阵为初始基的单纯形法就可以顺利地求解任何线性规划模型。
对于线性规划的解法研究探讨和理解单纯形法有一定参考意义。
二、关于大M法的改进
本文主要借鉴两阶段法的求解思路,用两阶段法来改良大M法,提出一种新的算法。
这种改进后的算法可以有效克服原来两种算法的不足,既能降低理解难度,又可化繁为简,提高算法的效率,保证算法的全局收敛性。
2.1改进的思路
无论大M法还是两阶段法,目标都是找到单纯形表迭代的基础,用人工变量构造出“初始可行基”。
表面上看二者区别在于大M法由此“初始可行基”出发,方向直指原问题的最优解;
两阶段法由此“初始可行基”出发先指向辅助问题的最优解即原问题的某个基本可行解,再以此为起点求原问题最优解。
而事实上大M法在求解过程中同样必然要途经原问题的某个基本可行解。
将大M法迭代的后半程,即取得原问题的基本可行解之后的过程用两阶段法第二阶段来代替,就得到改进的新算法。
2.3算法步骤总结
步骤1依照大M法将线性规划模型化为典型式,并建立初始单纯形表。
步骤2进行迭代,直到最后一个人工变量确定出基。
步骤3删除人工变量所在列,继续迭代至最终单纯形表。
2.3结语
本方法借鉴两阶段法思路对大M法进行改进,得到改进大M法。
这种算法相比大M法和两阶段法更容易理解和掌握,有效提高了算法的效率,为解决线性规划问题提供了有力保障。
但是对于允许解域是空集的线性规划问题,该算法基本上不能起到简化计算的作用。
参考文献
[1]胡运权,郭耀煌.运筹学教程[M].2版.北京:
清华大学出版社,2003:
19—36.
[2]王岚,李彦翔,靳松《线性规划问题新解——改进大M法》后勤工程学院学报
[3]申卯兴,许进《求解线性规划的单纯形法的直接方法》华中科技大学控制科学与工程系,武汉430074
四、实习心得
通过本课程的学习,掌握了计算机信息检索的基础知识、基本方法,文献信息资源该款、网络学术信息资源类型和检索方法,熟练掌握了获得科技文献的能力,具备初步获得外文文献的能力,为后续专业课程和毕业论文打好了一定的基础。