《模型与软件5结构化构模方法》由会员分享，可在线阅读，更多相关《模型与软件5结构化构模方法（36页珍藏版）》请在金锄头文库上搜索。
1、优化模型与软件工具结构化构模方法清华大学经济管理学院清华大学经济管理学院管理科学与工程系管理科学与工程系1结构化构模方法结构化构模方法w模型构造方法的演进模型构造方法的演进w模型构造方法：问题与机会模型构造方法：问题与机会w结构化构模方法结构化构模方法2模型构造方法的演进模型构造方法的演进3模型构造方法的进步模型构造方法的进步w50年代：计算机刚刚发明，模型构造方法十分原年代：计算机刚刚发明，模型构造方法十分原始，只有底层语言可供使用；始，只有底层语言可供使用；w6070年代：计算机软件有了很大进步，出现了年代：计算机软件有了很大进步，出现了商业化的数学规划软件，以及简单的数学描述语商业化的数
2、学规划软件，以及简单的数学描述语言言;w80年代：模型构造方法有了新的突破，结构化构年代：模型构造方法有了新的突破，结构化构模方法，出现较高级的模型语言；模方法，出现较高级的模型语言；w90年代以后：模型方法与年代以后：模型方法与IT技术结合，出现集成技术结合，出现集成化的模型应用环境；化的模型应用环境；4传统模型构造方法传统模型构造方法w模型描述方法简单模型描述方法简单max: 2x11 + 9x13-x21+2.5x22+6x23-2x31+5x33 s.t. - 4 x11 + 15x21 + 25x31 0 -14x12 + 5x22 + 15x32 0 -24x13 - 5x23 +
3、 5x33 0 0.1x11 - 0.5x21 - 0.9x31 0w数据与模型统一描述；数据与模型统一描述；w模型交流、修改十分困难；模型交流、修改十分困难；5模型描述的工业标准：模型描述的工业标准：MPS格式格式w更有效地描述稀疏矩阵（只描述非零元素），为模更有效地描述稀疏矩阵（只描述非零元素），为模型的计算机化打下基础；型的计算机化打下基础；w按模型名、约束名按模型名、约束名(Rows)、变量名、变量名(Columns)、右边、右边项项(Rhs)、变量界、变量界(Bounds)的顺序描述；的顺序描述；wRows：8个字符构成约束名，约束类型分为个字符构成约束名，约束类型分为N非约束；非约
4、束；G大于等于约束；大于等于约束；L 小于等于约小于等于约束；束；E等于约束；等于约束；wColumns：只描述模型中的非零元素；分别由行名、：只描述模型中的非零元素；分别由行名、列名和数值确定约束矩阵中的一个元素；列名和数值确定约束矩阵中的一个元素；wBounds：分为：分为：LO下界；下界；UP上界；上界；FX固定固定界；界；FR自由变量自由变量6MPS格式格式name MISC01rows N OBJ E ROW001 G ROW003 . . . L ROW054 columns COL001 ROW002 1. ROW006 50. COL001 ROW039 1. ROW041 1
5、. . . . . . . COL083 OBJ 1. ROW001 1. rhs RHS ROW002 1. ROW003 1. . . . . . . RHS ROW054 1. bounds lo BND COL001 1. fx BND COL001 1. . . . . . . fr BND COL083 endata7模型计算机化的初级阶段模型计算机化的初级阶段w矩阵生成（矩阵生成（MG）与报告生成（）与报告生成（RG）软件；）软件；w模型与数据分离；模型与数据分离；w还不能与数据库接口；还不能与数据库接口；MGRG数据文件最终用户报告数学规数学规划软件划软件MPS文件文件模型文件
6、输出文件8集成化模型系统集成化模型系统w提供模型描述、数据处理、模型求解等完整功能；提供模型描述、数据处理、模型求解等完整功能；w提供丰富的求解软件；提供丰富的求解软件；w提供可调用函数库，提供数据库接口；提供可调用函数库，提供数据库接口；集成化模型系统数学规数学规划软件划软件模型编译模型文件模型生成模型求解用户报告数据文件用户界面数据库9集成化的模型应用环境集成化的模型应用环境w电子表格优化系统电子表格优化系统免费学习软件，适于初学者使用；免费学习软件，适于初学者使用；适于构造中小规模的模型；适于构造中小规模的模型； EXCEL；w专用模型集成软件专用模型集成软件提供数据处理模型描述，求解等
7、完整功能提供数据处理模型描述，求解等完整功能;提供丰富的求解软件：提供丰富的求解软件：CPLEX, OSL, MINOS等等 提供可调用函数库，提供数据库接口；提供可调用函数库，提供数据库接口；GAMS, AMPL, ILOG, MPL等；等；10模型构造方法：问题与机会模型构造方法：问题与机会w问题之一：模型构造的低效率问题之一：模型构造的低效率模型构造需要的三种描述缺乏一致性工具模型构造需要的三种描述缺乏一致性工具自然描述：与模型使用者和管理者的交流与沟通；自然描述：与模型使用者和管理者的交流与沟通；数学描述：用于模型的理论与逻辑分析；数学描述：用于模型的理论与逻辑分析；实现描述：使用何种
8、工具、如何进行计算；实现描述：使用何种工具、如何进行计算；目前的方法存在很多冗余、不一致，需掌握多种技巧；目前的方法存在很多冗余、不一致，需掌握多种技巧；模型与计算机接口问题：没有统一接口，唯一的工模型与计算机接口问题：没有统一接口，唯一的工业标准业标准MPS格式太陈旧；格式太陈旧；大部分模型语言只支持有限的模型、只能支持模型大部分模型语言只支持有限的模型、只能支持模型构造生命周期的几个阶段；构造生命周期的几个阶段；11模型构造方法：问题与机会模型构造方法：问题与机会w问题二：管理者接受模型方法培训的可能性低问题二：管理者接受模型方法培训的可能性低模型描述过于复杂，非专业人员无法理解；模型描述
9、过于复杂，非专业人员无法理解；专业人士专业人士“以技术为中心以技术为中心”而不是而不是“以问题为中以问题为中心心”的方法引发的沟通问题；的方法引发的沟通问题；模型使用也过分依赖专业人员，管理者很难独立模型使用也过分依赖专业人员，管理者很难独立使用模型导致的排斥；使用模型导致的排斥；12模型构造方法：问题与机会模型构造方法：问题与机会w机会一：信息技术的进步带来计算机应用普及，很机会一：信息技术的进步带来计算机应用普及，很多原来不可能的事现在变为可能；多原来不可能的事现在变为可能；w机会二：与模型相关的其他技术的进步机会二：与模型相关的其他技术的进步模型构造技术：模型构造技术：电子表格模型的普及
10、；电子表格模型的普及；多种构模语言的出现：多种构模语言的出现：GAMS、AMPL等；等；概念模型与结构化构模方法的出现：概念模型与结构化构模方法的出现：SML信息化技术信息化技术数据库技术；数据库技术；面向对象的方法；面向对象的方法；软件工程的方法；软件工程的方法；人工智能、知识表达方法；人工智能、知识表达方法；13新一代模型系统应具备的特征新一代模型系统应具备的特征w统一性：将模型的自然表述、数学表述和计算机执统一性：将模型的自然表述、数学表述和计算机执行表述统一的模型架构体系；行表述统一的模型架构体系；w独立性：模型描述独立于求解工具，但可以对模型独立性：模型描述独立于求解工具，但可以对模
11、型组件、模型库进行灵活的管理和使用；组件、模型库进行灵活的管理和使用；w通用性：适用于各种模型的表述通用性：适用于各种模型的表述w完整性：可以支持模型构造的全生命周期；完整性：可以支持模型构造的全生命周期；w分离性：模型与数据的分离，即通用模型结构与描分离性：模型与数据的分离，即通用模型结构与描述具体模型的数据相分离；述具体模型的数据相分离；w界面友好性：模型的可视化、图表化和交互化；界面友好性：模型的可视化、图表化和交互化；w支持对数据库的访问；支持对数据库的访问；14结构化构模方法结构化构模方法w美国加州大学洛衫矶分校（美国加州大学洛衫矶分校（UCLA）的）的Geoffrion教教授于授于
12、1987年首先提出；年首先提出；An Introduction to Structured Modeling, Mang. Sci. 1987, Vol. 33, No. 5The Formal Aspects of Structured Modeling, Oper. Res. 1989, Vol. 37, No. 1The SML Language for Structured Modeling: Oper. Res. 1992, Vol. 40, No.1；15结构化构模方法结构化构模方法w结构化构模方法提供基于计算机的模型构造环境，目结构化构模方法提供基于计算机的模型构造环境，目的是：
13、的是：适用于模型构造的全生命周期，而不是个别阶段；适用于模型构造的全生命周期，而不是个别阶段；不仅有助于模型构造者，也有助于模型使用者（决策不仅有助于模型构造者，也有助于模型使用者（决策和政策制定者）；和政策制定者）；减少模型升级、维护的成本；减少模型升级、维护的成本；使用独立于具体计算机语言的模型描述语言；使用独立于具体计算机语言的模型描述语言；提供对资源（数据、模型、求解器等）的有效管理；提供对资源（数据、模型、求解器等）的有效管理；16结构化构模方法的挑战结构化构模方法的挑战w主要挑战：主要挑战：设计能够设计能够描述概念模型描述概念模型的架构；的架构；设计支持该架构的设计支持该架构的可执
14、行的模型构造语言可执行的模型构造语言；设计设计软件集成方法软件集成方法，w特点特点正规性（定义严格）正规性（定义严格）易理解性（与自然语言近似）易理解性（与自然语言近似）适用性（与数学模型方法、数据库管理、人工智适用性（与数学模型方法、数据库管理、人工智能表达的兼容性）能表达的兼容性）17模型定义系统模型定义系统w模型构造是给出某些事物部分知识的模型构造是给出某些事物部分知识的严格定义严格定义过程过程w一个一个“个别定义个别定义”被称为模型元素；被称为模型元素；w定义系统的特性：定义系统的特性：相关性：定义之间存在程度不同的相关性；相关性：定义之间存在程度不同的相关性；非循环性：相关性不能有闭
15、环（闭环将导致定义非循环性：相关性不能有闭环（闭环将导致定义的多义性）；的多义性）；分类性：定义可以按其性质分入不同类别；分类性：定义可以按其性质分入不同类别；聚合性：相似的定义可以聚合在一起；聚合性：相似的定义可以聚合在一起；层级性：聚合是按层级进行的。层级性：聚合是按层级进行的。18结构化构模的基本结构结构化构模的基本结构w要素结构（要素结构（elemental structure）w通用结构（通用结构（generic structure）w模块结构（模块结构（modular structure）w模型实例（模型实例（model instances）w模型类别（模型类别（model cla
16、sses）19要素结构要素结构w模型是由一些离散的要素组成，要素反映构成模型模型是由一些离散的要素组成，要素反映构成模型的基本事物、概念和它们的特征，的基本事物、概念和它们的特征，w每个要素要有严格定义，每个要素要有严格定义， 并以某种关系联系在一起，并以某种关系联系在一起，如集合关系、属性关系等。如集合关系、属性关系等。w要素既可以是原始（要素既可以是原始（primitive）要素也可以是已存在）要素也可以是已存在要素的组合；要素的组合；w要素可以按其特征和属性组织在具有层级结构的要要素可以按其特征和属性组织在具有层级结构的要素类（集合）中。素类（集合）中。w在结构化构模方法中，重要的模型构
17、造要素分为实在结构化构模方法中，重要的模型构造要素分为实体要素、属性要素和关系要素（函数、检验）。体要素、属性要素和关系要素（函数、检验）。 20Geoffrion定义的五类要素定义的五类要素w原始实体（原始实体（primitive entity）非数值型）非数值型代表构成模型的基本事物或概念代表构成模型的基本事物或概念；w复合实体（复合实体（compound entity）非数值型）非数值型利用其他实体定义的实体；利用其他实体定义的实体；w属性（属性（attribute）数值型）数值型代表事物或概念的某种数值特征；代表事物或概念的某种数值特征；w函数（函数（function）数值型）数值型根
18、据某种规则，利用某些实体属性计算的数值根据某种规则，利用某些实体属性计算的数值w检验（检验（test）逻辑型）逻辑型与函数类似，只是值只用与函数类似，只是值只用“真真”、“假假”表示；表示；21实体要素实体要素w代表构成模型的基本事物或概念，实体还可以分为代表构成模型的基本事物或概念，实体还可以分为原始实体和复合实体，复合实体是由原始实体组成原始实体和复合实体，复合实体是由原始实体组成的。的。例如在运输模型中，可定义供应点和需求点为两个例如在运输模型中，可定义供应点和需求点为两个原始实体；原始实体；连接供应点和需求点的运输线路则是复合实体。连接供应点和需求点的运输线路则是复合实体。在制造企业模
19、型中找出通用的实体要素，如：物料、在制造企业模型中找出通用的实体要素，如：物料、工艺、设备、工作中心、物料清单（工艺、设备、工作中心、物料清单（BOM）、工艺）、工艺路线、工单等。路线、工单等。w实体要素是模型的基本构件，模型的变量、约束都实体要素是模型的基本构件，模型的变量、约束都与实体要素相关。与实体要素相关。22属性要素属性要素w代表实体要素的某种数值特征，实体要素和属性要代表实体要素的某种数值特征，实体要素和属性要素的组合构成了对模型的完整描述。数据库中的记素的组合构成了对模型的完整描述。数据库中的记录都是由实体要素和属性要素组成的。录都是由实体要素和属性要素组成的。物料：物料是生产中
20、涉及的实体对象，其基本属物料：物料是生产中涉及的实体对象，其基本属性包括：物料编号、生产提前期、采购成本（或性包括：物料编号、生产提前期、采购成本（或销售价格）、库存成本、库存量、安全库存等。销售价格）、库存成本、库存量、安全库存等。工艺：工艺是利用生产工具对物料进行加工处理工艺：工艺是利用生产工具对物料进行加工处理的过程，其基本属性包括：工艺编号、工艺类型、的过程，其基本属性包括：工艺编号、工艺类型、工艺成本、工艺能力单位、替代工艺等。工艺成本、工艺能力单位、替代工艺等。 23关系要素关系要素w根据某种规则，建立某些实体要素属性之间的计量根据某种规则，建立某些实体要素属性之间的计量关系，主要
21、表现为数学函数关系和逻辑关系。关系，主要表现为数学函数关系和逻辑关系。w如何用简洁、通用的数学函数关系描述系统错综复如何用简洁、通用的数学函数关系描述系统错综复杂的关系是模型描述的难点，因此需要抓住一些共杂的关系是模型描述的难点，因此需要抓住一些共性的关系进行模型抽象。性的关系进行模型抽象。w例如计算企业销售收入，描述应是：例如计算企业销售收入，描述应是：销售收入销售收入 （销售产品数量（销售产品数量销售价格）。销售价格）。这一逻辑并不涉及具体产品和销售价格，任何企业都这一逻辑并不涉及具体产品和销售价格，任何企业都可以使用，因此是通用公式。可以使用，因此是通用公式。当需要生成具体模型时，模型生
22、成软件才会从企业数当需要生成具体模型时，模型生成软件才会从企业数据库中提取相关数据，并做出具体计算。据库中提取相关数据，并做出具体计算。 24通用结构（通用结构（generic structure）w通用结构将类似的元素集合在一起，使得模型可以通用结构将类似的元素集合在一起，使得模型可以集成化描述；集成化描述；w类似集合的概念，元素组合在集合中，集合还可以类似集合的概念，元素组合在集合中，集合还可以有不同的子集和分层的结构；有不同的子集和分层的结构；类（类（class），属（），属（genera），种（），种（genus）数学描述中的下标表述的某种分类数学描述中的下标表述的某种分类25模块结构
23、（模块结构（modular structure）w模块化结构用于概念模型的分层构建，模块化结构用于概念模型的分层构建，w当构模元素被组织在各种类、属中，再将这些类、当构模元素被组织在各种类、属中，再将这些类、属归集在概念单元（模块）中，这些概念单元还可属归集在概念单元（模块）中，这些概念单元还可以归集在高层级的概念单元（模块）中以归集在高层级的概念单元（模块）中，最后形，最后形成位于根节点的目标模型；成位于根节点的目标模型；w例如描述企业物流的供应链单元方法；例如描述企业物流的供应链单元方法；26模型实例（模型实例（model instances）w模型的逻辑结构由模型语言描述，该逻辑结构在特
24、模型的逻辑结构由模型语言描述，该逻辑结构在特定数据支持下构造出具体模型，每一个实现的具体定数据支持下构造出具体模型，每一个实现的具体模型称为模型实例；模型称为模型实例；w利用数据与模型分离的方法，可以构造出数据驱动利用数据与模型分离的方法，可以构造出数据驱动的模型，一个通用模型可以对应一系列模型实例；的模型，一个通用模型可以对应一系列模型实例；27模型类别（模型类别（model classes）w一些类似的模型可以归结为模型类别；一些类似的模型可以归结为模型类别；在模型研究中，注意力更集中在模型的通用结构，在模型研究中，注意力更集中在模型的通用结构，而不是具体数据；而不是具体数据；利用一个通用
25、模型类别的逻辑结构，通过更换数利用一个通用模型类别的逻辑结构，通过更换数据可以形成很多具体的类似的应用模型，例如石据可以形成很多具体的类似的应用模型，例如石油化工模型、水电优化模型、能源模型等；油化工模型、水电优化模型、能源模型等；28运输模型举例运输模型举例29运输模型举例运输模型举例303132运输模型举例运输模型举例33GAMS 模型模型SETS I plants / DAL, CHI / J customer / PITT, ATL, CLEV / ;PARAMETERS SUP(I) supply capacity of plant i / DAL 20000 CHI 42000 /
26、 DEM(J) demand at customer j / PITT 25000 ATL 15000 CLEV 22000 / ;TABLE C(I, J) transportation cost PITTS ATL CLEV DAL 23.5 17.75 32.45 CHI 7.65 25.75 34VARIABLES X(I, J) shipment quantities Z total transportation costs; POSITIVE VARIABLE X ;EQUATIONS COST define objective function SUPPLY (I) supply
27、 limit at plant i DEMAND (J) demand at customer j ; COST . Z =E= SUM(I, J), C(I, J)*X(I, J) ; SUPPLY(I) . SUM(J, X(I, J) =L= SUP(I) ; DEMAND(J) . SUM(I, X(I, J) =G= DEM(J) ;GAMS 模型模型35一个一个ILOG模型片段模型片段w物料平衡约束的自然语言描述：物料平衡约束的自然语言描述：所有的物料、在所有生产周期要满足：所有的物料、在所有生产周期要满足：制造数量制造数量 + 采购数量销售数量采购数量销售数量 + 期初库存量期初库存量期末库存量中间投入量期末库存量中间投入量 0w物料平衡约束的数学描述：物料平衡约束的数学描述：w物料平衡约束的计算机编程描述：物料平衡约束的计算机编程描述：Forall (i in M, t in T) xi,t + yi,t + Ii,t-1 - Ii,t - sum(j in I) BOMi,j*xj,t = 0 i M, t T 36
