运筹课程设计5.doc

长 春 工 业 大 学课 程 设 计 报 告课程设计名称 运筹课程设计 专 业 信息管理与信息系统班 级 080505 学 生 姓 名 李进中 指 导 教 师 王亚君 2011年7月8日课 程 设 计 任 务 书课程设计题目：第 29 题起止日期：2011、6、272011、7、8设计地点：教室、电子商务中心设计任务及日程安排：1、设计任务1.1通过课程设计可以增强学生解决实际运筹学问题的能力1.2通过课程设计可以使学生巩固、拓展和深化所学的基础理论、专业理论和知识。1.3通过课程设计可以使学生初步掌握用运筹学方法解决实际问题的过程和技巧，树立理论联系实际的工作作风。1.4通过课程设计可以使学生初步建立正确的设计思想和方法，进一步提高运算、计算机应用技能和综合分析、解决问题的能力。2、设计进度安排本课程设计时间分为两周：第一周（2011年6月27日-2011年7月1日）：建模阶段。此阶段各小组根据给出的题目完成模型的建立。主要环节包括 ：1.16月27日上午：发指导书；按组布置设计题目；说明进度安排。1.26月27日下午至29日：各小组审题，查阅资料，进行建模前的必要准备(包括求解程序的编写与查找)。1.3 6月30日至7月1日：各个小组进行建模，并根据题目及设计要求拟定设计提纲，指导教师审阅；同时阅读，理解求解程序，为上机求解做好准备。第二周（2011年7月4日-7月8日）：上机求解，结果分析及答辩。主要环节包括1.1 7月4日至7月5日：上机调试程序1.2 7月6日：完成计算机求解与结果分析。1.3 7月7日：撰写设计报告。 1.4 7月8日：设计答辩及成绩评定。（答辩时间：7月8日上午8：3012：00，下午2：005：00）组别：第三组设计人员：姜旭、焦永明、李进中设计时间：2011年6月27日2011年7月8日1.设计进度本课程设计时间分为两周：第一周（2011年6月27日-2011年7月1日）：建模阶段。此阶段各小组根据给出的题目完成模型的建立。主要环节包括 ：1.16月27日上午：发指导书；按组布置设计题目；说明进度安排。1.26月27日下午至29日：各小组审题，查阅资料，进行建模前的必要准备(包括求解程序的编写与查找)。1.3 6月30日至7月1日：各个小组进行建模，并根据题目及设计要求拟定设计提纲，指导教师审阅；同时阅读，理解求解程序，为上机求解做好准备。第二周（2011年7月4日-7月8日）：上机求解，结果分析及答辩。主要环节：1.1 7月4日至7月5日：上机调试程序1.2 7月6日：完成计算机求解与结果分析。1.3 7月7日：撰写设计报告。 1.4 7月8日：设计答辩及成绩评定2.设计题目二十九、(仓库租用问题)捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资.已知各月份所需仓库面积数列于表一所示，仓库租借费用随合同期而定,期限越长,折扣越大,具体数字见表二，租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要,在任何一个月初办理租借合同.每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订租借合同的最优决策,目的是使所付租借费用最小。并按要求分别完成下列分析：（1）2个月租借期限的合同期内的租费在何范围内变化时最优决策不变？（2）3月份所需仓库面积在何范围内变化时最优基不变？（3）2月份所需仓库面积20时的最优决策？月份1234所需仓库面积(100m2)15102012表1合同租借期限1个月2个月3个月4个月仓库借费用(元/100m2)2800450060007300表23. 建模过程 3.1 设定变量设决策变量xij表示捷运公司在第i(I=1,2,3,4)个月初签订的租借期为j(j=1,2,3,4)个月的仓库面积的合同(单位为100m2). Z表示租借总费用。 3.2 根据题意推理因5月份起该公司不需要租借仓库,故x24,x33,x34,x42,x43,x44均为零。一、二、三、四月初签订的租期为一个月的合同费用为：2800（ x11 + x21 + x31 + x41 ）； 一、二、三月初签订的租期为两个月的合同费用为：4500（ x12 + x22 + x32）；二、三月初签订的租期为三个月的合同费用为：6000（ x13 + x23 ）；四月初签订的租期为四个月的合同费用为：7300x14；一月份所需的仓库面积为：x11 + x12 + x13 + x14 15；二月份所需的仓库面积为：x12 + x13 + x14 + x21 + x22 + x23 10；三月份所需的仓库面积为：x13 + x14 + x22 + x23 +x31 + x32 20； 四月份所需的仓库面积为：x14 + x23 + x32 + x41 12；得该问题的LP问题为：minZ= 2800（ x11 + x21 + x31 + x41 ） +4500（ x12 + x22 + x32）+6000（ x13 + x23 ）+7300x14 x11 + x12 + x13 + x14 15 x12 + x13 + x14 + x21 + x22 + x23 10 x13 + x14 + x22 + x23 + x31 + x32 20 x14 + x23 + x32 + x41 12xij 0 (i =1,4; j =1,4)3.3 计算机求解前的手工数据准备 将原问题第一、二、三、四个约束条件添加松弛变量x1、x2、x3、x4；将原问题第一、二、三、四个约束条件添加人工变量x5、x6、x7、x8；将问题化为标准形式：maxZ= -2800（ x11 + x21 + x31 + x41 ） - 4500（ x12+ x22 + x32）- 6000（ x13 + x23 ）-7300x14x11 + x12 + x13 + x14 x1 + x5 = 15 x12 + x13 + x14 + x21 + x22 + x23 x2 + x6 = 10x13 + x14 + x22 + x23 + x31 + x32 x3 + x7 = 20x14 + x23 + x32 + x41 x4 + x8 = 12xij 0 (i =1,4; j =1,4) xk 0 (k =1,8)4程序功能介绍4.1总体介绍Java是一种简单的，跨平台的，面向对象的，分布式的，解释的，健壮的，安全的，结构的中立的，可移植的，性能很优异的多线程的，动态的语言。我们用java语言设计编辑了一个解题程序来解答这个问题，运用eclipse环境运行的，我们首先程序要求输入目标函数类型以确定使用哪种程序解决当前问题，然后函数要求输入约束条件的个数和变量个数，以用来确定所创建的数组，然后函数要求小于等于、大于等于、和等于的条件个数，同样用来创建数组和确定解题程序，然后函数要求输入题的系数矩阵，函数记录下来用于解题，当输入结束时函数会输出刚刚所录入的系数矩阵，以便让输入者确定所输入的矩阵是否正确，避免错误的产生，此时进行到程序的最后一步，函数要求输入目标函数系数，输入者正确输入后函数就会运算然后输出结果。LINDO是Linear Interactive and Discrete Optimizer字首的缩写形式，可以用来求解线性规划，整数规划和二次规划LINDO易于数学规划问题输入求解和分析，程序执行速度很快，LINDO学生版最多可求解200个变量和100个约束条件的规划问题。LINDO的求解机制采用单纯形法，一般是首先寻找一个可行解，在有可行解情况下在寻求最优解。用LINDO求解一个LP问题会得到不可行解可行解有最优解和解无解LINDO中包含了一种建模语言许多常用的数学函数可供使用者建立规划问题调用。4.2程序流程图 开始输入：变量个数，约束条件个数，选择目标函数的类型; 方程组系数矩阵A，操作符opt，目标函数系数C调整：目标函数为Max；右端常数项b为非负加入松弛变量和人工变量，调整约束方程位置，使基变量中最后k行为人工变量求 min W=dj的检验数是否非负选择主元列、行迭代，旋转变换 无可行解存在人工变量为基变量人工变量行非人工变量全为0去掉这些人工变量的列中具有“1”的所有行，再去掉相应的列。进入第二阶段求解结束W是否为0是是是是否否否强行迭代否用实际的目标函数取代余下的人工目标函数 是是否否否是否是停止输出最优解和最优值存在bij0选择主元素行r= minbi0bis换元后计算各行新的系数1、brj = brjbrs 2、bij = bij brs * brj 选择主元素列s 用非基变量的线性组合来表示基变量 读取第一阶段计算结果：A和b的值开始存在cj=15；X12+X13+X14+X21+X22+X23=10；X13+X14+X22+X23+X31+X32=20；X14+X23+X32+X41=12；X11=0；X12=0；X13=0；X14=0；X21=0；X22=0；X23=0；X31=0；X32=0；X41=0；END5.结果分析51 Java语言程序运行结果如图二、三所示：5.结果分析图二图三由图三可知：最优解如下：x11=3.0 x12=0 x13=0 x14=12.0 x21=0 x22=0 x23=0 x31=8.0 x32=0 x41=0 min=118400.0 即所付租借费用最小为118400.0。5.2 LINDO运行结果如下：5.2.1 LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 118400.0 VARIABLE VALUE REDUCED COST Z 0.000000 1.000000 X11 3.000000 0.000000 X21 0.000000 2800.000000 X31 8.000000 0.000000 X41 0.000000 1100.000000 X12 0.000000 1700.000000 X22 0.000000 1700.000000 X32 0.000000 0.000000 X13 0.000000 400.000000 X23 0.000000 1500.000000 X14 12.000000 0.000000LP OPTIMUM FOUND AT STEP 3 表示LINDO在3次迭代或旋转后得到最优解。 OBJECTIVE FUNCTION VALUE 表示目标函数的最优值。118400.0 表示目标函数的最优值为 118400.0。VARIABLE 表示变量。VALUE 表示变量值。REDUCED COST 表示检验数所在行变量系数。5.2.2 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -2800.000000 3) 2.000000 0.000000 4) 0.000000 -2800.000000 5) 0.000000 -1700.000000 6) 3.000000 0.000000 7) 0.000000 0.000000 8) 0.000000 0.000000 9) 12.000000 0.000000 10) 0.000000 0.000000 11) 0.000000 0.000000 12) 0.000000 0.000000 13) 8.000000 0.000000 14) 0.000000 0.000000 15) 0.000000 0.000000LACK OR SURPLUS 表示给出松弛变量的值。DUAL PRICE表示列出最优单纯形表中判别数所在行的松弛变量系数。5.2.3 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE Z 1.000000 INFINITY 1.000000 X11 2800.000000 400.000000 0.000000 X21 2800.000000 INFINITY 2800.000000 X31 2800.000000 400.000000 1100.000000 X41 2800.000000 INFINITY 1100.000000 X12 4500.000000 INFINITY 1700.000000 X22 4500.000000 INFINITY 1700.000000 X32 4500.000000 INFINITY 0.000000 X13 6000.000000 INFINITY 400.000000 X23 6000.000000 INFINITY 1500.000000 X14 7300.000000 0.000000 1700.000000RANGES IN WHICH THE BASIS IS UNCHANGED表示当目标函数的变量系数在什么变化范围内时，最优基不变。CURRENT COEF 表示初始目标函数的系数。ALLOWABLE INCREASE 表示允许变量系数增加的范围。ALLOWABLE DECREASE 表示允许变量系数减少的范围。若目标函数的系数C在 CURRENT COEF - ALLOWABLE DECREASE，CURRENT COEF + ALLOWABLE INCREASE 内变化时，最优基不变，最优解也不变，由于目标函数的系数发生改变了，所以最优值有可能改变。5.2.4 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 15.000000 INFINITY 3.000000 3 10.000000 2.000000 INFINITY 4 20.000000 INFINITY 8.000000 5 12.000000 3.000000 2.000000 6 0.000000 3.000000 INFINITY 7 0.000000 0.000000 INFINITY 8 0.000000 0.000000 INFINITY 9 0.000000 12.000000 INFINITY 10 0.000000 0.000000 INFINITY 11 0.000000 0.000000 INFINITY 12 0.000000 0.000000 INFINITY 13 0.000000 8.000000 INFINITY 14 0.000000 0.000000 INFINITY 15 0.000000 0.000000 INFINITYRIGHTHAND SIDE RANGES 表示约束条件右端项在什么范围内变化时，最优基不变：CURRENT RHS 表示初始约束条件右端项的值；ALLOWABLE INCREASE 表示允许b值增加的范围ALLOWABLE DECREASE 表示允许b值减少的范围若约束条件右端项的值在 CURRENT RHS - ALLOWABLE DECREASE ，CURRENT RHS + ALLOWABLE INCREASE 内变化时最优基不变，最优解不变，最优值也可能不变。5.3 结果分析思路5.3.1 2个月租借期限的合同期内的租费在何范围内变化时最优决策不变？ 此问题属于目标函数系数 C 的变化，即x12、x22、x32的系数变化对最优决策的影响，决定条件有三个，取公共部分，即最小范围即可。由5.2.3的分析结果可知：Current Allowable AllowableVariable Coefficient Increase DecreaseX12 4500.000 INFINITY 1700.000X22 4500.000 INFINITY 1700.000X32 4500.000 INFINITY 0.000000在最优决策不变的情况下X12的可变化范围为2800, +；X22的可变化范围为2800, +；X32的可变化范围为4500, +。取公共部分得：2个月租借期限的合同期内的租费在4500, +范围内变化时最优决策不变。5.3.2 3月份所、需仓库面积在何范围内变化时最优基不变？ 此问题属于约束条件右端常数项 b 的变化，即约束条件：x13 + x14 + x22 + x23 +x31 + x32 20，右端的常数项20的变化对最优基的影响，由5.2.4的分析结果可知：Righthand Side Ranges: Current Allowable Allowable Row RHS Increase Decrease 4 20.00000 INFINITY 8.000000在最优基不变的情况下第三个约束条件右端常数项的可变化范围为12, +，即3月份所、需仓库面积在12, +的范围内变化时最优基不变。5.3.3 2月份所需仓库面积20时的最优决策此问题属于约束条件右端常数项 b 的变化，即约束条件：x12 + x13 + x14 + x21 + x22 + x23 10，右端的常数项20的变化对最优解的影响由5.2.4的分析结果可知：Righthand Side Ranges:Current Allowable AllowableRow RHS Increase Decrease3 10.00000 2.000000 INFINITY在最优决策不变的情况下2月份所需仓库面积的变化范围，即第二个约束条件右端常数项的可变化范围为-,12。，因为2月份所需仓库面积变为20,大于12，所以最优解变化。输入程序得下图四：图四由图四可知2月份所需仓库面积20时的最优决策x11=3.0 x12=0 x13=0 x14=12.0 x21=0 x22=0 x23=0 x31=8.0 x32=0 x41=0所付租借费用最小为118400.0。6 创新内容6.1 1个月租借期限的合同期内的租费在何范围内变化时最优决策不变？此问题属于目标函数系数的变化，即x11、x21、x31、x41的系数变化对最优决策的影响，决定条件有四个，取公共部分，即最小范围。由5.2.4分析可得：Current Allowable AllowableVariable Coefficient Increase DecreaseX11 2800.000 400.0000 0.000000X21 2800.000 INFINITY 2800.000X31 2800.000 400.0000 1100.000X41 2800.000 INFINITY 1100.000在最优决策不变的情况下X11的可变化范围为大于2800小于3200；X21的可变化范围为大于0；X31的可变化范围为大于1700小于3200；X41的可变化范围为大于1700。取公共部分得：1个月租借期限的合同期内的租费在大于2800小于3200的范围内变化时最优决策不变。6.2 4月份仓库借费用800元/100m2时的最优解？因为4个月的变量只有X14，且此问题属于目标函数系数的变化，所以是求目标函数中X41的系数变化对最优解的影响。由2.2.3分析可得：Current Allowable AllowableVariable Coefficient Increase DecreaseX14 7300.000 0.000000 1700.000在最优决策解的情况下X14的可变化范围为大于5600小于7300。因为X14的系数变为800，超出可变化范围，所以代入程序得下图四：图五由图五可知 最优解如下：x11=0.0 x12=0 x13=0 x14=20.0 x21=0 x22=0 x23=0 x31=8.0 x32=0 x41=0 min=16000.0 即所付租借费用最小为16000.0。6.3 4月份所需仓库面积在何范围内变化时最优基不变？此问题属于约束条件右端常数项的变化，即约束条件：x14 + x23 + x32 + x41 12，右端的常数项的变化对最优基的影响。由5.2.4分析可得：Righthand Side Ranges: Current Allowable Allowable Row RHS Increase Decrease 5 12.00000 3.000000 2.000000在最优决基不变的情况下4月份所需仓库面积的变化范围，即第二个约束条件右端常数项的可变化范围为大于10小于15时4月份所需仓库面积在何范围内变化时最优基不变。 7 课程设计总结 说来挺惭愧的，最后用的程序是在网上下载并调试的