上海交通大学：《线性规划与非线性规划》教学资源_ILOG实验指导_运筹学实验指导书（2012-10）

实验编号 我持 实验指导书 实验项目： ILOG ODMS上机实验 所属课程： 线性规划与非线性规划 课程代码： 面向专业： 自动化系 学院（系）： 自动化系 2012年10月

实验编号 实 验 指 导 书 实验项目： ILOG ODMS 上机实验 所属课程: 线性规划与非线性规划 课程代码: 面向专业: 自动化系 学院(系): 自动化系 2012 年 10 月

一、实验目的 二、实验组成 .-3- 三、ILOG ODMS简介 -4- 1.ODMS (ILOG Optimization Decision Management System) -4 2.OPL (Optimization Programming Language) -5 3. ODM(ILOG Optimization Decision Manager).. -5- 四、上机实验一 -7- 使用OPL IDE求解生产计划问题. 7 1.实验目的… .-7- 2.生产计划问题 -7- 3. 生产问题的OPL模型 -7- 4. 实验内容及实验步骤 -11- 5. 实验要求 -11- 6.参考资料 -12- 五、上机实验二… .-13- 使用OPL IDE求解仓库选址问题. -13- 1.实验目的… -13- 2. 仓库选址问题 .-13- 3. 仓库选址问题的OPL模型. .-14- 4. 实验内容及实验步骤 .-17- 5.实验要求 .-17- 6.参考资料 -17- 六、上机实验三… -18- 使用OPL IDE求解交通运输问题 -18- 1.实验目的. -18- 2.交通运输问题及稀疏性 -18- 3. 实验内容及实验步骤 -22- 4. 实验要求 -22- 5.参考资料 -22- 七、上机实验四 -23- 使用ODM求解护士排班问题 -23- 1. 实验目的. -23- 2.ODM中用到的一些术语. -23- 3.护士排班问题 -24- 4. 护士排班问题OPL模型 .-24- 5. 实验内容及实验步骤 .-24- 6. 实验要求 25- 7. 其他参考资料 -25-

一、实验目的................................................................................................................................- 3 - 二、实验组成................................................................................................................................- 3 - 三、ILOG ODMS 简介.................................................................................................................- 4 - 1. ODMS（ILOG Optimization Decision Management System）..................................- 4 - 2. OPL（Optimization Programming Language）...........................................................- 5 - 3. ODM (ILOG Optimization Decision Manager)............................................................ - 5 - 四、上机实验一............................................................................................................................- 7 - 使用 OPL IDE 求解生产计划问题...............................................................................................- 7 - 1. 实验目的........................................................................................................................- 7 - 2. 生产计划问题................................................................................................................- 7 - 3. 生产问题的 OPL 模型.................................................................................................. - 7 - 4. 实验内容及实验步骤..................................................................................................- 11 - 5. 实验要求......................................................................................................................- 11 - 6. 参考资料......................................................................................................................- 12 - 五、上机实验二..........................................................................................................................- 13 - 使用 OPL IDE 求解仓库选址问题.............................................................................................- 13 - 1. 实验目的......................................................................................................................- 13 - 2. 仓库选址问题..............................................................................................................- 13 - 3. 仓库选址问题的 OPL 模型........................................................................................- 14 - 4. 实验内容及实验步骤..................................................................................................- 17 - 5. 实验要求......................................................................................................................- 17 - 6. 参考资料......................................................................................................................- 17 - 六、上机实验三..........................................................................................................................- 18 - 使用 OPL IDE 求解交通运输问题.............................................................................................- 18 - 1. 实验目的......................................................................................................................- 18 - 2. 交通运输问题及稀疏性..............................................................................................- 18 - 3. 实验内容及实验步骤..................................................................................................- 22 - 4. 实验要求......................................................................................................................- 22 - 5. 参考资料......................................................................................................................- 22 - 七、上机实验四..........................................................................................................................- 23 - 使用 ODM 求解护士排班问题.................................................................................................. - 23 - 1. 实验目的......................................................................................................................- 23 - 2. ODM 中用到的一些术语........................................................................................... - 23 - 3. 护士排班问题..............................................................................................................- 24 - 4. 护士排班问题 OPL 模型............................................................................................ - 24 - 5. 实验内容及实验步骤..................................................................................................- 24 - 6. 实验要求......................................................................................................................- 25 - 7. 其他参考资料..............................................................................................................- 25 -

一、实验目的 运筹学是一门应用科学，解决实际问题是运筹学研究的一个重要内容。 运筹学解决实际问题的工作步骤包括： 1.提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参 数，搜集有关资料 2.建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示 出来 3.求解。用各种手段（主要是数学方法，也可用其他方法）将模型求解。解可以是最 优解、次优解、满意解 4.解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题 5.解的控制。通过控制解的变化过程决定对解是否要作一定的改变 6. 解的实施。是指将解用到实际中必须考虑到实施的问题 以上过程应反复进行。 本实验不是教科书上内容的重复。本实验提供一个真实（或模拟真实）的应用环境，让 学生从实际用户的角度出发，通过4个实验，了解运筹学应用中的一些实际问题，达到如下 目的： 1.接触运筹学的一些有代表性的实际问题，及应用中会遇到的问题，从而了解运筹学 应用问题 2.熟悉应用运筹学解决实际问题的上述工作步骤，培养独立解决实际问题的能力 3.了解LOG ODMS软件的组成、用法、功能、特点，从而了解一般运筹学应用软件 应具有的功能等 4.通过LOG ODMS软件来求解几个实际问题，了解实际应用及计算的需求 5.通过这一组实验，能对运筹学应用软件的评估及设计能力的培养有所帮助 二、实验组成 本实验由四个上机实验组成： ●上机实验一使用OPL IDE求解生产计划问题 ● 上机实验二使用LOG IDE求解仓库选址问题 ● 上机实验三使用ILOG IDE求解交通运输问题 ● 上机实验四使用ILOG ODM求解护士排班问题 -3-

- 3 - 一、实验目的 运筹学是一门应用科学，解决实际问题是运筹学研究的一个重要内容。 运筹学解决实际问题的工作步骤包括： 1. 提出和形成问题。即要弄清问题的目标，可能的约束，问题的可控变量以及有关参 数，搜集有关资料 2. 建立模型。即把问题中可控变量、参数和目标与约束之间的关系用一定的模型表示 出来 3. 求解。用各种手段（主要是数学方法，也可用其他方法）将模型求解。解可以是最 优解、次优解、满意解 4. 解的检验。首先检查求解步骤和程序有无错误，然后检查解是否反映现实问题 5. 解的控制。通过控制解的变化过程决定对解是否要作一定的改变 6. 解的实施。是指将解用到实际中必须考虑到实施的问题 以上过程应反复进行。 本实验不是教科书上内容的重复。本实验提供一个真实（或模拟真实）的应用环境，让 学生从实际用户的角度出发，通过 4 个实验，了解运筹学应用中的一些实际问题，达到如下 目的： 1. 接触运筹学的一些有代表性的实际问题，及应用中会遇到的问题，从而了解运筹学 应用问题 2. 熟悉应用运筹学解决实际问题的上述工作步骤，培养独立解决实际问题的能力 3. 了解 ILOG ODMS 软件的组成、用法、功能、特点，从而了解一般运筹学应用软件 应具有的功能等 4. 通过 ILOG ODMS 软件来求解几个实际问题，了解实际应用及计算的需求 5. 通过这一组实验，能对运筹学应用软件的评估及设计能力的培养有所帮助 二、实验组成 本实验由四个上机实验组成：  上机实验一 使用 OPL IDE 求解生产计划问题  上机实验二 使用 ILOG IDE 求解仓库选址问题  上机实验三 使用 ILOG IDE 求解交通运输问题  上机实验四 使用 ILOG ODM 求解护士排班问题

三、ILOG ODMS简介 1.ODMS (ILOG Optimization Decision Management System) ILOG Optimization Decision Management System (ODMS)provides a complete set of tools for building custom optimization-based decision support applications.ILOG ODMS includes: ILOG CPLEX-A mathematical programming engine that solves the full range of LP and MIP problems encountered in the real world. ILOG CP Optimizer-A constraint programming-based optimizer. ILOG OPL Development Studio-A complete IDE for rapid development and deployment of optimization models. ILOG Optimization Decision Manager-A tool for developing interactive decision support applications with out-of-the-box "what-if"analysis,scenario comparisons and goal programming. Model Application Development Tools Development Tools ILOG OPL ILOG Optimization Development Studio Decision Manager Optimization Engines Math Programming Constraint Programming Engines(MP) Engines(CP) -ILOG CPLEX ILOG CP ILOG ODMS makes optimization more widely accessible than ever before,because it offers such a wide range of capabilities across several fundamental dimensions. Supporting many types of optimization applications:From off-line strategic planning applications through detailed scheduling to real-time operational applications. Supporting the complete model development and application life-cycle:Complete support for the application development process,from quick prototyping through model and application refinement, to application deployment and maintenance. Supporting multiple personas:OR and IT professionals,together with operations and business managers,can now collaborate in entirely new ways to rapidly generate custom decision-support applications. -4-

- 4 - 三、ILOG ODMS 简介 1. ODMS（ILOG Optimization Decision Management System） ILOG Optimization Decision Management System (ODMS) provides a complete set of tools for building custom optimization-based decision support applications. ILOG ODMS includes: ◆ ILOG CPLEX - A mathematical programming engine that solves the full range of LP and MIP problems encountered in the real world. ◆ ILOG CP Optimizer - A constraint programming-based optimizer. ◆ ILOG OPL Development Studio – A complete IDE for rapid development and deployment of optimization models. ◆ ILOG Optimization Decision Manager – A tool for developing interactive decision support applications with out-of-the-box “what-if” analysis, scenario comparisons and goal programming. ILOG ODMS makes optimization more widely accessible than ever before, because it offers such a wide range of capabilities across several fundamental dimensions. ◆ Supporting many types of optimization applications: From off-line strategic planning applications through detailed scheduling to real-time operational applications. ◆ Supporting the complete model development and application life-cycle: Complete support for the application development process, from quick prototyping through model and application refinement, to application deployment and maintenance. ◆ Supporting multiple personas: OR and IT professionals, together with operations and business managers, can now collaborate in entirely new ways to rapidly generate custom decision-support applications

2.OPL (Optimization Programming Language) Modeling languages were motivated by the desire to simplify the solving of mathematical programming problems.The fundamental insight underlying traditional modeling languages is the recognition that many mathematical programming problems can be expressed in a computer language whose syntax is close to the standard presentation of these problems in textbooks and scientific papers. These languages typically provide a number of data types such as arrays and sets,as well as computer-language equivalents to traditional algebraic notations. For instance,in AMPL,an expression such as can be written as sum (i in 1..n)a[i]x[i] In addition,some of these languages provide a clean separation between the model and the instance data. Finally,they are sometimes extended by a command language that makes it possible to solve sequences of related models and to make modifications to the models and solve the modified models.Traditional modeling languages have many benefits that make them appealing for stating and solving mathematical programming problems.Perhaps their most significant contribution is to provide a language that directly supports the natural statement of these problems.This language abstracts away the implementation details of the underlying solver and users are then relieved of mundane,low-level, considerations and can focus on the modeling of their applications.Also important is the clear separation between the model and the instance data,which ensures that the same model can be applied to many instances without inducing additional work.Note that,in these languages,the solver is a black box that can only be accessed through a set of well-defined parameters. Traditional modeling languages are particularly strong in mathematical programming applications,e.g, linear and integer programming.This is not surprising since this is the area from where they emerged. In addition,these problems are naturally expressed using traditional algebraic notations and effective solvers are available to solve the resulting models. 3.ODM(ILOG Optimization Decision Manager) ILOG Optimization Decision Manager(ODM)integrates ILOG OPL Development Studio,a modeling tool and development environment for OPL (Optimization Programming Language).ILOG ODM is both a tool for application development and a runtime environment,and the combined OPL and ODM products form a complete solution for the development and deployment of optimization-based planning and scheduling applications. -5-

- 5 - 2. OPL（Optimization Programming Language） Modeling languages were motivated by the desire to simplify the solving of mathematical programming problems. The fundamental insight underlying traditional modeling languages is the recognition that many mathematical programming problems can be expressed in a computer language whose syntax is close to the standard presentation of these problems in textbooks and scientific papers. These languages typically provide a number of data types such as arrays and sets, as well as computer-language equivalents to traditional algebraic notations. For instance, in AMPL, an expression such as 1n i i i a X  can be written as sum {i in 1..n} a[i] * x[i] In addition, some of these languages provide a clean separation between the model and the instance data. Finally, they are sometimes extended by a command language that makes it possible to solve sequences of related models and to make modifications to the models and solve the modified models. Traditional modeling languages have many benefits that make them appealing for stating and solving mathematical programming problems. Perhaps their most significant contribution is to provide a language that directly supports the natural statement of these problems. This language abstracts away the implementation details of the underlying solver and users are then relieved of mundane, low-level, considerations and can focus on the modeling of their applications. Also important is the clear separation between the model and the instance data, which ensures that the same model can be applied to many instances without inducing additional work. Note that, in these languages, the solver is a black box that can only be accessed through a set of well-defined parameters. Traditional modeling languages are particularly strong in mathematical programming applications, e.g., linear and integer programming. This is not surprising since this is the area from where they emerged. In addition, these problems are naturally expressed using traditional algebraic notations and effective solvers are available to solve the resulting models. 3. ODM (ILOG Optimization Decision Manager) ILOG Optimization Decision Manager (ODM) integrates ILOG OPL Development Studio, a modeling tool and development environment for OPL (Optimization Programming Language). ILOG ODM is both a tool for application development and a runtime environment, and the combined OPL and ODM products form a complete solution for the development and deployment of optimization-based planning and scheduling applications

Applications built with ILOG ODM allow users to adjust assumptions,operating constraints,and goals for planning and scheduling resources,and see the results in familiar business terminology,providing extensive what-if analysis and scenario comparison features"out of the box." In essence,you supply the mathematical model in OPL,and ODM supplies the GUI and interactivity with your model that makes it easy to use for operations managers and planners 参见 Overview of ILOG Optimization Decision Manager (overviewodm.pdf) -6-

- 6 - Applications built with ILOG ODM allow users to adjust assumptions, operating constraints, and goals for planning and scheduling resources, and see the results in familiar business terminology, providing extensive what-if analysis and scenario comparison features “out of the box.” In essence, you supply the mathematical model in OPL, and ODM supplies the GUI and interactivity with your model that makes it easy to use for operations managers and planners. 参见 Overview of ILOG Optimization Decision Manager（overviewodm.pdf）

四、上机实验一 使用OPL IDE求解生产计划问题 1)实验目的 1)熟悉生产问题 2) 了解OPL(ILOG Optimization Programming Language),及其特点 3)了解OPL IDE求解规划问题的整个过程，了解OPL IDE的特点 4)了解求解规划问题的计算需求 2)生产计划问题 The production-planning problem is as follows. To meet the demands of its customers,a company manufactures its products in its own factories(inside production)or buys them from other companies(outside production).Inside production is subject to some resource constraints:each product consumes a certain amount of each resource.In contrast, outside production is theoretically unlimited.Each product can be produced either inside the company or outside.at a higher cost. The problem is to determine how much of each product should be produced inside and outside the company while minimizing the overall production cost,meeting the demand,and satisfying the resource constraints. The variables for this problem are the inside and outside production for each product. An instance of the problem must specify the products,the resources,the capacity of the resources,the demand for each product,the consumption of resources by the different products,and the inside and outside costs of each product. 3)生产问题的OPL模型 1)The Model for the Production-Planning Problem The model for the production-planning problem is depicted in Code Sample 4.I below and the instance data in Code Sample 4.2. -7-

- 7 - 四、上机实验一 使用 OPL IDE 求解生产计划问题 1) 实验目的 1) 熟悉生产问题 2) 了解OPL（ILOG Optimization Programming Language），及其特点 3) 了解 OPL IDE 求解规划问题的整个过程，了解 OPL IDE 的特点 4) 了解求解规划问题的计算需求 2) 生产计划问题 The production-planning problem is as follows. To meet the demands of its customers, a company manufactures its products in its own factories (inside production) or buys them from other companies (outside production). Inside production is subject to some resource constraints: each product consumes a certain amount of each resource. In contrast, outside production is theoretically unlimited. Each product can be produced either inside the company or outside, at a higher cost. The problem is to determine how much of each product should be produced inside and outside the company while minimizing the overall production cost, meeting the demand, and satisfying the resource constraints. The variables for this problem are the inside and outside production for each product. An instance of the problem must specify the products, the resources, the capacity of the resources, the demand for each product, the consumption of resources by the different products, and the inside and outside costs of each product. 3) 生产问题的 OPL 模型 1) The Model for the Production-Planning Problem The model for the production-planning problem is depicted in Code Sample 4. 1 below and the instance data in Code Sample 4. 2

(string)Products =... (string)Resources =...i tuple productData float demand; float insideCost; float outsideCost; float consumption[Resources]; productData Product[Products]=... float Capacity[Resources】=·..; dvar float+Inside[Products]; dvar float+Outside[Products]; execute CPX PARAM cplex.preind =0; cplex.simdisplay 2; minimize sum(p in Products (Product[p】.insideCost Inside[p】+ Product[p】.outsideCost*Outside[p】): subject to forall(r in Resources ctInside: sum(p in Products Product[p】.consumption[r】★Inside【p】=Product[p].demand; Code Sample 4.I The Production-Planning Problem (product.mod) Products ="kluski","capellini","fettucine"} Resources ="flour","eggs") Product =# k1uski:, cape11ini:, -8-

- 8 - {string} Products = ...; {string} Resources = ...; tuple productData { float demand; float insideCost; float outsideCost; float consumption[Resources]; } productData Product[Products] = ...; float Capacity[Resources] = ...; dvar float+ Inside[Products]; dvar float+ Outside[Products]; execute CPX_PARAM { cplex.preind = 0; cplex.simdisplay = 2; } minimize sum( p in Products ) (Product[p].insideCost * Inside[p] + Product[p].outsideCost * Outside[p] ); subject to { forall( r in Resources ) ctInside: sum( p in Products ) Product[p].consumption[r] * Inside[p] = Product[p].demand; } Code Sample 4. 1 The Production-Planning Problem (product.mod) Products = { “kluski”, “capellini”, “fettucine” }; Resources = { “flour”, “eggs” }; Product = #[ kluski : , capellini :

fettucine: 】#: Capacity=【20,40】; Code Sample 4.2 Instance Data for the Production-Planning Problem (product.dat) The instruction tuple productData float demand; float insideCost; float outsideCost; float consumption【Resources】: declares a tuple type with four fields.The first three fields,of type float,are used to represent the demand and costs of a product;the last field is an array representing the resource consumptions of the product.These fields are intended to hold all the data related to a given product. The instruction ProductData product[Products]=... declares an array of these tuples,one for each product.Data structures in OPL can be constructed using tuples that cluster together closely related data. The...(ellipsis)syntax means that the data is initialized externally,that is,from a data file (product.dat). The initialization Product =# k1uski:, cape11ini:, fettucine: ]#: from Code Sample 4.2 specifies these various data items:tuples are initialized by giving values for each of their fields.It is of course possible to use a named initialization for the tuple,as shown in Code Sample 4.2,in which case the initialization is enclosed with #and >#Tuple fields can be obtained by suffixing the tuple with a dot and the field name.For instance,in the objective function minimize -9

- 9 - fettucine : ]#; Capacity = [ 20, 40 ]; Code Sample 4.2 Instance Data for the Production-Planning Problem (product.dat) The instruction tuple productData { float demand; float insideCost; float outsideCost; float consumption[Resources]; } declares a tuple type with four fields. The first three fields, of type float, are used to represent the demand and costs of a product; the last field is an array representing the resource consumptions of the product. These fields are intended to hold all the data related to a given product. The instruction ProductData product[Products] = ...; declares an array of these tuples, one for each product. Data structures in OPL can be constructed using tuples that cluster together closely related data. The ... (ellipsis) syntax means that the data is initialized externally, that is, from a data file (product.dat). The initialization Product = #[ kluski : , capellini : , fettucine : ]#; from Code Sample 4.2 specifies these various data items: tuples are initialized by giving values for each of their fields. It is of course possible to use a named initialization for the tuple, as shown in Code Sample 4.2, in which case the initialization is enclosed with ##. Tuple fields can be obtained by suffixing the tuple with a dot and the field name. For instance, in the objective function minimize

sum(p in Products (Product[p】.insideCost Inside[p】+ Product[p】.outsideCost*Outside[p】); the expression product [p].insidecost represents the field insidecost of the tuple product [p]. Similarly,in the constraint forall(r in Resources) sum(p in Products)product[p】.consumption【r】inside[p】I p in Products } excute{writeln("Result=",Result); you will see the following output.: Optimal solution found with objective:372 resu1t={} If you add the following ILOG Script postprocessing lines to the product.mod file -10-

- 10 - sum( p in Products ) (Product[p].insideCost * Inside[p] + Product[p].outsideCost * Outside[p] ); the expression product[p].insideCost represents the field insideCost of the tuple product[p]. Similarly, in the constraint forall(r in Resources) sum(p in Products) product[p].consumption[r] * inside[p] | p in Products }; excute{ writeln("Result=",Result); } you will see the following output.: Optimal solution found with objective: 372 result= { } If you add the following ILOG Script postprocessing lines to the product.mod file