线性与非线性编程：模型与应用

需积分: 0 85 浏览量更新于2024-07-25 收藏 4.94MB PDF 举报

"该资源涵盖了线性编程与非线性编程在运筹学与管理科学领域的应用。通过一系列书籍，深入探讨了这两种重要的优化技术及其在不同场景中的实际运用，如库存与供应链管理、健康风险分析、马尔科夫链模型、非线性整数规划、软计算在复杂多准则决策中的角色、评价与决策模型、大规模定制的挑战与解决方案、离散优化建模的手册、生产调度的手册、库存控制、医疗流程优化、现代项目调度的视角以及随机过程、优化与控制理论等。" 线性编程（Linear Programming, LP）是一种数学优化方法，用于在满足一组线性约束条件下，最大化或最小化一个线性目标函数。它在经济学、工程、运营管理和物流等领域有着广泛应用。线性编程的基础是线性规划模型，由决策变量、目标函数和约束条件组成。解决LP问题最著名的算法是 simplex 算法，这是一种保证找到最优解的迭代方法。非线性编程（Nonlinear Programming, NLP）则涉及到目标函数和/或约束条件不是线性的优化问题。非线性优化可以是连续的、离散的或混合的，并且可能包括各种复杂的函数类型，如二次项、指数、对数、绝对值等。解决非线性优化问题通常比线性问题更复杂，因为它可能没有全局最优解，或者最优解的求解需要更高级的算法，如梯度下降、牛顿法或拟牛顿法。本书系列中，如"NONLINEAR INTEGER PROGRAMMING"探讨了非线性整数规划，这是一个更加复杂的问题，因为决策变量不仅受限于非线性函数，还必须取整数值。这在现实世界中常见，例如在生产计划、网络设计和资源分配等问题中。 "MARKOV CHAINS: Models, Algorithms, and Applications"则关注马尔科夫链，这是概率论中的一个模型，用于描述一个系统随时间演变的行为，常用于预测和决策分析。 "SOFT COMPUTING FOR COMPLEX MULTIPLE CRITERIA DECISION MAKING"介绍软计算，这是模糊逻辑、神经网络和遗传算法等非精确计算方法的集合，特别适用于处理不完全信息和复杂决策问题。 "VACATION QUEUEING MODELS: Theory and Applications"则探讨了休假排队模型，这是一种模拟服务系统中员工休假情况的数学模型，对于理解和服务行业的运营至关重要。这个资源提供了全面的线性和非线性编程理论及其在不同领域的实践案例，是理解和应用这些技术的重要参考资料。

2 Chapter 1 Introduction

This book is centered around a certain optimization structure—that character-

istic of linear and nonlinear programming. Examples of situations leading to this

structure are sprinkled throughout the book, and these examples should help to

indicate how practical problems can be often fruitfully structured in this form. The

book mainly, however, is concerned with the development, analysis, and comparison

of algorithms for solving general subclasses of optimization problems. This is

valuable not only for the algorithms themselves, which enable one to solve given

problems, but also because identification of the collection of structures they most

effectively solve can enhance one’s ability to formulate problems.

1.2 TYPES OF PROBLEMS

The content of this book is divided into three major parts: Linear Programming,

Unconstrained Problems, and Constrained Problems. The last two parts together

comprise the subject of nonlinear programming.

Linear Programming

Linear programming is without doubt the most natural mechanism for formulating a

vast array of problems with modest effort. A linear programming problem is charac-

terized, as the name implies, by linear functions of the unknowns; the objective is

linear in the unknowns, and the constraints are linear equalities or linear inequal-

ities in the unknowns. One familiar with other branches of linear mathematics might

suspect, initially, that linear programming formulations are popular because the

mathematics is nicer, the theory is richer, and the computation simpler for linear

problems than for nonlinear ones. But, in fact, these are not the primary reasons.

In terms of mathematical and computational properties, there are much broader

classes of optimization problems than linear programming problems that have elegant

and potent theories and for which effective algorithms are available. It seems that

the popularity of linear programming lies primarily with the formulation phase of

analysis rather than the solution phase—and for good cause. For one thing, a great

number of constraints and objectives that arise in practice are indisputably linear.

Thus, for example, if one formulates a problem with a budget constraint restricting

the total amount of money to be allocated among two different commodities, the

budget constraint takes the form x

≤ B, where x

, i = 1 2, is the amount

allocated to activity i, and B is the budget. Similarly, if the objective is, for example,

maximum weight, then it can be expressed as w

, where w

, i = 1 2,

is the unit weight of the commodity i. The overall problem would be expressed as

maximize w

subject to x

≤B

≥0x

≥0

1.2 Types of Problems 3

which is an elementary linear program. The linearity of the budget constraint is

extremely natural in this case and does not represent simply an approximation to a

more general functional form.

Another reason that linear forms for constraints and objectives are so popular

in problem formulation is that they are often the least difficult to define. Thus, even

if an objective function is not purely linear by virtue of its inherent definition (as in

the above example), it is often far easier to define it as being linear than to decide

on some other functional form and convince others that the more complex form is

the best possible choice. Linearity, therefore, by virtue of its simplicity, often is

selected as the easy way out or, when seeking generality, as the only functional form

that will be equally applicable (or nonapplicable) in a class of similar problems.

Of course, the theoretical and computational aspects do take on a somewhat

special character for linear programming problems—the most significant devel-

opment being the simplex method. This algorithm is developed in Chapters 2

and 3. More recent interior point methods are nonlinear in character and these are

developed in Chapter 5.

Unconstrained Problems

It may seem that unconstrained optimization problems are so devoid of struc-

tural properties as to preclude their applicability as useful models of meaningful

problems. Quite the contrary is true for two reasons. First, it can be argued, quite

convincingly, that if the scope of a problem is broadened to the consideration of

all relevant decision variables, there may then be no constraints—or put another

way, constraints represent artificial delimitations of scope, and when the scope

is broadened the constraints vanish. Thus, for example, it may be argued that a

budget constraint is not characteristic of a meaningful problem formulation; since by

borrowing at some interest rate it is always possible to obtain additional funds, and

hence rather than introducing a budget constraint, a term reflecting the cost of funds

should be incorporated into the objective. A similar argument applies to constraints

describing the availability of other resources which at some cost (however great)

could be supplemented.

The second reason that many important problems can be regarded as having no

constraints is that constrained problems are sometimes easily converted to uncon-

strained problems. For instance, the sole effect of equality constraints is simply to

limit the degrees of freedom, by essentially making some variables functions of

others. These dependencies can sometimes be explicitly characterized, and a new

problem having its number of variables equal to the true degree of freedom can be

determined. As a simple specific example, a constraint of the form x

=B can

be eliminated by substituting x

= B −x

everywhere else that x

appears in the

problem.

Aside from representing a significant class of practical problems, the study

of unconstrained problems, of course, provides a stepping stone toward the more

general case of constrained problems. Many aspects of both theory and algorithms

4 Chapter 1 Introduction

are most naturally motivated and verified for the unconstrained case before

progressing to the constrained case.

Constrained Problems

In spite of the arguments given above, many problems met in practice are formulated

as constrained problems. This is because in most instances a complex problem such

as, for example, the detailed production policy of a giant corporation, the planning

of a large government agency, or even the design of a complex device cannot be

directly treated in its entirety accounting for all possible choices, but instead must be

decomposed into separate subproblems—each subproblem having constraints that

are imposed to restrict its scope. Thus, in a planning problem, budget constraints are

commonly imposed in order to decouple that one problem from a more global one.

Therefore, one frequently encounters general nonlinear constrained mathematical

programming problems.

The general mathematical programming problem can be stated as

minimize fx

subject to h





=0i=1 2m





≤0j=1 2r

x ∈S

In this formulation, x is an n-dimensional vector of unknowns, x =x

x

x

,

and f , h

, i = 12m, and g

, j = 12r, are real-valued functions of the

variables x

x

x

. The set S is a subset of n-dimensional space. The function

f is the objective function of the problem and the equations, inequalities, and set

restrictions are constraints.

Generally, in this book, additional assumptions are introduced in order to

make the problem smooth in some suitable sense. For example, the functions in

the problem are usually required to be continuous, or perhaps to have continuous

derivatives. This ensures that small changes in x lead to small changes in other

values associated with the problem. Also, the set S is not allowed to be arbitrary

but usually is required to be a connected region of n-dimensional space, rather than,

for example, a set of distinct isolated points. This ensures that small changes in x

can be made. Indeed, in a majority of problems treated, the set S is taken to be the

entire space; there is no set restriction.

In view of these smoothness assumptions, one might characterize the problems

treated in this book as continuous variable programming, since we generally discuss

problems where all variables and function values can be varied continuously.

In fact, this assumption forms the basis of many of the algorithms discussed,

which operate essentially by making a series of small movements in the unknown

x vector.

1.3 Size of Problems 5

1.3 SIZE OF PROBLEMS

One obvious measure of the complexity of a programming problem is its size,

measured in terms of the number of unknown variables or the number of constraints.

As might be expected, the size of problems that can be effectively solved has been

increasing with advancing computing technology and with advancing theory. Today,

with present computing capabilities, however, it is reasonable to distinguish three

classes of problems: small-scale problems having about five or fewer unknowns

and constraints; intermediate-scale problems having from about five to a hundred

or a thousand variables; and large-scale problems having perhaps thousands or even

millions of variables and constraints. This classification is not entirely rigid, but

it reflects at least roughly not only size but the basic differences in approach that

accompany different size problems. As a rough rule, small-scale problems can be

solved by hand or by a small computer. Intermediate-scale problems can be solved

on a personal computer with general purpose mathematical programming codes.

Large-scale problems require sophisticated codes that exploit special structure and

usually require large computers.

Much of the basic theory associated with optimization, particularly in nonlinear

programming, is directed at obtaining necessary and sufficient conditions satisfied

by a solution point, rather than at questions of computation. This theory involves

mainly the study of Lagrange multipliers, including the Karush-Kuhn-Tucker

Theorem and its extensions. It tremendously enhances insight into the philosophy

of constrained optimization and provides satisfactory basic foundations for other

important disciplines, such as the theory of the firm, consumer economics, and

optimal control theory. The interpretation of Lagrange multipliers that accom-

panies this theory is valuable in virtually every optimization setting. As a basis for

computing numerical solutions to optimization, however, this theory is far from

adequate, since it does not consider the difficulties associated with solving the

equations resulting from the necessary conditions.

If it is acknowledged from the outset that a given problem is too large and

too complex to be efficiently solved by hand (and hence it is acknowledged that

a computer solution is desirable), then one’s theory should be directed toward

development of procedures that exploit the efficiencies of computers. In most cases

this leads to the abandonment of the idea of solving the set of necessary conditions

in favor of the more direct procedure of searching through the space (in an intelligent

manner) for ever-improving points.

Today, search techniques can be effectively applied to more or less general

nonlinear programming problems. Problems of great size, large-scale programming

problems, can be solved if they possess special structural characteristics, especially

sparsity, that can be explioted by a solution method. Today linear programming

software packages are capable of automatically identifying sparse structure within

the input data and take advantage of this sparsity in numerical computation. It

is now not uncommon to solve linear programs of up to a million variables and

constraints, as long as the structure is sparse. Problem-dependent methods, where

the structure is not automatically identified, are largely directed to transportation

and network flow problems as discussed in Chapter 6.

6 Chapter 1 Introduction

This book focuses on the aspects of general theory that are most fruitful

for computation in the widest class of problems. While necessary and sufficient

conditions are examined and their application to small-scale problems is illustrated,

our primary interest in such conditions is in their role as the core of a broader

theory applicable to the solution of larger problems. At the other extreme, although

some instances of structure exploitation are discussed, we focus primarily on the

general continuous variable programming problem rather than on special techniques

for special structures.

1.4 ITERATIVE ALGORITHMS

AND CONVERGENCE

The most important characteristic of a high-speed computer is its ability to perform

repetitive operations efficiently, and in order to exploit this basic characteristic, most

algorithms designed to solve large optimization problems are iterative in nature.

Typically, in seeking a vector that solves the programming problem, an initial vector x

is selected and the algorithm generates an improved vector x

. The process is repeated

and a still better solution x

is found. Continuing in this fashion, a sequence of ever-

improving points x

, x

x

, is found that approaches a solution point x

∗

. For

linear programming problems solved by the simplex method, the generated sequence

is of finite length, reaching the solution point exactly after a finite (although initially

unspecified) number of steps. For nonlinear programming problems or interior-point

methods, the sequence generally does not ever exactly reach the solution point, but

converges toward it. In operation, the process is terminated when a point sufficiently

close to the solution point, for practical purposes, is obtained.

The theory of iterative algorithms can be divided into three (somewhat

overlapping) aspects. The first is concerned with the creation of the algorithms

themselves. Algorithms are not conceived arbitrarily, but are based on a creative

examination of the programming problem, its inherent structure, and the efficiencies

of digital computers. The second aspect is the verification that a given algorithm

will in fact generate a sequence that converges to a solution point. This aspect is

referred to as global convergence analysis, since it addresses the important question

of whether the algorithm, when initiated far from the solution point, will eventually

converge to it. The third aspect is referred to as local convergence analysis or

complexity analysis and is concerned with the rate at which the generated sequence

of points converges to the solution. One cannot regard a problem as solved simply

because an algorithm is known which will converge to the solution, since it may

require an exorbitant amount of time to reduce the error to an acceptable tolerance.

It is essential when prescribing algorithms that some estimate of the time required

be available. It is the convergence-rate aspect of the theory that allows some

quantitative evaluation and comparison of different algorithms, and at least crudely,

assigns a measure of tractability to a problem, as discussed in Section 1.1.

A modern-day technical version of Confucius’ most famous saying, and one

which represents an underlying philosophy of this book, might be, “One good

theory is worth a thousand computer runs.” Thus, the convergence properties of an

剩余550页未读，继续阅读

yueqing2005ok

粉丝: 0
资源: 1

线性与非线性编程：模型与应用

《Linear and Nonlinear Programming》- Luenberger & Ye：数学规划大师之作

线性与非线性编程：优化方法探索

优化理论精要：线性与非线性编程

Linear Complementarity, Linear and Nonlinear Programming

Linear complementarity, linear and nonlinear programming

Linear and Nonlinear optimization

Nonlinear Programming: The Nonlinear Extension of Linear Programming for Complex Problems

MATLAB Linear and Integer Programming: The Ultimate Tool for Solving Discrete Optimization Problems

The Secret to Accelerating Linear and Quadratic Programming Solutions

Exploring Techniques for Handling Nonlinear Constraints: MATLAB Linear Programming with Nonlinear ...

最新资源