数学规划中的分解技术详解：工程与科学应用

5星 · 超过95%的资源需积分: 12 69 浏览量更新于2024-08-01 1 收藏 2.93MB PDF 举报

"《数学规划中的分解技术》是一本专为学生和从业者编写的实用教材，旨在介绍优化中的分解技术。该书将理论背景与工程、科学领域的实际应用紧密结合，使其对实践者具有吸引力，同时也适合工程、运筹学和应用经济学的研究生及博士生学习。作者Antonio J. Conejo、Enrique Castillo、Roberto Mínguez和Raquel García-Bertrand四位专家分别来自西班牙卡斯蒂利亚-拉曼恰大学，他们在书中通过清晰、有说服力的示例和计算，涵盖了线性规划、混合整数线性规划、非线性规划和混合整数非线性规划等多个领域。书中的内容深入浅出，不仅提供了严谨的分解算法，还包括启发式方法，使得读者能够掌握实际应用并发展到可以直接使用的工作算法。对于理论背景，书本内容足够深入，对应用数学家也颇具价值。每一章末尾附有习题，而偶数章节的习题解答被编入了附录，方便读者自我检验和学习。本书的实用性使其成为数学规划教学和研究的重要参考资料，无论是对于寻求解决复杂工程问题的学生，还是在工业工程、交通工程或经济模型中寻求高效解决方案的从业者，都能从中受益匪浅。此外，图书馆编目号（Library of Congress Control Number: 2005934995）和ISBN-10/13号表明这是一本由Springer出版社发行的全球范围内的专业出版物，版权受法律保护。"

4 1 Motivating Examples

because its solution is just the given unique feasible decision. The feasibil-

ity region is formally deﬁned through equality and inequality conditions that

are denominated the constraints of the problem. Each one of these conditions

is mathematically expressed through one real-valued function of the decision

variables. This function is equal to zero, greater than or equal to zero, lower

than or equal to zero.

Therefore a mathematical programming problem, representing and opti-

mization decision framework, presents the formal structure below:

minimize objective function

subject to constraints

Depending upon the type of variables and the mathematical nature of the

objective function and the functions used for the constraints, mathematical

programming problems are classiﬁed in diﬀerent manners. If the variables

involved are continuous and both the objective function and the constraints

are linear, the problem is denominated “linear programming problem.” If any

of the variables involved is integer or binary, while the constraints and the

objective function are both linear, the problem is denominated “mixed-integer

linear programming problem.”

Analogously, if the objective function or any constraint is nonlinear and all

variables are continuous, the problem is denominated “nonlinear programming

problem.” If additionally, any variable is integer, the corresponding problem

is denominated “mixed-integer nonlinear programming problem.”

Generally speaking, linear programming problems are routinely solved

even if they involve hundred of thousands of variables and constraints. Nonlin-

ear programming problems are easily solved provided that they meet certain

regularity conditions related to the mathematical concept of convexity, which

is considered throughout the following chapters of this book. Mixed-integer

linear programming problems are routinely solved provided that the number

of integer variables is suﬃciently small, typically below one thousand. Mixed-

integer nonlinear programming problems are generally hard to solve and can

be numerically intractable, because: (a) a high number of integer variables,

and (b) the ugly mathematical properties of the functions involved. These

problems require an in-depth speciﬁc analysis before a solution procedure is

tried.

From an engineering point of view, operation problems involving engi-

neering systems are normally continuous problems, either linear or nonlin-

ear. However, design and capacity expansion planning problems are generally

mixed-integer linear or nonlinear problems. The reason is that some design or

planning variables are of integer nature while most operation variables are of

continuous nature.

This book considers particular cases of all these optimization problems.

These cases have structural properties that can be advantageously compu-

tationally exploited. These structural properties are brieﬂy illustrated and

described below.

1.1 Motivation 5

Many real-world systems present certain decentralized structures. For in-

stance, the highway network of two neighboring countries is in some cases

highly dense in the interior of each country but rather lightly connected at

the border boundary. The same fact is encountered, for instance, in telecom-

munication and electric energy systems.

On the other hand, investment decision of real-world systems are typically

of integer nature while subsequent operation decisions are continuous. For

instance, investment decisions to improve the water supply system of a city

are integer because a particular facility exist or does not exist, and a facility is

built instead of other possible alternatives. However, the operation decisions

of the already built water supply system are continuous, e.g., pressure values

to be assigned at pumping stations.

The operation problem of the highway network of the two neighboring

countries naturally decomposes by country provided that we take care of the

constraints related to the interconnections. Note, however, that the operation

solution obtained solving both national problems independently is not the

best combined solution and it might be even infeasible due to the lack of con-

sideration of the border constraints. In this book, techniques to properly take

into account border constraints while solving the problem in a decomposed

manner are described.

Note that the reason to address this transnational problem in a decen-

tralized manner is not necessarily numerical, but political; as decentralized

solutions are more acceptable from a social viewpoint.

Therefore a mathematical programming problem associated with the op-

timization model above presents the following formal structure:

maximize objective

+ objective

subject to constraints

constraints

common constraints common constraints

where the block of constraints “constraints

” is related to the ﬁrst terms of

the objective function “objective

” and corresponds to the ﬁrst country; while

the second block of constraints “constraints

” is related to the second part

of the objective function “objective

” and is related to the second country.

However, the block of common constraints aﬀects both countries (they are

border constraints) and complicates the solution of the problem because it

prevents the sub-problems associated with the two countries to be solved sep-

arately. Because of the above considerations, the common constraints are de-

nominated complicating constraints.

Finally, note that it would have been possible to consider any number of

countries with diﬀerent border structures instead of just two.

6 1 Motivating Examples

The capacity expansion problem of a water supply system involves integer

investment decision and continuous operating decisions. It is convenient to

process these two sets of decisions separately, due to their diﬀerent nature

(integer versus continuous).

A mathematical programming problem associated with this model presents

the formal structure below:

maximize objective

+ objective

subject to constraints

& constraints

(compl. variables)

constraints

& constraints

(compl. variables)

where the common part of both blocks of constraints is related to investment

(integer) decisions while the noncommon parts are related to the operations

(continuous) decisions. In this book, techniques to take into account sepa-

rately integer and continuous decisions while achieving a solution of the whole

problem are described. Treating integer variables is much more complicated

than treating continuous variables, and this is why problems including such

variables are denominated problems with complicating variables.

Additionally, note that once the integer decisions have been made, the

resulting sub-problem decomposes by blocks, which may clearly facilitate its

solution.

In dealing with nonlinear programming problems throughout this book,

we assume that these problems are convex. This is a requirement for most de-

composition algorithm to work. Although convexity is a strong mathematical

assumption, assuming convexity is not necessarily restrictive from a practical

viewpoint, as many engineering and science problems are convex in the region

where the solutions of interest are located, i.e., where solution are meaningful

from an engineering or science point of view.

Nowadays, people do not become totally satisﬁed when getting the solu-

tions to their problems; in addition, a sensitivity analysis is asked for. Sensitiv-

ity refers to how sensitive are the solutions of a problem to the assumptions

and data. A high sensitivity warns the designer about the possible conse-

quences that can follow if the assumptions or data used are far from reality

and directs him/her to the right action to prevent disastrous consequences.

In this book the problem of sensitivity analysis is analyzed in detail and

several procedures are presented to derive the sensitivities of optimization

problems. In particular, we study the sensitivities of the objective function

and constraints, and the sensitivities of the primal and dual variables to data.

There is a close connection between decomposition and sensitivity, as it

is shown in several examples used in this book. Decomposition permits the

easy obtention of some sensitivities that are diﬃcult to obtain from the initial

problem.

Within the framework above, the objectives pursued in this book are the

following:

1.2 Introduction 7

1. To motivate the interest of decomposition techniques in optimization using

a rich spectrum of real-world engineering examples.

2. To describe decomposition techniques related to linear and nonlinear prob-

lems that include both continuous and integer variables. These problems

must present appropriate structures.

3. To illustrate these decomposition techniques with relevant engineering

problems of clear practical interest.

4. To provide practical algorithms that work and can be readily used by

students and practitioners.

5. To introduce the reader to the problem of sensitivity analysis and provide

tools and techniques to derive the sensitivities once the optimal solution of

an optimization problem is already available.

We believe that no such a book is currently available, although it is much

needed for both engineering and economics graduate students and practition-

ers.

The organization of this book is as follows:

1. Chapter 1 provides a collection of motivating examples that illustrates

how optimization problems with decomposable structure are common in

the real-world.

2. Chapter 2 addresses solution procedures for linear programming problems

with complicating constraints.

3. Completing the analysis of linear programming problems, Chap. 3 considers

solution techniques for linear programming problems with complicating

variables.

4. Chapter 4 reviews and summarizes duality theory, a requirement to develop

the decomposition techniques for nonlinear problems and the sensitivity

analysis presented in the following chapters.

5. Chapter 5 describes decomposition techniques appropriate for nonlinear

programming (continuous) problems.

6. Chapter 6 presents decomposition procedures relevant for mixed-integer

linear and nonlinear problems.

7. Chapter 7 considers speciﬁc decomposition techniques not analyzed in the

previous chapters.

8. Chapter 8 provides a comprehensive treatment of sensitivity analysis for

both decomposable and nondecomposable problems.

9. Finally, Chap. 9 provides some case studies of clear interest for the engi-

neering profession.

1.2 Introduction

This chapter provides an intuitive description of diﬀerent practical problems

with a decomposable structure that can be exploited through a decomposition

technique. These problems arise naturally in engineering and science.

剩余540页未读，继续阅读

songlinjian

粉丝: 0
资源: 2

数学规划中的分解技术详解：工程与科学应用

代码学习笔记2.1

Decomposition Techniques in Mathematical Programming

分布式协调服务Zookeeper的安装配置与基本操作解析

Android开发：ADB：ADB高级调试技术.pdf

三菱plc实例程序66个，制糖机、送板机、收板机、卫生巾小包机、压入机、弯管机、橡胶注射机、橡胶硫化机、细针自动排序机等等

dy一键典藏评工具.zip

基于VB+ACCESS 实现的汽车美容管理系统(源代码+系统+外文翻译+英文文献+开题报告+任务书)

关于电机中绕组出现大小线圈时嵌线方式的探讨

GoC编程基础：魔法学院的奇幻之旅-从零开始学习C++画图

西南交通大学-数据结构实验1（2022级）

最新资源