运筹学实验指导书

实验一、线性规划综合性实验 一、实验目的与要求： 使学生掌握线性规划建模的方法以及至少掌握一种线性规划软件的使用，提高学生应用线性规划方法解决实际问题的实践动手能力。通过实验，使学生更深入、直观地理解和掌握线性规划的基本概念及基本理论和方法。要求学生能对一般的线性规划问题建立正确的线性规划数学模型，掌握运筹学软件包线性规划模块的操作方法与步骤，能对求解结果进行简单的应用分析。 二、实验内容与步骤： 1.选择合适的线性规划问题 学生可根据自己的建模能力，从本实验指导书提供的参考选题中或从其它途径选择合适的线性规划问题。 2.建立线性规划数学模型 学生针对所选的线性规划问题，运用线性规划建模的方法，建立恰当的线性规划数学模型。 3.用运筹学软件求解线性规划数学模型 学生应用运筹学软件包线性规划模块对已建好的线性规划数学模型进行求解。 4.对求解结果进行应用分析 学生对求解结果进行简单的应用分析。 三、实验例题： (一)线性规划问题 某集团摩托车公司产品年度生产计划的优化研究 1)问题的提出 某集团摩托车公司是生产各种类型摩托车的专业厂家，有30多年从事摩托车生产的丰富经验。近年来，随着国内摩托车行业的发展，市场竞争日趋激烈，该集团原有的优势逐渐丧失，摩托车公司的生存和发展面临严峻的挑战。为此公司决策层决心顺应市场，狠抓管理，挖潜创新，从市场调查入手，紧密结合公司实际，运用科学方法对其进行优化组合，制定出1999年度总体经济效益最优的生产计划方案。 2)市场调查与生产状况分析 1998年，受东南亚金融风暴的影响，国内摩托车市场出现疲软，供给远大于需求，该集团的摩托车生产经营也出现开工不足、库存增加和资金周转困难等问题。 该集团共有三个专业厂，分别生产轻便摩托车、普通两轮车和三轮摩托车三大系列产品。在市场调查的基础上，从企业实际出发普遍下调整车出厂价和目标利润率，有关数据如下 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 1 产品系列 轻便摩托车 普通两轮车 三轮摩托车 型号 M1 M2 M3 M4 M5 M6 M7 M8 M9 出厂价 1800元 2100元 2300元 3800元 4800元 6500元 8200元 8800元 9200元 目标利润率 6% 7% 10% 5% 6% 8% 6% 6% 6% 最大生产能力 50000辆 60000辆 10000辆                     1999年该集团可供摩托车生产的流动资金总量为4000万元，年周转次数为5次，生产各种型号摩托车资金占用情况如下表2 型号 M1 M2 M3 M4 M5 M6 M7 M8 M9 占用资金(元/辆) 1520 1700 1850 3200 4100 5400 6000 7450 8600                     由于发动机改型生产的限制，改型车M3和M6两种车1999年的生产量预测数分别为20000辆和22000辆。 经预测三种系列摩托车1999年产销率及仓储面积占用情况如下表3 产品系列 轻便摩托车 普通两轮车 三轮摩托车 产销率 97% 97% 92% 单车占用面积 1个仓储单位 1.5个仓储单位 3个仓储单位         公司1999年可提供的最大仓储能力为3000个仓储单位，库存产品最大允许占用生产资金为1600万元。 根据以上情况，该公司应如何制定1999年度总体经济效益最优的生产计划方案？ (二)线性规划建模 设Xj表示生产Mj型摩托车的数量(j=1,2,…,9),则总利润最大的摩托车产品生产计划数学模型为： MaxZ=0.18×0.06X1+0.21×0.07X2+0.23×0.1X3+0.38×0.05X4+0.48×0.06X5+0.65×0.08X6+0.82×0.06X7+0.88×0.06X8+0.92×0.06X9 =0.0108X1+0.0147X2+0.023X3+0.019X4+0.0288X5+0.052X6+0.0492X7+0.0528X8+0.0552X9 满足  X1+X2+X3≤50000                                                            (1) X4+X5+X6≤60000                                                            (2) X7+X8+X9≤10000                                                            (3) 0.152X1+0.17X2+0.185X3+0.32X4+0.41X5+0.54X6+0.6X7+0.745X8+0.86X9≤4000×5    (4) X3≤20000                                                                    (5) X6≤22000                                                                    (6) 0.03×(X1+X2+X3)+0.03×1.5(X4+X5+X6)+0.08×3(X7+X8+X9)≤3000                  (7) 0.00456X1+0.0051X2+0.00555X3+0.0096X4+0.0123X5+0.0162X6+0.048X7+0.0596X8+0.0688X9≤1600 (8) Xj≥0(j=1,2,3,4…9) 模型说明：约束(1)、(2)、(3)分别表示三种系列摩托车的最大生产能力限制； 约束(4)表示摩托车的生产受流动资金的限制； 约束(5)和(6)表示M3和M6两种车产量受发动机供应量限制； 约束 (7)表示未销售的产量受库存能力的限制； 约束(8)表示未销售产品占用资金的限制。 (三)模型求解 由管理运筹学软件包中可知最优解为X=(0，26000，20000，0，0，22000，0，0，0)T,最优值Z=1986.2万元。 说明一下，摩托车生产数量是整数，应该用整数规划来求解，但由于摩托车生产数量较大，故采用线性规划求解，四舍五入取整，误差很小。 (四)结果分析 1)根据计算结果，能够使年利润达到最大化的产品生产计划是：M2型车生产26000辆，M3型车生产20000辆，M6型车生产22000辆，共计68000辆。目标利润为1986.2万元。 2)由以上求解结果可知，三种系列的摩托车生产能力均有富余，尤其是三轮摩托车未安排生产，生产能力完全剩余；摩托车生产的流动资金完全用完，M3和M6两种车型的发动机也完全用完；库存容量和库存车占用的生产资金额度也有富余。由影子价格也可看出，流动资金、M3和M6两种车型的发动机是希缺的，若增加这三种资源，可提高总利润，并且增加流动资金可使总利润提高最快。因此上述产品生产计划在实践中应作出适当调整。 (五)方案调整分析 1)增加流动资金 一是流动资金总量不变，加速资金周转，比如年周转次数由5次增至6次，其它条件不变，求解 二是在资金周转加速的基础上，增加流动资金总量，比如增加1000万元，由流动资金的影子价格可看出，总利润有更大提高，求解 2)增加M3和M6两种车型的发动机 若M3和M6两种车型的发动机各增加5000台，在上述条件基础上，求解 3)合理安排生产品种 为保持公司各种系列摩托车有一定的市场占有率，需对上述结果作出修改，要保证三轮摩托车达到一个最低生产量。比如M9型车生产不少于2000辆，即增加约束X9≥2000，求解 4)适当增加库存能力 为保证三轮摩托车生产线的开动，公司整个摩托车的产量和目标利润受到较大影响，由于三轮摩托车占用的库存量较大，库存容量资源影子价格很高，可适当增加库存容量，以提高目标利润。比如增加库存容量500个单位，求解 四、实验参考选题： 1.某工厂生产A、B两种产品，均需经过两道工序，每生产一吨产品A需要经第一道工序加工2小时，第二道工序加工3小时；每生产一吨产品B需要经第一道工序加工3小时，第二道工序加工4小时。可供利用的第一道工序为12小时，第二道工序为24小时。          生产产品B的同时产出副产品C，每生产一吨产品B，可同时得到2吨产品C而毋需外加任何费用；副产品C一部分可以盈利，剩下的只能报废。出售产品A每吨能盈利400元、产品B每吨能盈利1000元，每销售一吨副产品C能盈利300元，而剩余要报废的则每吨损失200元。经市场预测，在计划期内产品C最大销量为5吨。 根据以上资料该工厂应如何制定生产方案，使工厂总的利润最大。 2.某公司在5年内考虑下列投资，已知：项目A可从第一年至第四年的年初投资，并于次年末收回本利共115%；项目B在第三年的年初投资，到第五年的年末收回本利135%,但规定投资额不能超过4万元；项目C在第二年的年初投资，到第五年的年末收回本利145%,但规定投资额不能超过3万元；项目D每年年初购买债券，年底归还，利息是0.06。公司现有资金10万元，问如何投资，才能使第五年年末拥有的资金最多？ 3.某企业在今后三年内有四种投资机会。第一种是在三年内每年年初投资，年底可回收本利和120％；第二种是在第一年年初投资，第二年年底可回收本利和150％，但该项投资不得超过2万元；第三种是在第二年年初投资，第三年年底回收本利和160％，但该项投资不得超过1.5万元；第四种是在第三年年初投资，该年年底可回收本利和140％，该项投资不得超过1万元。现在该企业准备拿出3万元资金，问如何制订投资计划，使到第三年年末本利和最大？ 4.某公司有钢材、铝材、铜材1200吨，800吨和650吨，拟调往物资紧张的地区甲、乙、丙。已知甲、乙、丙对上述物资的总需求为：900吨，800吨和1000吨，各种物资在各地销售每吨的获利如下表所示。问该公司应如何安排调运计划，才能获利最大？ 物资 获利 地区 甲 乙 丙 钢材 260 210 180 铝材 300 250 400 铜材 400 550 350         5.某工厂生产A，B，C三种产品，现根据订货 合同 劳动合同范本免费下载装修合同范本免费下载租赁合同免费下载房屋买卖合同下载劳务合同范本下载 及生产状况制定5月份的生产计划。已知合同甲为：A产品1000件，单件价格为500元，违约金为100元/件；合同乙为：B产品500件，单件价格为400元，违约金为120元/件；合同丙为：B产品600件，单件价格为420元，违约金为130元/件；C产品600件，单件价格为400元，违约金为90元/件；有关各产品生产过程所需工时以及原材料的情况如下表，问该工厂如何安排生产计划才能使利润最大？   工序1 工序2 工序3 原材料1 原材料 其它成本/件 产品A 2 3 2 3 4 10 产品B 1 1 3 2 3 10 产品C 2 1 2 4 2 10 总工时(原材料) 4600 4000 6000 10000 8000   工时原材料单位成本(元) 15 10 10 20 40                 实验二、对偶理论和灵敏度分析实验 一、实验目的与要求： 进一步熟悉对偶规划及灵敏度分析的有关基本概念；掌握写对偶线性规划，灵敏度分析和参数分析的使用方法及操作步骤；理解其输出结果。 二、实验内容与步骤： 1.选择线性规划模型 从本实验指导书提供的参考选题中或从其它途径选择合适的线性规划模型。 2.写出对偶线性规划模型 3.理解灵敏度分析 4.进行参数分析 三、实验题： 1．已知线性规划模型如下： MaxZ=X1+2X2+4X3+X4 满足  3X1+9X3+5X4≤15 6X1+4X2+X3+7X4≤30 4X1+3X3+4X4≤20 5X1+3X2+8X3+3X4≤40 Xj≥0    (j=1,2,3,4) 1)写出对偶线性规划，变量用Y表示； 2)求原问题及对偶问题的最优解； 3)分别写出价值系数Cj及右端常数bi的最大允许变化范围； 4)目标 函 关于工期滞后的函关于工程严重滞后的函关于工程进度滞后的回复函关于征求同志党风廉政意见的函关于征求廉洁自律情况的复函 数系数改为C=(4，2，6，1)，同时常数改为=(20,40,20,40),求最优解； 5)删除第四个约束同时删除第三个变量，求最优解； 6)增加一个变量X5，系数为(C5,a15,a25,a35,a45)=(6,5,4,2,3)，求最优解； 7)目标函数为MaxZ=(1+)X1+(2+3)X2+4X3+(1-)X4,分析参数的变化区间及对应解的关系，绘制参数与目标值的关系图。 2. 已知线性规划模型如下： MaxZ=4X1+2X2+3X3 满足  2X1+2X2+4X3≤100 3X1+X2+6X3≤100 3X1+X2+2X3≤120 Xj≥0    (j=1,2,3) 1)写出对偶线性规划，变量用Y表示；2)求原问题及对偶问题的最优解； 3)分别写出价值系数Cj及右端常数bi的最大允许变化范围； 4)目标函数系数改为C=(5，3，6)，同时常数改为=(120,140,100),求最优解； 5)在原模型基础上增加一个约束6X1+5X2+X3≤200， 同时增加一个变量X4，系数为(C4,a14,a24,a34,a44)=(7,5,4,1,2)，求最优解； 6)在5)的模型中删除第二个约束，求最优解； 7)原模型的右端常数改为b =(100+，100+3，120+),分析参数的变化区间及对应解的关系，绘制参数与目标值的关系图。 3. 已知线性规划模型如下： Max Z=X1+5X2+3X3+4X4 满足 2X1+3X2 +X3+2X4≦800 5X1+4X2+3X3+4X4≦1200 3X1+4X2+5X3+3X4≦1000 Xj≧0  (j=1,2,3,4) 1)写出对偶线性规划，变量用y表示；2)求原问题及对偶问题的最优解; 3)分别写出价值系数Cj及右端常数的最大变化范围; 4)目标函数系数改为C=(5,4，4，5),同时右端常数改为b=(800,1200，850)，求最优解； 5) 在原模型基础上增加一个约束条件4X1+4X2+2X3+2X4≤700, 同时增加一个决策变量X5，其系数为(C5,a15,a25,a35,)=(5,2,,5,3)，求最优解； 6) 在5)的模型中删除第一个约束条件，求最优解； 7)原模型的右端常数改为b=(800+t,1200+3t,1000+t),分析参数的变化区间及对应解的关系，绘制参数与目标值的关系图。 实验三、整数规划实验 一、实验目的与要求： 进一步熟悉整数线性规划的有关基本概念；掌握运筹学软件包求解整数线性规划的使用方法和操作步骤；理解其输出结果。 二、实验内容与步骤： 1.选择整数规划模型 从本实验指导书提供的参考选题中或从其它途径选择整数规划模型。 2.求解整数规划模型 3.理解其输出结果 三、实验例题： 1. 求解整数规划                                        2. 求解整数规划 MaxZ=3X1+2X2-5X3-2X4+3X5                                          Max Z=X1+5X2+3X3+4X4 满足  X1+X2+X3+2X4+X5≤4                        满足  2X1+3X2 +X3+2X4≦800 7X1  +3X3-4X4+3X5≤8                              5X1+4X2+3X3+4X4≦1200 11X1-6X2+3X4-3X5≥3                                3X1+4X2+5X3+3X4≦1000 Xj=0或1    (j=1，2，3，4，5)                         Xj≧0  (j=1,2,3,4)且为整数 实验四、分配问题和运输问题实验 一、实验目的与要求： 进一步熟悉指派问题和运输问题的有关基本概念；掌握运筹学软件求解指派问题和运输问题的使用方法和操作步骤；理解其输出结果。 二、实验内容与步骤： 1.选择分配问题和运输问题 从本实验指导书提供的参考选题中或从其它途径选择分配问题和运输问题。 2.求解分配问题和运输问题 3.理解其输出结果 三、实验例题： 1.分配问题 某商业集团计划在市内四个点投资四个专业超市，考虑的商品有电器、服装、食品、家具及计算机5个类别。通过评估，家具超市不能放在第3个点，计算机超市不能放在第4个点，不同类别的商品投资到各点的年利润(万元)预测值见下表4.1。该商业集团如何作出投资决策使年利润最大。表4.1 地点 商品 1 2 3 4 电器 120 300 360 400 服装 80 350 420 260 食品 150 160 380 300 家具 90 200 — 180 计算机 220 260 270 —           2.运输问题 某混凝土构件公司有3个碎石生产厂，供应4个搅拌站碎石。各碎石生产厂的产量和各搅拌站的碎石需求量以及每个碎石生产厂到各搅拌站的距离如下表所示，求使总运输量最小的方案。 销地 产地 B1 B2 B3 B4 产量 A1 3 2 7 6 500 A2 7 5 2 3 600 A3 1 5 4 6 300 销量 600 400 200 200 1400             说明：若为产销不平衡问题，事先不必化为平衡问题。 3. 某公司拟将四种新产品配置到四个工厂生产，每种新产品只能配置到一个工厂，一个工厂只能配置一种新产品，四个工厂的单位产品成本(元/件)如下表所示，如何进行配置才能使单件产品总成本最低？   产品1 产品2 产品3 产品4 工厂1 58 69 180 260 工厂2 75 50 150 230 工厂3 65 70 170 250 工厂4 82 55 200 280           4.人事部门欲安排四人到四个不同岗位工作，每个岗位一个人，每个人一个岗位。经考核五人在不同岗位的成绩(百分制)如下表所示，如何安排他们的工作使总成绩最好，应淘汰哪一位。 工作 人员 人力资源 物流管理 市场营销 信息管理 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 戊 76 85 92 93           5 求下表极小化运输问题的最优解 销地 单位运费 产地 B1 B2 B3 B4 产量 A1 4 11 3 5 9 A2 10 2 6 9 5 A3 8 7 1 6 10 销量 4 8 8 7 24 27             实验五：目标规划问题实验 一、实验目的与要求： 进一步熟悉目标规划问题的有关基本概念；掌握运筹学软件求解目标规划问题的使用方法和操作步骤；理解其输出结果。 二、实验内容与步骤： 1.选择目标规划问题 从本实验指导书提供的参考选题中或从其它途径选择目标规划问题。 2.求解目标规划问题 3.理解其输出结果 三、实验例题： 1、某公司分厂用一条生产线生产两种产品A和B ，每周生产线运行时间为60小时，生产一台A产品需要4小时，生产一台B产品需要6小时．根据市场预测，A、B产品平均销售量分别为每周9、8台，它们销售利润分别为12、18万元。在制定生产计划时，经理考虑下述4项目标： 首先，产量尽量不要超过市场预测的销售量； 其次，工人加班时间尽量最少； 第三，希望总利润尽量大； 最后，要尽可能满足市场需求, 当不能满足时, 市场认为B产品的重要性是A产品的2倍． 试建立这个问题的数学模型并求解． 2、 电视机厂装配25寸和21寸两种彩电，每台电视机需装备时间1小时，每周装配线计划开动40小时，预计每周25寸彩电销售24台，每台可获利80元，每周21寸彩电销售30台，每台可获利40元。 该厂目标： 1、充分利用装配线，避免开工不足。 2、允许装配线加班，但尽量不超过10小时。 3、尽量满足市场需求。 实验六、网络优化问题实验 一、实验目的与要求： 进一步熟悉最小树和最短路，最大流问题的有关基本概念；掌握运筹学软件求解最小树和最短路，最大流问题的使用方法和操作步骤；理解其输出结果。 二、实验内容与步骤： 1.选择最小树问题和最短路，最大流问题 从本实验指导书提供的参考选题中或从其它途径选择最小树问题和最短路问题及最大流问题。 2.求解最小树问题和最短路，最大流问题。 3.理解其输出结果 三、实验例题： 1.最小树问题 某铁路部门拟用铁路线将7个市镇连接起来,已知修建各市镇间铁路的费用如下图所示。这是一个赋权图,图中的顶点V1,V2,V3,…,V7表示7个市镇,每条边表示可能要修建的铁路,每个边的权值为修建该条铁路将要花的费用。现在铁路部门需知道，应修建哪几条铁路才能既可以将7个市镇连接起来又使所花费用最少。 2.最短路问题 下图是某地区的航线图,图中的顶点表示各个机场,图中的弧表示航线及航线方向,弧旁数字表示各相应机场间的飞行时间,现在的问题是:应如何确定航线,才能使从机场V1飞往机场V12所需的时间为最短。 3，最大流问题 某企业生产某种产品,通过市场调查获悉,目前该产品在市场上脱销,所以该企业决定将尽可能多的产品运到指定的市场销售。假定从生产厂到市场要经过一些中间环节，如下图：V1表示生产厂，V9表示指定的市场，各个弧表示各个渠道，各弧的权值表示该渠道单位时间内最大的通过能力，即允许通过的最多产品数。