运筹学实验综述

1、运筹学实验1线性规划建模与求解（周二、三）一 . 实验目的及要求1. 掌握线性规划建模的方法与过程，体会线性规划建模的核心思想。2. 掌握线性规划问题的求解方法。3.掌握用 Matlab 或 LINDO 求解线性规划问题的基本方法和步骤，学会分析Matlab 或 LINDO 的计算结果。4. 锻炼应用所学知识解决综合性问题的能力二 . 实验设备与器件1. 安装 win98 系统以上的计算机或 LINDO6.01或更高版本的软件三 . 实验原理线性规划常见可以解决资源分配问题，成本效益平衡问题。在求解线性规划时，常用的方法有图解法和单纯形法。单纯形法基本思路是：先找出一个基本可行解, 判断其是否

2、为最优解, 如果不是最优解，则转换到相邻的基本可行解 , 并使目标函数值不断增大 , 直到找出最优解或判断有无界解、无解为止。本实验是合理利用线材问题属于解决资源分配问题 使用 LINDO 6.01 进行操作： LINDO（ Linear Interactive and Discrete Optimizer）是一种专门用于求解数学规划问题的软件包。由于LINDO执行速度很快、易于方便输入、求解和分析数学规划问题，因此在数学、科研和工业界得到广泛应用。LINDO主要用于解线性规划、非线性规划、二次规划和整数规划等问题。也可以用于一些非线性和线性方程组的求解以及代数方程求根等。LINDO中包含了一

3、种建模语言和许多常用的数学函数（包括大量概论函数） ，可供使用者建立规划问题时调用。四 . 实验内容实验准备：1 自学运筹学实验指导书第一、二两章，复习巩固Matlab 基础知识；2 复习课本运筹学基础及应用第一章，熟悉线性规划模型建模的过程，模型标准化及模型求解的思路和过程，最优解判定的准则和方法。实验内容：1 自学运筹学实验指导书第三章，掌握线性规划模型求解的软件技术；2 利用软件实现运筹学实验指导书第三章所有例题的求解计算；3 参照例题，总结提炼线性规划建模与求解过程的主要难点问题、模型求解的程序命令及其适用条件等，形成便于自己理解的规范的操作指南；4 利用前面总结的方法，完成如下习题的

4、求解：1.7化标准型并用程序命令求解1.12建立模型，化标准型并用程序命令求解5 完成如下实际问题的建模与求解。线材切割问题在很多工程领域，都有线材切割问题。这一问题可表述为:设能购买到的不同长度的原线材有m种，长度分别为 L1,.,Lm，这些原线材只是长度不同，其它都相同。某工程中所要切割出的线材长度分别为li,i=1,2,.,n(这里 li< 所有Li) ，对应数量分别为Ni,i=1,2,.,n。设计优化计算方案，求出分别需要购买多少根不同长度的原线材 , 并能给出切割方案及线材利用率。具体事例现假设某装修工程中需要对铝合金线材进行切割，工程能购买到的同一规格的铝合金线材有二种长度，

5、一种长度是 8米，另一种是 12米 。现在假设要切割长度和数量如下所示的铝合金线材：表 5.1编号长度 ( 单位: 米) 数量(单位 : 根)16.209023.6012032.8013641.8531050.7521560.55320应用所设计的计算方案，请问至少需要购买多少根8米和 12米的线材，使浪费的线材比较少，并给出切割方案和计算线材利用率。实验报告要求：1 用自己的语言描述实验的目的，并设计实验过程，给出具体实施步骤；2 给出课本 P47，习题 1.7,1.12 的求解的过程和结果，并给出点评分析：3 出实际问题的建模过程，模型规范表述、模型求解过程及结果。4 给出线性规划建模与求

6、解过程的主要难点问题，总结模型求解的程序命令及其适用条件等，给出规范的操作指南，总结实验的得失和实验心得体会；5 给出进一步完善实验的建议和方法，或进一步探索性研究课题。其中 1-3 为所有人必做作业； 4,5 为选作题，供追求成绩优、良的人选作。前三项完成好，后两项至少完成一个方具备考虑给优秀成绩的资格。运筹学实验2线性规划的对偶原理及灵敏性分析（周三）一 . 实验目的及要求1.掌握线性规划的对偶理论，能够根据线性规划原问题给出其对偶问题，熟悉对偶问题的解与原问题的解之间的关系方法，并能将该结论用于线性规划求解；掌握对偶单纯形方法；2 理解线性规划灵敏度分析的意义，掌握线性规划灵敏性分析的常

7、用方法，理解影子价格，体会灵敏度分析结果对决策的影响。3 掌握用 Matlab 或 LINDO 进行灵敏性分析方法和步骤，读懂并学会分析Matlab 或 LINDO 的计算结果。4. 锻炼应用所学知识解决综合性问题的能力二 . 实验设备与器件1. 安装 win98 系统以上的计算机或 LINDO6.01或更高版本的软件三 . 实验原理 线性规划的对偶理论是线性规划理论的重要组成部分，是运筹学知识体系中具有鲜明特色的一个知识板块。理解线性规划对偶问题的概念，掌握线性规划原问题与对偶问题之间的关系可以进一步加深对线性规划问题及其求解方法的理解。同时，对偶问题的提出和研究，还可以进一步丰富我们科学研

8、究的思路和方法 , 为今后的学习和科研工作积累经验。 有时候，转换、丰富问题研究的视角，可以有意外的惊喜发现。 线性规划的灵敏度分析是线性规划理论的一个不可或缺的重点组成部分。 正是大量的假设情况分析使得线性规划的建模和求解能够更好的贴合实际需求， 同时也为管理者的决策提供更充分的支持。体会灵敏度分析的问题提出的背景，掌握灵敏度分析的主要内容和常见方法，理解灵敏度分析的核心思想，有助于我们更好地解决实际问题，为决策提供更全面的数据支持。3 灵敏度分析，或者称假设情况分析、whatif分析等，体现着一种负责务实的态度，一种积极主动提供更周到服务的理念。灵敏度分析的内容很丰富，目前数学软件大都提供

9、了一些与灵敏度分析有关的具体的技术和方法，但需要读者自己熟练应用，合理组织，形成一个系统化的分析总结方案。这个过程包含模型调整和优化、不同情况下的反复求解，求解结果的系统分析和深刻独到的问题发现等。它既是对前面掌握技术方法的一种演练提升，同时也锻炼我们的思考能力和分析综合能力，使我们再面对复杂的实际问题时，能够抓住关键问题以及问题的关键部分，找到适合北京背景环境的有效的满意“最优解”。四 . 实验内容实验准备：1 复习运筹学实验指导书第二章，课本运筹学基础及应用第一章，复习巩固线性规划建模、求解的方法和步骤；2 复习课本运筹学基础及应用第二章，熟悉线性规划对偶理论，对偶单纯形方法和灵敏度分析的

10、课题及主要内容。实验内容：1 复习运筹学实验指导书第三章，掌握线性规划模型求解的软件技术；2 总结写线性 规划对偶问题的准则，给出对偶理论的几个主要结论，结合实例验证结论的正确性；总结线性规划灵敏度分析的内容及主要结论，具体验证方法为： 选择实验一中已经求解过得几个实例， 首先写出他们的对偶问题并分别求解，然后验证对偶问题的解与原问题解之间的关系：P77， 2.4 利用程序命令求解原问题，验证题目所给原问题最优解的正确性；写出其对偶问题，并用程序命令求解；验证原问题与其对偶问题解之间的关系的几个重要结论；P77，2.7 写出其对偶问题，并分别用程序命令求解原问题及其对偶问题解；对比分析计算结果

11、，验证解之间的关系的几个重要结论；3 结合实例验证灵敏性分析结论的有效性及其局限。完成如下习题的求解：P77，2.8不利用定理结论，编成用试探法确定最优解保持不变的参数允许变动范围。P77，2.9不利用定理结论， 编成用试探法确定最优解保持不变的参数允许变动范围。注：这部分内容有助于帮助学生了解实验法的优势和局限，理解定理结论的重要性，加强对理论学习重要性的认知。4 完成如下实际问题的建模与求解（探究性实验，可选部分）。线材切割问题的进一步分析假设生成产品规格发生改变，请根据情况进行分析。1 第一种长为 6.20 的 90根变成了 150根；2 第一种产品长度要求变为6.30 ， 100根；3

12、 一种产品长度要求变为3.1 ， 180根。实验报告要求：1 用自己的语言描述实验的目的、过程和具体步骤；2 给出习题的求解的过程和结果，并给出点评分析：3 给出条件改变后实际问题的模型求解过程及结果，并进行分析。4 总结对偶理论的几个主要结论，讨论对偶问题的解与原问题解之间的关系。5 总结灵敏性分析实验的得失，理解实验计算的优势及局限，理解理论猜想结论及其证明等理论性成果的意义，写出心得体会；6 给出进一步完善实验的建议和方法，或给出一些可进一步讨论研究的探索性研究课题。其中 1-3 为必做作业， 4-6 为选作题，供追求成绩优、良的人选作。前三项完成好，后两项至少完成一个方具备考虑给优秀成

13、绩的资格。运筹学实验3运输问题（周四）一 . 实验目的及要求1. 了解运输问题， 特别是线性运输问题的提出背景、 运输问题理论和方法的特点， 掌握运输问题求解的表上作业法，最优性判定的闭回路法和位势法，理解运输问题求解与转化的机理，了解几种常见的变形。2 掌握用 Matlab 或 LINDO 求解运输问题的方法和步骤，读懂并学会分析Matlab 或 LINDO 的计算结果。4. 锻炼应用所学知识建立实际问题数学模型，并借助计算机和软件工具解决综合性实际问题的能力二 . 实验设备与器件1. 安装 win98 系统以上的计算机或 LINDO6.01或更高版本的软件三 . 实验原理1 运输问题是一类

14、常见的，具有明确的实际背景和鲜明特点的特殊的线性规划问题。这类问题的研究具有重要的理论和应用价值。作为特殊的线性规划，当然可以用经典的单纯形方法求解。但由于问题的特殊性，运输问题可以使用表上作业法等更简单的方法来求解。常见的数学平台软件，大都只是将它作为特殊的线性规划进行处理，并没有给出专门的求解运输问题的模块。近几年来，随着物流与网络分析技术的发展，专门求解大规模优化问题的软件渐渐多了起来，感兴趣的同学可以有意识地收集一下相关的资料。2 运输问题实验主要是体会运输问题的特点，并尝试较大规模问题的求解。四. 实验内容实验准备：1 复习运筹学实验指导书第三章，课本运筹学基础及应用第二、三章，复习

15、巩固线性规划建模、求解的方法和步骤；2 复习课本运筹学基础及应用第四章，熟悉运输问题数学模型，产销平衡运输问题求解的表上作业法、伏格尔法以及闭回路法等运输问题最优解判定的方法，产销不平衡等其他类型运输问题的转化方法。实验内容：1 自学运筹学实验指导书第四章，掌握运输问题模型求解的技术方法；2 运行调试运筹学实验指导书第四章例题；至少完成一个，三个以上为优。3 完成课本如下习题的求解：3.13.2，以表格3-35 为例4 分析课本第 104 页，案例 3光明市的菜篮子工程。实验报告要求：1 用自己的语言描述实验的目的、过程和具体步骤；2 给出习题的求解的过程和结果，并给出点评分析：3 课本第 1

16、04 页，案例 3光明市的菜篮子工程。4 总结实验的得失和实验心得体会，给出进一步完善实验的建议和方法，新的案例或进一步探索性研究课题。其中 1-2 为必做作业， 3-4 为选作题，供追求成绩优、良的人选作。前三项完成好，后两项至少完成一个方具备考虑给优秀成绩的资格。运筹学实验4整数规划之分支定界、割平面（周五）一 . 实验目的及要求1.理解整数线性规划和普通线性规划的区别，体会整数规划求解的分支定界法、割平面法与隐枚举方法的思想，掌握整数规划求解的方法与步骤。2掌握用 Matlab 或 LINDO 求解整数规划的方法和步骤，学会利用Matlab 或 LINDO 求解具体整数规划问题。3. 锻

17、炼应用所学知识解决综合性问题的能力二 . 实验设备与器件1. 安装 win98 系统以上的计算机或 LINDO6.01或更高版本的软件三 . 实验原理整数线性规划是一类特殊的线性规划，在实际生活中大量存在。整数规划问题的求解，通常是这样的一个过程： 首先，去掉整数约束， 借助普通线性规划求解的单纯形方法得到问题的一个最优解，然后进行整数约束判定，如果得到的是整数最优解，结束；否则，利用分支或者割平面方法去掉不满足整数约束的最优解，重新求解，知道得到问题的整数最优解或判定问题无解为止。本实验的主要目的是帮助学生加深对这一求解过程的认识和理解，掌握一种人机结合的半自动化的问题求解模式，并尝试将这个

18、过程尽量多的自动化。四 . 实验内容实验准备：1 复习运筹学实验指导书第二章， 课本运筹学基础及应用 第四章， 复习巩固整数线性规划建模、求解的方法和步骤；2 复习课本运筹学基础及应用第四章，熟悉整数规划模型的特点及其求解的分支定界法、割平面法。3 学习运筹学实验指导书第五章实验内容：1 运行调试运筹学实验指导书第五章例题程序。至少完成一个，三个以上为优。2 P126， 4.7 利用程序命令求解原问题，验证解是否满足整数约束；然后分支，求解，验证；循环迭代，直到找到整数最优解。3 P126，4.8 利用程序命令求解原问题，验证解是否满足整数约束；然后构造辅助约束，割去不满足整数约束的最优解，继

19、续求解；如此反复，直到找到整数最优解。4 选择课本案例4.1,4.2,4.3 中的一个，建立模型并进行求解分析（探究性实验，可选部分）。实验报告要求：1 用自己的语言描述实验的目的、过程和具体步骤；2 给出习题的求解的过程和结果，并给出点评分析：3 给出案例的数学模型，求解过程及结果，并进行必要的分析。4 给出进一步完善实验的建议和方法，或给出一些可进一步讨论研究的探索性研究课题。其中 1-2 为必做作业， 3-4 为选作题，供追求成绩优、良的人选作。前三项完成好，后两项至少完成一个方具备考虑给优秀成绩的资格。运筹学实验5整数规划之指派问题（周二）一 . 实验目的及要求1. 理解指派问题这一特

20、殊整数线性规划问题的特点，体会指派问题求解的匈牙利方法；2掌握用 Matlab 或 LINDO 求解指派问题的方法和步骤，学会利用Matlab 或 LINDO 求解具体指派问题及其变形问题。3. 锻炼应用所学知识解决综合性问题的能力二 . 实验设备与器件1. 安装 win98 系统以上的计算机或 LINDO6.01或更高版本的软件三 . 实验原理指派问题是一类常见的特殊0-1 整数线性规划，也可看作是特殊的运输问题。指数问题的求解也是一个不断试探、判断、再试探再判断的过程。如果能够很好的理解这中问题求解模式，并根据实际问题的需要加以变通，可以有效提升学生解决实际问题的能力。四. 实验内容实验准

21、备：1 复习运筹学实验指导书第二章，课本运筹学基础及应用第四章，复习巩固指派问题建模、求解的方法和步骤；2 复习课本运筹学基础及应用第四章，熟悉整指派问题的特点及其求解的匈牙利方法。3 学习运筹学实验指导书第六章实验内容：1 运行调试运筹学实验指导书第六章例题程序。至少完成一个，三个以上为优。2 P125， 4.33 P125， 4.44P125， 4.5 （探究性实验，可选部分）。实验报告要求：1 用自己的语言描述实验的目的、过程和具体步骤；2 给出习题的求解的过程和结果，并给出点评分析：3 给出进一步完善实验的建议和方法，或给出一些可进一步讨论研究的探索性研究课题。其中 1-2 为必做作业， 3 为选作题，供追求成绩优、良的人选作。前三项完成好，后两项至少完成一个