运筹学实验指导书

《运筹学》

实验指导书

西安交通大学

管理学院《运筹学》课程组

二零零五年四月

序言

指导书紧密配合《运筹学》课程的理论教学，系统地介绍了教学应用软件

QSB+（QuantitationSystemsforBusinessPlus）和最新的建模与求解方法（Spreadsheet

方法）。QSB+是运筹学上机实验软件，它技术成熟稳定，内容齐全，使用方便，对

于加深理解课程内容，提高初学者学习掌握本课程的兴趣具有良好的补充作用。

Spreadsheet建模与求解方法是近年来国际上在管理科学教学与应用方面流行而有

效的方法。它为管理科学提供了一种问题描述、数据处理、模型建立与求解的有效

工具，是在Excel（或其它）背景下就所需求解的问题进行描述与展开，然后建立数

学模型，并使用Excel的命令与功能进行预测、模拟、决策、优化等运算与分析。

指导书分为两部分，第一部分是QSB+的使用，通过五个实验来完成，每个

实验主要包括三个方面内容：①内容简介；②操作步骤；③实例分析与操作，另外

对WINQSB+进行了简要说明。第二部分是Spreadsheet建模与求解方法介绍，以

实例的形式说明其中的重点和常用部分，实验内容基本同QSB+,对其余内容感兴

趣的同学可参考相关资料。五个实验分别为：①线性规划；②运输问题；③动态规

划；④网格模型；⑤排队论。

指导书基于教师的教学过程和学生的上机实验，由《运筹学》课程组统一规划，

任课教师和参加上机辅导的研究生共同参与，最终由博士生薛顺利统稿完成。在编

写过程中参考了相关教材和资料，并得到许多老师和同学的热情帮助，在此表示衷

心感谢。由于水平有限，时间仓促，对于指导书中不妥与疏漏之处，恳请老师和同

学们提出宝贵意见，以便进一步修改。

I

第一部分QSB+软件

QSB+是用于《运筹学》的应用软件包，技术成熟，运行稳定，操作方便，对硬件要

求较低，非常适合初学者上机使用。

第一章QSB+内容简介

第一节QSB+的基本内容

QSB+是QSB的升级应用软件包，可求解如下16类问题：

1、线性规划LinearProgramming(LP)

2、整数规划IntegerLinearProgramming(ILP)

3、线性目标规划LinearGoalProgramming(LGP)

4、二次规划QuadraticProgramming(QP)

5、运输/转运问题TransportationandTransshipmentProblems(TRP)

6、指派/旅行商问题AssignmentandTravelingSalesmanProblems(ASTS)

7、网络模型NetworkModeling(NET)

8、关键路径法CriticalPathMethod(CPM)

9^计划评审技术ProgramEvaluatingandReviewTechnique(PERT)

10、动态规划DynamicProgramming(DP)

11、库存论InventoryTheory(INVT)

12、排队论QueuingTheory(QUEUE)

13>排队系统仿真QueuingSystemSimulation(QSIM)

14、决策与可靠性理论DecisionandProbabilityTheory(DSPB)

15、马尔科夫过程MarkovProcess(MKV)

16>时间序列预测TimeSeriesForecasting(TSFC)

QSB+采用分级菜单结构，思路清晰，使用方便。在操作过程中程序与用户交互进行,

2

自动地给出必要提示，以方便实现模型的建立、修改、数据输入及计算结果的输出等功能。

第二节软件结构介绍

本软件采用程序化菜单结构，大致可分为三级（如图1—1所示），第一级菜单为主菜

单（程序菜单），共分为十八个分项，分别为：①LP,②ILP,③GP,……，等等。可用

SolvewithStepsSolvewithoutStepsSpecialOperations

图1—1QSB+的菜单结构图

移动键（tI）选中的相应程序，也可以打入相应的数字或字母，按回车键进入相应程序

的下•级菜单。第二级菜单为功能菜单，根据选择程序的不同略有差异，如果选择LP程

序，则二级菜单分别为：©Overview,②Enter，③Read,④Show等等，

3

同样可用移动键（tI）选中相应功能，也可以打入相应的数字，按回车键确定，以交互

方式完成相应的操作。第三级菜单为相应功能的三级菜单，根据所选功能的不同而有所区

别。如果第二级菜单选择⑤Solveproblem菜单，则三级菜单会显示为：①SolvewithSteps,

②SolvewithoutSteps,©SpecialOperation.,等等。根据用户需要选择所需子项，按

回车键，使其执行即可。

第三节菜单内容说明

一、主菜单（程序菜单）

主菜单（程序菜单）（如图1—2所示）显示出QSB+所能完成的运筹学中的各种问

题的程序名称，务必认真阅读，搞清楚各程序和《运筹学》内容的对应关系，为后续学习

作好准备，具体可以参考第一节内容。

WelcometoQSB+(QuantitativeSystemsforBusinessPlus)!

Youmaychoosefromfollowingmanagementsciencedecisionsupportsystems:

CodeCode

No.ProgramNo.Program

1--LinearprogrammingA--Dynamicprogramming

2--IntegerlinearprogrammingB~-Inventorytheory

3--GoalprogrammingC~-Queuingtheory

4--QuadraticprogrammingD-•Queuingsystemsimulation

5--TransshipmentproblemE--Decision/probabilitytheory

6--Assignment/IYavel-salesmanF-Markovprocess

1--NetworkmodelingG--Timeseriesforecasting

8・・Projectscheduling-CPMII--Specifyprinter/displayadapter

9--Projectscheduling-PERTI--ExitfromQSB+

Note:UseoptionHtospecifyifyouconothaveanIBMgraphicsprinteror

color/graphicsadapter.Thiswillmakescreen/outputslessconfusing.

Programs1to3areinQSB+(I),programs4to9areinQSB+(II),and

programsAtoGareinQSB+(III)ifyoupurchase5.25"diskettes.

图1—2主菜单（程序菜单）图

二、功能菜单

4

选择某个程序后，按回车键即可进入相应的功能菜单，现以线性规划（LP）功能菜

单为例加以说明，其它功能菜单与此相似。

在主菜单（程序菜单）中选择选项1（LP项），按回车键即可进入线性规划（LP）程

序的功能菜单（如图1—3所示），现对各功能说明如下：

选项（Option）1：该选项可浏览该程序的基本情况，说明程序的功能和其它限制条

件等。

选项（Option）2：当有一个新问题时，用该选项可以将问题输入程序，可以在此定

义问题的范围，说明用固定格式还是自由格式输入问题等。

选项（Option）3：该选项可以调入以前所保存的问题。

WelcometoyourLinearProgramming(LP)DecisionSupportSystem!

TheoptionsavailableforLPareasfollows.

Ifyouareafirst-timeuser,youmightbenefitfromoption1.

OptionFunction

1——•-OverviewofLPDecisionSupportSystem

2-Enternewproblem

3----Readexistingproblenifromdisk(ctte)

4-Showinputdata

5----Solveproblem

6----Saveproblemondisk(ette)

7—Modifyproblem

8-Showfinalsolution

9Returntotheprogrammenu

0—ExitfromQSB+

图1—3LP程序的功能菜单图

选项（Option）4：显示输入的数据

选项（Option）5：求解问题

选项（Option）6：保存输入的问题备用

选项（Option）7：可以对问题的结构参数进行修改

选项（Option）8：详细或以特殊格式显示问题的最终结果。

选项（Option）9：返回程序菜单。

选项（Option）10：退出QSB+系统。

三、三级菜单（求解菜单）

5

三级菜单（求解菜单）的内容各不相同，但比较具体，容易理解，请自己阅读几个这

样的菜单，以便对整体功能有一个完整的了解。

图1—4显示的杲线性视划问题功能菜单选项1的内容。

如果用固定格式输入问题，你可以用移动键

（tI或后退键（BS）移动光标到相应

位置纠正错误。按照屏幕下面的提示进入下页

选择自由或固定格式

或前一•页。在约束条件中科学计数法是允许

输入数据，约束可以

的，如1.00、100.0、+100和1.0E+2是相同的,

单独输入。

＞=、＞、=＞＞和2是相同的，＜=＞V、=＜和忘

是相同的。

LPModelEntryforSAMPLE

Pleaseothefollowingconventionswhenenteringaproblem:

(1)Youmachooseafreeorfixedformattoenteryourdata.Bound

constraintscanbeenteredseparately.

(2)Forthefixedformatentry,ynnmayrnrrwterrorsbypressingtherows

orBSkeytomovethecursortothecorrectpositionandfollowthe

instructionatthebottomofscreentoproceedtotheprevious/nextpage.如果用自由

Scientificnumericnotationisallowedforthefixedformatsuchthat格式输入，请

100,100.0,1100,and1.0E+2arethesame.>=,>,=>,and>参考帮助信

and<=,<,=<,and<arethesameforconstraintdirections.息。

(3)Forthefreeformatentry,refertothehelpinformationfordirection：

(4)Youcanmodifytheenteredproblemusingoption7ofthefunctionmenu.、

Maximize(1)orminimize(2)theobjective?(Enter1or2)<1>K4你可以用功

Numberofvariables(excludingslacks/artificials):<4>\能菜单选项7

Numberofconstraints(excludingbounds):<3>修改已输入

Approximatepercentageofnon-zeros(default5%):<>的问题。

Usethedefaultvariablenames(Xl,...,Xn)(l(Yes),0(No)):<0>

Usethefreeformattoenterdata(l(Yes),0(No)):<0>

Usethefixedformatto映rbounds/integrality(1(Yes),0(No)):<0>

目标函数取最大值（1）或最小值（2）?（输入1或2）：<1>

决策变量数（不包括松弛变量/人工变量）：<4>

约束条件数（不包括边界条件）：<3>

非零近似百分数（近似值）（默认值为5%）：<>

使用默认变量名(XI,X2,……Xn)(l(Yes),0(No))：<0>

使用自由格式输入数据（l（Yes）,0（No））：<0>

使用固定各式输入边界/完整性条件（l（Yes）,0（No））：<0>

图1—4线性规划问题浏览

6

第二章操作以及算例示范

第一节线性规划（LinearProgramming）

一、线性规划求解问题的特别说明

1、能求解的线性规划问题的规模取决于计算机的内存；

2、数学模型的输入可以采用自由格式，也可以采用固定格式（选择了固定格式后，

只需在相应位置输入数据），一般采用固定格式：

3、变量名可以自己命名，但最多不能超过8个字符，也可以用默认的变量名，如：

XI,X2,.,Xn：

4、数据文件可保存到磁盘上，文件扩展名为：MPS；

5、输入问题时，可以用移动键（f-tI）、BS（后退键）、空格健和回车键移动

光标或翻页；如果要放弃输入的数据，可同时按“Ctrl”和“End”犍，并同时放

开，即可终止继续输入并放弃已输入的数据，返回到功能菜单；

6、给问题命名时，最长不得超过20个字符；

7、如果遇到未说明的问题，请注意仔细阅读英语显示；

8、显示中有关字母意义说明如下：

Sn：表示第n个约束条件的松驰变量（含剩余变量）；

An：表示第n个约束条件的人工变量；

A<ij）：表示第i个约束第j个变量的系数：

B⑴：表示第i个约束右边常数值；

C<j）：表示目标函数中第j个变量的系数；

M：大M法中的M：

C⑴一Z⑴：表示第j个变量的检验数。

二、用LP求解问题的步骤

1、分析问题，确定决策变量;

7

2、建立数学模型(参考教材)；

3、输入有关数据，或调入已存问题；

4、如果要核查数据，则选择选项4(Showinputdata)：

5、如果需要修改问题，则选择选项7(Modifyproblem)；

6、求解问题，选择选项5(Solveproblem),并根据提示选择逐步方式显示或其他；

7、显示、打印、或者保存最终结果，选择选项8(Showfinalsolution)；

8、保存数据备用，选择选项6(Saveproblemondisk)；

9、如果要求解另一个线性规划问题，则返回到第三步，否则，请选择选项9(Return

totheprogrammenu),返回主菜单(程序菜单)，选择其它程序；如果要退出，

请选择选项10(ExitfromQSB+)«

三、举例说明

问题：AMC公司用两种机器制造两种产品A和B,有关数据见表1—1所示，当前

市场对产品A和B的需求为供不应求，它们的市场价格分别为产品A每个50元，产品B

每个60元，请问如何安排生产可使其月收入最高？

表1-1问题数据表

耗用\产

机器机器每月可

工\品

AB用工时

机

12h3h180

23h2h150

操作步骤:

1、定义决策变量：

用A表示一个月生产A产品的数量，用B表示一个月生产B产品的数量。

2、建立数学模型如下：

8

MaxZ=50A^60B

‘24+35<180

用3A+284150

A,B>0

3、将问题输入系统

①在主菜单(程序菜单)选择选项1(Linearprogramming)；

②在功能菜单选择选项2(Enteranewproblem),按回车键会显示图2—1,在光

标处输入AMC,既给问题命名为AMCo

Pleasenameyourproblemuesingupto20characters?AMC

图1—5问题命名图

③按回车键出现如图1-6所示屏幕，请认真阅读英语说明，输入相关的数字,

可参考图1—4的中文说明；

LPModelEntryforAMC

Pleaseobservethefollowingconventionswhenenteringaproblem:

(1)Youmaychooseafreeorfixedformattoenteryourdata.Bound

constraintscanbeenteredseparately.

(2)Forthefixedformatentry,youmaycorrecterrorsbypressingthearrows

orBSkeytomovethecursortothecorrectpositionandfollowthe

instructiona*thebottomofscreentoproceedtotheprevious/nextpage.

Scientificnumericnotationisallowedfbrthefixedformatsuchthat

100,100.0,4-100,andLOE+2arethesame.>=,>,=>,and>arethesame;

and<=,<,=<,and<arethesamefarconstraintdirections.

(3)Forthefreeformatentry,refertothehelpinformationfordirection.

(4)Youcanmodifytheenteredproblemusingoption7ofthefunctionmenu.

Maximize(1)orminimize(2)theobjective?(Enter1or2)<1>

Numberofvariables(excludingslacks/artificials):<2>

Numberofconstraints(excludingbounds)：<2>

Approximatepercentageofnon-zeros(default5%):<>

Usethedefaultvariablenames(Xl,...,Xn)(l(Ycs),0(No)):<0>

Usethefreeformattoenterdata(l(Yes),0(No)):<0>

Usethefixedformattoenterbounds/integrality(l(Ycs),0(No)):<0>

图1—6AMC问题的参数选择

9

④参数输入后，按回车键出现如图1—7所示屏幕，输入变量名;

Enterthevariablenamesusingatmost8charactersPage1

(TousethedefaultnamesXI,X2,...,Xn,presstheENTERkey)

1:<A>2:<B>

图1-7输入决策变量名

⑤参数输入后，按回车键出现如图1—8所示屏幕，在该窗口中输入数学模型。

EntertheCoefficientsoftheLPModelPage:1

Max50卜60—B

Subjectto

(1)2一13一B<180.™

(2)3一一工2一一B<150

图1—8AMC问题的模型

4、选择功能菜单的选项4(Showinputdata),显示所输入的问题。图1一9所示为功

能菜单选项4(Showinputdata)的下级菜单；

OptionMenutoShowtheInputDataofAMC

Youhavethefollowingoptionsavailabletoshowtheinputdata.If

youwaMtoprinttheinputda⑶nukesurethattheprinterisready.

Option

1--Displaytheinputdata

2-——Printtheinputdata

3•…SavetheinputdatainanASCIIfile

4-——Displayinfreeformat

5-——Printinfreeformat

6--Saveinfreeformat

1・—Returntothefunctionmenu

图1—9显示数据菜单图

10

图1—10所示为选择图1—9中的选项1(Displaytheinputdata)时的显示结果，还可

以选择其他选项，自己操作认真阅读。

InputDataofTheProblemAMCPage:1

Max+50.0000A+60.0000B

Subjectto

(1)+2.00000A+3.00000B<+180,000

(2)+3.00000A+2.00000B<+150,000

图1—10AMC问题数据图

如果是以自由格式输入的数据，其显示结果如图1一11所示。

Fret?FormatModelforAMC

>>Max50A4-GOB

>>Subjectto

>>(1)2A+3B<=180

>>(2)3A+2B<=150

图1-11AMC问题数据的自由格式图

5、如果需要修改数据，可以选择功能菜单的选项7(Modifyproblem),所对应的

下级菜单如图1—12所示。

OptionRid]forModifyingAMC

Option

1Modifythemodelcoefficients

2----Modifyoneconstmint

3Addoneconstraint

4Deleteoneconstraint

5Addonevariable

6Deleteonevariable

7Modifyobjectivefunctioncriterion

8Modifyboundandintegrality

9Modifyvariablenames

0--Freeformatmodification

BShowinputdata

CReturntotliefunctionmenu

图1—12修改功能的下级菜单图

6、在功能菜单中选择选项5(Solveproblem)求解问题，其下级菜单如图1—13

11

所示，有各种求解问题方式供选择。

OptionMenuforSolvingAMC

Whensolvingaproblem,youhavetheoptiontodisplaystepsofthe

simplexmethod.Thisoptionispermissibleonlywhenyourproblemissmall,

；thatis,whenN+M+N2+N3*2<9,whoreNisthenumberofvariables,Nlis

tli«*niiiubtTofconstraints,N2istheniiinberof^'constraints,andN3is

ilunumberof^Constraints;otherwise,onlypivotinginformationwillbe

displayed.Youcanalsochoosetliegraphicmethodwhenyourproblemliasonly

2variablesandlessthan10constraints._________________________

Option

1----Solvewithoutdisplayinganytableau

2—--Solveanddisplaytheinitialtableau

3--Solveanddisplaythefinaltableau

I——-Solveanddisplaytheinitialandfinaltableaus

5Solveanddisplayeverytableau

6——Solvebyusingthegraphicm<?lhod

7----Sp<'cifynoscaling

X----K(4urntothefunctionmenu

L-—……....---‘—―_*'--•■——

图1—13问题求解菜单图

如果选择选项4（Solveanddisplaytheinitialandfinaltables）,就可以在屏幕上显示出每

次迭代的结果，参看图1—14至1—17所示。如果选择选项6（solvebyusingthegraphic

method）则可以显示出用图解法求解的结果（只有两个决策变量的情况）。

Initialtableau

ABSIS2B(i)

BasisC(j)50.0060.0000B(i)A(ij)

S102.0003.0001.0000180.00

S203.0002.00001.000150.00

c（j）-z（j）50.0060.00000

*BigM00000

图1—14初始表

12

Iteration1

ADSIS2B(i)

BasisC(j)50.0060.0000B(i)A(ij)

S102.0003.0001.0000180.0G0.00

S203.0002.00001.000150.075.00

C(j)-Z(j)50.0060.00000

*BigM00000

Currentobjectivefunctionvalue(Max.)=0

<Highlightedvariableistheenteringorleavingvariable>

Entering:BLeaving:SI

图1—15迭代表1

Iteration2

ABSIS2B(i)

BasisC(j)50.0060.000QB(i)A(ij)

B60.000.6671.0000.333060.0090.00

S201.6670-.6671.000-3.0018.00

CG)-z(j)10.000-20.003600

*BigM00000

Currentobjectivefunctionvalue(Max.)=3600

<Highlightedvariableistheenteringorleavingvariable>

Entering:ALeaving:S2

图1—16迭代表2

Finaltableau(Totaliteration=2)

ABSIS2B(i)

BasisCO)50.0060.0000B(i)A(ij)

B60.0001.0000.600-.40048.000

A50.001.0000-.4000.60018.000

c(j)-z(j)00-16.0-6.003780

♦BigM00000

(Max.)OptimalOBJvalue=3780

图1-17最终表

7、问题求解之后，可以选择功能菜单的选项8(Showfinalsolution),来显示最后的结

果，如图1—18所示。在此菜单中可以选择需要的内容进行显示，如果选择选项1(display

thesummarizedreport),那么，对应的显示结果如图1—19和图1—20所示。

13

OptionMenutoShowtheFinalSolutionofAMC

Youhavethefollowingoptionsavailabletoshowthefinalsolution.

Ifyouwanttoprintthesolution,makesurethattheprinterisready.

Option

1--Displaythesummarizedreport

2----Printthesummarizedreport

3Displaythesolution

4-Printthesolution

5Displaythesolutionandsensitivityanalysis

6-Printthesolutionandsensitivityanalysis

7-Printthefinaltableau

8-SavethefinalsolutioninanASCIIfile

9-Returntothefunctionmenu

图1—18显示最终解选择菜单图

SummarizedReportforAMCPage:1_____

Of)portunityObjectiveMinimumMaximum

NumberVariableSolutionCostCoefficientObj.Coeff.Obj.Coeff.

1A+18.0000000+50.000000+40.000000+90.000000

2B+48.0000000+60.000000+33.333336+75.000000

MaximizedOBJ=3780teration=2ElapsedCPUsecond=.109375

图1-19综合报表第一页

从此表可以看出：最优解为(+18,+48)\目标函数最优值(最大值)为3780；变

量A的系数在［+40,+90］内变化时，最优解不变，但最优值随之改变；变量B的系数在

［+33.33,+75］内变化时，最优解不变，但最优值随之改变。

SummarizedReportforAMCPage:2

ShadowSlackorMinimumMaximum

Constr.StatusRHSPriceSurplusRHSRHS

1Tight<+180,00000+16.0000000+100.00000+225.00000

2Tight<+150.00000+6.00000000+120.00000+270.00000

Maximized0BJ=3780Iteration=2lapsed3PUsecond=.109375

图1—20综合报表第二页

14

从此表可以看出：第一台机器的约束(+180)和第二台机器的约束(+150)都是紧约

束；第一台机器的生产能力在1+100,+225］内变化时，其影子价格为+16元，第二台机器

的生产能力在［+120,+270］内变化时，其影子价格为+6元。

8、在功能菜单中选择选项6(Saveproblemondisk),可以将所解问题的数据保存到

磁盘上，图1—21所示，即为保存文件时的屏幕显示。

SaveProblemonDisk(cttc)

Decideonafilenameforsavingyourproblem.

Thefilenamemaybethesameastheproblemname.

Typex：xxxxxxxx.xxxforyourfilename(e.g.,A:XYZ.DAT).

Whatisyourfilename(TypeA:,B:,orC:toseoallthefiles)?B:AMCFILE.DAT

DoyouwantB:AMCFILE.DATtobeanMPSfile(Y/N)?n

图1-20保存问题结果图

第二节运输/运转问题(TransportationandTransshipmentProblems)

一、概述

该程序能够求解运输/运转问题，源点(或供应点被定义为只有流出的点)，终点(或

销售点被定义为只有流入的点)，运输点(或中转点被定义为既进又出的点)。该程序能够

求解问题的规模取决于所用计算机的内存大小，供应量、需求量、运费或利润系数均为实

数。它能够提供问题的输入、保存、调用等功能，并且能够方便求解问题，显示问题，取

得相应的解，打印问题的结果。

问题输入程序后，会自动将问题转化为运输问题求解；能够提供确定初始方案的各种

方法；允许定义供应点、销售点和运输点的名称。对于规模较小的问题，可以显示解题步

骤，供应量、需求量、运费或利润等是需要给定的数据。

二、运输/运转问题的求解步骤

选择进入程序后，屏幕显示如图1—21所示，根据需要选择所需要的选项。

15

WelcometoyourTransshipmentProblem(TRP)System!

TheoptionsavailableforTRPareasfollows.

Ifyouareafirst-timeuser,youmightbenefitfromoption1.

OptionFunction

1OverviewofTRPDecisionSupportSystem

2--Enternewproblem

3--Readexistingproblemfromdisk(ette)

4Showinputdata

5--Solveproblem

6--Saveproblemondisk(ette)

7--Modifyproblem

8Showfinalsoluti