1 运筹学上机实验指导书重庆交通大学管理学院2 目录绪论运筹学上机实验软件简介第一章 运筹学上机实验指导 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) 与集的定义3 2.2 LINGO 中的函数与目标函数和约束条件的表示 2.3 LINGO 中的数据 2.4 LINDO 简介第三章 运筹学上机实验及要求实验一 .中小型线性规划模型的求解与 Lingo 软件的初步使用实验二 .中小型运输问题数学模型的 Lingo 软件求解。实验三 .大型线性规划模型的编程求解。实验四 .运输问题数学模型的 Lingo 编程求解。实验五 .分支定界法上机实验实验六 .整数规划、 0-1 规划和指派问题的计算机求解实验七：最短路问题的计算机求解实验八 :最大流问题的计算机求解4 绪论运筹学是研究资源最优规划和使用的数量化的管理科学， 它是广泛利用现有的科学技术和计算机技术，特别是应用数学方法和数学模型，研究和解决生产、经营和经济管理活动中的各种优化决策问题。运筹学通常是从实际问题出发， 根据决策问题的特征， 建立适当的数学模型，研究和分析模型的性质和特点， 设计解决模型的方法或算法来解决实际问题， 是一门应用性很强的科学技术。 运筹学的思想、 内容和研究方法广泛应用于工程管理、工商企业管理、物流和供应链管理、交通运输规划与管理等各行各业，也是现代管理科学和经济学等许多学科研究的重要基础。在解决生产、经营和管理活动中的实际决策问题时，一般都是建立变量多、约束多的大型复杂的运筹学模型，通常都只能通过计算机软件才能求解，因此，学习运筹学的计算机求解和进行上机实验，就是运筹学教学的重要组成部分。现在求解各类运筹学模型的软件多种，主要有 Microexcel， Matlab， LINDO ，LINGO ， WinQSB 和 英国运筹学软件 Dash-Xpress。 Microexcel 主要利用规划求解来解线性规划模型， WinQSB 功能比较齐全，但是主要适合解决规模较小的运筹学模型，英国运筹学软件 Dash-Xpress现在在中国的使用率不高， Matlab 是通过矩阵的方法解决线性规划， 对非线性规划和其它运筹学模型特别是大规模的模型的输入不太方便， 。而 LINGO 和 LINDO 是使用最广泛的运筹学专业软件，前者功能强大， 能解决几乎所有的运筹学优化模型， 后者主要功能是线性规划模型的求解。 在 LINGO 中模型的输入和编程都比较方便， 可解决大规模的运筹学模型。因此， 本课程的教学就是以 LINGO 为主， 适当补充 Excel 和 LINDO 作为运筹学上机软件，后者的优势主要在于能获得最优单纯形表以进行更全面地灵敏度分析。LINGO 是用来求解线性和非线性优化问题的简易工具。 LINGO 内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用 LINGO 高效的求解器可快速求解并分析结果。LINGO 全称是 Linear INteractive and General Optimizer的缩写 -交互式的线性和通用优化求解器。它是一套设计用来帮助您快速 ,方便和有效的构建和求解线性 ,非线性 ,和整数最优化模型的功能全面的工具 .包括功能强大的建模语言 ,建立和编辑问题的 全功能环境 ,读取和写入 Excel 和数据库的功能 ,和一系列完全内置的求解程序 . 运行环境： Win9x/NT/2000/XP/2003/Vista/Win7 软件类别： 国外软件 /工具软件 /计算工具软件语言： 英文LINGO 是使建立和求解线性、非线性和整数最佳化模型更快更简单更有效率的综合工具。 LINGO 提供强大的语言和快速的求解引擎来阐述和求解最佳化模型。 LINGO 具有如下的优势：1 简 单的模型表示LINGO 可以将线性、非线性和整数问题迅速得予以公式表示，并且容易阅读、了解和修改。 LINGO 的建模语言允许您使用汇总和下标变量以一种易懂的直观的方式来表达模型， 非常类似您在使用纸和笔。 模型更加容易构建， 更容易5 理解，因此也更容易维护。2方便的数据输入和输出选择LINGO 建立的模型可以直接从数据库或工作表获取资料。同样地， LINGO 可以将求解结果直接输出到数据库或工作表。 使得您能够在您选择的应用程序中生成报告 . 3强大的求解器LINGO 拥有一整套快速的 ,内建的求解器用来求解线性的 ,非线性的 (球面 & 非球面的 ),二次的 ,二次约束的 ,和整数优化问题 .您甚至不需要指定或启动特定的求解器 ,因为 LINGO 会读取您的方程式并自动选择合适的求解器 . 4. 交互式模型或创建 Turn-key 应用程序您能够在 LINGO 内创建和求解模型 ,或您能够从您自己编写的应用程序中直接调用 LINGO. 对于开发交互式模型 ,LINGO 提供了一整套建模环境来构建 ,求解和分析您的模型 .对于构建 turn-key 解决方案 ,LINGO 提供的可调用的 DLL 和OLE 界面能够从用户自己写的程序中被调用 .LINGO 也能够从 Excel 宏或数据库应用程序中被直接调用 . 5. 广泛的文件和 HELP 功能安装好了的 LINGO ， 启动后的界面如下图 1 所示， 即可输入求解运筹学模型的程序。图 1 6 第一章 运筹学上机实验指导 1.1 中小型线性规划模型的计算机求解对于小型线性规划模型的求解， LINGO 中可以用一种与线性规划的数学模型及其类似的方式直接输入模型来求解，简单方便。例 1.1 求解下面的线性规划max z=2x1+3x2 x1+2x2 8 4x1 16 4x2 16 x1， x2 0 LINGO 中的输入的代码如图 2 所示， 这种输入方式的优势在于适合 LINDO 系统。图 2 注 1： LINGO 中输入的代码和线性规划模型的差异如下：(1) max z max,min z min；(2) 每一行 (包括目标函数 )用英文的分号结束；(3) 数与变量的乘积用 *表示；(4) 不等号和用 =或 表示；(5) LINGO 系统默认所有的变量非负， 因此非负变量的约束可省略， 而非正变量和自由变量要用 x1=2; free (x4); 11 求解可得解报告：Global 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.000000 1.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(I): sum(js(J):a(I,J)*x(J)= b(3); ! 自由变量 ;free (x(4); ! 指定常量的值 ;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 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.000000 14 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