《运筹学》实验指导书.doc

《《运筹学》实验指导书.doc》由会员分享，可在线阅读，更多相关《《运筹学》实验指导书.doc（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date运筹学实验指导书电子商务安全运筹学实 验 指 导 书适用专业： 工业工程 东北大学秦皇岛分校控制工程学院工业工程专业2014年3月前 言对于工业工程专业来说，运筹学是一门公共基础课，是应用性很强的课程。它是利用现代数学研究各种资源的运用、筹划和相关决策等问题的一门重要学科，主要研究如何在一定条件下科学、合理地分配人力、物力、财力等资源，使实际系统有效运行。它可以用来预

2、测发展趋势，制定行动规划或优选方案，从而为行政管理人员和决策者在决策时提供科学的依据。运筹学的实际运用包括如下六个步骤：问题分析；模型构造；模型求解；模型验证；解的有效控制；方案实施。随着计算机软件的发展，许多复杂的运筹学计算可以由计算机软件来完成，如matlab、mathematica、lingo、excel等。本实验课程以lingo软件为工具，使学生在学习了运筹学基本原理的基础上，进一步掌握使用软件工具解决运筹学实际问题的方法。本实验课程共8学时，内容如下：1、软件编程基础及其在运筹学中的应用（2学时）2、单纯形法的计算机实现（2学时）3、解运输问题（2学时）4、解目标规划、整数规划问题和

3、指派问题（2学时）实验一 软件编程基础及其在运筹学中的应用（2学时）一、实验目的1、 熟悉lingo的操作环境。2、 学会用lingo编程的方法来求解运筹学问题并读取结果。二、实验素材例题1、（利润最大化问题）某工厂生产甲、乙两种产品。每生产一个单位的甲产品需要使用A设备1小时，工人劳动时间1小时，可赢利20元；生产一个单位的乙产品需要使用B设备1小时，工人劳动时间2小时，可赢利30元。受工厂条件限制，每天的总劳动时间不能超过120小时，A设备的总使用时间不能超过60小时，B设备的总使用时间不能超过50小时。试建立线性规划模型，每天生产多少甲、乙产品，可使利润最大？解：建立线性规划模型。设x1

4、为每天生产甲产品的数量，x2为每天生产乙产品的数量。由此得到线性规划模型：max=20*x1+30*x2;x1+2*x2=120;x1=60;x2=0;x2=0;将程序输入lingo软件，不需输入最后两行（变量的非负约束），点击solve按钮，得到求解结果如下： Global optimal solution found. -（已找到全局最优解） Objective value: 2100.000 -（最优目标函数值） Infeasibilities: 0.000000 -（找到的解违反了几个约束条件） Total solver iterations: 1 -（迭代次数） Variable V

5、alue Reduced Cost X1 60.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 2100.000 1.000000 2 0.000000 15.00000 3 0.000000 5.000000 4 20.00000 0.000000由上述结果得到，每天生产甲产品60个单位，乙产品30个单位，每天可获得的最大利润是2100元。（注：大家在“help”中查找“solver status”，即可查询到solver status box的详细解释。关于lingo软件的使用问题都可以通过查询he

6、lp文件得到答案）习题1、max=6*x7+7*x2;7*x1+5*x2=3500;5*x1+8*x2=4000;2*x1+5*x2=2000;习题2、min=x1+x2;x1-x2=-1;x1+x2=-1;习题3、（装船问题）设有甲、乙、丙三种货物需要装船。它们的积载因数分别为1.5、2和1（m3/kg），舱时量（装船速度）分别为50、100和40（kg/h），总装货量为1000kg，货物总容积不能超过1400m3。问该船应各装甲、乙、丙货物多少千克，才能使装货时间最短？习题4、（最高性价比问题）某饲养场饲养动物出售。设每头动物每天至少需要700g蛋白质、30g矿物质、100mg维生素。现有

7、五种饲料可供选用，其每千克的营养成分含量及价格如下表所示。要求确定既满足动物需要、又使费用最低的饲料选择方案。饲料蛋白质（g）矿物质（g）维生素（mg）价格（元/千克）1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8注：粗看起来，目标函数与约束条件是有显著区别的，但细致分析，就可以发现他们之间没有本质上的区别。例如，一个企业增加生产量，创造高的经济收入显然是目标。这个企业拥有的资金、设备是限制条件，把拥有的资金和设备说成是目标是不妥的，但若要求一个企业“以最少的资金创造最高的经济收入”，这里的资金就有目标的含义。所以给目标加上某一限制，就成了

8、约束条件。习题5、（人力资源分配问题）某昼夜服务的公交线路每天各时间段内所需要的工作人员人数如下表所示。设工作人员在各时间段一开始时上班，并连续工作8小时。问该公交线路该如何安排工作人员，才能既满足工作需要，又可以配备最少的工作人员？班次时间段所需人数16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030习题6、（投资计划问题）某地区在今后3年内有4种投资机会：第一种是在3年内每年年初投资，年底可获利润20%，并可将本金收回。该投资机会每年都有，投资者可自行决定到底是每年都这样投资，还是只选择其中的一

9、、两年进行这种投资。第二种是在第一年年初投资，第二年年底可获利50%，并可将本金收回，但该项投资金额不超过200万元。请注意只有第一年年初有这样的投资机会，第二年年初就没有了。第三种是在第二年年初投资，第三年年底收回本金，并获利润60%，但该项投资金额不超过150万元。请注意只有第二年年初有这样的投资机会。第四种是在第三年年初投资，当年底收回本金，并获利润40%，但该项投资金额不超过100万元。现在该地区准备了300万元资金，如何制定投资方案，使到第三年年末本利的和最大？例题2、（lingo程序的通用形式）在书写数据量较大的程序时，使用通用形式更加简便。请大家对比以下两个程序，它们的功能相同，

10、但书写形式不同：直接求解的程序：max=2*x1+5*x2;x1+x3=4;x2+x4=3;x1+2*x2+x5=8;通用形式的程序：sets:var_num/1.5/:c,x;const_num/1.3/:b;matrix(const_num,var_num):A;endsetsmax=sum(var_num:c*x);for(const_num(i):sum(var_num(j):A(I,j)*x(j)=b(i);data:c=2,5,0,0,0;b=4,3,8;A=1,0,1,0,0, 0,1,0,1,0, 1,2,0,0,1;enddata三、实验内容及步骤1、 打开lingo软件文件

11、夹，双击“Lingo11.exe”,打开软件。2、 实践例题1，初步学会读report。请注意如下几点：（1） 程序第一行的max表示求极大，min表示求极小；（2） 注意每个语句后面加上分号；（3） Lingo软件保持着单纯形法的特点，默认为所有变量都是非负限制的，因此不需把变量非负限制的约束条件写入模型；3、 实践习题1、2，观察report有何不同。4、 解习题3、4的运筹学问题。习题5、6为附加题，可依个人能力选做。5、 实践例题2。四、实验结果本部分由学生填写。请仿照例题1的解题步骤，将实验步骤3、4的结果写在实验报告中。五、实验仪器及工具Lingo软件。实验二 单纯形法的计算机实现

12、（2学时）一、 实验目的1、 进一步练习运用lingo软件去解决线性规划、对偶等实际问题。2、 理解lingo report中slack or surplus以及dual price的经济含义。3、 学会使用lingo进行灵敏度分析。二、 实验素材例题1、同实验一的例题1。（利润最大化问题）某工厂生产甲、乙两种产品。每生产一个单位的甲产品需要使用A设备1小时，工人劳动时间1小时，可赢利20元；生产一个单位的乙产品需要使用B设备1小时，工人劳动时间2小时，可赢利30元。受工厂条件限制，每天的总劳动时间不能超过120小时，A设备的总使用时间不能超过60小时，B设备的总使用时间不能超过50小时。试建

13、立线性规划模型，每天生产多少甲、乙产品，可使利润最大？解：建立线性规划模型。设x1为每天生产甲产品的数量，x2为每天生产乙产品的数量。由此得到线性规划模型：max=20*x1+30*x2;x1+2*x2=120;x1=60;x2=50;将程序输入lingo软件，不需输入最后两行（变量的非负约束），点击solve按钮，得到求解结果如下： Global optimal solution found. -（已找到全局最优解） Objective value: 2100.000 -（最优目标函数值） Infeasibilities: 0.000000 Total solver iterations:

14、1 Variable Value Reduced Cost X1 60.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 2100.000 1.000000 2 0.000000 15.00000 3 0.000000 5.000000 4 20.00000 0.000000由上述结果得到，每天生产甲产品60个单位，乙产品30个单位，每天可获得的最大利润是2100元。A、 report的含义：B、 Reduced cost：检验数取负。slack or surplus：表示在线性规划中在最优解处，松弛变量

15、或剩余变量的值。如果这个值为0，则表示此约束为紧约束，也就是说，改动此时约束的值会影响到最优解的值。如果不为0，则表示此约束为松约束，也就是说，在一定的范围内改动约束的值，并不影响最优解的值。那么，当紧约束的值改变时，最优解改变多少呢？dual price会告诉我们。Dual price：对偶价格（影子价格），表示在最优解下，资源增加1单位时，效益的增量（即资源增加1单位对效益的贡献）。它与原问题的约束条件相联系，而不与变量相联系。例如在本题中，例如在本题中，总劳动时间每增加1小时，将会使利润增加15元；增加B设备的生产能力（可使用时间），对利润没有影响；B设备的生产能力由50小时一直减小到3

16、0小时，都对利润没有影响，如果再接着往下减，就会有影响了。从dual price中我们可以看出，增加某些资源会对效益有提升，那么，资源是不是能够无限制增加呢？灵敏度分析会告诉我们。C、 灵敏度分析：在作灵敏度分析之前，需要对lingo软件中的参数进行调整，其方法如下图所示： 然后在完成程序计算后，在程序运行状态窗口下，单击LINGO下的Range按钮，则软件会弹出灵敏度分析报告。例如，每增加1小时的劳动时间，利润可增加15元，但最多只能增加40小时，达到160小时，再增加劳动时间就可能达不到增加利润的效果了。同样，A设备的生产能力也只能增加60小时，达到120小时。习题1、某公司有甲乙两个工厂

17、生产A、B两种产品，产品分别由甲乙两个工厂中的加工车间和装配车间来完成，有关这两个工厂中各车间的生产成本、工时定额和可利用工时限额的资料如下表所示。这两种产品运到南北两个地区去出售，有关最大的市场销售量、售价、销售费用和运输费用如下表所示。现公司希望采取一些措施来提高经济效益，为此要弄清应关注哪些问题。是扩大销售量呢？还是改善工厂的生产能力？若扩大销售量呢，是首先扩大南方市场还是北方市场？是先扩大产品A的销售量还是扩大B的销售量？如果要增加工厂中的有效工时，那么首先关注哪一家工厂及哪一个车间？资料出售到南方出售到北方产品A产品B产品A产品B最大销售量（件）90001200075006000每件

18、售价（元）12171318销售费用（元/件）4534运输费用（元/件）工厂甲1122工厂乙2212资料工厂甲工厂乙产品A产品B产品A产品B单件生产成本5645工时定额（小时）加工车间1.5212装配车间122.51.5可利用工时定额（小时）加工车间1200016000800022000装配车间共30000共40000习题2、某工厂生产A、B、C三种产品，其所需劳动力、材料等有关数据如下表所示。要求：（1）确定获利最大的生产方案；（2）产品A、B、C的利润分别在什么范围内变动时，上述最优方案不变；（3）如果生产一种新产品D，每件消耗劳动力8个单位，消耗材料2个单位，每件可获利3元，该种产品是否值

19、得生产？（4）如果劳动力数量不增，材料不足时可从市场购买，每单位0.4元，问该厂要不要购进原材料扩大生产，若需购进，以购多少为宜？资源产品可用量（单位）ABC劳动力63545材料34530产品利润（元/件）314三、 实验内容及步骤1、 打开lingo软件文件夹，双击“Lingo11.exe”,打开软件。2、 实践例题1。3、 针对上次实验中的习题3、4，分析report中影子价格的经济含义。4、 解本实验的习题1、2。四、实验结果本部分由学生填写。将实验步骤3、4的结果写在实验报告中。五、实验仪器及工具Lingo软件。实验三 解运输问题（2学时）一、实验目的1、 学会使用lingo进行运输问

20、题的求解。二、实验素材习题1、（产销平衡问题）将货物从两个产地A、B运往三个销售地1、2和3。各产地供应数量、各销售地需求数量及运费如下图所示。问如何组织运输，才能使总运输费用最少。习题2、（供过于求问题）有三个产地的产品需要运往四个销地，各产地供应数量、各销售地需求数量及运费如下表所示。如何调运使总运费最少？B1B2B3B4产量A1626730A2495325A3881521销量15172212习题3、（供不应求问题）有三个产地的产品需要运往四个销地，各产地供应数量、各销售地需求数量及运费如下表所示。如何调运使总运费最少？B1B2B3B4产量A13116107A219978A375889销量

21、7867习题4、（转运问题）对于习题1，假设货物可以在产地与产地间、销地与销地间转运，如下图所示。（1）问如何组织运输，才能使总运输费用最少。（2）对比本结果与习题1的计算结果，你能得出什么结论？习题5、（运输问题悖论）有四个产地的产品需要运往五个销地，各产地供应数量、各销售地需求数量及运费如下表所示。（1）如何调运使总运费最少？（2）如果A1、A3多产5个单位，B2多销10个单位，那么最优运输方案是什么？总运费又是多少？（3）从本实验结果中，你能发现些什么吗？请尽量深入地写出你的结论、想法等。B1B2B3B4B5产量A11415613147A216922131618A38511456A412

22、41891015销量41112811三、实验内容及步骤1、 打开lingo软件。2、 解习题14。习题5为选做。四、实验结果本部分由学生填写。将习题15的结果写在实验报告中。五、实验仪器及工具Lingo软件。实验四 解目标规划、整数规划问题和指派问题（2学时）一、实验目的1、 学会使用lingo进行整数规划、指派问题和目标规划问题的求解。二、实验素材习题1、（整数规划问题-排产问题）某工厂生产A1和A2两种产品，需要经过B1、B2、B3三道工序，单位工时和利润及各工序每周工时限额如下表所示。问：工厂应如何安排生产，才能使总利润最大？产品工序单位利润B1B2B3A10.30.20.325A20.

23、70.10.540工时限额（小时/周）250100200提示：为满足条件“变量x取整数”，只需加上一个限制函数gin（x）。习题2、（0-1型整数规划问题-投资项目的选择问题）某地区有5个可考虑的投资项目，其期望纯收益与所需投资额如下表所示。这5个项目中，在项目、和之间必须且只能选择一项；项目和之间至少选择一项；和两个项目是密切相关的，以的实施为前提。该地区共筹集到资金15万元，究竟应该选择哪些项目才能使其期望纯收益最大呢？工程项目期望纯收益（万元）所需投资（万元）10.06.08.04.07.02.06.04.09.05.0提示：1、为满足条件“变量x取0或1”，只需加上一个限制函数bin（

24、x）。2、期望纯收益指已经扣除投资之后的收益。3、该模型涉及一类选择问题。习题3、（整数规划问题与0-1型整数规划问题-选址问题）某市计划在新建的5个居民小区中的2个内各设立一所小学。下表给出了各小区内及各小区间的平均步行时间（分钟）及各居民小区的小学生人数。该市教委希望：两所小学的招生人数基本持平，学生总的上学步行时间最短。请向该市教委提供决策建议：两所小学分别建于哪两个小区，以及各居民小区学生应分配到哪所小学上学？小区如果在该小区建立小学小学生人数1234515201525102002204201525180315206251530042515254121605102515125350习题

25、4、（指派问题-游泳队员选拔问题）某高校准备从5名游泳队员中选择4人组成接力队，参加市里的4*100m混合泳接力比赛。5名队员4种泳姿的百米平均成绩如下表所示，问应如何选拔队员组成接力队？队员蝶泳仰泳蛙泳自由泳甲66.875.68758.6乙57.26666.453丙7867.884.659.4丁7074.269.657.2戊67.47183.862.4例题1、（目标规划问题-工厂排产问题）某工厂生产A、B两种产品，需要用不锈钢、铜材和铝材三种主要原料。各种材料的库存量、单位产品材料消耗定额及利润等数值如下表所示。（1）若该厂生产的产品都能销售出去，问该厂的决策者应如何安排A、B两种产品的产量

26、，使工厂的利润最大？（2）若以利润达到3000元或以上作为主要目标，恰好用完铝材作为第二目标，则应该如何安排A、B两种产品的产量？每件材料消耗产品材料库存千克/件ABKg材料不锈钢23120铜材2180铝材-130利润6070解：（1） 显然，这一问题可以用线性规划模型来描述。设x1、x2分别表示A、B两种产品的产量，则问题的数学模型为：max=60*x1+70*x2;2*x1+3*x2=120;2*x1+x2=80;x2=3000元）的偏差变量，d2p和d2m是次要目标（恰好用完铝材）的偏差变量，p1和p2分别为主要目标和次要目标的优先因子。则主要目标的目标函数可表示为：min=p1*d1m

27、，次要目标的目标函数可表示为：min=p2*(d2p+d2m)。于是总的目标函数为：min=p1*d1m+p2*(d2p+d2m)。故本题的数学模型为：min=p1*d1m+p2*(d2p+d2m); - 目标函数60*x1+70*x2+d1m-d1p=3000; - 目标约束1x2+d2m-d2p=30; - 目标约束22*x1+3*x2=120; - 系统（绝对）约束12*x1+x2=80; - 系统（绝对）约束2B、使用lingo对本模型进行求解。使用序贯式算法。（根据优先级的先后次序，将目标规划问题分解成一系列的单目标规划问题，依次求解）先求第一级目标（主要目标）：min=d1m;60

28、*x1+70*x2+d1m-d1p=3000;x2+d2m-d2p=30;2*x1+3*x2=120;2*x1+x2=80;运行结果为： Global optimal solution found. Objective value: 0.000000 Infeasibilities: 0.000000 Total solver iterations: 2 Variable Value Reduced Cost D1M 0.000000 1.000000 X1 15.00000 0.000000 X2 30.00000 0.000000 D1P 0.000000 0.000000 D2M 0.0

29、00000 0.000000 D2P 0.000000 0.000000 Row Slack or Surplus Dual Price 1 0.000000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 20.00000 0.000000可见目标函数的最优值为0，即第一级偏差d1m为0；然后求第二级目标：min=d2p+d2m;60*x1+70*x2+d1m-d1p=3000;x2+d2m-d2p=30;2*x1+3*x2=120;2*x1+x2=80;d1m=0;运行结果为： Global o

30、ptimal solution found. Objective value: 0.000000 Infeasibilities: 0.000000 Total solver iterations: 2 Variable Value Reduced Cost D2P 0.000000 1.000000 D2M 0.000000 1.000000 X1 15.00000 0.000000 X2 30.00000 0.000000 D1M 0.000000 0.000000 D1P 0.000000 0.000000 Row Slack or Surplus Dual Price 1 0.0000

31、00 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000 5 20.00000 0.000000 6 0.000000 0.000000可见目标函数的最优值为0，即第二级偏差d2p+d2m也为0。x1=15，x2=30。故应该生产15件A、30件B。此时的利润为3000元，铝材刚好用完。习题5、（目标规划问题-排产问题）某工厂生产A、B两种产品，工人的有效工时为每月1400小时，有关安排生产计划所需的数据如下表所示。（1）试制定生产两种产品的月产量，使得在生产量不超过最大销售量的情况下，利润最大；（2）工厂决策者制定了一些具体指标：首先要求完成利润指标24000元；其次要求生产量不超过最大销售量；最后要求不要超过每月有效工时。试制定生产两种产品的月产量。产品工时定额（小时/吨）最大销售量（吨/月）利润（元/吨）A2060300B10100120三、实验内容及步骤1、 打开lingo软件。2、 解习题15。四、实验结果本部分由学生填写。将习题15的结果写在实验报告中。五、实验仪器及工具Lingo软件。-