运筹与优化算法实现

1、. .成绩*工程学院实 习 报 告实 习 名 称运筹与优化算法实现(运筹学与控制论方向)学 院 专 业班 级学 生 姓 名学 号实 习 地 点指 导 教 师 实习起止时间：2012年05月07日至2012年05月11日1.实验目的与要求在了解“运筹学及应用与“图与网络分析根本的优化模型的根底上，理解其根本原理，掌握其根本的算法，会用这些模型与算法，用相关的软件编写程序，来解决有关的实际问题，到达对创新能力、实践能力的培养要求。2.实习方案1问题分析、查找相关文献第一天2模型建立第二天3设计算法求解第三天4算法的程序实现并进展结果分析第四天5整理实习报告、实习日志等材料第五天3.实习主要内容1实

2、习题目北方印染公司需要的技工分为初级、中级、高级三个层次。统计资料显示：培养出来的每个初级工每年可为公司增加产值1万元，每个中级工每年可为公司增加产值4万元，每个高级工每年可为公司增加产值5.5万元。公司方案在今后三年拨出150万元作为职工的培训费，第一年投资55万元，第二年投资45万元，第三年投资50万元。通过公司过去培养初级工、中级工、高级工的经历并经过咨询，预计培养一名初级工，在高中毕业后需要一年，费用为1000元；培养一名中级工，高中毕业后需要三年的时间，第一年和第二年的费用为3000元，第三年的费用为1000元；培养一名高级工，高中毕业后也需要三年的时间，其中第一年的费用为3000元

3、，第二年的费用为2000元，第三年的费用为4000元。目前公司共有初级工226人，中级工560人，高级工496人。假设通过提高目前技术工人的水平来增加中级工和高级工的人数，其培养时间和培养的费用分别是：由初级工培养为中级工需要1年时间，费用为2800元；由初级工直接培养为高级工需要两年，第一年费用为2000元，第二年费用为3200元；由中级工培养为高级工需要1年，费用为3600元。由于公司目前的师资力量缺乏，教学环境有限，每年可培训的职工人数受到一定的限制，根据目前情况，每年在培养的初级工不超过90人，中级工不超过80人，高级工不超过80人。2模型的建立为了方便理解依题要求，所作表如以下图投资

4、培训费用元第一年第二年第三年高中生升初级工1000高中生升中级工300030001000高中生升高级工300020004000初级工升中级工2800初级工升高级工20003200中级工升高级工3600公司目前人数每人每年为公司增值每年可培训初级工22610000元90中级工56040000元80高级工49655000元80依题，解：设变量xij为第i类培训方式在第j年培训的人数，如下表：第一年第二年第三年高中生升初级工x11X12X13高中生升中级工X21X22X23高中生升高级工X31X32X33初级工升中级工X41X42X43初级工升高级工X51X52X53中级工升高级工X61X62X63

5、那么每年底培养出来的初级工、中级工、高级工人数分别为，如图：第一年年底第二年年底第三年年底初级工X11X12X13中级工X41X42X21+x43高级工X61X51+x62X31+x52+x63依题分析建立数学模型，为了使公司创造更大的经济效益确定约束条件，每培养出的初级工为公司增加产值1万元，说明利润为1万元，初级工创造的总利润为x11+x12+x13；每培养出的中级工为公司增加4万元，中级工创造的总利润为4(x41+x42+x21+x43)；每培养出的高级工为公司增加5.5万元，高级工创造的总利润为5.5(x61+x62+x63+x51+x52+x31)。所以目标函数为maxZ=x11+x

6、12+x13+4(x41+x42+x21+x43)+5.5(x61+x62+x63+x51+x52+x31)如图表显示的数据进展分析并得出约束条件：第一年的本钱分析：第一年，由高中生培养到初级工费用1000元，由高中生培养到中级工第一年费用3000元，高中生培养到高级工第一年费用3000元，由初级工培养到中级工2800元，初级工培养到高级工2000元，由中级工培养到高级工2000元，每年公司投资的费用有所不同第一年投资55万元，因此得出数据：1000x11+3000x21+3000x31+2800x41+2000x51+3600x61550000第二年的本钱如同以上分析: 1000x12+30

7、00x21+2000x31+2800x42+3200x51+2000x52+3600x62450000第三年的本钱如同以上分析:1000x13+1000x21+4000x31+2800x43+3200x52+3600x63500000 由于目前公司有初级工、中级工的人数分别是226人，560人得出约束条件X41+x42+x43+x51+x52226X61+x62+x63560根据目前情况，每年在培养的初级工不超过90人，中级工不超过80人，高级工不超过80人。第一年培养初级工X1190第二年培养初级工x1290第三年培养初级工x1390第一年培养中级工x21+x4180第二年培养中级工x21+

8、x4280第三年培养中级工x21+x4380第一年培养高级工x31+x51+x6180第二年培养高级工x31+x51+x52+x6280第三年培养高级工x31+x52+x6380分析数据并列出以上约束条件，利用计算软件，为了方便输入条件，所以设x11x1，x12x2,x13x3,x21x4,x31x5,x41x6,x42x7,x43x8,x51x9,x52x10,x61x11,x62x12,x63x133模型的求解含编程求解计算结果如下*最优解如下* 目标函数最优值为 : 2319.428 变量 最优解 相差值 - - - x1 38 0 x2 0 .429 x3 90 0 x4 0 8.48

9、6 x5 0 8.114 x6 80 0 x7 57.857 0 x8 80 0 x9 0 3.329 x10 0 3.214 x11 80 0 x12 80 0 x13 80 0 约束 松弛/剩余变量 对偶价格 - - - 1 0 .001 2 0 .001 3 248000 0 4 8.143 0 5 320 0 6 52 0 7 90 0 8 0 1 9 0 1.2 10 22.143 0 11 0 4 12 0 1.9 13 0 .357 14 0 5.5 目标函数系数范围 : 变量 下限 当前值 上限 - - - - x1 0 1 1.429 x2 无下限 1 1.429 x3 0

10、1 无上限 x4 无下限 4 12.486 x5 无下限 5.5 13.614 x6 2.8 4 无上限 x7 2.8 4 4.278 x8 0 4 无上限 x9 无下限 5.5 8.829 x10 无下限 5.5 8.714 x11 3.6 5.5 无上限 x12 5.143 5.5 无上限 x13 2.286 5.5 无上限 常数项数范围 : 约束 下限 当前值 上限 - - - - 1 512000 550000 602000 2 288000 450000 472800 3 252000 500000 无上限 4 217.857 226 无上限 5 240 560 无上限 6 38 9

11、0 无上限 7 0 90 无上限 8 0 90 338 9 61.429 80 88.143 10 57.857 80 无上限 11 0 80 88.143 12 65.556 80 90.556 13 73.667 80 125 14 0 80 400计算得出：最优解为2319.428最优数目标值：X11=38 x12=0 x13=90 x21=0 x31=0 x41=80 x42=57.857 x43=80 x51=0 x52=0 x61=80 x62=80 x63=80高中毕业生中培养的初级技工128人，由高中毕业生中培养的中级技工0人，高中毕业生中培养的高级技工0人，培养初级工到中级工

12、217人，培养初级工到高级工0人，培养中级工到高级工240人。4结果分析依据得出的最优解和最优目标函数值可知，要想使公司利用有限的培训费培养更多的技术工人并为公司创造更大的经济利益，就要确定第一年在投资的55万元中应培训初级工人数，高中生中培养初级技工的人数为38人；培养的中级工人数中，初级技工升中级技工的人数80人；培养的高级工中中级工升高级工80人，这样第一年中培养的初、中、高级工的人数各没有超过90、80、80人，满足公司要求。第二年年底，在公司投资的45万元中培养初级工人数，不培养高级生升初级技工；培养的中级工要求，初级工升中级工人数为57人；培养高级工要求，不培养初级升高级工，培养中