运筹学课程设计- 题目是《某车间有两台机床甲和乙，可用来加工三种工件》

运筹学课程设计- 题目是《某车间有两台机床甲和乙，可用来加工三种工件》 工 业 大 学 课 程 设 计 报 告 课程设计名称 运筹课程设计 专 业 班 级 学 生 姓 名 指 导 教 师 2011年7月12日 课 程 设 计 任 务 书 课程设计题目: 第 11 题 起止日期:2011.6.29,2011.7.12 设计地点:教室、电子商务中心 设计任务及日程安排: 1、设计任务 1.1通过课程设计可以增强学生解决实际运筹学问题的能力 1.2通过课程设计可以使学生巩固、拓展和深化所学的基础理论、专业理论和知识。 1.3通过课程设计可以使学生初步掌握用运筹学方法解决实际问题的过程和技巧，树立理论联系实际的工作作风。 1.4通过课程设计可以使学生初步建立正确的设计思想和方法，进一步提高运算、计算机应用技能和综合分析、解决问题的能力。 2、设计进度安排 本课程设计时间分为两周: 第一周(2011年6月29日----2011年7月5日):建模阶段。此阶段各小组根据给出的题目完成模型的建立。主要环节包括 : 1.1 6月29日上午:发指导书;按组布置设计题目;说明进度安排。 1.2 6月29日下午至7月1日:各小组审题，查阅，进行建模前的必要准备(包括求解程序的编写与查找)。 1.3 7月1日至7月5日:各个小组进行建模，并根据题目及设计要求拟定设计提纲，指导教师审阅;同时阅读，理解求解程序，为上机求解做好准备。 第二周(2011年7月6日---7月12日):上机求解，结果分析及答辩。主要环节包括 1.1 7月6日至7月8日:上机调试程序 1.2 7月8日:完成计算机求解与结果分析。 1.3 7月11日:撰写设计报告。 1.4 7月12日:设计答辩及成绩评定。 (答辩时间:7月12日上午8:30,12:00，下午2:00,5:00) 1 组别:第十九组 设计人员: 设计时间:2011年6月29日—2011年7月12日 1.设计进度 本课程设计时间分为两周: 第一周(2011年6月29日----2011年7月12日):建模阶段。此阶段各小组根据给出的题目完成模型的建立。主要环节包括 : 1.1 6月29日上午:发指导书;按组布置设计题目;说明进度安排。 1.2 6月29日下午至7月1日:各小组审题，查阅资料，进行建模前的必要准备(包括求解程序的编写与查找)。 1.3 7月4日至7月5日:各个小组进行建模，并根据题目及设计要求拟定设计提纲，指导教师审阅;同时阅读，理解求解程序，为上机求解做好准备。 第二周(2011年7月6日---7月12日):上机求解，结果分析及答辩。主要环节包括 1.1 7月6日至7月7日:上机调试程序 1.2 7月8日:完成计算机求解与结果分析。 1.3 7月11日:撰写设计报告。 1.4 7月12日:设计答辩及成绩评定。 2.设计题目 某车间有两台机床甲和乙，可用来加工三种工件。假定这两台机床的可用台时数分别为700和800，三种工件的数量分别为300，500和400，且已知用不同加工机床加工单位数量不同工件所需的台时数和加工费用(表25)，问怎样分配机床的加工任务，才能既满足加工工件的要求，又使总加工费用最低,并按要求分析:(1)工件2的加工费用在何范围内变化时最优解不变,(2)乙机床的可用台时数在何范围内变化时最优基不变,(3)工件1的数量在何范围内变化时最优基不变,(4)当甲机床的可用台时数为600时，应如何分配机床的加工任务, 2 表25 工件的加工情况 机床类单位工件所需加工台时 单位工件的加工费用 可 用 型 台时数 工件1 工件2 工件3 工件1 工件2 工件3 甲 0.4 1.1 1.0 13 9 10 700 乙 0.5 1.2 1.3 11 12 8 800 3. 建模过程 3.1设定变量 设 在甲机床加工工件1,2,3的数量分别为X X X123 在乙机床加工工件1,2,3的数量分别为X X X 456 3.2根据题意推理 min w = 13X+9X+10X+11X+12X+8X 123456 X+X=300 工件1的加工数量为300 14 X+X=500 工件2的加工数量为500 25 X+X=400 工件3的加工数量为400 36 0.4X+1.1X+X?700 甲机床加工台时数不超过700 123 0.5X+1.2X+1.3X?800 乙机床加工台时数不超过800 456 X?0 j=1，2，„,6 j 3.3计算机求解前的手工数据准备 将原问题的所有约束条件添加人工变量X X X XX 78910 11max Z = -13X-9X-10X-11X-12X-8X 123456 X+X+X=300 147 X+X+X=500 258 X+X+X=400 369 0.4X+1.1X+X+X=700 12310 0.5X+1.2X+1.3X+X=800 45611 X?0 j=1，2，„,8 j 3 4.程序功能介绍 4.1 总体介绍: C语言是目前世界上流行、使用最广泛的高级程序设计语言。,语言是一种结构化语言。它层次清晰，便于按模块化方式组织程序，易于调试和维护。C语言的表现能力和处理能力极强。它具有丰富的运算符和数据类型，便于实现各类复杂的数据结构。我们用C语言编制的程序能够很好的解决运筹学问题,程序各个功能齐全,并且注释详细清楚,便于读者阅读和理解。C程序语言能够将复杂的问题简单化，大大节省了人力和物力，是解决运筹学问题的很好的工具。 C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。 C语言是结构式语言。结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。C 语言是以函数形式提供给用户的，这些函数可方便的调用，并具有多种循环、条件语句控制程序流向，从而使程序完全结构化。 同时，C语言具有简洁紧凑、灵活方便、运算符丰富、数据类型丰富等特点，适用于初级程序的编写，具有易于理解和操作等特点，是学习其他语言的基础。 LINDO是Linear Interactive and Discrete Optimizer字首的缩写形式，可以用来求解线性规划，整数规划和二次规划LINDO易于数学规划问题输入求解和分析，程序执行速度很快，LINDO学生版最多可求解200个变量和100个约束条件的规划问题。LINDO的求解机制采用单纯形法，一般是首先寻找一个可行解，在有可行解情况下在寻求最优解。用LINDO求解一个LP问题会得到不可行解、可行解有最优解和无最优解。LINDO中包含了一种建模语言许多常用的数学函数可供使用者建立规划问题调用。 4 4.2 程序图 开始 输入:变量个数8，约束条件个数5，选择目标函数的类型; 方 程组系数矩阵A，操作符opt，目标函数系数C 调整:目标函数为Max;右端常数项b为非负 加入松弛变量和人工变量，调整约束方程位置，使基变 量中最后k行为人工变量 k ,d求 max Z = ,jj,1 迭代，旋转变换 dj的检验数是否非负 选择主元列、行 是 否 W是否为0 无可行解 是 否 强行迭代 存在人工变量为基变量 否 是 人工变量行非人工变量全为0 是 去掉这些人工变量的列中具有 “1”的所有行，再去掉相应的列。 进入第二阶段求解 停止 5 第二阶段开始 读取第一阶段计算结果:A和b的值 用实际的目标函数取代余下的人工目标函数 用非基变量的线性组合来表示基变量 输出最优解存在cj<0 和最优值 否 是 无有界最优解 选择主元素列s 是否进行灵 敏度分析 是 否 存在b>0 ij c、b变化是是 否影响最优 解和最优基 选择主元素行r= min{b,b} i0is 否 是 重新计 换元后计算各行新的系数 算并输1、b = b,b rjrjrs重新计算Z、 。* 出Z、X。*2、b = b – b * bijijrsrj X，并代入 单纯行表， 重新迭代， 输出结果。 结束 4.3数据录入 6 在程序运行后，需要依据所编程序的要求录入相应数据，其具体过程如图所示 1、首先输入题中所要求的各个数据(图1) 图1 5. 计算机求解过程 5.1 C语言程序运行结果如下:(图2) 图2 7 5.2 LINDO运行结果如下: 5.2.1 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 11000.00 VARIABIE VALUE REDUCED COST X1 0.000000 2.000000 X2 500.000000 0.000000 X3 0.000000 2.000000 X4 300.000000 0.000000 X5 0.000000 3.000000 X6 400.000000 2.000000 表1 5.2.2列出最优单纯形表中判别数所在行的松弛变量系数 ROW SLACK OF SURPLUS DUAL PRICES 2) 0.000000 -11.000000 3) 0.000000 -9.000000 4) 0.000000 -8.000000 5) 150.000000 0.000000 6) 130.000000 0.000000 表2 5.2.3 RANGES IN WHICH THE BASIS IS UNCHANGED: 当目标函数的变量系数在什么 变化范围内时，最优基不变。 CURRENT COEF:初始目标函数的系数。 ALLOWABLE INCREASE:允许变量系数增加的范围。 ALLOWABLE DECREASE:允许变量系数减少的范围。 当目标函数的系数C在 [初始目标函数的系数-允许变量系数减少的范围，初始 目函数的系数+允许变量系数增加的范围] 内变化时，最优基不变，最优解也不变， 由于目标函数的系数发生改变了，所以最优值有可能改变。 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 13.000000 INFINITY 2.000000 X2 9.000000 3.000000 INFINITY X3 10.000000 INFINITY 2.000000 8 X4 11.000000 2.000000 INFINITY X5 12.000000 INFINITY 3.000000 X6 8.000000 2.000000 INFINITY 表3 5.2.4 RIGHTHAND SIDE RANGES:约束条件右端项在什么范围内变化时，最优基不变: CURRENT RHS:初始约束条件右端项的值; ALLOWABLE INCREASE:允许b值增加的范围 ALLOWABLE DECREASE:允许b值减少的范围 当约束条件右端项的值在 [初始约束条件右端项的值-允许b值减少的范围，初 始约束条件右端项的值+允许b值增加的范围] 内变化时最优基不变，最优解不变， 最优值也可能不变。 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 300.000000 260.000000 300.000000 3 500.000000 136.000000 500.000000 4 400.000000 100.000000 400.000000 5 700.000000 INFINITY 150.000000 6 800.000000 INFINITY 130.000000 表4 5.3规定题目的分析过程及结果 5.3.1、工件2的加工费用变化使最优解不变属于LP问题模型中目标函数参数C 的变化，所以分为两种情况: (1)若Cj是非基变量Xj的系数: 先确定非基变量系数变化范围，非基变量系数变化只影响自身的检验数，因此: -1设Cj为非基变量Xj的系数，令它在当前最优表中的检验数δj=CBPj-Cj>=0,当Cj发生B 了?Cj变化后，要保证当前最优表中相应的检验数仍大于或等于0，必有: 即:δj=δj-?Cj>=0或?Cj<=δj 这就是说，当Xj的系数Cj增大?Cj以后其增量变化范围小于等于该变量在当前最 优表中相应的检验数时，最优解不变;否则最优解改变，将δj的值代入最优表中重 新迭代。 (2)若Cj是基变量Xj的系数: 先确定基变量系数变化范围，基变量系数变化影响所有非基变量的检验数和目标 9 函数值。如果Cj的变化范围在基变量Cj增量的变化范围之内则其最优解、最优值均不变;反之如果Cj的变化范围超出基变量Cj增量的变化范围，则需要重新迭代求出最优值。 根据表3得:工件2在甲机床加工费用在[,?，9.000000+3.000000]范围内变化时和工件2在已机床加工费用在[12.000000-3.000000，+?]范围内变化时最优解不变。 5.3.2、乙机床的可用台时数变化、工件1的加工数量变化使最优基不变和甲机床的可用台时数变为600都属于LP问题模型中约束条件右端参数b的变化: 根据max{-bi/βir | βir>0}<=b<=min{-bi/βir | βir<0} 确定b的变化范围。 -1 (1)如果b的变化在该范围之内最优基不变最优解变化，最优解由公式X=Bb求得。 B -1 (2)如果b的变化超出该范围最优基最优解均发生变化，重新计算CBb、B-1bB代入最优表中重新迭代。 根据表4得:乙机床的可用台时数在[800.000000-130.000000，+?]范围内变化时，工件1的加工数量在[300.000000-300.000000,300.000000+260.000000]范围内变化时最优解不变。当甲机床的可用台时数变为600时，在[700.000000-150.000000, +?]范围内。所以最优解不变。 6.创新内容 6.1 工件1的加工费用在什么范围内变化时，最优解不变, 由表3可知 工件1在甲机床加工费用在[13.000000-2.000000，+?]范围内变化时和工件1在乙机床加工费用在[-?，11.000000+2.000000]范围内变化时最优解不变。 6.2 工件2的数量变化为700时，最优解是否变化, 由表4可知 工件2的数量在[500.000000-500.000000,500.000000+136.363632]范围内变化时，最优解不变。所以，当工件2的数量变化为700时，不在该范围内，所以最优解改变。 7.课程设计 通过两周的课程设计，发现自己有很多才意识到平时课上学的虽内容然听懂了，但到实际应用的时候才发现自己的能力真的有限。实践过程中遇到各种各样的问题。但最后都在老师和同学的帮助下顺利解决了。也让我深深的意识到了一个人的力量是 10 微小的，团队合作才会让我们更加顺利的完成任务。 这次课程设计，我们组分到的是有关灵敏度分析的问题。刚开始建模过程还算顺利。变量个数和约束条件相对较少。但到了编程阶段就遇到很多问题，对以前学过的计算机语言也有些陌生了。最后在网上找了一段程序进行修改。但在修改过程中还是遇到很多问题。每次运行程序都会出现很多错误，一次次的修改，一次次的出错。终于，在不懈的努力下，程序运行成功，并求得最优解。最后，我们用LINDO软件进行了灵敏度分析，题目最终解决了。使用程序求解节省了我们很多时间。我们所选题目需要用两阶段法求解，经过八次迭代才得到最优解。如果是人工求解，可能要花费很多时间了。看来，我们真的要好好学习计算机，并将它应用到实践中。 这次课程设计，收获很多。以前学习C语言。以为只要考下二级证就可以了，没想到应用到实践中才发现自己所学的远远不够。对于运筹学我也有了更深的了解。知道运筹是专业课，所以上课有好好学，可是课程设计刚刚开始时真的很让我头疼。不知从哪里入手。经过两周的研究，小组成员的努力。终于完成报告。真的感觉从中学会好多。 通过这次课程设计，才意识到我们所学的东西付诸实践是多么重要。深深的体会到了“学以致用”这个词的真正含义。无论书本上的知识学的怎么好，不会应用，不会联系实际，都是没有用的。只有一切从实际情况出发，才能真正发挥我们所具备的能力。课程设计也是我们大学生涯中必不可少的，它使我们在实践中巩固了所学的知识，在实践中锻炼自己的动手能力。它让我们学到了很多课堂上根本就学不到的知识。不仅开阔了自己的视野，也增长了自己的见识。 11