优化软件ILOG_OPL教材

1、优化技术与软件ILOG OPL 开发环境ILOG ODMS光盘已放至FTPn地址 ftp:/n账户和密码都是 downloadn端口 21课程介绍n课程目标n学习使用ILOG OPL 开发环境n解决实际问题n掌握OPL的特征和功能n了解在解决复杂商业优化问题时nOPL 开发环境的规则nOPL与其他工具的关系课程介绍n听众n需要建模解决商业优化问题的专家n预备知识n对微软Windows 操作系统的了解n数学规划的知识将有助于对本课程知识的掌握，但并不是必须的。n基本的编程知识对于ILOG OPL 的开发是非常有用的，但并不是必须的。课程内容n介绍ILOG OPL 的优化技术n使用线性规划的优化产

2、品n生产计划和OPL 数据结构介绍ILOG OPL 的优化技术概述优化技术、OPL 和一个典型的生产计划问题什么是优化？优化是一种基于数学的技术，它以最大的运作效益为目标来分配各种资源。n它是如何工作的？n优化是一个可应用于特定问题的一个过程。这样，逻辑上第一步是对要解决问题的一个清晰的描述。随后的步骤如下：n为你的问题构造一个模型n将数据加入模型中n利用数学优化引擎分析该模型，以找到最好的可能解n当优化模型嵌入到实际应用中时，计划人员和运作管理者可以进行what-if 分析，并可以比较各种方案。什么可以进行优化？优化是一种决策工具，它实际上可以应用于各种行业中，下图所示优化技术的应用领域。什

3、么可以进行优化？从长期规划到实时决策，大量的决策问题可以进行优化。例如：n多少产品需要进行生产，何时生产，如何生产n如何运输产品、人员、材料n如何混合配置原材料n如何调度安排人员、工作和设备n如何对设施和设备进行选址和分配n如何花费资金，等等优化过程优化过程需要处理的一些信息类型，及其产生的结果。优化技术在优化技术广泛应用的领域，需要复杂的数学或先进的计算机科学方法来对复杂计划、调度和定价问题进行优化求解。在优化中用到的规划技术主要有：n线性规划(LP)n二次规划(QP)n约束规划(CP)实际中，许多整数规划都含有浮点计算，因此混合整数规划(MIP)的应用要多于纯IP。应用，技术，计划类型，开

4、发时间OPL 可以描述的规划问题类型当目标函数是 变量可以是 约束是线性的浮点整数线性不等式(=，=)二次的浮点整数线性或二次不等式(=.=)OPL 和优化OPL 开发环境是ILOG 全部优化解决方案组件中的一个。ILOG 优化工具可以分成两类：nILOG PowerOpsn全面、预先建立的应用，它们利用了超过15 年的经验，这些经验为在制造业和运输业中的一些特殊领域中的工作提供了优化技术。nODMSn优化决策管理系统，开发定制模型的一个成熟系统，是基于ILOG 的、经过工业验证的、优化引擎的应用。ILOG 的优化产品ODMS 中的OPLILOG OPL 开发环境是优化决策管理系统（ODMS）

5、中的一个组成成分。ODMS 是一套工具组件，包括ILOG 优化引擎，它可以用来开发定制模型和应用。可以利用OPL 开发环境来设计定制模型，用来解决商业或机构中的特定问题，这个过程并不需要低级开发语言。ODMS 中的OPL可以利用OPL 集成开发环境（IDE）来进行这一过程，它为用户提供了一个图形用户界面，从而为模型的开发提供了直观的工具。n这些模型可以直接和ILOG 优化决策管理器（ODM）一起集成到开发的应用中，从而使商业用户可以进行what-if 分析，并且比较各种方案。n数据与模型是相互独立的，这样所开发的原型就具有了可重用性。ODMS 中的各种软件是为从事商业优化的不同人员的工作而设计

6、的。角色和目标nOPL 是为优化专家们设计的工具n利用这个工具，他们可以与其他领域的专家进行交互工作。n开发各种应用的软件工程师n利用ODM 或ILOG Concert 技术的程序库n决策制定者n为构建模型提供了基本信息，并且作为开发的应用的最终用户。什么是OPL 开发环境？ILOG OPL 开发环境是一个IDE（集成开发环境），利用OPL（优化编程语言）建立并运行由目标函数和约束组成的数学模型，读取相应的数据对其进行优化。OPL 开发环境的组成包括：n优化编程语言（OPL）n用代数符号建立优化模型，类似于写在纸上的模型nOPL IDEn运行、测试和调试优化模型n应用编程接口（APIs）n可将

7、模型嵌入到应用程序中什么是OPL 开发环境？优化编程语言（OPL）、OPL IDE、应用编程接口（APIs）是建立在ILOG Concert 技术基础之上，与ILOG CPLEX 优化引擎相连接，并提供了对CPLEX 算法各种设置的完全读取。 什么是OPL 开发环境？OPL 开发环境IDE 包括:n建立OPL 模型的图形编辑器n用表格显示数据和解n用于优化调试的菜单和按钮nOPL 语法的在线帮助OPL 语言的特征n为建立数学规划模型而提供的简洁语言n为了描述数据而提供的先进数据类型n提供了与关系型数据库和Excel 电子表格的连接n对于数据处理和交互式的解决过程提供了ILOG ScriptOP

8、L APIs 的作用利用以下的计算机开发语言，APIs 允许将OPL 模型和脚本嵌入到应用程序中。nC+nMicrosoft.NETnVisual Basic.NET， C#，J#，etc.nMicrosoft Office 2003 via Visual Studio Tools for OfficenJavanWebnASP.NET ，JSP模型，数据和项目OPL IDE 允许构建与数据独立的模型。这就意味着当数据发生改变时，不需要改变模型。模型在一个独立的文件中（模型文件）进行维护，它与数据（数据文件）相独立，因此，对于具有不同输入数据的同一问题的多个实体，模型是可重用的。模型文件和一个

9、或多个数据文件（也可以不包括数据文件）组成了一个项目。模型，数据和项目除了模型和数据，项目还包括控制信息，用于实例化一个或多个问题。n项目控制信息包含在2 类结构中n一个或多个设置文件（.ops 文件） n控制冲突解决、选择和线性规划算法的运行n一个或多个运行配置n它们是模型、数据和设置文件的集合nthat are meant to run together模型，数据和项目nModel 是一个问题的抽象，它与数据无关nOPL 可以建立与数据无关的模型的数学描述n一个项目包括一个模型和一个或多个数据文件（也可以不包括数据文件），这些数据文件说明了特殊的问题实例。n一个问题实例是一个使用专门数据集

10、的项目的详细实例化，并受控于设置文件和运行配置。有关OPL OPL 项目的更多内容项目文件（.prj）包含了相应的各种文件和与一个问题相关的参数。它组织相关的模型和数据文件，并提供一种方便的方法来维护相关文件和运行选择之间的关系。在项目中：n模型文件（.mod）声明了数据项目n但是并不需要初始化它们n数据文件（.dat）包含了在模型中声明的数据的初始化有关OPL 项目的更多内容n设置文件（.ops）n当决定改变一个或多个数学规划和其他选择的缺省值时，该文件保存用户定义的值。n运行配置并不是一个文件类型，而是为了运行目的设置的项目变化。一个运行配置组合了一个模型文件和一个或多个数据文件，考虑到内

11、容和/或设置，它们与项目中原始的模型和数据是不同的，但是是针对同一个数学问题。n在一个项目中，可以根据自己的需要定义多个运行配置。有关OPL 项目的更多内容n一个最小的项目有n一个模型文件n对于同一模型文件的一个缺省的运行配置n一个典型的项目有n一个或多个模型文件n任意数量的数据文件（或者没有数据文件）n一个或多个设置文件n一个或多个运行配置，以设定这些模型、数据和设置文件的不同组合。通过一个典型的生产计划案例学习OPL 开发环境的功能和特征在OPL IDE 中为生产计划问题建模关键词：n决策变量n目标函数n约束在OPL IDE 中为生产计划问题建模目标函数描述了优化希望的最终结果。例如，为了

12、获得最大利润而寻找最优的生产数量。为此，需要考虑生产中的各种约束条件。例如，每个产品所需生产的零件数，和每个零件的当前库存量。IDE 会自动用不同颜色加亮关键字。在OPL IDE 中为生产计划问题建模假设生产的是一种化工产品，下面的表格列出了模型中所需的数据以及它们在OPL IDE 中是如何声明的：数据描述OPL 中的声明产品是： Ammonium gas(NH3)Ammonium chloride(NH4Cl)Products = “gas”，”chloride”;数据描述OPL 中的声明产品是：Ammonium gas(NH3)Ammonium chloride(NH4Cl)Product

13、s = “gas”, ”chloride”;成分是：N,H,ClComponments = “ nitrogen” ,”hydrogen”, ”chlorine”;各种成分的需求是：1 个单位的N 和3 个单位的H 组成1 个单位的NH31 个单位的N，4 个单位的H 和1 个单位的Cl 组成1 个单位的NH4ClDemand = 1, 3, 0, 1, 4, 1;现有库存：50 个单位的N，180 个单位的H，40 个单位的ClStock = 50, 180, 40;每种产品的利润：NH3 = 30，NH4Cl = 40Profit = 30, 40;练习：学习使用OPL 对汽油生产问题进行

14、建模，然后，可以将模型应用到不同的生产环境中。通过这个建模过程熟悉IDE 及其特征。在开始之前，双击在桌面或是在Windows 开始菜单中OPL IDE 的图标，运行OPL IDE。 OPL IDE 具有多文档界面（MDI），这样可以同时编辑多个文件。 下面的图表显示了IDE主窗口（一个项目已经加载进IDE 中）和它的一些其它组成部分。步骤：1、打开OPL IDE 案例项目OPLXx.LabsGasworkgas.prj项目包含两个文件：gas.mod（模型文件）和gas.da（数据文件）。2、和同学一起讨论这些文件3、点击工具条中的运行命令 ，并检查结果。调试OPL IDE 提供了错误捕捉机

15、制，这些错误包括语法错误或运行错误。为了快速演示如何使用这些功能，执行下面的步骤。1、在gas.mod 文件中的一行语句的末尾删除一个分号，产生一个语法错误；2、运行该项目并注意输出窗口，然后在代码编辑窗口中出错行会被加亮。n还可以在程序中加入断点，并查看它的状态。n在线文档给出了详细的说明。3、纠正这个语法错误，然后保存这个模型文件。改变产品，重复使用模型现在，假设不是生产化工产品，而是生产珠宝，相应数据如下。使用相同的模型，写一个新的数据文件。数据描述OPL 中的声明产品是：戒指，耳环Products = “rings”，”earrings”;数据描述OPL 中的声明产品是：戒指，耳环Pr

16、oducts = “rings”，”earrings”;成分是：黄金，钻石Componments = “Gold”, ”Diamonds”;各种成分的需求是：3 个单位的黄金和1 颗钻石生产1 个戒指2 个单位的黄金和2 颗钻石生产1 个耳环Demand = 3, 1, 2, 2;现有库存：150 个单位的黄金，180 颗钻石Stock = 150, 180;每种产品的利润：戒指 = 60，耳环 = 40Profit = 60, 40;过程：1、在OPL IDE 中，从菜单条中选择FileNewProject，创建一个新的项目。2、使用导航按钮进入目录文本框中，用Make New Folder

17、 按钮在OPLXx.LabsGasworkjewelry 目录中创建一个新的jewelry目录。通过点击Create project 按钮完成这些操作。这个项目将打开一个空白的模型文件。3、在Project 窗口中，在jewelry.mod 上点击鼠标右键，并从上下文菜单中选择Remove item。不用完全重新创建一个模型文件，可以利用现有的一个模型。过程：4、在项目文件上点击鼠标右键，并从上下文菜单中选择Add existing document，选择OPLXx.LabsGasworkgas.mod 并将它添加到你的项目中。5、在Project 窗口，将gas.mod 文件拖入Config

18、urations1，将它添加到缺省的运行配置中。6、在项目文件上点击鼠标右键，并从上下文菜单中选择Add new document。Create document 对话框将被打开。过程：7、在Create document 对话框中，选择OPL data 作为文件类型，将它保存到OPLXx.LabsGasworkjewelry 中，并命名为jewelry.dat。点击Create document，数据文件在编辑区打开，注意到它已经添加到Configuration1 中。8、为珠宝生产问题编写数据文件，如上面表格中所列情况，并保存你的工作。运行这个项目。是否得到一个有效的结果呢？9、将这个结果

19、与gas.prj 得到的结果进行比较。总结n优化是一种基于数学的技术，它针对最大的运作效益来分配资源，可应用于多种工业和商业情况中。nOPL 开发环境是ILOG 优化决策管理系统(ODMS)的一个组成成分，ODMS 是一个工具组件，包括ILOG 优化引擎，可以用来开发定制模型和应用。n OPL 开发环境的主要用户是优化建模专家，他们用来为一个商业行为或机构的具体问题设计定制解决方案，这个过程不需要低级的编程语言。总结nOPL 开发环境提供一个集成的开发环境（IDE），它允许使用直观的图形界面进行建模。模型可以集成到由ILOG 优化决策管理器（ODM）开发的应用中，允许用户执行what-if分析

20、，比较不同方案。并提供了多个APIs。n数据与模型独立，因此开发的模型是可重用的。使用线性规划的优化工具介绍线性规划概念学习OPL 语言的运算符和语法学习目标n分析一个简单的生产问题n并将它转换成优化语言n使用OPL ，利用线性规划技术n解决一个简单的生产问题n学习OPL 语言的运算符和语法n完成第一个模型n并学习如何独立地处理数据一个生产流程问题一个电话公司加工并销售两种类型的产品：固定电话，便携式电话。每种类型的电话都由公司进行组装和喷漆，公司希望每种产品至少生产100 个并最大化它的季度利润。为了实现这个目标，公司需要计算每种电话最优的生产数量。生产条件n一个固定电话的加工时间n12 分

21、钟，在装配机器上n30 分钟，在喷漆机器上n一个便携式电话的加工时间n24 分钟，在装配机器上n24 分钟，在喷漆机器上n每个季度装配机器可用的工作时间是400小时n每个季度喷漆机器可用的工作时间是490小时n固定电话的利润为每个12美元n便携式电话的利润为每个20美元电话生产问题的优化语言描述用优化术语，我们可以这样描述这个问题： 决策变量目标函数约束条件生产每种产品数量Desk：固定电话Cell：便携式电话最大化利润12Desk+20Cell受制于：固定电话最小生产量=100便携式电话最小生产量=1000.2desk+0.4cell=400(组装机上的工作时间限制)0.5desk+0.4c

22、ell=线性表达式n线性表达式=线性表达式任何一个线性约束都可以改写成一个或两个下面类型的表达式：n线性表达式=7 是线性的X*y+5=z是非线性的线性不等式必须是严格不等式不等式必须具有的形式是=或=5 是对的X+3*不是正确的不等式目标函数必须是线性的目标函数不能包含二次表达式或变量相乘Minimize(2*x+5.0*y)是线性的Minimize(2*x*y+5.0*y)是非线性的变量边界线性规划的约束条件常常会设置变量允许的边界。这样，一个约束条件通常具有以下形式：下界=变量=上界n下界为变量可取的最小值n上界为变量可取的最大值在运筹学中，一个边界可以在也可以不在变量的域内。如果一个边

23、界处于变量的域内，这个变量可假设为就取该值，而不小于（下界）或大于（上界）。当一个边界不在变量的域内，这个变量严格大于下界或严格小于上界，但并不会取这个边界值。逻辑约束条件一个逻辑约束条件是用逻辑运算符，例如逻辑和、逻辑或、非（否）、条件语句（ifthen）来组合线性约束条件，从而用来表达线性约束条件之间的复杂关系。ILOG CPLEX 也可以处理某些出现在线性约束条件中的逻辑表达式。一类逻辑表达式是变量集合的最小化，另一类逻辑表达式是一个变量的绝对值。逻辑约束条件除了描述线性约束条件的关系之外，ILOG CPLEX 可以处理下面约束条件中的逻辑运算符：n&（连接）n|（分离）n！（否

24、）n！=（不同）这样，将线性约束条件和逻辑约束条件组合起来，就可以在应用中构造复杂的表达式。解线性规划一个线性规划的解空间是一个欧几里得空间的子集，该欧几里得空间具有与线性规划的变量数相等的维数。这个解空间叫做可行域。可行域的边界有时称为多面体。解的类型n线性规划的一个可行解n是满足所有约束条件的变量赋值n线性规划的一个最优解n是解空间中具有最优目标函数值的点因为在线性规划中强调最优性，术语“解” 通常用来表示“最优解”。在电话生产问题中解的可行域最优解在解的可行域中，线性规划搜索一个值或一组值，它们在不同约束条件限制的集合内最大化问题所定义的利润。在下图中，沿着一条直线（线性关系）可以找到给

25、定某一结果的所有的解，这些产生一个值的结果集可以沿着一条直线找到，该直线平行于产生另一可选结果的结果集（即具有相同的斜率） 。这个过程不断地增大目标值，直到达到最大值。在电话生产问题中，只有一个最优解。一个线性规划的最优解总是在可行域的边界上。用OPL 为电话生产问题建模n基本的OPL 关键字nDvar（决策变量）nQuantifiernAggregator（聚集器）nSetoffnRangenTuplenArraynOPL 数据类型(见列表)nOPL 运算符(见列表)在OPL 中的LP 模型一个OPL 说明文件划分成3个独立部分：n数据结构和变量声明narrays，sets，tuples，f

26、loat，int，等n目标函数n由关键字maximize 或minimize 标识n声明约束条件n用关键字subject to或constraints来标识n关键字subject to和constraints是等价的、可互换的OPL 数据类型和决策变量类型nOPL 数据类型nint整型变量nfloat浮点型变量nstring字符串变量nOPL 决策变量类型ndvar int整数决策变量ndvar float浮点型决策变量OPL 使用的 4 种数据结构数据结构描述例子或setof数据集。为了定义数据集，指定的数据类型包含在大括号中。int myIntegerSet = 1，2，3;string

27、weekendDays =“Saturday”，”Sunday”;Range，range float范围定义。可以是整数型范围或浮点数范围。Range weeks = 1.52;Range float x=52或(数组)数组可以具有任意类型，包括 tuple 。一个数组范围可以由固定范围、整数范围或一个集合来定义，也支持多维数组。tupleTypemyEventsweekendDays weeks;Tuple允许用户自己定义数据类型的数据结构。它可用来创建可快速求解的模型。Tuple myEventsString name;String location; ;数据重复运算符在约

28、束条件和目标函数中的表达式和算术项，常常需要针对不同的数据重复计算多次。这些操作是相同的，不同的是它们的下标。OPL 提供了两种方式来处理这种情况：nForall 是通用quantifiern它允许用户通过一个下标进行迭代运算n为不同下标的每一个变量生成一个约束条件数据重复运算符n聚集器n为不同下标的每一个变量中的一个数学运算的应用产生一个总的结果。例如目标函数forall (p in products)maximize sum (p in Products) profitp * productionp;说明了聚集运算符sum 的用法，它用来对各个利润进行求和。OPL 中可用的聚集器nSum

29、计算相关表达式的和nProd 计算相关表达式的乘积nMin 计算最小值nMax 计算最大值一个quantifier 和聚集器一起使用的例子：forall (p in products)salesp = sum (l in locations) locSaleslp;在线性规划中使用的运算符运算符类型运算符描述浮点+，-，*，/通用数学运算符Inifinity表示无限（IEEE754）Abs(f)F 的绝对值Ceil(f)大于等于f 的最小的整数部分Floor(f)小于等于f 的最低整数部分Trunc(f)F 的整数部分Frac(f)F 的小数部分distToInt(f)F 距它最近的整数的距离Round(f)距f 最近的整数在线性规划中使用的运算符整型+，-，*，div通用数学运算符X mod y 或x%yX除以y 的整数余数Abs(x)X 的绝对值Maxint最大整数SetFirst，last集合中第一（最后）个元素Item集合中第n 个元素Card集合中元素的个数Ord(name)集合中name 的整数rankNext，prev集合中下一个（上一个）元素Nextc，prevc与上相同，但循环到结束在线性规划中使用的运算符SetA inter b交集A union b合并A diff b不同A symdiff b对称不同St