运筹学教案-实验

重庆三峡学院财经学院LINGO程序设计简明教程与应用举例运筹学综合实验教程主要内容：

LINGO简介（包括常用菜单项、基本组成、运算符与函数）

运筹学主要内容程序段（部分内容可扩展应用）

目录TOC\o"1-3"\h\u1. LINGO简介 11.1LINGO常用菜单项 11.1.1文件菜单 21.1.2编辑菜单： 31.1.3LINGO菜单 41.2LINGO的基本组成 111.3集合定义的语法规则： 111.4运算符： 121.5函数 122. LINGO编程应用举例 132.1线性与整数规划 13例2.1.1（资源分配问题） 13例2.1.2（混合问题） 13例2.1.3（条材下料问题） 14例2.1.4（投资分配问题） 15例2.1.5（生产安排问题） 16例2.1.6（排班问题） 17例2.1.7计划排序程序（稀疏集合：直接列表法） 18例2.1.8配对模型（稀疏集合：元素过滤法） 192.2指派问题 19例2.2.1 19例2.2.2 202.3运输问题 22例2.3.1 22例2.3.2（P103-7） 23例2.3.3（P104） 232.4目标规划 25例2.4.1（P116例6.5） 262.5图与网络模型 272.5.1最短路问题 272.5.2最大流问题 282.6动态规划 282.6.1最短路问题 282.6.2资源分配问题 292.7存储论 302.7.1不允许缺货，即时补充模型（基本EOQ模型） 302.7.2不允许缺货，生产需要一定时间模型 302.7.3允许缺货，即时补充模型 312.7.4允许缺货，生产需要一定时间模型 312.8决策分析 322.8.1不确定型决策 322.8.2风险型决策 332.8.3贝叶斯公式 332.9对策论 342.9.1二人零和对策 34LINGO简介LINGO是LinearInteractiveandGeneralOptimizer的缩写，即“交互式的线性和通用优化求解器”，由美国LINDO系统公司（LindoSystemInc.）推出的，可以用于求解非线性规划，也可以用于一些线性和非线性方程组的求解等，功能十分强大，是求解大规模优化模型的最佳选择。其特色在于内置建模语言，提供十几个内部函数，可以允许决策变量是整数(即整数规划，包括0-1整数规划)，方便灵活，而且执行速度非常快。能方便与EXCEL，数据库等其他软件交换数据。1.1LINGO常用菜单项标题栏：显示所建立文件的标题，默认的为Lingo1、Lingo2…菜单栏：包括文件（File）、编辑（Edit）、Lingo、窗口（Window）、帮助（Help）.工具栏：将常用的命令列于此栏，以便快捷操作：1.1.1文件菜单（1）新建（New）（2）打开（Open）（3）保存(Save)（4）另存为．．．(SaveAs．．．)（5）关闭（Close）（6）打印(Print)（7）打印设置(PrintSetup．．．)（8）打印预览(PrintPreview)

（9）输出到日志文件(LogOutput．．．)（10）提交LINGO命令脚本文件(TakeCommands．．．)（11）引入LINGO文件(ImportLingoFile．．．)（12）退出（Exit）1.1.2编辑菜单：（1）恢复(Undo)（2）剪切(Cut)（3）复制(Copy)（4）粘贴(Paste)（5）粘贴特定..（PasteSpecial。。）（6）全选(SelectAll)（7）选择所有(SelectAll)（8）查找（9）查找下一个（10）复位（11）光标移到某一行(GoToLine)（12）匹配括号(MatchParenthesis)（13）粘贴函数(PasteFunction)（14）选择字体(SelectFont...)（15）插入新对象(InsertNewObject...)（16）连接(links)（17）对象性质(ObjectProperties)1.1.3LINGO菜单（1）求解模型（Slove）（2）求解结果（Solution）可以文本或图形（柱状图bar，折线图Line,饼图Pie)显示结果。（3）查看（Look）（4）灵敏性分析（Range，Ctrl+R）（5）选项（Options):有7个选项卡，其中最常用的是通用求解器(GenerlSolver)中的对偶计算(DualComputations).若要进行灵敏度分析，则在对偶计算中选择PricesandRanges;（6）生成模型的展开形式(Generate)：用代数表达式显示完整形式。（7）生成图形(Picture):以矩阵形式显示模型系数（8）调试(Debug)（9）显示模型统计资料(ModelStatistics)（10）查看(Look):以文本形式显示模型内容，前面加行号。第（5）项选项（Option）参数设置列表：Interface（界面）选项卡选项组选项含义General(一般选项)ErrorsinDialogs(错误信息对话框)如果选择该选项，则求解程序遇到错误时将打开了个对话框显示错误，关闭该对话框后程序才会继续执行；否则，错误信息将在报告窗口显示，程序仍会继续执行。SplashSreen(弹出屏幕)如果选择该选项，则LINGO每次启动时会在屏幕上弹出一个对话框，显示LINGO的版本和版权信息；否则不弹出。StatusBar(状态栏)如果选择该选项，则LINGO系统在主窗口最下面一行显示状态栏（其中显示时间、光标位置、菜单提示和程序的当前状态）；否则不显示。StatusWindow(状态窗口)如果选择该选项，则LINGO系统每次运行LINGOSoler（求解命令时会在屏幕上弹出求解状态窗口；否则不弹出。TerseOutput(简洁输出)如果选择该选项，则LINGO系统对求解结果报告等将以简洁形式输出（仅显示目标函数值）；否则以详细形式输出。Toolbar(工具栏)如果选择该选项，则显示工具栏；否则不显示。SolutionCutoff(解的截断)如果中小于等于这个值的解将报告为“0”，以免分散注意力，SolutionCutoff默认值是10-9.FileFormat(文件格式)Lg4(extended)(扩展格式)模型文件的默认保存格式是lg4格式（这是一种二进制文件，只有LINGO能读出）Lng(testonly)(纯文本格式)模型文件的默认保存格式是lng格式（纯文本）SyntaxColoring(语法配色)Linelimit(行数限制)语法配色的行数限制（默认是1000），LINGO模型窗口中将LINGO关键词显示为蓝色，注释为绿色，其他为黑色，超过该行数限制后不再区分颜色。特别是，设置行数限制为0时，整个文件不再区分颜色。Delay(延迟)设置语法配色的延迟时间（秒，默认为0，从最后一次击键算起）ParenMatch(括号匹配)如果选择该选项，则模型中当前光标所在处的括号及其相匹配的括号将以红色显示；否则不使用该功能。CommandWindow(命令窗口)SendReportstoCommandWindow(报告发送到命令窗口)如果选择该选项，则输出信息将会发送到命令窗口，而不是单独的报告窗口；否则不使用该功能。EchoInput(输入信息反馈)如果选择该选项，则用File|TakeCommand命令执行脚本文件时，处理信息会发送到命令窗口，这对调试命令脚本有用；否则不使用该功能。LineCountLimits(行数限制)命令窗口能显示的行数的最大值为Maxmum（默认为800）；如果要显示的内容超过这个值，每次从命令窗口滚动删除的最小行数为Minmum(默认值为400)PageSizeLimit(页面大小限制)命令窗口每次显示的行数的最大值为Length(默认为没有限制)，显示这么多行后会暂停，等待用户响应；每行最大字符数为Width(默认为74，可以设定为64-200之间)，多余的字符将被截断。GeneralSolver(通用求解器)选项卡选项组选项含义GeneratorMemoryLimit(MB)模型生成器的内存限制（兆）为模型生成器预留内在，默认值为32M,如果模型生成器使用的内在超过该限制，LINGO将报告“Themodelgeneratorranoutofmemory”.该值设置大则对大型模型有利，但不宜过高，过高了会造成求解程序可使用的内存减少，导致LINGO运行不畅。RuntimeLimits运行限制Iterations迭代次数上限求解一个模型时，允许的最大迭代次数（默认值为无限）Time(sec)运行时间（秒）求解一个模型时，允许的最大迭代时间（默认值为无限）DualComputations对偶计算求解时控制对偶计算的级别，有以下四种可能的设置：None:不计算任何对偶信息，有利于加快运行；Prices:计算对偶值（默认设置），但不计算灵敏度；PricesandRanges:计算对偶值和灵敏度；Prices,OptOnly:只计算最优行的对偶信息。ModelRegeneration模型的重新生成控制重新生成模型的方式，有三种可能的设置：Onlywhentextchanges:只有当模型的文本修改后才再生成模型；Whentextchangesorwhthexternalreferences:当模型的文本修改或模型含有外部引用时且外部数据源被改变时重新生成模型（默认设置）；Always:每当有需要时。Linearization控制线性化选项Degeer线性化程度决定求解模型时线性化的程度，有四种可能的设置：SolverDecodes:若变量数小于等于12个，则尽可能全部线性化；否则不做任何线性化（默认设置）Nome:不做任何线性化。Low:对函数@ABS,@MAX,@MIN,@SMAX,@SMIN,以及二进制变量与连续变量的乘积项做线性化。High:同上，此外对逻辑运算符#LE#,#EQ#,#NE#做线性化ABigM(线性化的大M系数）设置线性化的大M系数（默认值为10-6）该数如果太小，则模型可能最终无可靠解，该值太大，则可能导致产生算法的稳定性问题。Delta(线性化的误差限)设置线性化的误差限（默认值为10-6），大多数模型无需改变此默认值）AllowUnrestrictedUseofPrimitive/setMemberNames允许无限制地使用基本集合的成员名选择该选项可以保持与LINGO4.0以前的版本兼容，即允许使用基本命令的成员名称直接作为该成员在该命令的索引值(Lingo4.0以后的版本要求使用@INDEX函数）。默认不选择该选项。CheckforDuplicateNamesinDataandModel(检查数据和模型中的名称是否重复使用)选择该选项，LINGO将检查数据和模型中的名称是否重复使用，如基本命令的成员名是否与决策变量名重复。UseR/CformatnamesforMPSI/O(在MPS文件格式的输入输出中使用R/C格式的名称)在MPS文件格式的输入输出中，将变量和行名转换为R/C格式LinearSolver(线性求解器)选项卡选项组选项含义Method求解方法求解时的算法，有四种可能的设置：SolverDecides:LINGO自动选择算法（默认设置）PrimalSimplex:原始单纯形法DualSimplex:对偶单纯形法Barrier:障碍法（内点法）大体上，求解行数少于列数的稀疏模型时用原始单纯形法较好，求解列数少于行数的稀疏模型时用对偶单纯形法较好，而求解密集型或大型规划时用障碍法较好。InitialLinearFeasibilityTol:初始线性可靠性误差限控制线性模型中约束被满足时的初始允许误差限，即在该限度内时就认为约束得到满足（默认值为3*10-6）FinalLinearFeasibilityTol:最后线性可靠性误差限控制线性模型中约束被满足时的最后允许误差限（默认值为10-7）ModelReduction模型降维控制是否检查模型中的无关变量，从而降低模型的规模：Off:不检查On:检查，LINGO在求解之前尝试从表达式中识别并移除无关的变量和约束SolverDecides:LINGO自动决定（默认设置）PricingStrategies价格策略（决定出基变量的策略）PrimalSolver原始单纯形法有三种可能的设置：SolverDecides:LINGO自动决定（默认设置）Partial:LINGO对一部分可能的出基变量进行尝试Devex:用Steepest-Edge（最陡边）近似算法对所有可能的变量进行尝试，找到使目标值下降最多的出基变量。DualSolver对偶单纯形法有三种可能的设置：SolverDecides:LINGO自动决定（默认设置）Dantzig:按最大下降比例法确定出基变量Steepest-Edge:最陡边策略，对所有可能的变量进行尝试，找到使目标值下降最多的出基变量。MatrixDecomposition矩阵分解选择该选项，LINGO将尝试把一个大模型分解为几个小模型求解；否则不尝试。ScaleModel模型尺度的改变选择该选项，LINGO检查模型中的数据是否平衡（数量级是否相差太大）并尝试改变尺度使模型平衡；否则不尝试。NonlinearSolver(非线性求解器)选项卡选项组选项含义InitialNonlinearFeasibilityTol初始非线性可行性误差限控制模型中的约束满足的初始误差限，参阅线性求解器的相关说明，默认值为10-3FinalNonlinearFeasibilityTol最后非线性可行性误差限控制模型中约束满足的最后误差限（默认值为10-6）NonlinearOptimalityTol非线性规划的最优性误差限如果目标函数的梯度的改变量小于等于这个值，则停止迭代（默认值为2*10-7）SlowProgressIterationLimit缓慢改进的迭代次数的上限当目标函数在连续这么多次迭代没有显著改进以后，停止迭代（默认值5）Derivatives导数计算方式Numerical数值法用有限差分法计算数值导数，默认用该方法Analytical解析法用解析法计算导数（仅对只含有自述运算符的函数使用）Strategies策略CrashInitialSolution生成初始解选择该选项，LINGO将用启发式方法生成一个“好”的出发点（初始解）；否则不生成（默认值）。QuadraticRecognition识别二次规划选择该选项，LINGO将判别模型是否为二次规划，若是则采用二次规划算法（包含在线性规划的内点法中）；否则不判别（默认值）SelectiveConstraintEval有选择地检查约束选择该选项，LINGO在每次迭代时只检查必须检查的约束（如果有些约束函数在某些区栏目没有定义，这样做会出现错误）；否则，检查所有约束（默认值）SLPDirectionsSLP方向选择该选项，LINGO在每次迭代时用SLP（SuccessiveLP,逐次线性规划）方法寻找搜索方向，运用线性逼近的方法加快迭代时间（默认值）SteepestEdge最陡边策略选择该选项，LINGO在每次迭代时将对所有可能的变量进行尝试，找到使目标值下降最多的变量进行迭代，此时选择变量所花费的时间较多，但每次迭代时目标函数值的改变量较大；默认值为不使用最陡边策略。IntegerPre-Solver(整数预处理求解器)选项卡选项组选项含义Heuristics启发式方法Level水平控制采用启发式搜索的次数（默认值为3，可能的值为0-100）。启发式方法的目的是从分枝节点的连续解出发尝试找到一个好的整数解。MinSeconds最小时间每个分枝节点使用启发式搜索的最小时间（秒，默认值是0）ProbingLevel探测水平（级别）控制采用探测（probing)技术的级别（探测能够用于混合整数线性规划模型，收紧变量的上下界和约束的右端项的值）。多数时候探测可以充分紧缩模型并缩短求解时间，但有时并非如此，可能的取值为：SolverDecides:LINGO自动决定（默认设置）1-7：探测级别逐步升高同。ConstraintCuts约束的割（平面）Application应用节点控制在分枝定界树中，哪些节点需要增加割（平面），可能的取值为：RootOnly:仅根节点增加割（平面）AllNodes:所有节点均增加割（平面）SolverDecides:LINGO自动决定（默认设置）RelativeLimit相对上限控制生成的割（平面）的个数相对于原问题的个数的上限（比值），默认值为0.75MaxPasses最大迭代检查的次数为了寻找合适的割，最大迭代检查的次数，有两个参数：Root:对根节点的次数（默认值为200）Tree:对其他节点的次数（默认值为2）Types类型控制生成的割（平面）的策略，共有12种策略可供选择（如想了解细节，请参阅整数规划方面的专著）IntegerSolver(整数求解器)选项卡选项组选项含义Branching分枝Direction取整方向控制分枝策略中优先对变量取整的方向，有三种选择：Both:LINGO自动决定（默认设置）Up:向上取整优先Down:向下取整优先Priority优先级控制分枝策略中优先对哪些变量进行分枝，有两种选择：LINGODecides:LINGO自动决定（默认设置）Binary:二进制（0-1）变量优先。Integrality取整性质Absolute绝对误差限当变量与整数的绝对误差小于这个值时，该变量被认为是整数，默认值为10-6Relative相对误差限当变量与整数的绝对误差小于这个值时，该变量被认为是整数，默认值为8*10-6Optimality优化选项。整数规划问题非常复杂，求解大型整数规划时，通常选择运行几分钟得到挖于真正最优解的可行解，而不是运行很长时间（几天）来找最优解。Absolute目标函数的绝对误差限如果当前目标函数值与目前找到的最优值的绝对误差小于这个值时，则当前解被认为是最优解（也就是说：只需要搜索比当前解至少改进这么多个单位的解），从而缩短求解时间。默认值是8*10-8Relative目标函数的相对误差限如果当前目标函数值与目前找到的最优值的绝对误差小于这个值时，当前解被认为是最优解（也就是说：只需要搜索比当前解至少改进这么多百分比的解），从而缩短求解时间。默认值是5*10-8TimetoRelative开始采用相对误差限的时间（秒）在程序开始运行后这么多秒内，不采用相对误差限策略，目的是希望找到真正的最优解；此后才使用相对误差限策略，在求解比较耗费时间的情况下，用相对误差限策略来缩短求解时间（放弃追求高精度，缩短求解时间）。默认值为100s.Tolerances误差限，控制分支定界法求解整数规划的分支策略Hurdle控制值IP目标函数的阈值，即最优解的一个界限，如果知道某个整数可行解，可利用这个可行解的目标函数值，设置最优解的界限，只寻找比廖值好的目标函数对应的整数解，一个好的阈值能够大大缩短求解时间。一旦找到一个初始整数解，Hurdle值就不再为None.表示没有指定这个阈值。NodeSelection节点选择控制算法如何选择节点分枝的次序，有以下选项：LINGODecides:LINGO自动选择（默认设置）DepthFirst:采用深度优先策略WorstBound:选择具有最弱限制的节点BestBound:选择具有最强限制的节点StrongBranch强分枝的层数控制采用强分枝的层数，即分枝树的前n层运用更精深（强）的分支策略。所谓强分枝，就是在一个节点对多个变量分别尝试进行预分枝，找出其中最好（使目标函数改变最大）的解（变量）最终进行实际分枝。默认值为10.IntegerPre-Solver(整数预处理求解器)选项卡选项组选项含义GlobalSolver全局最优解程序UseGlobalSolver使用全局最优程序很多非线性规划是非凸的和（或）不光滑的，LINGO默认的非线性算法会收敛到局部的次最优点，这个点可能离真正的全局最优点很远。如果选中该选项，LINGO将用全局最优求解程序求解模型，尽可能得到全局最优解（求解花费的时间可能很长，但是，如果变量不很多，使用全局最优求解程序花费的时间并不多）；否则不使用全局最优求解程序，通常只得到局部最优解（有时局部最优解就是全局最优解）VariableUpperBound变量上界有两个栏目可以控制变量上界（按绝对值）：value:设定变量的上界，若该值为d，则变量的赋值被限制在区域[d,-d]内该值尽可能设置得紧凑些，防止进入无意义的搜索区域而浪费求解时间，默认值为1010；Application列表框设置这个界的三种应用范围：None:所有变量都不使用这个上界，一般不推荐；All:所有变量都使用这个上界；Selected:先找到第一个局部最优解，然后使用这个上界，并且只用于不中止于初始局部解的变量（默认设置）Tolerances误差限包括两个栏目（按绝对值）：optimality:只搜索比当前解至少改进这么多个单位的解（默认值为10-6）Delta:全局最优求解程序在凸化过程中增加的附加约束的误差限，即必须满足的程度（默认值为10-7）Strategies策略可以控制全局最优求解程序的三类策略：branching:第1次对变量分枝时使用的分枝策略：AbsoluteWidth(绝对宽度）LocalWidth(局部宽度)GlobalWidth(全局宽度)GlobalDistance(全局距离)ABS(Absolute)Violation(绝对冲突）Rel(Relative)Violation(相对冲突，默认设置)BoxSelection:选择活跃分枝节点的方法；DepthFirst(深度优先)WorstBound(具有最坏界的分枝优先，默认设置)Reformulation:模型重整的级别；None(不进行重整)Low(低)Medium(中)High(高，默认设置)MultistartSolver多初始点求解程序Attempts尝试次数尝试多少个初始点求解，有以下几种可能的设置：SolverDecides:由LINGO决定（默认设置，对小规模NLP问题为5次，对大规模问题不使用多点求解）Off:不使用多点求解N(>1的正整数):N点求解Barrier:障碍法（即内点法）注意：Multistart算法将急剧增加求解时间。1.2LINGO的基本组成Model:sets:！集合定义部分;语句体;endsetsdata:！数据初始化部分;语句体;enddata！目标函数与约束条件语句;min(max)=...;@for(...);End模型均以model:开头，以end结束；每条语句用分号";"结束；注释部分以"!"开头，";"结束；集合定义与数据初始化开始以":"标识，结束语句不加任何符号；所有表达式中乘号"*"不能省略；为便于阅读，通常采取缩进式编写。1.3集合定义的语法规则：sets:集合名/成员(可以省略不写明)/:属性(可以没有);endsets例：BIANLANG/B1..B4/:X;YUESU/A1..A3/:B;！以上两个集合为初始集合，相当于一维数组;YXB(YUESU,BIANLANG):A;!此集合由两个初始集合构成，称为衍生集合或派生集合；数据的初始化：sets:BIANLANG/B1..B4/:X;YUESU/A1..A3/:B;YXB(YUESU,BIANLANG):A;endsetsdata:B=100,200,400;A=1,2,3,44,5,6,77,8,9,10;此集合由两初始集合所有成员组合，为稠密集合。sets:BIANLANG/B1..B4/:X;YUESU/A1..A3/:B;YXB(YUESU,BIANLANG),/A1,B1A1,B2A2,B3A3,B4/:A;endsets此集合成员只有两初始集合部分成员组合，称为稀疏集合。1.4运算符算术运算符：-取反；＾乘方；﹡乘；／除；﹢加；﹣减。逻辑运算符：最高#not#,最低#and#和#or#,其余中间平级#not# 否定该操作数的逻辑值，＃not＃是一个一元运算符#eq# 若两个运算数相等，则为true；否则为flase#ne# 若两个运算符不相等，则为true；否则为flase#gt# 若左边的运算符严格大于右边的运算符，则为true；否则为flase#ge# 若左边的运算符大于或等于右边的运算符，则为true；否则为flase#lt# 若左边的运算符严格小于右边的运算符，则为true；否则为flase#le# 若左边的运算符小于或等于右边的运算符，则为true；否则为flase#and# 仅当两个参数都为true时，结果为true；否则为flase#or# 仅当两个参数都为false时，结果为false；否则为true关系运算符：“=”、“<=”和“>=”优先顺序：单目优于双目，算术优于逻辑，逻辑优于关系，平级从左到右，括号改变次序。1.5函数LINGO提供了15个数学函数，14个概率函数，9个集合操作函数，4个变量定界函数，5个文件输入输出函数，2个金融函数，4个结果报告函数，以及文字信息、条件和允许C语言或fortran语言编写并编译函数，共73个函数。本课程所涉及内容所用到的主要是集合操作函数和变量定界函数，其他函数一旦用到，可查看相应的函数使用说明。常用的集合函数：@for(s:e);@sum(s:e);@max(s:e);@min(s:e);@prod(s:e);@wrap(i,n);前5个的格式：@函数名(集合名｜条件：表达式)，后1个用于转换集合端点。变量定界函数：@BIN(X),@BND(L,X,U),@GIN(X),@FREE(X)条件函数：@if(条件表达式,条件为真的表达式,条件为假的表达式);LINGO编程应用举例2.1线性与整数规划例2.1.1（资源分配问题）求解运筹学问题程序段model:sets:dv/1..2/:x,c;st/1..2/:b;dxs(st,dv):a;endsetsdata:c=3,2;b=10,8;a=2,11,1;enddatamax=@sum(dv:c*x);@for(st(i):@sum(dv(j):a(i,j)*x(j))<=b(i););end例2.1.2（混合问题）饲料营养成分含量g/kg单价元/kg营养甲营养乙营养丙123450.52.03.000.060.080.700.350.250.0226543需求量g85518Model: sets: dv/1..5/:x,c; st/1..3/:b; dxs(dv,st):a; endsets data: c=2,6,5,4,3; b=85,5,18; a=0.5,0.1,0.082,0.06,0.73,0.04,0.351.5,0.15,0.25 0.8,0.2,0.02; enddata min=@sum(dv:c*x); @for(st(j):@sum(dv(i):a(i,j)*x(j))>=b(j););end例2.1.3（条材下料问题）圆钢长5.5m，需要A(3.1m)、B(2.1m)、C(1.2m)三种圆钢材料分别为100、200、400根，试安排下料方式，使所需圆钢原材料的总数量最少？（截取方式不超过5种）model:sets: jefa/1..5/:x; cailao/1..3/:l,b;cxj(cailao,jefa):a;endsetsdata: l=3.1,2.1,1.2; b=100,200,400;enddata min=@sum(jefa:x); @for(jefa(j):@sum(cailao(i):l(i)*a(i,j))<=5.5;); @for(cailao(i):@sum(jefa(j):x(j)*a(i,j))>=b(i);); @for(jefa:@gin(x));@for(cxj:@gin(a));end例2.1.4（投资分配问题）(P25案例2-2)万得集团有限公司是一家集工、商、贸一体化的企业，为了拓展公司的业务范围，增加企业的竞争实力，公司董事会确定了投资方向。责成财务经理制定出切实可行的投资计划。财务部门通过收集相关资料和数据，决定在今后五年内给A、B、C、D四个产品项目投资6000万元。财务部门设计的投资方案如下：产品项目A:从第一年到第五年每年年初都可以进行投资，当年年末就能收回本利110%。产品项目B：从第一年到第四年每年年初都可以进行投资，次年年末收回本利125%。产品项目C：投资必须在第三年年初进行，到第五年年末收回本利140%。产品项目D：投资需在第二年年初进行，到第五年年末收回本利155%。其中：项目B的每年最大投资额不能超过900万元，项目C的最大投资额不能超过2400万元，项目D的最大投资额不能超过3000万元。在满足各个投资项目的限制条件下，使企业在五年内获得最大的收益max=1.1*x51+1.25*x42+1.4*x33+1.55*x24;x11+x12=6000;x21+x22+x24=1.1*x11;x31+x32+x34=1.1*x21+1.25*x12;x41+x42=1.1*x31+1.25*x22;x51=1.1*x41+1.25*x32;x12<=900;x22<=900;x32<=900;x42<=900;x33<=2400;x24<=3000;model: sets: nian/1..5/; xiangmu/1..4/; nxx(nian,xiangmu):例2.1.5（生产安排问题）（P35）Sytech国际公司是一家在同行业中处于领先地位的计算机和外围设备的制造商。公司的主导产品分类如下：大型计算机（MFRAMES）、小型计算机（MINIS）、个人计算机（PCS）、和打印机（PRINTERS）。公司的两个主要市场是北美和欧洲。公司一直按季度作出公司最初的重要决策。公司必须按照营销部门的需求预测来对分布在全球的三个工厂调整产量，公司下一季度需求预测如下：表2-SEQ表2-\*ARABIC1需求预测产品北美欧洲大型计算机962321小型计算机44171580个人计算机4821015400打印机155406850而公司的三个工厂的生产能力限度又使得其不能随心所欲地在任一工厂进行生产，限制主要是各工厂规模及劳动力约束。表2-SEQ表2-\*ARABIC2工厂的生产能力产品空间（平方英尺）劳动力（小时）伯灵顿540710277710中国台湾201000499240爱尔2-SEQ表2-\*ARABIC3资源利用率产品空间/单位劳动小时/单位大型计算机17.4879.0小型计算机17.4831.5个人计算机3.006.9打印机5.305.6最终分析所要求的数据由会计部门提供，表2-23所显示的数据表示单位利润贡献（税后）。表2-SEQ表2-\*ARABIC4产品单位利润单位利润大型计算机小型计算机个人计算机打印机伯灵顿16136.4613694.038914.476956.231457.181037.571663.511345.43中国台湾17358.1414709.969951.047852.361395.351082.491554.551270.16爱尔兰15652.6813216.349148.557272.891197.521092.611478.91312.44model:sets: chanpin/1..4/:xuqiu1,xuqiu2; chandi/1..3/; ziyan/1..2/; cpxz(chanpin,ziyan):danhao; cdxz(chandi,ziyan):nengli; cdxcp(chandi,chanpin):x,y,cx,cy;endsetsdata:xuqiu1=962,4417,48217,15540;xuqiu2=321,1580,15400,6850;danhao=17.48,79.0 17.48,31.5 3.00,6.9 5.30,5.6;nengli=540710,277710 201000,499240 146900,80710;cx=16136,8914,1457,1663 17358,9915,1395,1554 15652,9148,1197,1478;cy=13694,6956,1037,1345 14709,7852,1082,1270 13216,7272,1092,1312;enddatamax=@sum(cdxcp:cx*x+cy*y);@for(chanpin(j):@sum(chandi(i):x(i,j))>=xuqiu1(j);@sum(chandi(i):y(i,j))>=xuqiu2(j););@for(chandi(i):@sum(chanpin(j):danhao(i,1)*x(i,j))<=nengli(i,1);@sum(chanpin(j):danhao(i,2)*y(i,j))<=nengli(i,2););@for(cdxcp:@gin(x);@gin(y););End例2.1.6（排班问题）星期星期一星期二星期三星期四星期五星期六星期目需求15171414151920model:sets: zou/mon..sun/:x,r;endsetsdata: r=15,17,14,14,15,19,20;enddatamin=z;z=@sum(zou:X);@for(zou(i):z-x(@wrap(i+1,7))-x(@wrap(i+2,7))>=r(i));@for(zou:@gin(x));end例2.1.7计划排序程序（稀疏集合：直接列表法）11项工作，工作时间如表所示，先后顺序如图所示。交给4个工作站完成，工作站也按顺序分配，不能倒流。如何安排，可使装配时间最少。任务ABCDEFGHIJK时间4511950151212121289model:sets: task/A..K/:t; station/1..4/; txt(task,task)/a,bb,cc,fc,gd,ee,he,if,jg,jh,ji,jj,k/; txs(task,station):x;endsetsdata:t=4511950151212121289;enddata@for(task(i):@sum(station(j):x(i,j))=1);@for(txt(i,j):@sum(station(k):k*x(j,k)-k*x(i,k))>=0);@for(station(k):@sum(task(i):t(i)*x(i,k))<=cyctime);min=cyctime;@for(txs:@bin(x));end例2.1.8配对模型（稀疏集合：元素过滤法）某公司准备将8个职员安排到4个办公室，每室2人，根据观察，两两之间的合作相容性如表所示，数字越小相容性越好。如何安排可使总相容程度最好？s1s2s3s4s5s6s7s8s19342156s2173521s344292s41552s5876s623s74model:sets:ren/1..8/;links(ren,ren)|&2#gt#&1:c,x;!第2个父集索引值大于第1个父集索引值;endsetsdata: c=9,3,4,2,1,5,6 1,7,3,5,2,1 4,4,2,9,2 1,5,5,2 8,7,6 2,3 4;enddatamin=@sum(links:c*x);@for(ren(i):@sum(links(j,k)|j#eq#i#or#k#eq#i:x(j,k))=1);@for(links:@bin(x));End2.2指派问题例2.2.1四名队员A,B,C,D参加混合接力赛，其100米自由泳、蛙泳、蝶泳、仰泳成绩如下：自由泳蛙泳蝶泳仰泳ABCD56635756746977766165636363716772如何安排可使预期成绩最好。Model:Sets:Xiangmu/ziyouyong,wayong,dieyong,yangyong/;Renyuan/A..D/;XXR(renyuan,xiangmu):X,C;EndsetsData:C= 56,74,61,63 63,69,65,71 57,77,63,67 56,76,63,72;EnddataMin=@sum(xxr:c*x);@for(xiangmu(j):@sum(renyuan(i):x(i,j))=1);@for(renyuan(i):@sum(xiangmu(j):x(i,j))=1);@for(xxr:@bin(x));end例2.2.2P73案例4-4分配甲、乙、丙、丁四个人去完成A、B、C、D、E五项任务，每个人完成各项任务的时间如表4-6所示。表4-6完成任务所用时间任务人员ABCDE甲乙丙丁2539342429382742312628364220402337333245由于任务数多于人数，故考虑：（1）任务E必须完成，其他4项中可任选3项完成；（2）其中有一个人完成两项，其他每人完成一项；（3）任务A由甲或丙完成，任务C由丙或丁完成，任务E由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项。试分别确定最优分配方案，使完成任务的总时间为最小。(1)任务E必须完成，其他4项中可任选3项完成Model:Sets:Renyuan/jia,yi,bing,ding/;Renwu/A..E/;RXR(renyuan,renwu):c,x;EndsetsData:C= 25,20,31,42,3739,38,26,20,3334,27,28,40,3224,42,36,23,45;EnddataMin=@sum(rxr:c*x);@for(renyuan(i):@sum(renwu(j):x(i,j))=1);@sum(renyuan(i):x(i,4))=1;@for(renwu(j)|j#ne#4:@sum(renyuan(i):x(i,j))<=1);@for(rxr:@bin(x));End(2)其中有一个人完成两项，其他每人完成一项Model:Sets:Renyuan/jia,yi,bing,ding/;Renwu/A..E/;RXR(renyuan,renwu):c,x;EndsetsData:C= 25,20,31,42,3739,38,26,20,3334,27,28,40,3224,42,36,23,45;EnddataMin=@sum(rxr:c*x);@for(renyuan(i):@sum(renwu(j):x(i,j))>=1);@for(renyuan(i):@sum(renwu(j):x(i,j))<=2);@for(renwu(j):@sum(renyuan(i):x(i,j))=1);@for(rxr:@bin(x));End(3)任务A由甲或丙完成，任务C由丙或丁完成，任务E由甲、乙或丁完成，且规定4人中丙或丁完成两项任务，其他每人完成一项Model:Sets:Renyuan/jia,yi,bing,ding/;Renwu/A..E/;RXR(renyuan,renwu):c,x;EndsetsData:C= 25,20,31,42,3739,38,26,20,3334,27,28,40,3224,42,36,23,45;EnddataMin=@sum(rxr:c*x);@sum(renyuan(i)|i#eq#1#or#i#eq#3:x(i,1))=1;@sum(renyuan(i)|i#eq#3#or#i#eq#4:x(i,3))=1;@sum(renyuan(i)|i#ne#3:x(i,5))=1;@for(renwu(j)|j#eq#2#or#j#eq#4:@sum(renyuan(i):x(i,j))=1);@for(renyuan(i)|i#le#2:@sum(renwu(j):x(i,j))=1);@for(renyuan(i)|i#gt#2:@sum(renwu(j):x(i,j))<=2);@for(rxr:@bin(x));End2.3运输问题例2.3.1（P96案例5-1）某化肥公司根据现有定单及对市场的预测，估计下一年度每个季度对化肥的需求量分别为10万吨、25万吨、25万吨、10万吨，其每季度的生产能力和生产成本如表5-22所示，假设在每个季度内产销都是平稳的，又若产品当季不销售，每季度存储费用为10万元/万吨，要求在满足需求量的前提下，如何制订生产计划，才能使全年总成本（包括生产成本和存储费用）最低？表5-22生产能力及生产成本表季度生产能力（万吨）生产成本（万元/万吨）Ⅰ20250Ⅱ25280Ⅲ25300Ⅳ20250model: sets: jijie/1..4/:xuqiu,nengli,chengben; jxj(jijie,jijie)|&2#ge#&1:x,c; endsets data: xuqiu=10,25,25,10; nengli=20,25,25,20; chengben=250,280,300,250; enddata @for(jxj(i,j):c(i,j)=chengben(i)+10*(j-i)); @for(jijie(i):@sum(jijie(j)|j#ge#i:x(i,j))<=nengli(i)); @for(jijie(j):@sum(jijie(i)|i#le#j:x(i,j))=xuqiu(j));End例2.3.2（P103-7）model: sets: chandi/1..4/:chanliang,chengben; xiaodi/A..F/:xiaoliang,xiaojia; cxx(chandi,xiaodi):x,c; endsets data: chanliang=200,300,400,100; chengben=1.2,1.4,1.1,1.5; xiaoliang=200,150,400,100,150,150; xiaojia=2.0,2.4,1.8,2.2,1.6,2.2; enddata @for(cxx(i,j):c(i,j)=xiaojia(j)-chengben(i)); @for(chandi(i):@sum(xiaodi(j):x(i,j))=chanliang(i)); @for(xiaodi(j)|j#ne#3:@sum(chandi(i):x(i,j))>=0.8*xiaoliang(j)); @sum(chandi(i):x(i,3))>=100; @sum(chandi(i):x(i,4))=xiaoliang(4); max=@sum(cxx:c*x);End例2.3.3（P104）（1）继续仅由火车运输model: sets: product/1..3/:quanlity; market/1..5/:demand; pxm(product,market):cx,cy,invers,x,y; endsets data: quanlity=15,20,15; demand=11,12,9,10,8; cx= 61,72,45,55,66 69,78,60,49,56 59,66,63,61,47; cy= 31,38,24,1000,35 36,43,28,24,31 1000,33,36,32,26; invers=275,303,238,1000,285 293,318,270,250,265 1000,283,275,268,240; enddata min=@sum(pxm:cx*x); @for(product(i):@sum(market(j):x(i,j))=quanlity(i)); @for(market(j):@sum(product(i):x(i,j))=demand(j));end最优值：2816.仅由船只运输（船只无法到达除外）model: sets: product/1..3/:quanlity; market/1..5/:demand; pxm(product,market):cx,cy,invers,x,y; endsets data: quanlity=15,20,15; demand=11,12,9,10,8; cx= 61,72,45,55,66 69,78,60,49,56 59,66,63,61,47; cy= 31,38,24,1000,35 36,43,28,24,31 1000,33,36,32,26; invers=275,303,238,1000,285 293,318,270,250,265 1000,283,275,268,240; enddata min=z;z=@sum(pxm:@if(cx*x#le#cy*y+invers,cx*x,cy*y+invers)).; @for(product(i):@sum(market(j):x(i,j)+y(i,j))=quanlity(i)); @for(market(j):@sum(product(i):x(i,j)+y(i,j))=demand(j));end最优值：3563.由运费少来决定。model: sets: product/1..3/:quanlity; market/1..5/:demand; pxm(product,market):cx,cy,invers,x,y; endsets data: quanlity=15,20,15; demand=11,12,9,10,8; cx= 61,72,45,55,66 69,78,60,49,56 59,66,63,61,47; cy= 31,38,24,1000,35 36,43,28,24,31 1000,33,36,32,26; invers=275,303,238,1000,285 293,318,270,250,265 1000,283,275,268,240; enddata min=@sum(pxm:@if(cx*x#le#cy*y+invers,cx*x,cy*y+invers)); @for(product(i):@sum(market(j):x(i,j)+y(i,j))=quanlity(i)); @for(market(j):@sum(product(i):x(i,j)+y(i,j))=demand(j));End最优值：851.2.4目标规划介绍两种方法：序贯算法与线性加权法。例2.4.1（P116例6.5）序贯算法STEP1MIN=D1_;2*X1+2*X2<=12;2*X1+3*X2+D1_-D1=15;求解结果：d1_=0，固定转第2步STEP2MIN=D2_+D2;2*X1+2*X2<=12;2*X1+3*X2+D1_-D1=15;D1_=0;2*X1-X2+D2_-D2=0;求解结果：D2_=D2=0,固定转第3步STEP3:MIN=3*D3_+3*D3+D4;2*X1+2*X2<=12;2*X1+3*X2+D1_-D1=15;D1_=0;2*X1-X2+D2_-D2=0;D2_=0;D2=0;4*X1+D3_-D3=16;5*X2+D4_-D4=15;优化结果：Globaloptimalsolutionfound.Objectivevalue:29.00000Infeasibilities:0.000000Totalsolveriterations:0VariableValueReducedCostD3_8.0000000.000000D30.0000006.000000D45.0000000.000000X12.0000000.000000X24.0000000.000000D1_0.0000000.000000D11.0000000.000000D2_0.0000000.000000D20.0000000.000000D4_0.0000001.000000线性加权法MIN=100*D1_+10*(D2_+D2)+3*D3_+3*D3+D4;2*X1+2*X2<=12;2*X1+3*X2+D1_-D1=15;2*X1-X2+D2_-D2=0;4*X1+D3_-D3=16;5*X2+D4_-D4=15;优化结果：Globaloptimalsolutionfound.Objectivevalue:29.00000Infeasibilities:0.000000Totalsolveriterations:4VariableValueReducedCostD1_0.000000100.0000D2_0.00000015.66667D20.0000004.333333D3_8.0000000.000000D30.0000006.000000D45.0000000.000000X12.0000000.000000X24.0000000.000000D11.0000000.000000D4_0.0000001.0000002.5图与网络模型2.5.1最短路问题A例：求A到G的最短路A13A13A32A32A312AAAA312AAAA34A34A41A41A22model:sets: CITIES/A..G/:FL;!定义城市; ROADS(CITIES,CITIES)/A,BA,CB,DB,EB,FC,DC,EC,FD,GE,GF,G/:W,P; !定义相邻城市、城市间里程及最短路径;endsetsdata: w=2,4,3,3,1,2,3,1,1,3,4;enddata N=@size(cities);FL(N)=0; @for(cities(i)|i#lt#n:FL(i)=@min(roads(i,j):w(i,j)+FL(J))); @for(roads(i,j):P(i,j)=@if(FL(i)#eq#w(i,j)+FL(j),1,0));End2.5.2最大流问题对2.5.1例题求从A到G的最大流。model:sets: POINT/A..G/; LINKS(POINT,POINT)/A,BA,CB,DB,EB,FC,DC,EC,FD,GE,GF,GG,A/:c,f;endsetsdata: c=2,4,3,3,1,2,3,1,1,3,4,1000;enddata MAX=F(7,1); @for(LINKS(i,j):f(i,j)<=c(i,j)); @for(point(i):@sum(links(j,i):f(j,i))=@sum(links(i,j):f(i,j)));end2.6动态规划2.6.1最短路问题A例：求A到G的最短路A13A13A32A32A312AAAA312AAAA34A34A41A41A22model:sets: CITIES/A..G/:FL;!定义城市; ROADS(CITIES,CITIES)/A,BA,CB,DB,EB,FC,DC,EC,FD,GE,GF,G/:W,P; !定义相邻城市、城市间里程及最短路径;endsetsdata: w=2,4,3,3,1,2,3,1,1,3,4;enddata N=@size(cities);FL(N)=0; @for(cities(i)|i#lt#n:FL(i)=@min(roads(i,j):w(i,j)+FL(J))); @for(roads(i,j):P(i,j)=@if(FL(i)#eq#w(i,j)+FL(j),1,0));End2.6.2资源分配问题model:sets: jieduan/A..D/:F; ziyuan/1..6/; jxz(jieduan,ziyuan):W,X;endsetsdata: w=0,4,8,11,11,110,5,9,11,12,120,3,7,9,11,120,0,0,0,0,0;enddata N=@size(jieduan);F(N)=0; @for(jieduan(i)|i#lt#n:F(i)=@max(jxz(i,j):w(i,j)+f(i+1))); @for(jxz(i,j)|i#lt#n:x(i,j)=@if(F(i)#eq#w(i,j)+F(i+1),1,0)); @for(ziyuan(j):x(n,j)=1);Endmodel:sets: jieduan/A..D/:F; ziyuan/1..6/; jxz(jieduan,ziyuan):W,X;endsetsdata: w=0,4,8,11,11,110,5,9,11,12,120,3,7,9,11,120,0,0,0,0,0;enddata N=@size(jieduan);f(N)=0; @for(jieduan(i)|i#lt#n:f(i)=@max(jxz(i,j):w(i,j)+f(i+1))); @for(jxz(i,j)|i#lt#n:x(i,j)=@if(f(i)#eq#w(i,j)+f(i+1),1,0)); @for(ziyuan(j):x(n,j)=1);End设备负荷问题model:sets: jd/1..4/:s,x,v; zb/1..5/:f;endsetsf(5)=0;s(1)=100;@for(jd:x<=s);@for(jd(k)|k#lt#4:s(k+1)=0.65*X(K)+0.95*(S(K)-X(K)));@FOR(JD(K):V(K)=9*X(K)+4*(S(K)-X(K)));@FOR(ZB(K)|k#lt#5:f(k)=v(k)+f(k+1));max=f(1);end2.7存储论2.7.1不允许缺货，即