运筹学上机作业.docx

运筹学上机作业.docx

《运筹学上机作业.docx》由会员分享，可在线阅读，更多相关《运筹学上机作业.docx（10页珍藏版）》请在冰点文库上搜索。

运筹学上机作业

运筹学实验指导书

实验目：

充分发挥WinQSB这一先进计算机工具强大功能，理论及应用结合，丰富教学内容，提高学习兴趣，使学生能基本掌握WinQSB软件常用命令和功能。

实验要求：

能用软件求解运筹学中常见数学模型。

实验一　线性规划及对偶问题

1．用软件完成求解案例1　配料方案问题

软件说明：

（1）WinQSB软件求解LP不必化为标准型，对于有界变量及无约束变量可不转化为标准型，只要修改系统变量类型即可，对于不等式约束也不必转化为标准型，直接输入不等式符号。

（2）调用LP和ILP程序（点击开始→程序→WINQSB→LinearandIntegerProgramming）。

（3）打开已存在文件（系统自动带几个典型例题供学习）。

观赏例题：

点击Problem→lp.lpp，点击菜单栏SolveandAnalyze→Solvetheproblem或点击工具栏中图标用单纯形法求解，直接得到最终单纯形表。

观赏一下用单纯形法迭代步骤：

点击菜单栏SolveandAnalyze→SolveandDisplaysteps，再在菜单栏中点击simplexiteration→nextiteration则可。

（4）建立新问题，输入数据。

在选择输入格式时，选择spreadsheetmatrixform则以电子表格形式输入变量系数矩阵和右端常数矩阵。

2、产品产量问题

某企业生产两种产品，分别使用4种原材料，4种原材料目前库存量分别为300吨，400吨，500吨和500吨，两种产品所需各种原材料数量如表示。

又知两种产品单位利润分别为2800吨和3200吨，如何计划两种产品产量，使利润达到最大。

原材料

产品　

1

2

3

4

产量

A

1.4

1.3

1.4

1.4

x1

B

1.6

1.7

1.5

1.7

x2

库存量

300

400

500

500

（1）建立该问题线性规划模型，并用软件求出最优解。

（2）写出该问题对偶问题，并由原问题最优结果（表），分析对偶解。

软件说明：

（1）启动线性规划及整数规划程序，建立新问题，输入数据，存盘。

（2）点击Format─→SwitchtoDualForm,得到对偶问题数据表，点击Format─→SwitchtoNormalModelForm,得到对偶模型，点击Edit─→VariableName,分别修改变量名，回车后得到以y为变量名对偶模型。

（3）再一次求对偶返回到原问题，查看最优表中影子价格（ShadowPrice）对应列数据就是对偶问题最优解。

（4）观察最优表中最后两列可得价值系数（cj）及右端常数（bi）最大最小（allowablemin/allowablemax）允许变化范围。

（灵敏度分析）

3、用软件完成求解案例13生产计划及灵敏度分析。

实验二　运输问题及整数规划

1、女子体操团体赛规定：

（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡木、鞍马和自由体操。

（2）每个运动员最多参加3个项目，并且每个项目只能参赛一次。

（3）每个项目至少要有人参赛一次，并且总参赛人次数等于10。

（4）每个项目采用10分制计分，将10次比赛得分求和，并排序，分数越高成绩越好。

已知代表队5名运动员各单项预赛成绩如表所示。

高低杠

平衡木

鞍马

自由体操

甲

8.6

9.7

8.9

9.4

乙

9.2

8.3

8.5

8.1

丙

8.8

8.7

9.3

9.6

丁

8.5

7.8

9.5

7.9

戊

8.0

9.4

8.2

7.7

为安排运动员参赛项目使团体总分最高，试建立该问题线性规划模型，并用软件求解。

2、某商场规定：

营业员每周连续工作5天后休息2天，轮流休息。

根据统计，商场每天需要营业员如表所示。

商场人力资源部应如何安排每天上班人数，使商场总营业员最少。

星期

需要人数

星期

需要人数

一

300

五

480

二

300

六

600

三

350

日

550

四

400

试建立该问题线性规划模型，并用软件求解。

3、对典型案例5（运输问题）：

用软件求出最优调运方案。

软件说明：

（1）调用子程序networkmodeling，新建问题，选择运输问题（transportationProblem）,输入标题、产地及销地数。

（2）输入数据，并重命名产地和销地。

（3）求解，点击菜单栏solveandanalyze,下拉菜单有四个选项：

solvetheproblem（只求出最优解，）solveanddisplaysteps-networks（网络图求解并显示迭代步骤）solveanddisplaysteps-tableuau（表格求解并显示迭代步骤）和只求初始解，根据要求选择其中一种方法。

（4）显示图解结果。

点击菜单栏results－graphicsolution,系统以网络流形式显示最优调运方案。

实验三　动态规划问题

1、背包问题。

这是运筹学中一个著名问题。

某人外出旅游，需将5个物品装入背包，但背包装物重量有限制，总重量W不得超过15千克。

物品重量及其价值关系如下表所示。

试问：

如何装入这些物品，使背包总价值最大？

物品

重量（千克）

价值（元）

A

6

18

B

5

15

C

2

8

D

3

10

E

1

6

软件说明：

（1）调用子程序DP，新建问题，选择背包问题（KnapsackProblem）,输入标题和物品品种数。

（2）在弹出表格中输入有关数据，见图1。

图1　背包问题数据输入窗口

第一列itemidentification为物品名称。

第二列unitsavailable为物品限量和背包载重量限制。

第三列unitscapacityrequried为单位物品重量。

最后一列returnfunction为物品价值函数。

2、最短路径问题：

用软件求出图2中最短路线。

设某工厂自国外进口一部精密机器，由机器制造厂至出口港有三个港口可供选择，而进口港又有三个可供选择，进口后可经由两个城市到达目地，其间运输费用如题图中数字所示（单位：

百元）。

试求：

总运费最低廉路线（用动态规划方法求解）。

软件说明：

（1）调用子程序DP，新建问题，选择问题（stagecoach[shortedroute]Problem）,输入标题和节点数。

（2）在弹出表格中输入两点间距离，两点间没有弧连接时不输入数据。

图2

3、生产及存储问题：

某配送中心销售某一商品在未来4个月估计量如表所示。

进价每百件1000元，保管费用每百件50元，每批进货杂费3000元。

假定1月初存货和5月初存货为0。

设每批最多进货量为6件，试求该配送中心在这4个月最优进货计划。

要求建立该问题动态规划模型，并用软件求解。

月份

1

2

3

4

销售量ak

2

3

2

4

软件说明：

（1）调用子程序DP，新建问题，选择生产及存储问题（ProductionandInventoryschedulingProblem）,输入标题和生产时期数。

（2）在弹出表格中输入数据。

数据输入界面如图3所示，图中第2列periodidentification为阶段标识，第3列demand为各期需求量，第4列productioncapacity为每期产品最大生产能力约束，能力无限制，输入M，第5列storagecapacity为每期库存限制，第6列productionsetupcost为生产时固定成本，最后一列为每期变动成本函数，P是产量，H是存量。

图3

实验四　网络图

1、最短路线问题：

用软件完成作业中最短路线问题求解。

软件说明：

（1）调用子程序NetworkModeling，新建问题，选择问题（ShortedPathProblem）,输入标题和节点数。

（2）在弹出表格中输入数据，如果是有向图就按弧方向输入数据，若是无向图，每一条边必须输入两次，无向边变成两条方向相反弧。

点击solveandanayze后系统提示选择图起点和终点，求解结果不仅给出v1到终点最短路径和路长，还给出v1到其余各点最短路径和路长。

2、网络最大流问题：

用软件完成作业中网络最大流问题求解。

软件说明：

调用子程序NetworkModeling，新建问题，选择最大流问题（MaximalFlowProblem）,输入节点数,求解及最短路方法相同。

结果还可显示为网络图，点击results─→graphicssolution，输出最大流网络图。

实验五　存贮论

1、某公司经理一贯采用不允许缺货经济批量公式确定订货批量，因为他认为缺货虽然随后补上总不是好事。

但由于激烈竞争迫使他不得不考虑采用允许缺货策略。

已知对该公司所销产品需求为R＝800件一年。

每次订货费用为150元，存贮费为3元／（件·年），发生短缺时损失为20元／（件·年），试分析：

（1）计算采用允许缺货策略较之原先不允许缺货策略带来费用上节约；

（2）如果该公司为保持一定信誉，自己规定缺货随后补上数量不超过总量15％，任何一名顾客因供应不及时需等下批货到达补上时间不得超过3周。

问这种情况下，允许缺货策略能否被采用?

软件求解

　　不允许缺货时，数据输入界面如图1，数据输出如图2所示。

图1　经济订货批量数据输入窗口

　图2　　经济订货批量数据输出窗口

允许缺货时，输入窗口中，输入项“Unitshortagecostperyear”改为M即可。

结果说明：

（1）由图2知：

不允许缺货时，订购量Q0＝283件，存贮总费用f1=848.53元／年；

（2）同理可求得允许缺货时，订购量Qs＝303件，存贮总费用f2=791.27元／年。

　　最大缺货量S＝40件。

（3）分析

由求解数据知，允许缺货比不允许缺货每年节约费用57.26元，节约率为6.74%。

又最大缺货量S＝40件，故缺货比例为

，小于最大缺货量15％。

而缺货等待最大时间为：

（天），小于3周，故允许缺货策略可以接受。

从这个例题我们可以看出，如果缺货造成损失很小时，缺货模型是一种使存贮总费用较低存贮模型。

2、某食品店出售生日蛋糕，每盒成本5元，售价7元。

若到期卖不完，则削价为每盒4元销售完毕。

已知蛋糕销售量Q服从λ＝8泊松分布。

问应订购多少盒蛋糕为宜？

　解：

（1）建模

这个问题可视为一个需求为随机简单单周期存贮模型。

据题意有：

单位产品利润

α＝7－5＝2（元），滞销损失β＝1，则最佳订购量Q*应满足下面公式：

（2）软件求解　

我们调用存贮论中“Single-periodStochasticDemand（Newsboy）Problem”模型求解，数据输入界面如图3所示，数据输出界面如图4所示。

图3　单周期随机存贮模型数据输入窗口

图4　单周期随机存贮模型数据输出窗口

　　（3）分析

　　　从图4，我们知道最佳订购量Q*＝9盒，期望利润为12.87元。

我们还知道服务水平为71.66%，这里服务水平实际上就是蛋糕需求量小于等于9概率。