运筹学实验指导书(第1部分).doc

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

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date运筹学实验指导书(第1部分)运筹学实验指导书预备知识 WinQSB 软件操作指南WinQSB 软件简介QSB 是 Quantitative Systems for Business 的缩写，早期的版本是在 DOS 操作系统下运行的， 后来发展成为在 Windows 操作系统下运行的 WinQSB软件，目前已经有2.0 版。该软件是由美籍华人 Yih-Long Chan

2、g 和 Kiran Desai 共同开发，可广泛应用于解决管理科学、决策科学、运 筹学及生产管理等领域的问题。该软件界面设计友好，使用简单，使用者很容易学会并用它来解 决管理和商务问题，表格形式的数据录入以及表格与图形的输出结果都给使用者带来极大的方便，同时使用者只需要借助于软件中的帮助文件就可以学会每一步的操作。WinQSB 应用软件包可求解如下19 类问题：序号程 序缩写、文件名名称应用范围1Acceptance Sampling AnalysisASA抽样分析各种抽样分析、抽样方案设计、假设分析2Aggregate PlanningAP综合计划编制具有多时期正常、加班、分时、转包生产量，

3、需求量，储存费用，生产费用等复杂的整体综合生产计划的编制方法。将问题归结到求解线性规划模型或运输模型3decision analysis DA决策分析确定型与风险型决策、贝叶斯决策、决策树、二人零和对策、蒙特卡罗模拟。4Dynamic ProgrammingDP动态规划最短路问题、背包问题、生产与储存问题5Facility Location and Layout FLL设备场地布局设备场地设计、功能布局、线路均衡布局6Forecasting and Linear regressionFC预测与线性回归简单平均、移动平均、加权移动平均、线性趋势移动平均、指数平滑、多元线性回归、Holt-Wint

4、ers季节迭加与乘积算法7Goal Programming and Integer Linear Goal Programming GPIGP目标规划与整数线性目标规划多目标线性规划、线性目标规划，变量可以取整、连续、01或无限制8Inventory Theory and Systems ITS存储论与存储控制系统经济订货批量、批量折扣、单时期随机模型，多时期动态储存模型，储存控制系统（各种储存策略）9Job SchedulingJOB作业调度，编制工作进度表机器加工排序、流水线车间加工排序10Linear programming and integer linear programming

5、LPILP线性规划与整数线性规划线性规划、整数规划、写对偶、灵敏度分析、参数分析11MarKov Process MKP马耳科夫过程转移概率，稳态概率12Material requirements planning MRP物料需求计划物料需求计划的编制，成本核算13Network Modeling Net网络模型运输、指派、最大流、最短路、最小支撑树、货郎担等问题，14NonLinear ProgrammingNLP非线性规划有（无）条件约束、目标函数或约束条件非线性、目标函数与约束条件都非线性等规划的求解与分析15Project Scheduling PERT-CPM网络计划关键路径法、计划

6、评审技术、网络的优化、工程完工时间模拟、绘制甘特图与网络图16Quadratic programming QP二次规划求解线性约束、目标函数是二次型的一种非线性规划问题，变量可以取整数17Queuing AnalysisQA排队分析各种排队模型的求解与性能分析、15种分布模型求解、灵敏度分析、服务能力分析、成本分析18Queuing System SimulationQSS排队系统模拟未知到达和服务时间分布、一般排队系统模拟计算19Quality control chartsQCC质量管理控制图建立各种质量控制图和质量分析WinQSB 软件的基本操作1. 安装与启动 点击 WinQSB 安装程

7、序的 Setup，指定安装目录后，软件自动完成安装。读者在使用该软件时，只需要根据不同的问题，调用程序当中的不同模块，操作简单方便。进入某个模块以后，第一项工作就是建立新问题或者打开已经存盘的数据文件。在 WinQSB 软件安装完成后，每一个模块都提供了一些典型的例题数据文件， 使用者可以先打开已有的数据文件， 了解数据的输入格式，系统能够解决什么问题，结果的输出格式等内容。2.数据的录入与保存数据的录入可以直接录入，同时也可以从 Excel 或 Word 文档中复制数据到 WinQSB。首先 选中要复制的电子表格中单元格的数据，点击复制，然后在 WinQSB 的电子表格编辑状态下选择要粘贴的

8、单元格，点击粘贴即可。 如果要把 WinQSB 中的数据复制到 office 文档中，选中 WinQSB 表格中要复制的单元格， 点击 Edit/Copy，to clipboard 即可。 数据的保存，只需要点击 File/Save as 即可，计算结果的保存亦相同，只是注意系统以文本格式（*.txt）保存结果，使用者可以编辑该文本文件。实验1 线性规划问题的WinQSB应用实验目的 1.了解WinQSB软件的集成环境，掌握WinQSB集成环境的基本操作方法； 2.掌握利用WinQSB求解LP问题的最优解，并进行灵敏度分析； 3.学会对利用WinQSB求得结果的解释。实验内容上机实习教材P9例

9、2，并将求解结果与P15相应的图解法结果、P26的例5的单纯形解法相比较，并看P61-62的影子价格、P65-70灵敏度分析的例题6-9。实验要求1.首先给出P9例2的理论求解(图解法、单纯行法、灵敏度分析)。2.完成【实现提示】中的所有操作，并合理组织写出实验报告。实现提示 例 求解下列LP问题 AMC 公司用两种机器制造两种产品A 和B，有关数据见表1-1 所示，当前市场对产品A 和B 的需求为供不应求，它们的市场价格分别为产品A 每个50 元，产品B每个60 元，请问如何安排生产可使其月收入最高？机器A机器B每月可用工时1231802321501. 求解步骤Step 1 启动程序。开始程

10、序/WinQSB/Linear and Integer Programming，则弹出如下界面Step 2 将问题输入系统。点击New Problem，在弹出的界面中填入或选中参数，如下：其中 Problem Title：问题名； Number of Variables：变量数；Number of Constraint: 约束条件数 Objective Criterion: 目标函数标准（最大、最小） Default Variable Type: 默认变量类型（非负连续、非负整数、二进制、无符号/无限制） Data Entry Format: 数据输入格式（表格矩阵形式、常规模型形式）参数设置

11、完后按“OK”，在弹出的表中输入数据，如下Step 3 求解问题。点击Solve and Analyze，如下图：(1)点击“Solve the Problem”，其作用是求解不显示迭代过程，结果如下：从此表可以看出：最优解为（18，48）T，目标函数最优值（最大值）为3780；变量x1 的系数在40，90内变化时，最优解不变，但最优值随之改变；变量x2 的系数在33.33，75内变化时，最优解不变，但最优值随之改变。从此表可以看出：第一台机器的约束（180）和第二台机器的约束（150）都是紧约束；第一台机器的生产能力在100，225内变化时，其影子价格为16 元，第二台机器的生产能力在120

12、，270内变化时，其影子价格为6 元。(2)点击Solve and Display steps，其作用是求解并显示单纯形法迭代步骤，结果如下：按菜单Simplex Iteration/Next Iteration,弹出如下界面按菜单Simplex Iteration/Next Iteration,弹出如下界面即为最终单纯形表。(3)点击Graphic Method,其作用使用图解法进行求解.结果如下：2. 补充说明(1)修改变量类型：系统给出了非负连续、非负整数、0-1 型和无符号限制或者无约束 4 种变量类型选项，当选择了某一种类型后系统默认所有变量都属于该种类型。例如，在上例中，10 x

13、1 20 ，直接将 x1 中 的下界 （Lower Bound） 改为 10， （Upper Bound） 上界改为 20。 x2设定为无约束 （Unrestricted），则x2 中 的下界 （Lower Bound） 改为 M， （Upper Bound） 上界改为 +M， M 是一个任意大的正数。 （2）修改变量名和约束名：系统默认变量名为 X1，X2，Xn，约束名为 C1，C2，Cm。默认名可以修改，点击菜单栏 Edit 后，下拉菜单有四个修改选项：修改标题名(Problem Name)、变量名(Variable Name)、 约束名(Constraint Name)和目标函数准则(m

14、ax 或 min)。3. 灵敏度分析点击菜单栏 result 或者点击快捷方式图标，下拉菜单有若干选项。只显示最优解(Solution Summary)。 约束条件摘要(Constraint Summary)，比较约束条件两端的值。 对目标函数进行灵敏度分析(Sensitivity Analysis of OBJ)。 对约束条件右端常数进行灵敏度分析(Sensitivity Analysis of RHS)。 求解结果组合报告(Combined Report)，显示详细综合分析报告。 进行参数分析(Perform Parametric Analysis)，某个目标函数系数或约束条件右端常数带有

15、参数，计算出参数的变化区间及其对应的最优解，属于参数规划内容。 显示最后一张单纯性表(Final Simplex Tableau)。 显示另一个基本最优解(Obtain Alternate Optimal)，存在多重解时，系统显示另一个基本最优解，然后考虑对基本最优解进行组合可以得到最优解的通解。 显示系统运算时间和迭代次数(Show Run Time and Itration)。 不可行性分析(Infeasibility Analysis)，线性规划问题无可行解时，系统指出存在无可行解的原因，无界性分析(Unboundedness Analysis)，线性规划问题存在无界解时，系统指出存在无

16、界解的可能原因。【问题1】 对目标系数c2进行灵敏度分析 点击Results/ Perform Parametric Analysis,弹出对话框，选择分析目标系数及决策变量，如下图单击OK得结果如下：分析如下： (1)c2从60增加到75，目标函数值从3780增加到4500，斜率48，出基变量x1，进基变量Slack_c2; (2) c2从75增加到，目标函数值从4500增加到，斜率60;(3)c2从60减少到33.33，目标函数值从3780减少到2500，斜率48，出基变量x2，进基变量Slack_c1;(4) c2从33.33减少到到-，目标函数值保持2500不变。点击Results/

17、Graphic Parametric Analysis,得c2变化的参数分析图【问题2】 对右端项b2进行灵敏度分析点击Results/ Perform Parametric Analysis,弹出对话框，选择选项，如下图单击OK得结果如下：分析如下： (1)b2从150增加到270，目标函数值从3780增加到4500，斜率6，出基变量x2，进基变量Slack_c2; (2) b2从270增加到，目标函数值保持4500不变。(3)b2从150减少到120，目标函数值从3780减少到3600，斜率6，出基变量x1，进基变量Slack_c1;(4) b2从120减少到到0，目标函数值从3600减少

18、到0，斜率30，出基变量x2。点击Results/ Graphic Parametric Analysis,得b2变化的参数分析图4. 写出对偶模型点击菜单栏 Format/Switch to Dual Form，系统自动给出线性规划的对偶模型，再点击一次 给出原问题模型。5.点击Edit/Insert a Contraint（插入一个约束）求解。6.点击Edit/Insert a Variable（插入一个变量）求解。7.点击Edit/Delete a Contraint（删除一个约束）求解。 8.注意每一个问题都是针对原线性规化问题分析求解，每一步都必须回到原模型。操作技巧是，做完一个问题

19、后退出所有活动窗口，打开存储的原文件。实验2 整数规划问题的WinQSB应用实验目的 1.掌握利用WinQSB求解整数规划(纯整数、混合整数、0-1规划)； 2.掌握利用WinQSB求解分配问题的方法； 3.学会对利用WinQSB求得结果的解释。实验内容1. 上机实习教材P106例1；并理解P114分支定界法、P116割平面法的求解过程。2. 上机实习教材P110例2；并理解匈牙利法的求解过程。实验要求1.给出P106例1的理论求解(分支定界法、割平面法)。2.给出P110例2的匈牙利法求解过程3.完成【实现提示】中的所有操作，并合理组织写出实验报告。实现提示【提示1】 WinQSB求解整数规

20、划的步骤 例2-1 某企业接受某项产品订货，需求量为每日3500千克，现有3种生成过程供选择，各生产过程所需固定成本(投资)、生产成本、最大日产量如下表生产过程的种类固定投资/元生产成本 (元/千克)最大日产量(千克)甲乙丙100020003000543200030004000问如何安排生产？ 设 xi为采用第i种生产过程生产的数量，i=1,2,3.这是6个变量，7个约束的混合ILP问题。Step 1 启动程序。开始程序/WinQSB/Linear and Integer Programming/File /New Problem，选择参数，则弹出如下界面按“OK”，在弹出的表中输入数据，如下

21、(1) 更改变量名。将x4、x5、x6改为y1、y2、y3。单击Edit/Varivble Names,在弹出的窗口更改，结果如下：(2)修改变量类型。按“OK”，在弹出的输入数据表中双击y1，则y1的变量类型由连续型(Continnuous)变为整数型(Integer)，再双击一次则变为二进制型(Binary)。同样将y2,y3变为二进制。按模型要求，双击相应的不等号，修改Direction。Step 2 将问题输入系统。注意模型中的M用较大的数代替，如-9999.Step 3 求解问题。点击Solve and Analyze/ Solve the Problem,结果如下： 由结果知：(1

22、)虽y2=1,但x2=0.0001,所以最优生产方式应选第3种(y3=1),生产3500千克(x3=3500)，总成本13500元(15500-2000=13500)。其中生产成本10500元，固定成本3000元。(2)x1的缩减成本为2.5元，若增加使用第1种生产方式，每件增加变动成本2.5元，并增加固定成本1000元。若增加使用第2种生产方式，增加固定成本2000元。若增加使用第3种生产方式，将再增加固定成本3000元。 (3)由松弛变量可知，第3种生产方式生产能力尚有500千克剩余。若产量在增加500千克以内时，固定成本不会发生变化。【提示2】 WinQSB求解分配问题的步骤例2-2有一

23、份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？ 任务人员ABCD甲乙丙丁643575191191082842Step 1 启动程序。开始程序/WinQSB/Network Modeling/File/New Problem，选择参数，则弹出如下界面选择第3个问题类型，输入任务和人员数。由于效率矩阵中行、列代表的是任务或人员可能不同，故Number of Objects代表的是行数，Number of Assignments代表的是列数。输入相应的值，并选取目标要

24、求，单击OK,弹出数据编辑窗口。Step 2 将问题输入系统。(1) 修改人员、任务名称：Edit/Node Names,在弹出的窗口操作，结果如下：(2) 输入效率矩阵。单击OK,输入效率矩阵，如下：Step 3 求解问题。点击Solve and Analyze/ Solve the Problem,结果如下：即最优的安排是甲完成任务D，乙完成任务A，丙完成任务B，丁完成任务C，总时间为15. 说明：(1)WinQsb求解分配问题，目标可以是最大化，也可以是最小化。人员数与任务数可以相等，也可不等。（2）点击点击 Solve and Analyze/Solve the Display Ste

25、ps-Tableau 时，系统输出匈牙利解法的每一步迭代结果。(3) 点击菜单栏 Results/Graphic Solution，以网络图的形式显示结果。实验3 动态规划问题的WinQSB应用实验目的 1.理解最短路问题、背包问题、生产与存储问题的动态规划算法； 2.掌握利用WinQSB求解以上3类问题的方法； 3.学会对利用WinQSB求得结果的解释。实验内容1.上机实习教材P198例1；并理解动态规划问题的解题思路。2.上机实习教材P213例8；并掌握动态规划求解背包问题的求解方法。3.上机实习教材P210例6；并掌握动态规划求解生产问题的求解方法。实验要求1.给出以上3个例题的理论求解

26、。2.完成【实现提示】中的所有操作，并合理组织写出实验报告。实现提示【提示1】 WinQSB求解最短路问题的步骤 Step 1 启动程序。开始程序/WinQSB/Dynamic Programming/File/New Problem，选择参数最短路问题(Stagecoach Shortest Route Problem)，节点数(Number of Nodes),单击OK。Step 2 单击Edit/Node Names，修改节点名称，单击OK，在弹出的数据窗口输入数据(l邻接矩阵)。Step 3点击Solve and Analyze/ Solve the Problem，求解该问题。【提示

27、2】 WinQSB求解背包问题的步骤【例3-1】一商贩拟用一10吨载重量的大卡车装载3种货物，如下表，问如何组织装载，可使总价值最大。货物编号 1 2 3单位重量(吨)单位价值 3 4 5 4 5 6Step 1启动程序。开始程序/WinQSB/Dynamic Programming/File/New Problem，选择参数背包问题(Knapsack Problem)，输入物品种类数(Number of Items),弹出如下界面Step 2单击OK，在弹出的数据窗口输入数据,装载物品的价值必须是公式，该值=物品的价值系数乘以x，x表示装载的数量。其中第3列为各物品最大装载重量和总载重量；第

28、4列为各物品单件的重量，最后一列为装载物品的价值。Step 3点击Solve and Analyze/ Solve the Problem，求解该问题。即物品1装载2吨，物品2装载1吨，总价值13个货币单位。【提示3】 WinQSB求解生产存储问题的步骤【例3-1】一个工厂生产某种产品，1-6月份生产成本和产品需求量的变化情况如下表月份(k)1 2 3 4 5 6需求量(件)生产能力(件)单位产品成本单位产品存储成本 20 30 35 40 25 45 50 50 50 40 40 40 15 12 16 19 18 16 2 1 1.5 1.5 1.8 1.8每批生产准备成本为C=3000元

29、，月底交货，分别求解下列问题(1)1月份与6月底存储量为0，仓库容量为s=50件，不允许缺货且生产能力无限。(2)1月初存储量有20件产品，仓库容量为s=40件，不允许缺货，生产能力见上表。Step 1启动程序。开始程序/WinQSB/Dynamic Programming/File/New Problem，选择参数生产与存储问题(Production and Inventory Problem)，时期数(Number of Periods),弹出如下界面Step 2单击OK，在弹出的数据窗口输入各期需求量(Demand)、生产能力(Production Capacity)、存储能力（Storage Capacity）、调整费用(Production Setup Cost)、变动成本计算公式(Variable Cost Funtion，该公式中p为产量，h为存储量)。 Step 3点击Solve and Analyze/ Solve the Problem，求解该问题。最有生产策略是第1、3、5月分别生产50、75、70件，总成本为12411元。即为(1)的解。 为求得(2)的解，只需将Step2中弹出的数据窗口的最后一行(Initial Inventory)改为20，将存储能力（Storage Capacity）改为40，并修改生产能力。-