运筹学实验.doc

运筹学实验报告班级：姓名：学号：学期：成都理工大学 核技术与自动化学院2013 年 12 月 30日实验进度安排序号名称学时1生产计划安排问题22对偶理论应用23其他问题24综合案例2实验一 生产计划安排问题一、 实验目的（一）实验目的：安装WinQSB软件，了解WinQSB软件在Windows环境下的文件管理操作，熟悉软件界面内容，掌握操作命令。用WinQSB软件求解线性规划。（二）内容和要求：安装与启动软件，建立新问题，输入模型，求解模型，结果的简单分析。（三）操作步骤：1.将WinQSB文件复制到本地硬盘；在WinQSB文件夹中双击setup.exe。2.指定安装WinQSB软件的目标目录（默认为C: WinQSB）。3. 安装过程需输入用户名和单位名称（任意输入），安装完毕之后，WinQSB菜单自动生成在系统程序中。4.熟悉WinQSB软件子菜单内容及其功能，掌握操作命令。5求解线性规划。启动程序 开始程序WinQSBLinear and Integer Programming 。6观赏例题 点击FileLoad Problemlp.lpp, 点击菜单栏Solve and Analyze或点击工具栏中的图标用单纯形法求解，观赏一下软件用单纯形法迭代步骤。用图解法求解，显示可行域，点击菜单栏Option Change XY Ranges and Colors，改变X1、X2的取值区域（坐标轴的比例），单击颜色区域改变背景、可行域等8种颜色，满足你的个性选择。二、 实验内容实验1 伟恩精密设备制造有限公司生产计划安排问题 伟恩精密设备制造有限公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？三、 实验分析（保留主要的步骤和结果）解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。 求 xi 的利润：利润 = 售价 - 各成本之和 产品甲全部自制的利润 =23-(3+2+3)=15 产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13 产品乙全部自制的利润 =18-(5+1+2)=10 产品乙铸造外协，其余自制的利润 =18-(6+1+2)=9 产品丙的利润 =16-(4+3+2)=7可得到 xi （i = 1,2,3,4,5） 的利润分别为 15、10、7、13、9 元。通过以上分析,可建立如下的数学模型:目标函数： Max = 15x1 + 10x2 + 7x3 + 13x4 + 9x5 约束条件： 5x1 + 10x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0点击fileNew problem建立新问题输入数据变量为5，约束是3点击slove and analyze 键得出最终结果：点击resultssolution summary得到最优解点击constraint summary得到约束条件摘要点击sensitivity analysis of OBJ得到目标函数系数灵敏度分析 点击sensitivity analysis of RHS得到约束条件常数灵敏度分析 点击combined report 得到综合分析报告点击final simplex tableau显示最后一张单纯形表 实验二：对偶理论（一）实验目的：掌握winQSB软件写对偶规划，灵敏度分析和参数分析的操作方法（二）内容和要求：用winQSB软件完成下列问题1写出对偶线性规划，变量用y表示。2求原问题及对偶问题的最优解。3分别写出价值系数cj及右端常数的最大允许变化范围。4目标函数系数改为C（5，3，6）同时常数改为b=（120，140，100），求最优解。5增加一个设备约束和一个变量x4，系数为（c4,a14,a24,a34,a44）=（7，5，4，1，2），求最优解。6在第5问的模型中删除材料2的约束，求最优解。7原模型的资源限量改为，分析参数的变化区间及对应解的关系，绘制参数与目标值的关系图。（三）操作步骤1启动线性规划与整数规划程序(Linear and Integer Programming)，建立新问题，输入数据并存盘。2点击FormatSwitch to Dual Form，点击FormatSwitch to Normal Model Form，点击EditVariable Name，分别修改变量名为yi。3再求一次对偶返回到原问题，求解模型显示最优解。查看最优表中影子价格（Shadow Price）对应列的数据写出对偶问题的最优解。4在综合分析报告表中查找Allowable min(max)对应列，写出价值系数及右端常数的允许变化范围。5修改模型数据并求解。6点击EditInsert a Contraint 插入一个约束，点击EditInsert a Variable 插入一个变量，求解。7点击EditDelete a Contraint，选择要删除的约束C2，求解。8对原问题求后，点击ResultsPerform Parametric Analysis，在参数分析对话框中选择右端（RHS），输入参数的系数（1，3，1），求解后写出（或打印）参数分析结果。9点击ResultsGraphic Parametric Analysis，打印参数与目标值的关系图。10注意事项。7个问题是独立求解和分析，每个问题都是针对原线性规划分析和求解，每一步都必须回到原模型。技巧：作完一个问题后退出所有活动窗口，打开刚才储存的原问题文件。这样不必修改数据。三.实验分析（保留主要的步骤和结果）根据题意知道变量（Number of Variables）和约束条件(Number of Constraints)各有三个，设置如下图。其余选择默认即可。点”OK”得到下表，根据实验条件输入数据并存盘。1.得到对偶问题极其模型（1）点击FormatSwitch to Dual Form，得到对偶问题的数据表如下：点击FormatSwitch to Normal Model Form，得到对偶模型。点击EditVariable Name.分别将变量X修改变量名为y点上图中的“ok”, 得到以y为变量的对偶模型2.返回原问题求出最优解及最优值再求一次对偶返回到原问题，求解模型显示最优解为X=(25,25,0)，最优值为Z=150。查看最优表中影子价格(Shadow Price)对应列的数据就是对偶问题的最优解为 Y=(0.5,1.0，0)见表5，还可以根据性质求出，显示最终单纯形表。松弛变量检验数的相反数就是对偶问题的最优解。3求价值系数c及右端常数的最大允许变化范围.在综合分析报告表中查找Allowable min(max)对应列，写出价值系数及右端常数的允许变化范围。由表最后两列价值系数Cj (j=1,2,3) 取最大允许范围分别是2，6 1.3333,4-,8右端常数bi(9=1,2,3)的最大允许变化范围分别是66.6667,20050,120100, +4 修改目标函数系数，常数向量并求最优解（1）修改系数和常数向量，把原条件的C=（4，2，3）变为（5，3，6）常数由（100，100，120）变为（120，140，100）。修改后如下：（2）按下(solve and analyze)得到下表：由表中可以得到修改模型的最优解为X=(20,20,10 )。最优值为Z=220.5. 改变约束条件和系数求解（1）插入约束条件点击EditInsert a Contraint 选择在结尾处插入变量（The end）再按下“ok”插人一个约束6x+5x+x200，(2)修改相应系数如（1）中一样操作，点击EditInsert a Variable插入一个变量，选择在末尾添加。改变系数： (c，a，a，a，a)=(7，5，4，1，2)， 按下solve and analyze得到下列结果：由H表中可以查得：最优解为：X=(14.2857,0,0,14.2857),最优值为Z=157.1429.6. 删除约束条件操作其操作类似于添加约束条件：点击EditDelete a Contraint，选择要删除的约束C2点“ok”再求解即可。得到如下结果：由表中可以查得：最优解为X=(30.7692,0,0,7.6923),最优值为Z=176.9231.7. 改变资源限量并分析绘图（1）返回到原问题数据表，先求解。目标函数系数由两部分构成，记住参数u的系数（1，3，-1）对原问题求解后，点击ResultsPerform Parametric Analysis，在参数分析对话框中选择目标函数（Objective Function）,（2）输入参数u的系数(1，3，-1)，（3）确定后显示下表。表中没有显示参数在区间内的最优解，这是因为最优解是参数u的函数，只有给定了具体参数值才能得到具体的最优解，（4）由上表知，将参数u奉承5个区间讨论，在不同区间显示了目标函数值的变化区间及其变化率（slope）,出基变量和进基变量（Leaving Variable Entering Variable）点击ResultsGraphicParametric analysis打印参数与目标值的关系图。 显示下图图3-18管理报告：某厂排气管车间生产计划的优化分析1问题的提出排气管作为发动机的重要部件之一，极大地影响发动机的性能。某发动机厂排气管车间长期以来，只生产一种四缸及一种六缸发动机的排气管。由于其产量一直徘徊不前，致使投资较大的排气管生产线，一直处于吃不饱状态，造成资源的大量浪费，全车间设备开动率不足50%。为了充分发挥车间的潜力，该车间在厂部的大力协助下主动出击，一方面争取到了工厂自行开发的特殊机型排气管生产权，另一方面瞄准国际市场以较低的价格和较高的质量赢得了世界两大著名汽车公司CUMMINS和FORD的信任，成为其8种型号排气管最具竞争实力的潜在供应商。如果这8种排气管首批出口进入国际市场畅销的话，后续订单将会成倍增长，而且两大公司有可能逐步减少其它公司的订单，将其它型号排气管全部转移到该车间生产。针对这种状况，该车间组织工程技术人员对8种排气管的产品图纸进行了评审，进行了工艺设计和开发（编排工艺流程图、进行PFMEA分析和编制控制计划），进行样品试制，同时对现生产能力和成本进行了认真细致的核算和预测工作。如何调整当前的生产计划，是否增加设备或改造生产线，其它类型新产品需要多长时间才能投入生产等一系列问题尚缺乏科学的、定量的依据。而目前厂部和车间最关心的资源问题，主要是加工设备的生产能力。一位工商管理硕士（MBA)毕业的厂部管理人员马上想到，这是一个合理利用有限资源，如何制定生产计划使产出最大的优化问题，理论上可以用线性规划方法解决。2生产概况及有关资料（1）车间概况该车间按两班制生产，每班8小时，标准工作日为22天。车间现有员工30名，其中生产工人27人，每月安排职工政治学习及业务培训时间为4小时，进行文明生产等非生产性工作每月平均2小时/人月，排气管工废按产量的1%计算，料废按2%计算。 车间生产工人工作时间按44小时/人周（每月4周）进行考核。（2）生产状况该车间排气管生产为10道工序，分别在不同的10类机床上进行加工，每种排气管所占用的设备时间如表C-1所示。各种排气管的成本构成如表C-2所示， 目前，由于市场不景气，排气管生产的上工序即铸造厂产能富裕，只要资金到位该厂可准时、足量供货，而且品种可以保证。而出口排气管外商的的资金可以及时到位，并且许诺如果需要可预付50%以上的预付款，只不过对某些产品提出了特殊要求，即第一种、第七种排气管月产量均不能低于10000，第三种不能低于5000/月，第六种排气管产量不高于60000/月，第二和第四种排气管配对使用，但由于第二种排气管使用中易损，故每月必须多生产3000根。因此原材料来源和资金不足是增加生产的制约因素。制约该车间排气管产量的主要是设备计划外停工及基本生产工人工时，即设备与人力资源。根据以往经验，各设备加工能力见表C-3。表C-1 8种排气管设备消耗时间（单位：台时/1000件） 产品 时间设备123456781.平面铣床44.54.85.85.24.04.65.62.卧铣床3.94.54.35.04.94.45.14.83.组合钻5.95.85.76.36.56.06.66.44.单面铣床3.53.03.74.03.83.04.13.45.攻丝床5.86.25.76.46.36.06.56.26.精铣床5.55.74.76.05.95.26.25.67.扩孔钻床3.93.84.04.13.73.54.13.68.摇臂钻床4.14.04.04.34.23.84.34.39.去毛刺机2.52.92.73.03.02.53.12.810.清洗机2.82.92.13.23.02.53.23.0总计41.943.341.748.146.540.947.845.7表C-2 8种排气管成本构成表（单位：元/根） 产品项目12345678毛坯价格981049411210697104102辅料消耗22222222动能消耗1010101010101010工具等消耗10131214158911管理费用1.4551.0991.211.441.1881.22651.3081.56税收151614.81716.514.515.615.5售价150160.1149172166145.6157.8155.8利润（元）13.54514.00114.9915.5615.31212.873515.89213.74注：表中售价为含税价。表C-3 设备加工能力一览表 设备台数（台）标准工作日（日/月）标准工作日长度（时/日）台均维修保养时间（时/月）月可利用工时实际工时（99%）1.平面铣床42216413921378 2.卧铣床42216214001386 3.组合钻床62216520822061 4.单面铣床222162700693 5.攻丝床62216420882067 6.精铣床42216313961382 7.扩孔钻床42216813761362 8.摇臂钻床42216613841370 9.去毛刺机222162700693 10.清洗机222162700693 根据以上资料，请你完成下列3和4两项工作。3制定利润最大的生产计划（1）建立线性规划数学模型（2）用WinQSB软件求解（3）写出各种产品月生产量及月总利润。4结果分析（1）分析各种资源的利用情况，根据线性规划得到的结果，如何重新调整资源（2）利用影子价格分析各资源对利润的边际贡献，分析哪些是影响增加利润的关键设备（3）如果企业现有一订单，各种排气管的需要量是：15000，5000，5000，3000，15000，60000,10000,60000（根）。正常时间内1个月能否完成任务，如果不能完成，哪些资源需要加班多少时间，假定加班不额外增加成本。（4）对现有资源和生产能力进行分析，提出你对排气管车间整个计划的看法和建议。解：车间基本生产工人工时计算如下：S=27(228-2-4)=4590人时/月按产量1%的工废实际可用时间：4590/1.14544每种设备月实际可利用工时如表C2最后一列。从表C3中减去料废成本后每种排气管利润如下表所示：产品项目12345678毛坯价格981049411210697104102料废成本1962.081.882.242.121.942.082.04辅料消耗22222222动能消耗1010101010101010工具等消耗10131214158911管理费用1.4551.0991211441.1881.22651.3081.56税收151614.81716.514.515.615.5售价150160.1149172166145.6157.8155.8利润（元）13.54514.00114.9915.5615.31212.873515.89213.74根据给定的条件及要求,设x1，x2，x8分别为第一种、第二种第八种排气管的月产量，月产量单位为1000根/月。将目标函数取为每月的总产品利润，得出关于月计划的线性规划模型为：maxZ=11.585X1+11.921X2+13.11X3+13.32X4+13.192X5+10.9335X6+13.812X7+11.7X8s.t454441.9+43.9+42.3+47.8+4.0+4.5+4.8+5.8+5.2+4.0+4.6+5.613783.9+4.5+4.3+5.0+4.9+4.4+5.1+4.813865.9X1+5.8X2+5.7X3+6.3X4+6.5X5+6.0X6+6.6X7+6.4X820613.5X1+3.0X2+3.7X3+4.0X4+3.8X5+3.0X6+4.1X7+3.4X86935.8X1+6.2X2+5.7X3+6.4X4+6.3X5+6.0X6+6.5X7+6.2X820675.5X1+5.7X2+4.7X3+6.0X4+5.9X5+5.2X6+6.2X7+5.6X813825.9X1+3.8X2+4.0X3+4.1X4+3.7X5+3.5X6+4.17+3.6X813624.1X1+4.0X2+4.0X3+4.3X4+4.2X5+3.8X6+4.3X7+4.3X813702.5X1+2.9X2+2.7X3+3.0X4+3.0X5+2.5X6+3.1X7+2.8X86932.8X1+2.9X2+2.1X3+3.2X4+3.0X5+2.5X6+3.2X7+3.0X8693X110 X2X4=3X35 X660 X71X1,X2,X3,X4,X5,X6,X7,X803.1打开线性规划模块3.2 输入数据及运行结果3.2.1制定利润最大的生产计划（1） 数学模型建立如上；（2） 求解如下：由以上计算结果可知，问题最优解为：X=(10000,3000,82773,0.0,0,10,0)；目标函数值即最大利润值为Z1374888(元)；（3） 各种产品月生产量及月总利润月生产应如下安排：第一到第八种排气管分别安排10000,3000,82773,0,0,0,10000,0根；月最大可获利1374888元。3.2.2结果分析（1） 资源利用率见下表：资源月可利用工时实际利用工时剩余资源实际利用率1.平面铣床1378496.8106881.19 36.05%2.卧铣床1386459.4241926.58 33.15%3.组合钻2061614.20641446.79 29.80%4.单面铣床693391.2603301.74 56.46%5.攻丝床2067613.40641453.59 29.68%6.精铣床1382523.1333858.87 37.85%7.扩孔钻床1362422.4922939.51 31.02%8.摇臂钻床1370427.0922942.91 31.17%9.去毛刺机693288.1872404.81 41.59%10.清洗机693242.5234450.48 35.00%人工454445440.00 100.00%结果表明，各种设备负荷都远没有达到饱和，而人工已经满负荷运转，所以应提高人工的有效工时。（2） 人工工时的影子价格等于0.3099，所有设备的影子价格全等于零，因此人工工时是制约车间产量或利润增长的关键资源。（3） 将模型改为：maxZ=11.585+13.11+13.32+13.192+10.9335+13.812+11.7s.t.41.9+43.9+42.3+47.8+45444.0+4.5+4.8+5.8+5.2+4.0+4.6+5.613783.9+4.5+4.3+5.0+4.9+4.4+5.1+4.813865.9X1+5.8X2+5.7X3+6.3X4+6.5X5+6.0X6+6.6X7+6.4X820613.5X1+3.0X2+3.7X3+4.0X4+3.8X5+3.0X6+4.1X7+3.4X86935.8X1+6.2X2+5.7X3+6.4X4+6.3X5+6.0X6+6.5X7+6.2X820675.5X1+5.7X2+4.7X3+6.0X4+5.9X5+5.2X6+6.2X7+5.6X813825.9X1+3.8X2+4.0X3+4.1X4+3.7X5+3.5X6+4.17+3.6X813624.1X1+4.0X2+4.0X3+4.3X4+4.2X5+3.8X6+4.3X7+4.3X813702.5X1+2.9X2+2.7X3+3.0X4+3.0X5+2.5X6+3.1X7+2.8X86932.8X1+2.9X2+2.1X3+3.2X4+3.0X5+2.5X6+3.2X7+3.0X8693X115 X25 X35 X43 X515 X660 X710 X860X1,X2,X3,X4,X5,X6,X7,X80用WinQSB软件求解，结果显示见下表：令所有产量为等式约束，给定一个较大的人工工时数，如10000小时，求解后显示工时的参数变化区间为（7516.4，M）,见下表所示。说明人工工时最少要加班75174544=2973小时。设备时间有剩余。（4） 该车间设备的生产能力已经相当充足，但人工的严重不足限制了生产。而且人工加班不是长久之计，所以解决方案是增加生产工人人数、提高设备的无人看管性或改进工艺降低人工工时消耗。配料问题某饲料公司生产肉用种鸡配合饲料，每千克饲料所需营养质量要求如表C4所示。表C4营养成分肉用种鸡国家标准肉用种鸡公司标准产蛋鸡标准代谢能2.72.8Mcal/kg2.7Mcal/kg2.65Mcal/kg粗蛋白135 145g/kg135 145g/kg151g/kg粗纤维Solve the problem，问题已解决且存在解，求解结果如图C-3所示:图C-3：（2）按照肉用种鸡国家标准求1千克配合饲料中每种原料各配多少成本最低。建立数学模型并WinQSB求解，由模型可知目标函数和约束条件，输入到Linear and Integer program的主窗体中设置如图C-4:图C-4：输入数据后得到图C-5：图C-5：点击Solve and Analyze-Solve the problem，问题已解决且存在解，求解结果如图C-6所示：图C-6：（3）原材料结构调整公司采购了一批花生饼,单价是0.6元/kg，代谢能到有机磷的含量分别为（2.4,38,120,0,0.92,0.15,0.17）,求肉用种鸡成本最低的配料方案。1. 按照肉用种鸡公司标准在调整后方案，用WinQSB来处理数据如图C-72. :图C-7:输入数据后得到图C-8：图C-8:点击Solve and Analyze-Solve the problem，问题已解决且存在解，求解结果如图C-9所示：图C-9：2. 按照肉用种鸡国家标准在调整后方案，用WinQSB来处理数据如图C-10所示：图C-10：输入数据后得到图C-11:图C-11：如图点击Solve and Analyze-Solve the problem，问题已解决且存在解，求解结果如C-12所示：图C-12:（4）求产蛋鸡的最优饲料配方方案由模型可知，目标函数为minimization，变量数12个，约束条件9，变量类型为continuous，设置问题属性如图C-13所示：图C-13:输入数据得到图C-14：图C-14:点击Solve and Analyze-Solve the problem，问题已解决且存在解，求解结果如图C-15和C-16示，“the problem is infeasible”，这个问题没有最优的配料方案，只能根据公司的实际情况而选择相应的满意方案来进行：图C-15：图C-16:（5）价格系数灵敏度分析公司考虑到未来鱼粉、骨粉和碳酸钙将要涨价，米糠将要降价，价格变化率都是原价的r %试对两种产品配方方案进行分析。1. 肉用鸡按公司标准问题在WinQSB分析结束后，Results-Sensitivity Analysis of OBJ可以的到如图C-17：图C-17：图中米糠，鱼粉，骨粉和碳酸钙的价格cj（j=4，7，10，11）满足使得最优解不变的大小变化范围分别为：0.0754, +）,1.0898,+）,0.1920,0.6343,1.0201,1.5423;四种原料的价格分别变化时，不影响原配料方案的r%波动的允许范围为：当且仅当鱼粉涨价时，变化率满足r%=0%,又有c7的没有最大限，说明鱼粉的价格的涨价情况下的价格变化率可以没有限制的波动，均不会使得原有的原料配方方案不会发生变化；当且仅当骨粉涨价时，变化率满足r%=0%,有c10的最大限为0.6343，r%的最大不使公司原有的最优配料方案发生变动的值为(0.6343-0.56)/0.56*100%=13.27%，即0%=r%=0%的同时要满足变化率是的c11的最大限为1.5423，即0%=r%=37.71%，当r%在这个范围内波动时，原配方不会变化，若在这个范围之外，公司就要对配料方案进行调整；当仅米糠降价时，价格变化率的最大值应不超过（0.22-0.0754）/0.22=65.73%，当0%=r%=65.73%时，米糠降价不会影响公司的原配料方案，变化率超过这个范围时，就需要对配料方案进行调整才满足市场需求；若市场中四种原料价格同时变动时，且变化率为r%则，有可以得出当r%得波动范围在0%=r%Sensitivity Analysis of OBJ可以的到如图C-18:图C-18:图中米糠，鱼粉，骨粉和碳酸钙的价格cj（j=4，7，10，11）满足使得最优解不变的大小变化范围分别为:0.1658,0.3360,0.9210,+）,-2.5718,0.6744,0.9675,5.3507;四种原料的价格分别变化时，不影响原配料方案的r%波动的允许范围为：当且仅当鱼粉涨价时，变化率满足0%=0%,有c10的最大限为0.6744，r%的最大不使公司原有的最优配料方案发生变动的值为(0.6744-0.56)/ 0.56*100%=20.43%，即0%=r%=0%的同时要满足变化率是的c11的最大限为5.3507，即0%=r%=377.74%，当r%在这个范围内波动时，原配方不会变化，若在这个范