网络优化：连续与离散模型——Dimitri P. Bertsekas著作

网络优化

需积分: 46 164 浏览量更新于2023-05-22 收藏 3.02MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

"网络优化：连续和离散模型是由Dimitri P. Bertsekas撰写的一本书，主要探讨了网络优化的理论与应用，包括连续模型和离散模型两种方法。这本书由Athena Scientific出版社出版，并提供了在线书讯和订购的网址。内容涵盖了网络分析、数学优化等主题，并附有参考文献和索引。该书强调了对电子或机械方式的复制进行版权保护。作者Dimitri P. Bertsekas在希腊国立技术大学学习机械和电气工程，并在系统科学领域获得了博士学位。" 网络优化是解决网络中资源分配、路径选择、流量控制等问题的关键技术，广泛应用于通信网络、物流网络、电力网络等领域。Dimitri P. Bertsekas的《网络优化：连续和离散模型》深入探讨了这一主题，旨在提供一个全面的理论框架和实用工具。连续模型在优化问题中通常处理的是可以连续变化的变量。例如，在网络流问题中，流量可以被视为连续变量，允许微小的调整。这些模型通常使用微积分和线性代数等工具进行分析和求解，如线性规划、动态规划等方法。书中可能涉及如何构建连续优化模型，以及如何利用数值方法或解析解来找到最优解。离散模型则关注于只有有限个可能值的变量，如在网络中的开关状态、路由选择等。离散优化问题包括图论中的最短路径问题、旅行商问题等。这些问题可能更复杂，因为它们通常是非线性的，且可能存在组合爆炸问题。书中可能会介绍如何使用整数规划、分支定界法、遗传算法等方法来解决离散优化问题。此外，书中可能还涵盖了混合模型，它结合了连续和离散变量，这在实际问题中非常常见。混合模型的优化通常需要更加复杂的策略，如割平面法、内点法等。书中的内容可能还包括如何处理约束条件、如何评估和比较不同模型的效率，以及如何在实际应用中调整和实施优化方案。通过阅读本书，读者可以掌握网络优化的基础理论，理解如何构建和分析连续与离散模型，并学会运用这些知识解决实际问题。书中的案例研究和习题将帮助读者巩固概念，提高解决复杂网络优化问题的能力。此外，作者的学术背景和实践经验使得这本书不仅理论严谨，而且具有很高的实践指导价值。

资源详情

资源推荐

Sec. 1.1 Graphs and Flows 3

matical formulations and practical examples of network optimization mod-

els. Finally, in Section 1.3, we give an overview of some of the types of

computational algorithms that we develop in subsequent chapters.

1.1 GRAPHS AND FLOWS

In this section, we introduce some of the basic deﬁnitions relating to graphs,

paths, ﬂows, and other related notions. Graph concepts are fairly intuitive,

and can be understood in terms of suggestive ﬁgures, but often involve

hidden subtleties. Thus the reader may wish to revisit the present section

and pay close attention to some of the ﬁne points of the deﬁnitions.

A directed graph, G =(N, A), consists of a set N of nodes and a set

A of pairs of distinct nodes from N called arcs. The numbers of nodes and

arcs are denoted by N and A, respectively, and it is assumed throughout

that 1 ≤ N<∞ and 0 ≤ A<∞. An arc (i, j) is viewed as an ordered

pair, and is to be distinguished from the pair (j, i). If (i, j) is an arc, we

say that (i, j)isoutgoing from node i and incoming to node j; we also say

that j is an outward neighbor of i and that i is an inward neighbor of j.We

say that arc (i, j)isincident to i and to j, and that i is the start node and

j is the end node of the arc. We also say that i and j are the end nodes of

arc (i, j). The degree of a node i is the number of arcs that are incident to

i. A graph is said to be complete if it contains all possible arcs; that is, if

there exists an arc for each ordered pair of nodes.

We do not exclude the possibility that there is a separate arc connect-

ing a pair of nodes in each of the two directions. However, we do not allow

more than one arc between a pair of nodes in the same direction, so that we

can refer unambiguously to the arc with start i and end j as arc (i, j). This

is done for notational convenience.† Our analysis can be simply extended

to handle multiple arcs with start i and end j; the extension is based on

modifying the graph by introducing for each such arc, an additional node,

call it n, together with the two arcs (i, n) and (n, j). On occasion, we will

pause to provide examples of this type of extension.

We note that much of the literature of graph theory distinguishes

between directed graphs where an arc (i, j) is an ordered pair to be distin-

guished from arc (j, i), and undirected graphs where an arc is associated

with a pair of nodes regardless of order. One may use directed graphs, even

in contexts where the use of undirected graphs would be appropriate and

conceptually simpler. For this, one may need to replace an undirected arc

(i, j) with two directed arcs (i, j) and (j, i) having identical characteristics.

† Some authors use a single symbol, such as a, to denote an arc, and use

something like s(a) and e(a) to denote the start and end nodes of a, respectively.

This notational method allows the existence of multiple arcs with the same start

and end nodes, but is also more cumbersome and less suggestive.

4 Introduction Chap. 1

We have chosen to deal exclusively with directed graphs because in our

development there are only a few occasions where undirected graphs are

convenient. Thus, all our references to a graph implicitly assume that the

graph is directed. In fact we often omit the qualiﬁer “directed” and refer

to a directed graph simply as a graph.

1.1.1 Paths and Cycles

A path P in a directed graph is a sequence of nodes (n

,...,n

) with

k ≥ 2 and a corresponding sequence of k−1 arcs such that the ith arc in the

sequence is either (n

i+1

) (in which case it is called a forward arc of the

path) or (n

i+1

) (in which case it is called a backward arc of the path).

Nodes n

and n

are called the start node (or origin) and the end node (or

destination)ofP , respectively. A path is said to be forward (or backward)

if all of its arcs are forward (respectively, backward) arcs. We denote by

and P

−

the sets of forward and backward arcs of P, respectively.

A cycle is a path for which the start and end nodes are the same. A

path is said to be simple if it contains no repeated arcs and no repeated

nodes, except that the start and end nodes could be the same (in which

case the path is called a simple cycle). A Hamiltonian cycle is a simple

forward cycle that contains all the nodes of the graph. These deﬁnitions

are illustrated in Fig. 1.1. We mention that some authors use a slightly

diﬀerent terminology: they use the term “walk” to refer to a path and they

use the term “path” to refer to a simple path.

Note that the sequence of nodes (n

,...,n

) is not suﬃcient to

specify a path; the sequence of arcs may also be important, as Fig. 1.1(c)

shows. The diﬃculty arises when for two successive nodes n

and n

i+1

the path, both (n

i+1

) and (n

i+1

) are arcs, so there is ambiguity as

to which of the two is the corresponding arc of the path. If a path is known

to be forward or is known to be backward, it is uniquely speciﬁed by the

sequence of its nodes. Otherwise, however, the intended sequence of arcs

must be explicitly deﬁned.

A graph that contains no simple cycles is said to be acyclic. A graph

is said to be connected if for each pair of nodes i and j, there is a path

starting at i and ending at j; it is said to be strongly connected if for each

pair of nodes i and j, there is a forward path starting at i and ending

at j. Thus, for example, the graph of Fig. 1.1(b) is connected but not

strongly connected. It can be shown that if a graph is connected and each

of its nodes has even degree, there is a cycle (not necessarily forward) that

contains all the arcs of the graph exactly once (see Exercise 1.5). Such

a cycle is called an Euler cycle, honoring the historically important work

of Euler; see the discussion in Section 10.1 about the K¨onigsberg bridge

problem. Figure 1.2 gives an example of an Euler cycle.

We say that a graph G



=(N



, A



)isasubgraph of a graph G =(N, A)

if N



⊂Nand A



⊂A.Atree is a connected acyclic graph. A spanning

6 Introduction Chap. 1

tree of a graph G is a subgraph of G, which is a tree and includes all the

nodes of G. It can be shown [Exercise 1.14(c)] that a subgraph is a spanning

tree if and only if it is connected and it contains N − 1 arcs.

1.1.2 Flow and Divergence

In many applications involving graphs, it is useful to introduce a variable

that measures the quantity ﬂowing through each arc, like for example,

electric current in an electric circuit, or water ﬂow in a hydraulic network.

We refer to such a variable as the ﬂowofanarc. Mathematically, the ﬂow

of an arc (i, j) is simply a scalar (real number), which we usually denote

by x

. It is convenient to allow negative as well as positive values for ﬂow.

In applications, a negative arc ﬂow indicates that whatever is represented

by the ﬂow (material, electric current, etc.), moves in a direction opposite

to the direction of the arc. We can always change the sign of a negative

arc ﬂow to positive as long as we change the arc direction, so in many

situations we can assume without loss of generality that all arc ﬂows are

nonnegative. For the development of a general methodology, however, this

device is often cumbersome, which is why we prefer to simply accept the

possibility of negative arc ﬂows.

Given a graph (N, A), a set of ﬂows



| (i, j) ∈A



is referred to

as a ﬂow vector. The divergence vector y associated with a ﬂow vector x

is the N-dimensional vector with coordinates



{j|(i,j)∈A}

−



{j|(j,i)∈A}

, ∀ i ∈N. (1.1)

Thus, y

is the total ﬂow departing from node i less the total ﬂow arriving

at i; it is referred to as the divergence of i.

We say that node i is a source (respectively, sink) for the ﬂow vector

x if y

> 0 (respectively, y

< 0). If y

= 0 for all i ∈N, then x is called

a circulation. These deﬁnitions are illustrated in Fig. 1.3. Note that by

adding Eq. (1.1) over all i ∈N, we obtain



i∈N

=0.

Every divergence vector y must satisfy this equation.

The ﬂow vectors x that we will consider will often be constrained to

lie between given lower and upper bounds of the form

≤ x

≤ c

, ∀ (i, j) ∈A.

Given a ﬂow vector x that satisﬁes these bounds, we say that a path P is

unblocked with respect to x if, roughly speaking, we can send some positive

ﬂow along P without violating the bound constraints; that is, if ﬂow can

剩余584页未读，继续阅读

颹蕭蕭

粉丝: 5w+
资源: 36

会员权益专享

网络优化：连续与离散模型——Dimitri P. Bertsekas著作

Dimitri Bertsekas introduction to probability

DIMITRI BERTSEKAS_Convex Optimization Theory_solutions

nonlinear programming Dimitri P.B solution

网络优化：连续与离散模型详解

动态规划与最优控制第三版

"非线性规划第二版课后答案完整版更新

麻省理工概率论入门：理论与应用

伯特塞卡斯的约束优化与拉格朗日乘子方法详析

introdection to prebabillity dimitri p. bertsekos. john n. t sitsiblis

data networks dimitri bertsekas solution

强化学习与最优控制。pdf

关于强化学习的书籍推荐

可以推荐强化学习的书籍吗

推荐一本强化学习的教材

概率论导论中文版pdf

linux安装doxygen

doxygen安装centos

强化学习和最优控制（Dimitri P. Bertsekas）扩展演讲/摘要

约束优化与拉格朗日乘子法深入解析

矩阵优化与拉格朗日乘子法详解

会员权益专享

最新资源