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

该【《运筹学》实验指导书 】是由【世界末末日】上传分享，文档一共【21】页，该文档可以免费在线阅读，需要了解更多关于【《运筹学》实验指导书 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。《运筹学》
实 验 指 导 书
适用专业： 工业工程
东北大学秦皇岛分校把握工程学院工业工程专业
2023 年 3 月
前 言
对于工业工程专业来说，运筹学是一门公共根底课，是应用性很强的课程。它是利用现代数学争论各种资源的运用、筹划和相关决策等问题的一门重要学科，主要争论如何在确定条件下科学、合理地安排人力、物力、财力等资源，使实际系统有效运行。它可以用来推想进展趋势，制定行动规划或优选方案，从而为行政治理人员和决策者在决策时供给科学的依据。运筹学的实际运用包括如下六个步骤：问题分析；模型构造；模型求解；模型验证；解的有效把握；方案实施。
随着计算机软件的进展，很多简洁的运筹学计算可以由计算机软件来完成，如matlab、mathematica、lingo、excel 等。本试验课程以lingo 软件为工具，使学生在学习了运筹学根本原理的根底上，进一步把握使用软件工具解决运筹学实际问题的方法。本试验课程共8 学时，内容如下：
1、软件编程根底及其在运筹学中的应用〔2 学时〕
2、单纯形法的计算机实现〔2 学时〕
3、解运输问题〔2 学时〕
4、解目标规划、整数规划问题和指派问题〔2 学时〕
试验一 软件编程根底及其在运筹学中的应用〔2 学时〕
一、试验目的
1、 生疏 lingo 的操作环境。
2、 学会用 lingo 编程的方法来求解运筹学问题并读取结果。
二、试验素材
例题 1、〔利润最大化问题〕某工厂生产甲、乙两种产品。每生产一个单位的甲产品需要使用 A 设备 1 小时，工人劳动时间 1 小时，可赢利 20 元；生产一个单
位的乙产品需要使用 B 设备 1 小时，工人劳动时间 2 小时，可赢利 30 元。受工厂条件限制，每天的总劳动时间不能超过 120 小时，A 设备的总使用时间不能超过 60 小时，B 设备的总使用时间不能超过 50 小时。试建立线性规划模型，每天生产多少甲、乙产品，可使利润最大？
解：建立线性规划模型。设 x1 为每天生产甲产品的数量，x2 为每天生产乙产品的数量。由此得到线性规划模型：
max=20*x1+30*x2; x1+2*x2<=120; x1<=60;
x2<=50; x1>=0; x2>=0;
将程序输入 lingo 软件，不需输入最终两行〔变量的非负约束〕，点击 solve
按钮，得到求解结果如下：
Global optimal solution found. ---〔已找到全局最优解〕 Objective value: 〔0

最--优-目标函数值〕
Infeasibilities: -0-0-0〔0找到的解违反了几个约束条件〕
Total solver iterations: 1〔迭--代-次数〕
Variable Value Reduced Cost
X1


X2


Row
Slack or Surplus
Dual Price
1


2


3


4


由上述结果得到，每天生产甲产品 60 个单位，乙产品 30 个单位，每天可获得的最大利润是 2100 元。
〔注：大家在“help”中查找“solver status”，即可查询到solver status box
的具体解释。关于 lingo 软件的使用问题都可以通过查询 help 文件得到答案〕
习题 1、max=6*x7+7*x2;
7*x1+5*x2<=3500;
5*x1+8*x2<=4000;
2*x1+5*x2<=2023;
习题 2、min=x1+x2;
x1-x2<=-1; x1+x2<=-1;
习题 3、〔装船问题〕设有甲、乙、丙三种货物需要装船。它们的积载因数分别为 、2 和 1〔m3/kg〕，舱时量〔装船速度〕分别为 50、100 和 40〔kg/h〕，总装货量为 1000kg，货物总容积不能超过 1400m3。问该船应各装甲、乙、丙货物多少千克，才能使装货时间最短？
习题 4、〔最高性价比问题〕某饲养场饲养动物出售。设每头动物每天至少需要700g 蛋白质、30g 矿物质、100mg 维生素。现有五种饲料可供选用，其每千克的养分成分含量及价格如下表所示。要求确定既满足动物需要、又使费用最低的饲料选择方案。
饲料
蛋白质〔g〕
矿物质〔g〕
维生素〔mg〕
价格〔元/千克〕
1
3
1


2
2



3
1



4
6
2
2

5
18



注：粗看起来，目标函数与约束条件是有显著区分的，但细致分析，就可以觉察
他们之间没有本质上的区分。例如，一个企业增加生产量，制造高的经济收入显
然是目标。这个企业拥有的资金、设备是限制条件，把拥有的资金和设备说成是
目标是不妥的，但假设要求一个企业“以最少的资金制造最高的经济收入”，这里
的资金就有目标的含义。所以给目标加上某一限制，就成了约束条件。
习题 5、〔人力资源安排问题〕某昼夜效劳的公交线路每天各时间段内所需要的工作人员人数如下表所示。设工作人员在各时间段一开头时上班，并连续工作8 小时。问该公交线路该如何安排工作人员，才能既满足工作需要，又可以配备最少的工作人员？
班次
时间段
所需人数
1
6:00~10:00
60
2
10:00~14:00
70
3
14:00~18:00
60
4
18:00~22:00
50
5
22:00~2:00
20
6
2:00~6:00
30
习题 6、〔投资打算问题〕某地区在今后 3 年内有 4 种投资时机：
第一种是在 3 年内每年年初投资，年底可获利润 20%，并可将本金收回。该投资时机每年都有，投资者可自行打算到底是每年都这样投资，还是只选择其中的一、两年进展这种投资。
其次种是在第一年年初投资，其次年年底可获利 50%，并可将本金收回，但该项投资金额不超过 200 万元。请留意只有第一年年初有这样的投资时机，其次年年初就没有了。
第三种是在其次年年初投资，第三年年底收回本金，并获利润60%，但该项投资金额不超过 150 万元。请留意只有其次年年初有这样的投资时机。
第四种是在第三年年初投资，当年底收回本金，并获利润40%，但该项投资金额不超过 100 万元。
现在该地区预备了 300 万元资金，如何制定投资方案，使到第三年年末本利的和最大？
例题 2、〔lingo 程序的通用形式〕在书写数据量较大的程序时，使用通用形式更加简便。请大家比照以下两个程序，它们的功能一样，但书写形式不同：
直接求解的程序： 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;
endsets max=***@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 软件文件夹，双击“”,翻开软件。
2、 实践例题 1，初步学会读 report。
请留意如下几点：
程序第一行的 max 表示求极大，min 表示求微小；
〔1〕
留意每个语句后面加上分号；
〔2〕
Lingo 软件保持着单纯形法的特点，默认为全部变量都是非负限制
〔3〕
的，因此不需把变量非负限制的约束条件写入模型；
3、 实践习题 1、2，观看 report 有何不同。
4、 解习题 3、4 的运筹学问题。习题 5、6 为附加题，可依个人力气选做。
5、 实践例题 2。
四、试验结果
本局部由学生填写。请仿按例题 1 的解题步骤，将试验步骤 3、4 的结果写在试验报告中。
五、试验仪器及工具
Lingo 软件。
试验二 单纯形法的计算机实现〔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 小时。试建立线性规划模型，每天生产多少甲、乙产品，可使利润最大？
解：建立线性规划模型。设 x1 为每天生产甲产品的数量，x2 为每天生产乙产品的数量。由此得到线性规划模型：
max=20*x1+30*x2; x1+2*x2<=120; x1<=60;
x2<=50;
将程序输入 lingo 软件，不需输入最终两行〔变量的非负约束〕，点击 solve
按钮，得到求解结果如下：
Global optimal solution found. ---〔已找到全局最优解〕 Objective value: 〔0
Infeasibilities:
Total solver iterations: 1

最--优-目标函数值〕
Variable
Value
Reduced Cost
X1


X2


Row
Slack or Surplus
Dual Price
1


2


3


4


由上述结果得到，每天生产甲产品 60 个单位，乙产品 30 个单位，每天可获得的最大利润是 2100 元。
A、 report 的含义：
B、 Reduced cost：检验数取负。
slack or surplus：表示在线性规划中在最优解处，松弛变量或剩余变量的值。假设这个值为 0，则表示此约束为紧约束，也就是说，改动此时约束的值会影响到最优解的值。假设不为 0，则表示此约束为松约束，也就是说， 在确定的范围内改动约束的值，并不影响最优解的值。
那么，当紧约束的值转变时，最优解转变多少呢？dual price 会告知我们。Dual price：对偶价格〔影子价格〕，表示在最优解下，资源增加 1 单位时，效益的增量〔即资源增加 1 单位对效益的奉献〕。它与原问题的约束条件相联系，而不与变量相联系。
例如在此题中，例如在此题中，总劳动时间每增加 1 小时，将会使利润增加15 元；增加B 设备的生产力气〔可使用时间〕，对利润没有影响；B 设备的生产力气由 50 小时始终减小到 30 小时，都对利润没有影响，假设再接着往下减，就会有影响了。
从 dual price 中我们可以看出，增加某些资源会对效益有提升，那么，资源是不是能够无限制增加呢？灵敏度分析会告知我们。
C、 灵敏度分析：
在作灵敏度分析之前，需要对 lingo 软件中的参数进展调整，其方法如以以下图所示：

然后在完成程序计算后，在程序运行状态窗口下，单击 LINGO 下的 Range 按钮， 则软件会弹出灵敏度分析报告。
例如，每增加 1 小时的劳动时间，利润可增加 15 元，但最多只能增加 40 小时， 到达 160 小时，再增加劳动时间就可能达不到增加利润的效果了。同样，A 设备的生产力气也只能增加 60 小时，到达 120 小时。
习题 1、某公司有甲乙两个工厂生产 A、B 两种产品，产品分别由甲乙两个工厂中的加工车间和装配车间来完成，有关这两个工厂中各车间的生产本钱、工时定额和可利用工时限额的资料如下表所示。这两种产品运到南北两个地区去出售， 有关最大的市场销售量、售价、销售费用和运输费用如下表所示。现公司期望实行一些措施来提高经济效益，为此要弄清应关注哪些问题。是扩大销售量呢？还是改善工厂的生产力气？假设扩大销售量呢，是首先扩大南方市场还是北方市场？