运筹学上机试验指导书.doc

《运筹学上机试验指导书.doc》由会员分享，可在线阅读，更多相关《运筹学上机试验指导书.doc（60页珍藏版）》请在三一办公上搜索。

1、运筹学上机实验指导书重庆交通大学管理学院目录绪论运筹学上机实验软件简介第一章 运筹学上机实验指导1.1 中小型线性规划模型的计算机求解1.2 大型线性规划模型的编程计算机求解1.3线性规划的灵敏度分析1.4运输问题数学模型的计算机求解1.5目标规划数学模型的计算机求解1.6整数规划数学模型的计算机求解1.7 指派问题的计算机求解1.8最短路问题的计算机求解1.9最大流问题的计算机求解第二章LINGO软件基础及应用2.1 原始集(primitive set)和派生集(derived set)与集的定义2.2 LINGO中的函数与目标函数和约束条件的表示2.3 LINGO中的数据2.4 LINDO

2、简介第三章 运筹学上机实验及要求实验一.中小型线性规划模型的求解与Lingo软件的初步使用实验二.中小型运输问题数学模型的Lingo软件求解。实验三.大型线性规划模型的编程求解。 实验四.运输问题数学模型的Lingo编程求解。实验五.分支定界法上机实验实验六.整数规划、0-1规划和指派问题的计算机求解实验七：最短路问题的计算机求解实验八:最大流问题的计算机求解绪论运筹学是研究资源最优规划和使用的数量化的管理科学，它是广泛利用现有的科学技术和计算机技术，特别是应用数学方法和数学模型，研究和解决生产、经营和经济管理活动中的各种优化决策问题。运筹学通常是从实际问题出发，根据决策问题的特征，建立适当的

3、数学模型，研究和分析模型的性质和特点，设计解决模型的方法或算法来解决实际问题，是一门应用性很强的科学技术。运筹学的思想、内容和研究方法广泛应用于工程管理、工商企业管理、物流和供应链管理、交通运输规划与管理等各行各业，也是现代管理科学和经济学等许多学科研究的重要基础。在解决生产、经营和管理活动中的实际决策问题时，一般都是建立变量多、约束多的大型复杂的运筹学模型，通常都只能通过计算机软件才能求解，因此，学习运筹学的计算机求解和进行上机实验，就是运筹学教学的重要组成部分。现在求解各类运筹学模型的软件多种，主要有Microexcel，Matlab，LINDO，LINGO，WinQSB和英国运筹学软件D

4、ash-Xpress。Microexcel主要利用规划求解来解线性规划模型，WinQSB 功能比较齐全，但是主要适合解决规模较小的运筹学模型，英国运筹学软件Dash-Xpress现在在中国的使用率不高，Matlab是通过矩阵的方法解决线性规划，对非线性规划和其它运筹学模型特别是大规模的模型的输入不太方便，。而LINGO和LINDO是使用最广泛的运筹学专业软件，前者功能强大，能解决几乎所有的运筹学优化模型，后者主要功能是线性规划模型的求解。在LINGO中模型的输入和编程都比较方便，可解决大规模的运筹学模型。因此，本课程的教学就是以LINGO为主，适当补充Excel和LINDO作为运筹学上机软件，

5、后者的优势主要在于能获得最优单纯形表以进行更全面地灵敏度分析。LINGO是用来求解线性和非线性优化问题的简易工具。LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。LINGO全称是Linear INteractive and General Optimizer的缩写-交互式的线性和通用优化求解器。它是一套设计用来帮助您快速,方便和有效的构建和求解线性,非线性,和整数最优化模型的功能全面的工具.包括功能强大的建模语言,建立和编辑问题的 全功能环境,读取和写入Excel和数据库的功能,和一系列完全内置的求解程序. 运行环境： Win

6、9x/NT/2000/XP/2003/Vista/Win7 软件类别： 国外软件/工具软件/计算工具 软件语言： 英文 LINGO 是使建立和求解线性、非线性和整数最佳化模型更快更简单更有效率的综合工具。LINGO 提供强大的语言和快速的求解引擎来阐述和求解最佳化模型。 LINGO具有如下的优势：1 简单的模型表示 LINGO 可以将线性、非线性和整数问题迅速得予以公式表示，并且容易阅读、了解和修改。LINGO的建模语言允许您使用汇总和下标变量以一种易懂的直观的方式来表达模型，非常类似您在使用纸和笔。模型更加容易构建，更容易理解，因此也更容易维护。 2方便的数据输入和输出选择 LINGO 建立

7、的模型可以直接从数据库或工作表获取资料。同样地，LINGO 可以将求解结果直接输出到数据库或工作表。使得您能够在您选择的应用程序中生成报告. 3强大的求解器 LINGO拥有一整套快速的,内建的求解器用来求解线性的,非线性的(球面&非球面的),二次的,二次约束的,和整数优化问题.您甚至不需要指定或启动特定的求解器,因为LINGO会读取您的方程式并自动选择合适的求解器. 4. 交互式模型或创建Turn-key应用程序 您能够在LINGO内创建和求解模型,或您能够从您自己编写的应用程序中直接调用LINGO.对于开发交互式模型,LINGO提供了一整套建模环境来构建,求解和分析您的模型.对于构建turn

8、-key解决方案,LINGO提供的可调用的DLL和OLE界面能够从用户自己写的程序中被调用.LINGO也能够从Excel宏或数据库应用程序中被直接调用. 5. 广泛的文件和 HELP 功能安装好了的LINGO，启动后的界面如下图1所示，即可输入求解运筹学模型的程序。图1第一章 运筹学上机实验指导1.1 中小型线性规划模型的计算机求解对于小型线性规划模型的求解，LINGO中可以用一种与线性规划的数学模型及其类似的方式直接输入模型来求解，简单方便。例1.1 求解下面的线性规划max z=2x1+3x2 x1+2x28 4x1 16 4x216 x1，x20LINGO中的输入的代码如图2所示，这种输

9、入方式的优势在于适合LINDO系统。图2注1：LINGO中输入的代码和线性规划模型的差异如下：(1) max zmax,min zmin；(2) 每一行(包括目标函数)用英文的分号结束；(3) 数与变量的乘积用*表示；(4) 不等号和用=或表示；(5) LINGO系统默认所有的变量非负，因此非负变量的约束可省略，而非正变量和自由变量要用x1=0和free(x2)表示；(6) LINGO中不能输入下标，x1x1。图3注2：例1.1的模型求解还可以按图4的方式输入代码求解。此时LINGO中输入的代码和线性规划模型的除注1的相关差异外，还有如下不同：(1) 数与变量的乘积，乘号用空格表示；(2) 约

10、束条件之前用s.t.或subject to表示后面是约束；(3) 每行后面不用分号结束；(4) 这种输入法的好处是和LINDO的输入一致，可以直接在LINDO中求解，做灵敏度分析较方便，也能得到最优单纯形表。图4点菜单栏的LINGOSolver，或直接点工具栏上的 ，可得求解结果即解的状况(Solver Status)和解报告(Solution Report)：图5关于图5的Solver Status的注释如下：(1) Model(模型) LP(线性规划Linear programming，其它模型还有非线性规划NLP(Nonlinear programming )，整数线性规划ILP(Int

11、eger)，整数非线性规划 INLP)(2) State(状态) Global Opt(整体最优解Global optimal solution，线性规划的最优解都是整体最优解，非线性规划有局部最优解(Local Opt)和整体最优解之分，其它状态还有无可行解(Infeasible)图7和无界解(Unbounded) 图8)(3) Objective，目标函数值为14，由于处于最优解状态，所以这里表示最优值为14。(4) Infeasibility 0，不可行性0，表示此时有可行解，否则没有可行解。(5) Iteration 1，表示迭代了1步求得最优解。(6) Extended Solver

12、 Status，表示扩展的解的状况，主要用于整数规划和非线性规划。(7) Variables，表示变量，Total 2，表示总决策变量2个，非线性(Nonlinear)变量和整数(Integer)变量都是0个。(8) Constraints，表示约束，Total 4，表示包括目标函数一共4个约束，非线性(Nonlinear)约束0个。(9) Nonzeros，表示非零系数，Total 6，表示包括目标函数和约束条件中变量的非零系数6个，右端常数项不算。图6图7图8关于图6的Solution Report的注释如下：(1) Global optimal solution found.整体最优解被

13、找到。(2) Objective value: 14.00000.最优值为14。(3) Total solver iterations: 1.求解的总迭代步数为1步。(4) Variable Value Reduced Cost X1 4.000000 0.000000 X1 2.000000 0.000000最优解的变量X1=4.000000，X2 =2.000000。(5) Reduced Cost：表示减少的成本，即最小化问题的最优目标函数中各变量的检验数，即在其它变量不变时，该变量减少一个单位，目标费用减少的数量如图8。对于最大化问题，是最优目标函数中各变量的检验数的相反数，表示当该变

14、量增加一个单位时目标函数减少的数量如图9。这里由于上面X1和X2为取值非零的基变量，所以检验数为零。Reduced Cost为在最优解时，最小化问题中变量的检验数，最大化问题中变量检验数的相反数。(6) Row Slack or Surplus Dual Price 1 14.00000 1.000000 2 0.000000 1.500000 3 0.000000 0.1250000 4 4.000000 0.000000Slack or Surplus表示松弛或剩余变量，即将最优解带入各个约束条件后，左边比右边小的或大的数量，表示在最优方案中，剩余或超过的资源数量。注意，这里第一行表示目标

15、函数，其松弛或剩余变量和对偶价格都没有意义。(7) Dual Price，对偶价格，即最大化问题中对偶变量的最优解的值如图9所示，对于最小化问题，对偶价格为对偶变量的最优解的值的相反数。图9图10例1.2 求解下面线性规划的数学模型min z=-3x1+4x2-2x3+5x4;4x1-x2+2x3-x4=-2;x1+x2+3x3-x414;-2x1+3x2-x3+2x42;x1,x2,x30,x4无约束;LINGO中输入如下的代码：min =-3*x1+4*x2-2*x3+5*x4;4*x1-x2+2*x3-x4=-2;x1+x2+3*x3-x4=2;free(x4);求解可得解报告：Glob

16、al optimal solution found. Objective value: 2.000000 Total solver iterations: 0 Variable Value Reduced Cost X1 0.000000 15.50000 X2 8.000000 0.000000 X3 0.000000 8.500000 X4 -6.000000 0.000000 Row Slack or Surplus Dual Price 1 2.000000 -1.000000 2 0.000000 4.500000 3 0.000000 0.5000000 4 10.00000 0.

17、0000001.2 大型线性规划模型的编程计算机求解教学过程中所见到的运筹学模型大多是小型的，但是，在解决生产和经营管理活动中的实际时，建立的通常是含有很多和变量和约束条件的模型，用前面的方法，经常要花费大量的时间来输入代码或模型，下面介绍编程的方法，对于解决大型复杂的模型，效果显著。下面是求解例1的线性规划的LINGO程序。例2.1 用LINGO编程求解例1.1的线性规划模型!定义变量与常量，给出了值的为常量;sets:is/1.3/:b;js/1.2/:c,x;links(is,js):a;endsets!目标函数;max=sum(js(J):c(J)*x(J);!约束条件;for(is(

18、I): sum(js(J):a(I,J)*x(J)=b(I);!指定常量的值;data:!直接输入数据;c=2 3;b=8 16 12;a=1 2 4 0 0 4;end dataend求解可得Solution ReportGlobal optimal solution found. Objective value: 14.00000 Total solver iterations: 1 Variable Value Reduced Cost B( 1) 8.000000 0.000000 B( 2) 16.00000 0.000000 B( 3) 12.00000 0.000000 C( 1

19、) 2.000000 0.000000 C( 2) 3.000000 0.000000 X( 1) 4.000000 0.000000 X( 2) 2.000000 0.000000 A( 1, 1) 1.000000 0.000000 A( 1, 2) 2.000000 0.000000 A( 2, 1) 4.000000 0.000000 A( 2, 2) 0.000000 0.000000 A( 3, 1) 0.000000 0.000000 A( 3, 2) 4.000000 0.000000 Row Slack or Surplus Dual Price 1 14.00000 1.0

20、00000 2 0.000000 1.500000 3 0.000000 0.1250000 4 4.000000 0.000000这里以!开始和分号结束的语句为注释语句，该程序的求解方法和解报告与小型模型类似，只是编程的解报告会把所有的系数也表述出来而已。从例3可以看出，一个LINGO的程序由四个部分组成。1. 以“sets:”开始，以“endsets”结束的语句定义模型中出现的变量集。2. 以sets中定义的变量和常量来表达目标函数。3. 以sets中定义的变量和常量来表达全部的约束条件。4. 以“data:”开始，以“end data”结束的语句给常量指定数值。第二章详细解释每一部分的含

21、义及如何表达对应的数学模型。例2.2 求解下面线性规划的数学模型;min z=-3x1+4x2-2x3+5x4;4x1-x2+2x3-x4=-2;x1+x2+3x3-x414;-2x1+3x2-x3+2x42;x1,x2,x30,x4无约束;编程如下：!定义变量与常量，给出了值的为常量;sets:is/1.3/:b;js/1.4/:c,x;links(is,js):a;endsets!目标函数;min=sum(js(J):c(J)*x(J);!约束条件;sum(js(J):a(1,J)*x(J)=b(1);sum(js(J):a(2,J )*x(J)= b(3);!自由变量;free(x(4)

22、;!指定常量的值;data:c=-3 4 -2 5;b=-2 14 2;a=4 -1 2 -1 1 1 3 -1 -2 3 -1 2;end data!结束;end求解可得解报告：Global optimal solution found. Objective value: 2.000000 Total solver iterations: 2 Variable Value Reduced Cost B( 1) -2.000000 0.000000 B( 2) 14.00000 0.000000 B( 3) 2.000000 0.000000 C( 1) -3.000000 0.000000

23、C( 2) 4.000000 0.000000 C( 3) -2.000000 0.000000 C( 4) 5.000000 0.000000 X( 1) 0.000000 15.50000 X( 2) 8.000000 0.000000 X( 3) 0.000000 8.500000 X( 4) -6.000000 0.000000 A( 1, 1) 4.000000 0.000000 A( 1, 2) -1.000000 0.000000 A( 1, 3) 2.000000 0.000000 A( 1, 4) -1.000000 0.000000 A( 2, 1) 1.000000 0.

24、000000 A( 2, 2) 1.000000 0.000000 A( 2, 3) 3.000000 0.000000 A( 2, 4) -1.000000 0.000000 A( 3, 1) -2.000000 0.000000 A( 3, 2) 3.000000 0.000000 A( 3, 3) -1.000000 0.000000 A( 3, 4) 2.000000 0.000000 Row Slack or Surplus Dual Price 1 2.000000 -1.000000 2 0.000000 4.500000 3 0.000000 0.5000000 4 10.00

25、000 0.0000001.3线性规划的灵敏度分析在求解了一个线性规划的模型的时候，如果是编程输入的模型，还可以通过LINGO中的命令显示线性规划的数学模型。例3.1 通过图和图的操作，可显示例2.1LINGO程序的数学模型。图11图12图13MODEL: _1 MAX= 2 * X_1 + 3 * X_2 ; _2 X_1 + 2 * X_2 = 8 ; _3 4 * X_1 = 16 ; _4 4 * X_2 = 12 ; END只是系统默认的非负约束没有显示，下图表明自由变量和非正变量都会显示出来。图14下面的图演示了对线性规划的灵敏度分析首先求解一个线性规划模型，然后选中“prices

26、 & Ranges”图15然后在菜单LINGORanges图16点击Ranges，得到在最优基或最优解不变时，单个价值系数和右端系数变化范围的灵敏度分析结果。图17Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X( 1) 2.000000 INFINITY 0.5000000 X( 2) 3.000000 1.000000 3.000000 Righthand Side

27、Ranges Row Current Allowable Allowable RHS Increase Decrease 2 8.000000 2.000000 4.000000 3 16.00000 16.00000 8.000000 4 12.00000 INFINITY 4.000000LINDO中也可以作灵敏度分析，一般在求解了线性规划模型后，自动出现是否进行灵敏度分析的对话框，如图图18点击“是”，就可得解和灵敏度分析报告：LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 14.00000 VARIABLE VALUE RE

28、DUCED COST X1 4.000000 0.000000 X2 2.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.500000 3) 0.000000 0.125000 4) 4.000000 0.000000 NO. ITERATIONS= 2 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 2.00000

29、0 INFINITY 0.500000 X2 3.000000 1.000000 3.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 8.000000 2.000000 4.000000 3 16.000000 16.000000 8.000000 4 12.000000 INFINITY 4.0000001.4运输问题数学模型的计算机求解1. 中小型运输问题的求解中小型运输问题可以和小型线性规划一样，直接输入运输问题的数学模型代码求解。例4.1 求解下面运输问题的数学模型

30、单位 销地运价产地B1B2B3B4产量A13113107A219284A3741059销量3656LINGO中的输入代码为：min=3*x11+11*x12+3*x13+10*x14+x21+9*x22+2*x23+8*x24+7*x31+4*x32+10*x33+5*x34;x11+ x12+ x13+ x14 = 7;x21+ x22+ x23+ x24 = 4;x31+ x32+ x33+ x34 = 9;x11+ x21+ x31= 3;x12+ x22+ x32 = 6;x13+ x23+ x33 = 5;x14+ x24+ x34 = 6;求解可得:Global optimal s

31、olution found. Objective value: 83.00000 Total solver iterations: 0 V Variable Value Reduced Cost X11 0.000000 0.000000 X12 0.000000 2.000000 X13 5.000000 0.000000 X14 2.000000 0.000000 X21 3.000000 0.000000 X22 0.000000 2.000000 X23 0.000000 1.000000 X24 1.000000 0.000000 X31 0.000000 9.000000 X32 6.000000 0.000000 X33 0.000000 12.00000 X34 3.000000 0.000000 Row Slack or Surplus Dual Price 1 85.00000 -1.000000 2 0.000