运筹学实验任务书.docx
《运筹学实验任务书.docx》由会员分享，可在线阅读，更多相关《运筹学实验任务书.docx（21页珍藏版）》请在冰点文库上搜索。
运筹学实验任务书
《运筹学实验》1——线性规划建模与求解（周二、三）
一.实验目的及要求
1.掌握线性规划建模的方法与过程，体会线性规划建模的核心思想。
2.掌握线性规划问题的求解方法。
3.掌握用Matlab或LINDO求解线性规划问题的基本方法和步骤，学会分析Matlab或LINDO的计算结果。
4.锻炼应用所学知识解决综合性问题的能力
二.实验设备与器件
1.安装win98系统以上的计算机
2.malab6.0或LINDO6.01或更高版本的软件
三.实验原理
线性规划常见可以解决资源分配问题，成本效益平衡问题。
在求解线性规划时，常用的方法有图解法和单纯形法。
单纯形法基本思路是：
先找出一个基本可行解,判断其是否为最优解,如果不是最优解，则转换到相邻的基本可行解,并使目标函数值不断增大,直到找出最优解或判断有无界解、无解为止。
本实验是合理利用线材问题属于解决资源分配问题
使用LINDO6.01进行操作：
LINDO（LinearInteractiveandDiscreteOptimizer）是一种专门用于求解数学规划问题的软件包。
由于LINDO执行速度很快、易于方便输入、求解和分析数学规划问题，因此在数学、科研和工业界得到广泛应用。
LINDO主要用于解线性规划、非线性规划、二次规划和整数规划等问题。
也可以用于一些非线性和线性方程组的求解以及代数方程求根等。
LINDO中包含了一种建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题时调用。
四.实验内容
实验准备：
1自学运筹学实验指导书第一、二两章，复习巩固Matlab基础知识；
2复习课本《运筹学基础及应用》第一章，熟悉线性规划模型建模的过程，模型标准化及模型求解的思路和过程，最优解判定的准则和方法。
实验内容：
1自学运筹学实验指导书第三章，掌握线性规划模型求解的软件技术；
2利用软件实现运筹学实验指导书第三章所有例题的求解计算；
3参照例题，总结提炼线性规划建模与求解过程的主要难点问题、模型求解的程序命令及其适用条件等，形成便于自己理解的规范的操作指南；
4利用前面总结的方法，完成如下习题的求解：
●1.7化标准型并用程序命令求解
●1.12建立模型，化标准型并用程序命令求解
5完成如下实际问题的建模与求解。
线材切割问题
在很多工程领域，都有线材切割问题。
这一问题可表述为:
设能购买到的不同长度的原线材有m种，长度分别为L1,...,Lm，这些原线材只是长度不同，其它都相同。
某工程中所要切割出的线材长度分别为li,i=1,2,...,n（这里li<所有Li），对应数量分别为Ni,i=1,2,...,n。
设计优化计算方案，求出分别需要购买多少根不同长度的原线材,并能给出切割方案及线材利用率。
具体事例
现假设某装修工程中需要对铝合金线材进行切割，工程能购买到的同一规格的铝合金线材有二种长度，一种长度是8米，另一种是12米。
现在假设要切割长度和数量如下所示的铝合金线材：
表5.1
编号
长度（单位:
米）
数量（单位:
根）
1
6.20
90
2
3.60
120
3
2.80
136
4
1.85
310
5
0.75
215
6
0.55
320
应用所设计的计算方案，请问至少需要购买多少根8米和12米的线材，使浪费的线材比较少，并给出切割方案和计算线材利用率。
实验报告要求：
1用自己的语言描述实验的目的，并设计实验过程，给出具体实施步骤；
2给出课本P47，习题1.7,1.12的求解的过程和结果，并给出点评分析：
3出实际问题的建模过程，模型规范表述、模型求解过程及结果。
4给出线性规划建模与求解过程的主要难点问题，总结模型求解的程序命令及其适用条件等，给出规范的操作指南，总结实验的得失和实验心得体会；
5给出进一步完善实验的建议和方法，或进一步探索性研究课题。
其中1-3为所有人必做作业；4,5为选作题，供追求成绩优、良的人选作。
前三项完成好，后两项至少完成一个方具备考虑给优秀成绩的资格。
《运筹学实验》2——线性规划的对偶原理及灵敏性分析（周三）
一.实验目的及要求
1.掌握线性规划的对偶理论，能够根据线性规划原问题给出其对偶问题，熟悉对偶问题的解与原问题的解之间的关系方法，并能将该结论用于线性规划求解；掌握对偶单纯形方法；
2理解线性规划灵敏度分析的意义，掌握线性规划灵敏性分析的常用方法，理解影子价格，体会灵敏度分析结果对决策的影响。
3掌握用Matlab或LINDO进行灵敏性分析方法和步骤，读懂并学会分析Matlab或LINDO的计算结果。
4.锻炼应用所学知识解决综合性问题的能力
二.实验设备与器件
1.安装win98系统以上的计算机
2.malab6.0或LINDO6.01或更高版本的软件
三.实验原理
①线性规划的对偶理论是线性规划理论的重要组成部分，是运筹学知识体系中具有鲜明特色的一个知识板块。
理解线性规划对偶问题的概念，掌握线性规划原问题与对偶问题之间的关系可以进一步加深对线性规划问题及其求解方法的理解。
同时，对偶问题的提出和研究，还可以进一步丰富我们科学研究的思路和方法,为今后的学习和科研工作积累经验。
有时候，转换、丰富问题研究的视角，可以有意外的惊喜发现。
②线性规划的灵敏度分析是线性规划理论的一个不可或缺的重点组成部分。
正是大量的假设情况分析使得线性规划的建模和求解能够更好的贴合实际需求，同时也为管理者的决策提供更充分的支持。
体会灵敏度分析的问题提出的背景，掌握灵敏度分析的主要内容和常见方法，理解灵敏度分析的核心思想，有助于我们更好地解决实际问题，为决策提供更全面的数据支持。
3灵敏度分析，或者称假设情况分析、what……if分析等，体现着一种负责务实的态度，一种积极主动提供更周到服务的理念。
灵敏度分析的内容很丰富，目前数学软件大都提供了一些与灵敏度分析有关的具体的技术和方法，但需要读者自己熟练应用，合理组织，形成一个系统化的分析总结方案。
这个过程包含模型调整和优化、不同情况下的反复求解，求解结果的系统分析和深刻独到的问题发现等。
它既是对前面掌握技术方法的一种演练提升，同时也锻炼我们的思考能力和分析综合能力，使我们再面对复杂的实际问题时，能够抓住关键问题以及问题的关键部分，找到适合北京背景环境的有效的满意“最优解”。
四.实验内容
实验准备：
1复习运筹学实验指导书第二章，课本《运筹学基础及应用》第一章，复习巩固线性规划建模、求解的方法和步骤；
2复习课本《运筹学基础及应用》第二章，熟悉线性规划对偶理论，对偶单纯形方法和灵敏度分析的课题及主要内容。
实验内容：
1复习运筹学实验指导书第三章，掌握线性规划模型求解的软件技术；
2总结写线性规划对偶问题的准则，给出对偶理论的几个主要结论，结合实例验证结论的正确性；总结线性规划灵敏度分析的内容及主要结论，
具体验证方法为：
选择实验一中已经求解过得几个实例，首先写出他们的对偶问题并分别求解，然后验证对偶问题的解与原问题解之间的关系：
●P77，2.4利用程序命令求解原问题，验证题目所给原问题最优解的正确性；写出其对偶问题，并用程序命令求解；验证原问题与其对偶问题解之间的关系的几个重要结论；
●P77，2.7写出其对偶问题，并分别用程序命令求解原问题及其对偶问题解；对比分析计算结果，验证解之间的关系的几个重要结论；
3结合实例验证灵敏性分析结论的有效性及其局限。
完成如下习题的求解：
●P77，2.8不利用定理结论，编成用试探法确定最优解保持不变的参数允许变动范围。
●P77，2.9不利用定理结论，编成用试探法确定最优解保持不变的参数允许变动范围。
注：
这部分内容有助于帮助学生了解实验法的优势和局限，理解定理结论的重要性，加强对理论学习重要性的认知。
4完成如下实际问题的建模与求解（探究性实验，可选部分）。
线材切割问题的进一步分析
假设生成产品规格发生改变，请根据情况进行分析。
1第一种长为6.20的90根变成了150根；
2第一种产品长度要求变为6.30，100根；
3一种产品长度要求变为3.1，180根。
实验报告要求：
1用自己的语言描述实验的目的、过程和具体步骤；
2给出习题的求解的过程和结果，并给出点评分析：
3给出条件改变后实际问题的模型求解过程及结果，并进行分析。
4总结对偶理论的几个主要结论，讨论对偶问题的解与原问题解之间的关系。
5总结灵敏性分析实验的得失，理解实验计算的优势及局限，理解理论猜想结论及其证明等理论性成果的意义，写出心得体会；
6给出进一步完善实验的建议和方法，或给出一些可进一步讨论研究的探索性研究课题。
其中1-3为必做作业，4-6为选作题，供追求成绩优、良的人选作。
前三项完成好，后两项至少完成一个方具备考虑给优秀成绩的资格。
《运筹学实验》3——运输问题（周四）
一.实验目的及要求
1.了解运输问题，特别是线性运输问题的提出背景、运输问题理论和方法的特点，掌握运输问题求解的表上作业法，最优性判定的闭回路法和位势法，理解运输问题求解与转化的机理，了解几种常见的变形。
2掌握用Matlab或LINDO求解运输问题的方法和步骤，读懂并学会分析Matlab或LINDO的计算结果。
4.锻炼应用所学知识建立实际问题数学模型，并借助计算机和软件工具解决综合性实际问题的能力
二.实验设备与器件
1.安装win98系统以上的计算机
2.malab6.0或LINDO6.01或更高版本的软件
三.实验原理
1运输问题是一类常见的，具有明确的实际背景和鲜明特点的特殊的线性规划问题。
这类问题的研究具有重要的理论和应用价值。
作为特殊的线性规划，当然可以用经典的单纯形方法求解。
但由于问题的特殊性，运输问题可以使用表上作业法等更简单的方法来求解。
常见的数学平台软件，大都只是将它作为特殊的线性规划进行处理，并没有给出专门的求解运输问题的模块。
近几年来，随着物流与网络分析技术的发展，专门求解大规模优化问题的软件渐渐多了起来，感兴趣的同学可以有意识地收集一下相关的资料。
2运输问题实验主要是体会运输问题的特点，并尝试较大规模问题的求解。
四.实验内容
实验准备：
1复习运筹学实验指导书第三章，课本《运筹学基础及应用》第二、三章，复习巩固线性规划建模、求解的方法和步骤；
2复习课本《运筹学基础及应用》第四章，熟悉运输问题数学模型，产销平衡运输问题求解的表上作业法、伏格尔法以及闭回路法等运输问题最优解判定的方法，产销不平衡等其他类型运输问题的转化方法。
实验内容：
1自学运筹学实验指导书第四章，掌握运输问题模型求解的技术方法；
2运行调试运筹学实验指导书第四章例题；至少完成一个，三个以上为优。
3完成课本如下习题的求解：
●3.1
●3.2，以表格3-35为例
4分析课本第104页，案例3——光明市的菜篮子工程。
实验报告要求：
1用自己的语言描述实验的目的、过程和具体步骤；
2给出习题的求解的过程和结果，并给出点评分析：
3课本第104页，案例3——光明市的菜篮子工程。
4总结实验的得失和实验心得体会，给出进一步完善实验的建议和方法，新的案例或进一步探索性研究课题。
其中1-2为必做作业，3-4为选作题，供追求成绩优、良的人选作。
前三项完成好，后两项至少完成一个方具备考虑给优秀成绩的资格。
《运筹学实验》4——整数规划之分支定界、割平面（周五）
一.实验目的及要求
1.理解整数线性规划和普通线性规划的区别，体会整数规划求解的分支定界法、割平面法与隐枚举方法的思想，掌握整数规划求解的方法与步骤。
2掌握用Matlab或LINDO求解整数规划的方法和步骤，学会利用Matlab或LINDO求解具体整数规划问题。
3.锻炼应用所学知识解决综合性问题的能力
二.实验设备与器件
1.安装win98系统以上的计算机
2.malab6.0或LINDO6.01或更高版本的软件
三.实验原理
整数线性规划是一类特殊的线性规划，在实际生活中大量存在。
整数规划问题的求解，通常是这样的一个过程：
首先，去掉整数约束，借助普通线性规划求解的单纯形方法得到问题的一个最优解，然后进行整数约束判定，如果得到的是整数最优解，结束；否则，利用分支或者割平面方法去掉不满足整数约束的最优解，重新求解，知道得到问题的整数最优解或判定问题无解为止。
本实验的主要目的是帮助学生加深对这一求解过程的认识和理解，掌握一种人机结合的半自动化的问题求解模式，并尝试将这个过程尽量多的自动化。
四.实验内容
实验准备：
1复习运筹学实验指导书第二章，课本《运筹学基础及应用》第四章，复习巩固整数线性规划建模、求解的方法和步骤；
2复习课本《运筹学基础及应用》第四章，熟悉整数规划模型的特点及其求解的分支定界法、割平面法。
3学习运筹学实验指导书第五章
实验内容：
1运行调试《运筹学实验指导书》第五章例题程序。
至少完成一个，三个以上为优。
2P126，4.7利用程序命令求解原问题，验证解是否满足整数约束；然后分支，求解，验证；循环迭代，直到找到整数最优解。
3P126，4.8利用程序命令求解原问题，验证解是否满足整数约束；然后构造辅助约束，割去不满足整数约束的最优解，继续求解；如此反复，直到找到整数最优解。
4选择课本案例4.1,4.2,4.3中的一个，建立模型并进行求解分析（探究性实验，可选部分）。
实验报告要求：
1用自己的语言描述实验的目的、过程和具体步骤；
2给出习题的求解的过程和结果，并给出点评分析：
3给出案例的数学模型，求解过程及结果，并进行必要的分析。
4给出进一步完善实验的建议和方法，或给出一些可进一步讨论研究的探索性研究课题。
其中1-2为必做作业，3-4为选作题，供追求成绩优、良的人选作。
前三项完成好，后两项至少完成一个方具备考虑给优秀成绩的资格。
《运筹学实验》5——整数规划之指派问题（周二）
一.实验目的及要求
1.理解指派问题这一特殊整数线性规划问题的特点，体会指派问题求解的匈牙利方法；
2掌握用Matlab或LINDO求解指派问题的方法和步骤，学会利用Matlab或LINDO求解具体指派问题及其变形问题。
3.锻炼应用所学知识解决综合性问题的能力
二.实验设备与器件
1.安装win98系统以上的计算机
2.malab6.0或LINDO6.01或更高版本的软件
三.实验原理
指派问题是一类常见的特殊0-1整数线性规划，也可看作是特殊的运输问题。
指数问题的求解也是一个不断试探、判断、再试探再判断的过程。
如果能够很好的理解这中问题求解模式，并根据实际问题的需要加以变通，可以有效提升学生解决实际问题的能力。
四.实验内容
实验准备：
1复习运筹学实验指导书第二章，课本《运筹学基础及应用》第四章，复习巩固指派问题建模、求解的方法和步骤；
2复习课本《运筹学基础及应用》第四章，熟悉整指派问题的特点及其求解的匈牙利方法。
3学习运筹学实验指导书第六章
实验内容：
1运行调试《运筹学实验指导书》第六章例题程序。
至少完成一个，三个以上为优。
2P125，4.3
3P125，4.4
4P125，4.5（探究性实验，可选部分）。
实验报告要求：
1用自己的语言描述实验的目的、过程和具体步骤；
2给出习题的求解的过程和结果，并给出点评分析：
3给出进一步完善实验的建议和方法，或给出一些可进一步讨论研究的探索性研究课题。
其中1-2为必做作业，3为选作题，供追求成绩优、良的人选作。
前三项完成好，后两项至少完成一个方具备考虑给优秀成绩的资格。
《运筹学实验》6——网络最小支撑树与最短路（周四）
一.实验目的及要求
1.理解图与网络分析的研究背景，理解网络图的最小支撑树、两点之间最短路等基础概念，并加强对网络最小支撑树、最短路等问题求解方法的基本思想，求解计算过程的具体步骤等内容的理解和掌握；
2掌握用Matlab或LINDO求解最小支撑树、两点之间最短路的方法和步骤，学会利用Matlab或LINDO求解最小支撑树、两点之间最短路及其变形问题。
3.锻炼应用所学知识解决综合性问题的能力
二.实验设备与器件
1.安装win98系统以上的计算机
2.malab6.0或LINDO6.01或更高版本的软件
三.实验原理
图与网络分析是运筹学一个重要分支。
网络图具有直观形象、便于分析理解的特点。
实际生活中的很多问题都可以转化为一个网络图来进行分析求解，网络图具有鲜明的实际背景和广泛的应用。
因此，网络图的建模和分析是极具特色的一个知识板块。
最小支撑树和最短路问题是网络图分析中的两类典型问题，受到研究人员的广泛关注，给出很多求解分析算法。
我们教材中介绍了典型的破边法、加边法，以及标号算法。
这些方法便于人们操作，可以方面的求解小规模问题。
但它们不太适合计算机实现，也难以用于中大规模问题求解。
计算机进行图与网络分析的时候，引入了一些新的概念和方法，这些方法与课本介绍的方法相比有不同的特色。
两者对比分析，可以进一步加深我们对问题及其求解过程的认识，同时也可引发一些有意义的思考。
四.实验内容
实验准备：
1复习运筹学实验指导书第二章，课本《运筹学基础及应用》第二章，复习巩固线性规划模型及其求解的方法步骤；
2复习课本《运筹学基础及应用》第六章，熟悉图与网络分析的基础概念和最小支撑树、最短路问题的建模及求解的方法和步骤；
3学习运筹学实验指导书第八章。
实验内容：
1运行调试《运筹学实验指导书》第八章例题程序。
至少完成一个，三个以上为优。
2P165，例6用计算机求解图6-13从s到t的最大流；P166，例7；P170，例9（可选）；
3P171，习题6.1，6.3，6.4（按学号后两位被四除的余数1，2，3，0分别做a,b,c,d四个图之一。
）
4P172，学号后两位奇数做习题6.7（a），6.9；偶数做6.7（b），6.11。
习题6.5都做。
5P176，案例6.1（探究性实验，可选部分）。
实验报告要求：
1用自己的语言描述实验的目的、过程和具体步骤；
2给出课本例题、习题的求解的过程和结果，并给出点评分析：
3给出案例的建模、求解过程和结果，并进行分析总结。
（可选）
4给出进一步完善实验的建议和方法，或给出一些可进一步讨论研究的探索性研究课题。
（可选）
其中1-2为必做作业，3-4为选作题，供追求成绩优、良的人选作。
前三项完成好，后两项至少完成一个方具备考虑给优秀成绩的资格。
《运筹学实验》7——网络最大流（周四）
一.实验目的及要求
1.了解网络最大流问题的研究背景，加强对网络可行流、最大流、最小费用最大流等概念以及网络最大流问题求解方法的基本思想和过程步骤地理解和掌握；
2掌握用Matlab或LINDO求解网络最大流问题的方法和步骤，学会利用Matlab或LINDO求解网络最大流、最小费用最大流及其变形问题。
3.锻炼应用所学知识解决综合性问题的能力
二.实验设备与器件
1.安装win98系统以上的计算机
2.malab6.0或LINDO6.01或更高版本的软件
三.实验原理
网络最大流问题是图与网络分析中一类重要应用问题，有着明确的实际背景和广泛的应用。
教材中给出了求解网络最大流的算法，其基本思想是寻找可扩展的可行流。
理论分析的时候是基于概念和概念之间的关系，而程序实现是基于可操作的步骤和可计算的数据。
事实上，有些概念容易理解，但不容易计算；有些容易操作可以计算，但不太好理解。
因此，在计算机上求解网络最大流的时候，与课本的理论分析既有共同点，又有很多的不同；有些理论内容被省略了，但同时也增加了一些新内容。
这一次实验一方面要掌握计算机求解网络最大流问题的技术方法；另一方面，也要体会并思考这种理论和技术的微妙差别。
把实际问题要转化为数学上可以处理的问题，和把实际问题转化成计算机可以处理的问题，这两个过程都叫建模。
两个过程有很多的共性，同时也有一些显著的差异。
不同行业的工作人员有不同的行业术语和行业习惯，作为一个应用数学工作者，或者一个跨行业的工作人员，一个很重要的素质就是接受不同行业的术语、习惯和规范，并尝试实现它们的对接和转换。
千里之行，始于足下。
请从现在开始，请从身边开始，请从小事开始。
积累，成长！
四.实验内容
实验准备：
1复习运筹学实验指导书第二章，课本《运筹学基础及应用》第二章，复习巩固线性规划模型及其求解的方法步骤；
2复习课本《运筹学基础及应用》第六章，熟悉图与网络分析的基础概念和最大流建模及求解的方法和步骤；
3学习运筹学实验指导书第七章——网络最大流。
实验内容：
1运行调试《运筹学实验指导书》第八章例题程序。
至少完成一个，三个以上为优。
2P165，例6用计算机求解图6-13从s到t的最大流；P166，例7；P170，例9（可选）；
3P174，习题6.12（按学号后两位被四除的余数1，2，3，0分别做a,b,c,d四个图之一。
）
4P174，学号后两位奇数做习题6.13，6.15（a）；偶数做6.14，6.15（b）。
习题6.16都做。
5P177，案例6.2（探究性实验，可选部分）。
实验报告要求：
1用自己的语言描述实验的目的、过程和具体步骤；
2给出课本例题、习题的求解的过程和结果，并给出点评分析：
3给出案例的建模、求解过程和结果，并进行分析总结。
（可选）
4给出进一步完善实验的建议和方法，或给出一些可进一步讨论研究的探索性研究课题。
（可选）
其中1-4为必做作业，5为选作题，供追求成绩优、良的人选作。
前三项完成好，后两项至少完成一个方具备考虑给优秀成绩的资格。
《运筹学实验》之8——关键线路法（周四）
一.实验目的及要求
1.了解计划评审技术（PERT）和关键线路法的研究背景和主要发展历程，掌握计划评审技术网络图的绘制和计算方法、关键路线的定义和求法、不确定性因素的处理方法以及网络计划的优化方法等技术方法，加强对理论知识的理解，提高其应用水平；
2掌握用Matlab或LINDO求解网络计划评审图的关键线路的方法和步骤，学会利用Matlab或LINDO进行网络分析和优化。
3.锻炼应用所学知识解决综合性问题的能力
二.实验设备与器件
1.安装win98系统以上的计算机
2.malab6.0或LINDO6.01或更高版本的软件
三.实验原理
计划评审方法（ProgramEvaluationandReviewTechnique，简写为PERT）和关键路线法（CriticalPathMethod,简写为CPM）是网络分析的一个重要组成部分，它广泛应用于系统分析和项目管理。
较之管理上常用的甘特图方法，计划评审方法能够更直观清晰地反映计划各部门或各项工作之间的相互联系制约，便于掌握计划的全盘情况。
同时，能够更好地反映部门或项目在全局中的地位和影响，便于发现薄弱环节并加以控管优化。
更重要的是，它可以方便地利用计算机进行数据计算和推理，有利于各种计划方案的比较分析和优化。
这部分内容没有复杂的理论，但包含大量的实用的技术和方法。
通过对若干实际问题的建模和分析，可有效提高学生们利用所学方法和计算机工具通过建模和求解分析解决实际问题的能力。
四.实验内容
实验准备：
1复习运筹学实验指导书第二章，课本《运筹学基础及应用》第二章，复习巩固线性规划模型及其求解的方法步骤；
2复习课
升级会员 