运筹学实验指导书(第1部分)汇总

1、预备知识WinQSB软件操作指南WinQSB软件简介QSB是QuantitativeSystemsforBusiness勺缩写，早期的版本是在DOS操作系统下运行的，后来发展成力在Windows操作系统下运行的WinQSB软件，目前已经有2.0版。该软件是由美籍华人Yih-LongChang和KiranDesai共同开发，可广泛应用于解决管理科学、决策科学、运筹学及生产管理等领域的问题。该软件界面设计友好，使用简单，使用者很容易学会并用它来解决管理和商务问题，表格形式的数据录入以及表格与图形的输出结果都给使用者带来极大的方便，同时使用者只需要借助于软件中的帮助文件就可以学会每一步的操作。Win

2、QSB应用软件包可求解如下19类问题：号序程序缩写、文件名名称应用范围1AcceptanceSamplingA抽样分析管种抽样分析、抽任方案设AnalysisSA计、假设分析具有多时期正常、加班、分时、转包生产量，需求量，储2AggregatePlanningPA综合计划编制存费用，生产费用等复杂的整体综合生产计划的编制方法。将问题归结到求解线性规划模型或运输模型D确定型与风险型决策、贝叶斯3decisionanalysisA决策分析决策、决策树、二人零和对策、蒙特卡罗模拟。4DynamicProgrammingPD动态规划最短路问题、背包问题、生产与储存问题sFacilityLocation

3、andLayoutLLF设备场地布局设备场地设计、功能布局、线路均衡布局ForecastingandLinearF预测与线性回简单平均、移动平均、加权移6regressionC归动平均、线性趋势移动平均、指数平滑、多元线性回归、Holt-Winters季节迭加与乘积算法GoalProgrammingandG目标规划与整G数线性目标规多目标线性规划、线性目标规7IntegerLinearGoalPIGP戈上变量可以取整、连续、0Programming划1或无限制经济订货批量、批量折扣、单8InventoryTheoryandSystemsI存储论与存储时期随机模型，多时期动态储TS控制系统存模型

4、，储存控制系统（各种储存策略）9JobSchedulingJ作业调度，编机器加工排序、流水线车间加OB制工作进度表工排序LinearprogrammingandL线性规划与整线性规划、整数规划、写对0integerlinearP-ILP数线性规划偶、灵敏度分析、参数分析programming11MarKovProcessKPM马耳科夫过程转移概率，稳态概率21MaterialrequirementsRPM物料需求计划物料需求计划的编制，成本核planning算31NetworkModelingetN网络模型运输、指派、最大流、最短路、最小支撑树、货郎担等问题，有（无）条件约束、目标函数1NT或

5、约束条件非线性、目标函数4NonLinearProgrammingLP非线性规划与约束条件都非线性等规划的求解与分析1.ProjectSchedulingP1网络计划关键路径法、计划评审技术、5ERT-CPM网络的优化、工程完工时间模Quadraticprogramming6QueuingAnalysis1QueuingSystem8Simulation19QualitycontrolchartsP二次规划Q排队分析AQQQ排队系统模拟SSQ质量管理控制CC图求解线性约束、目标函数是二次型的一种非线性规划问题，变量可以取整数各种排队模型的求解与性能分析、15种分布模型求解、灵敏度分析、服务能力

6、分析、成本分析未知到达和服务时间分布、般排队系统模拟计算建立各种质量控制图和质量分析WinQSB软件的基本操作1 .安装与启动点击WinQSB安装程序的Setup,指定安装目录后，软件自动完成安装。读者在使用该软件时，只需要根据不同的问题，调用程序当中的不同模块，操作简单方便。进入某个模块以后，第一项工作就是建立新问题或者打开已经存盘的数据文件。在WinQSB软件安装完成后，每一个模块都提供了一些典型的例题数据文件，使用者可以先打开已有的数据文件，了解数据的输入格式，系统能够解决什么问题，结果的输出格式等内容。2 .数据的录入与保存数据的录入可以直接录入，同时也可以从Excel或Word文档中

7、复制数据到WinQSB0首先选中要复制的电子表格中单元格的数据，点击复制，然后在WinQSB的电子表格编辑状态下选择要粘贴的单元格，点击粘贴即可。如果要把WinQSB中的数据复制到office文档中，选中WinQSB表格中要复制的单元格，点击Edit/Copy,toclipboard即可。数据的保存，只需要点击File/Saveas即可，计算结果的保存亦相同，只是注意系统以文本格式（*.txt）保存结果，使用者可以编辑该文本文件。实验1线性规划问题的WinQSB应用实验目的1 .了解WinQSB件的集成环境，掌握WinQS既成环境的基本操作方法；2 .掌握利用WinQSBJjLP问题的最优解，

8、并进行灵敏度分析；3 .学会对利用WinQS球得结果的解释。实验内容上机实习教材P9例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每月可用工时1

9、23180232150maxz=50+60巧2$+3毛<1803演i2M<150可之0,之。1.求解步骤Step1启动程序。开始程序/WinQSB/LinearandIntegerProgramming,则弹出如下界面Step2将问题输入系统。点击NewProblem,在弹出的界面中填入或选中参数，如其中ProblemTitle:问题名；NumberofVariables：变量数；NumberofConstraint:约束条件数ObjectiveCriterion:目标函数标准（最大、最小）DefaultVariableType:默认变量类型（非负连续、非负整数、二进制、无符号/无

10、限制）DataEntryFormat:数据输入格式（表格矩阵形式、常规模型形式）参数设置完后按“OK”，在弹出的表中输入数据，如下Step3求解问题。点击SolveandAnalyze,如下图:（1点击“SoketheProblem”，其作用是求解不显示迭代过程，结果如下:从此表可以看出：最优解为（18,48）T,目标函数最优值（最大值）为3780;变量x1的系数在40,90内变化时，最优解不变，但最优值随之改变；变量x2的系数在33.33,75内变化时，最优解不变，但最优值随之改变。从此表可以看出：第一台机器的约束（180）和第二台机器的约束（150）都是紧约束；第一台机器的生产能力在100

11、,225内变化时，其影子价格为16元，第二台机器的生产能力在120,270内变化时，其影子价格为6元。（2点击SolveandDisplaysteps,其作用是求解并显示单纯形法迭代步骤，结果如下:AlSimplexTableauIteTation1XIX2Slack_C1Slnck_C2BasisG(j)50.0000EO.QQOdQ0FLH.S.Slack_C102.00003.00001.00000180.0000Slock_C203.00002.000001-0000150.0000c(j)-zu)50.000060,0000000按菜单SimplexIteration/NextIte

12、ration,弹出如下界面SimplexTableau-Iteration2X1Slock_C1siociTeFBasis50,000060000000RH.SX2GO.OOOO；06S671.00000.3333Q60.000ISlack_CZ01.66670-D.6667kOOOO3D.0QQIc（j）-如11).0000020.000003.600.0001按菜单SimplexIteration/NextIteration,弹出如下界面SimplexTableau-Iteration3XIX2Slack_C1Slack_C2B口sisCO)50.000060,0000Q0R.H.X260

13、.0000O.OOOOl1.0000O.BOOO-0.-400048.XI5000001.00000.0000-040000.600010.0016JOQ0-6.00003.780即为最终单纯形表。（3点击GraphicMethod,其作用使用图解法进行求解.结果如下:2.补充说明(1修改变量类型：系统给出了非负连续、非负整数、0-1型和无符号限制或者无约束4种变量类型选项，当选择了某一种类型后系统默认所有变量都属于该种类型。例如，在上例中，10救1<20直接将x1中的下界(LowerBound)改为10,(UpperBound)上界改为20。x2设定为无约束(Unrestricted)

14、,贝Ux2中的下界(LowerBound)改为-M,(UpperBound)上界改为+M,M是一个任意大的正数。(2)修改变量名和约束名：系统默认变量名为X1,X2,，Xn,约束名为C1,C2,，Cm默认名可以修改，点击菜单栏Edit后，下拉菜单有四个修改选项：修改标题名(ProblemName、变量名(VariableName、约束名(ConstraintName和目标函数准则(max或min。3.灵敏度分析点击菜单栏result或者点击快捷方式图标，下拉菜单有若干选项只显示最优解(SolutionSummary。约束条件摘要(ConstraintSummary,比较约束条件两端的值。对目标

15、函数进行灵敏度分析(SensitivityAnalysisofOBJ。对约束条件右端常数进行灵敏度分析(SensitivityAnalysisofRHS求解结果组合报告(CombinedReport,显示详细综合分析报告。进行参数分析(PerformParametricAnalysis,某个目标函数系数或约束条件右端常数带有参数，计算出参数的变化区间及其对应的最优解，属于参数规划内容。显示最后一张单纯性表（FinalSimplexTableau。显示另一个基本最优解（ObtainAlternateOptimal,存在多重解时，系统显示另一个基本最优解，然后考虑对基本最优解进行组合可以得到最优解

16、的通解。显示系统运算时间和迭代次数（ShowRunTimeandItration。不可行性分析（InfeasibilityAnalysis,线性规划问题无可行解时，系统指出存在无可行解的原因，无界性分析（UnboundednessAnalysis线性规划问题存在无界解时，系统指出存在无界解的可能原因。【问题1】对目标系数c2进行灵敏度分析点击Results/PerformParametricAnalysis;弹出对话框，选择分析目标系数及决策变量，如下图单击OK得结果如下:分析如下:（1c2从60增加到75,目标函数值从3780增力口至I4500,斜率48,出基变量x1,进基变量Slack_c

17、2;（2c2从75增加到工，目标函数值从4500增力口至：工，斜率60;（3c2从60减少到33.33,目标函数值从3780减少到2500,斜率48,出基变量x2,进基变量Slack_c1;(4c2从33.33减少到到-力，目标函数值保持2500不变。点击Results/GraphicParametricAnalysis,4c2变化的参数分析图ijS-【问题2】对右端项b2进行灵敏度分析点击Results/PerformParametricAnalysis;弹出对话框，选择选项，如下图单击OK得结果如下:分析如下：(1b2从150增力口至IJ270,目标函数值从3780增加到4500,斜率6,

18、出基变量x2,进基变量Slack_c2;(2b2从270增加到工:，目标函数值保持4500不变（3b2从150减少到120,目标函数值从3780减少到3600,斜率6,出基变量x1,进基变量Slack_c1;（4b2从120减少到到0,目标函数值从3600减少到0,斜率30,出基变量x2。点击Results/GraphicParametricAnalysis,4b2变化的参数分析图4 .写出对偶模型点击菜单栏Format/SwitchtoDualForm,系统自动给出线性规划的对偶模型，冉点击一次给出原问题模型。5 .点击Edit/InsertaContraint（插入一个约束）求解。6 .点

19、击Edit/InsertaVariable；（插入一个变量）求解。7 .点击Edit/DeleteaContraint（删除一个约束）求解。8 .注意每一个问题都是针对原线性规化问题分析求解，每一步都必须回到原模型。操作技巧是，做完一个问题后退出所有活动窗口，打开存储的原文件。实验2整数规划问题的WinQSB应用实验目的1 .掌握利用WinQSB求解整数规划（纯整数、混合整数、0-1规划；2 .掌握利用WinQSB求解分配问题的方法；3 .学会对利用WinQSB求得结果的解释。实验内容1 .上机实习教材P106例1;并理解P114分支定界法、P116割平面法的求解过程。2 .上机实习教材P11

20、0例2;并理解匈牙利法的求解过程。实验要求1 .给出P106例1的理论求解（分支定界法、割平面法。2 .给出P110例2的匈牙利法求解过程3 .完成【实现提示】中的所有操作，并合理组织写出实验报告。实现提示【提示1】WinQSB求解整数规划的步骤例2-1某企业接受某项产品订货，需求量为每日3500千克，现有3种生成过程供选择，各生产过程所需固定成本（投资、生产成本、最大日产量如下表生产过程的种类固定投资/元生产成本（兀/千克最大日产量（千克甲100052000乙200043000丙300034000问如何安排生产？1,采用第附4:产过程；设.0,小采用第/种生产过程，xi为采用第i种生产过程生

21、产的数量，i=1,2,3.minz=I(KM)J,十2000y十3000M+5A+3a,*/x二+/>3500.£2000vt.<3000%<44KX)内M-3拉y2&内£加公/1,3=0,l;x(_3之0这是6个变量，7个约束的混合ILP问题。Step1启动程序。开始程序/WinQSB/LinearandIntegerProgramming/File/NewProblem,选择参数，则弹出如下界面按“OK”，在弹出的表中输入数据，如下(1更改变量名。将x4、x5、x6改为y1、y2、y3。单击Edit/VarivbleNames,在弹出的窗口更改

22、，结果如下：(2修改变量类型。按“OK”，在弹出的输入数据表中双击y1,则y1的变量类型由连续型(Continnuous变为整数型(Integer,再双击一次则变为二进制型(Binary。同样将y2,y3变为二进制。按模型要求，双击相应的不等号，修改Direction。Step2将问题输入系统。注意模型中的M用较大的数代替，如-9999.Step3求解问题。点击SolveandAnalyze/SolvetheProblem果如下:由结果知:(1虽y2=1，但x2=0.0001所以最优生产方式应选第3种(y3=1，生产3500千克(x3=3500,总成本13500元(15500-2000=135

23、0。其中生产成本10500元，固定成本3000元。(2x1的缩减成本为2.5元，若增加使用第1种生产方式，每件增加变动成本2.5元，并增加固定成本1000元。若增加使用第2种生产方式，增加固定成本2000元。若增加使用第3种生产方式，将再增加固定成本3000元。(3由松弛变量可知，第3种生产方式生产能力尚有500千克剩余。若产量在增加500千克以内时，固定成本不会发生变化。【提示2WinQSB求解分配问题的步骤例2-2有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、Do现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间

24、最少？任务ABC人员甲6711乙459丙3110丁598D2842Step1启动程序。开始程序/WinQSB/NetworkModeling/File/NewProblem,选择参数，则弹出如下界面选择第3个问题类型，输入任务和人员数。由于效率矩阵中行、列代表的是任务或人员可能不同，故NumberofObjects代表的是行数，NumberofAssignments代表的是列数。输入相应的值，并选取目标要求，单击OK,弹出数据编辑窗口。Step2将问题输入系统。(1修改人员、任务名称：Edit/NodeNames在弹出的窗口操作，结果如下:(2输入效率矩阵。单击OK,输入效率矩阵，如下:r-J

25、Step3求解问题。点击SolveandAnalyze/SolvetheProblem,结果如下:即最优的安排是甲完成任务D,乙完成任务A,丙完成任务B,丁完成任务C,总时间为15.说明：(1WinQsb求解分配问题，目标可以是最大化，也可以是最小化。人员数与任务数可以相等，也可不等。(2)点击点击SolveandAnalyze/SolvetheDisplaySteps-TableaU寸,系统输出匈牙利解法的每一步迭代结果。(3点击菜单栏Results/GraphicSolution,以网络图的形式显示结果。实验3动态规划问题的WinQS而用实验目的1 .理解最短路问题、背包问题、生产与存储问

26、题的动态规划算法；2 .掌握利用WinQSB求解以上3类问题的方法；3 .学会对利用WinQSB求得结果的解释。实验内容1 .上机实习教材P198例1;并理解动态规划问题的解题思路。2 .上机实习教材P213例8;并掌握动态规划求解背包问题的求解方法。3 .上机实习教材P210例6;并掌握动态规划求解生产问题的求解方法。实验要求1 .给出以上3个例题的理论求解。2 .完成【实现提示】中的所有操作，并合理组织写出实验报告。实现提示【提示1】WinQSB求解最短路问题的步骤Step1启动程序。开始程序/WinQSB/DynamicProgramming/File/NewProblem,选择参数最短

27、路问题（StagecoachShortestRouteProblem节点数（NumberofNodes,单击OK。Step2单击Edit/NodeNames,修改节点名称，单击OK,在弹出的数据窗口输入数据（l邻接矩阵。Step3点击SolveandAnalyze/SolvetheProblem,求解该问题。【提示2】WinQSB求解背包问题的步骤【例3-1】一商贩拟用一10吨载重量的大卡车装载3种货物，如下表，问如何组织装载，可使总价值最大。货物编号123单位重量（吨单位价值Step1启动程序。开始程序/WinQSB/DynamicProgramming/File/NewProblem,选择参数背包问题（KnapsackProblem,输入