nach oben

1987 | Buch

Kapitel lesen Erstes Kapitel lesen

The Simplex Method

A Probabilistic Analysis

verfasst von: Prof. Dr. Karl Heinz Borgwardt

Verlag: Springer Berlin Heidelberg

Buchreihe : Algorithms and Combinatorics

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Über dieses Buch

For more than 35 years now, George B. Dantzig's Simplex-Method has been the most efficient mathematical tool for solving linear programming problems. It is proba bly that mathematical algorithm for which the most computation time on computers is spent. This fact explains the great interest of experts and of the public to understand the method and its efficiency. But there are linear programming problems which will not be solved by a given variant of the Simplex-Method in an acceptable time. The discrepancy between this (negative) theoretical result and the good practical behaviour of the method has caused a great fascination for many years. While the "worst-case analysis" of some variants of the method shows that this is not a "good" algorithm in the usual sense of complexity theory, it seems to be useful to apply other criteria for a judgement concerning the quality of the algorithm. One of these criteria is the average computation time, which amounts to an anal ysis of the average number of elementary arithmetic computations and of the number of pivot steps. A rigid analysis of the average behaviour may be very helpful for the decision which algorithm and which variant shall be used in practical applications. The subject and purpose of this book is to explain the great efficiency in prac tice by assuming certain distributions on the "real-world" -problems. Other stochastic models are realistic as well and so this analysis should be considered as one of many possibilities.

Inhaltsverzeichnis

Frontmatter

Chapter 0. Introduction

Formulation of the Problem and Basic Notation

Abstract

This book deals with the computational effort required for solving linear programming problems of the following type

$$ _{\begin{subarray}{l} subject to\quad a_1^Tx \leqslant {b^1},...,a_m^Tx \leqslant {b^m}\left( {x \geqslant 0\;optional} \right) \\ where\quad v,x,{a_1},...,{a_m} \in {R^n},b \in {R^m} \end{subarray} }^{{Maximize\quad {v^T}x}} $$

(0.1.1)

Karl Heinz Borgwardt

Chapter 1. The Shadow-Vertex Algorithm

Abstract

This chapter is to explain the algorithm which shall be analyzed. For our probabilistic analysis it is necessary to use a so-called dual interpretation. Most of the readers may not be familiar with that way to describe the procedure. Therefore we start with the commonly used and well-known primal interpretation. In Section 2 we repeat most of the arguments of Section 1 in the new interpretation. And in Section 3 we show how the algorithm (in dual representation) can be realized in a corresponding tableau-form. So it is clear that much of the material is of an expository nature and that a certain amount of repetitions will occur. But the often observed confusion of readers by the different interpretations may be avoided by this way.

Karl Heinz Borgwardt

Chapter 2. The Average Number of Pivot Steps

Abstract

Let us define what we mean by “average number of pivot steps” precisely. For this purpose consider the matrix of the input data

$$ {\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{A}}: = \left[ \begin{gathered} a_1^T \hfill \\ . \hfill \\ a_m^T \hfill \\ {v^T} \hfill \\ \end{gathered} \right] \in {R^{{\left( {m + 1} \right)n}}} $$

(2.1.1)

of a problem

$$ \begin{gathered} Maximize\quad {v^T}x \hfill \\ subject\,to\quad a_1^Tx \leqslant 1,...,a_m^Tx \leqslant 1 \hfill \\ where\quad v,x,{a_1},...,{a_m} \in {R^n},m \geqslant n \hfill \\ \end{gathered} $$

(2.1.2)

We regard this matrix Â as a random variable in a probability space

$$ \left( {{R^{{\left( {m + 1} \right)n}}},A,P} \right) $$

(2.1.3)

, Where A is the σ-algebra of the Lebesgue-measurable sets of R^(m+1)n, and where P is a probability measure defined on A.

Karl Heinz Borgwardt

Chapter 3. The Polynomiality of the Expected Number of Steps

Abstract

In this chapter we are going to prove that E_m,n(S) and also E_m,n(s) are polynomial in m and n. The proof is highly technical and must be done very carefully. So I will explain it in detail and I will try to illustrate our considerations as well as possible.

Karl Heinz Borgwardt

Chapter 4. Asymptotic Results

Abstract

In the chapter before we have demonstrated a rather complicated and lengthy derivation of our main theorem, which states that our Simplex-Method is polynomial with respect to the expected number of pivot steps. Our upper bounds had the size

$$ 0({m^1}{/^{{(n - 1)}}}{n^3})\;for\;{E_{{m,n}}}(S) $$

$$ 0({m^1}{/^{{n - 1}}}{n^4})\;for\;{E_{{m.n}}}({s_t}) $$

. These bounds seem to exaggerate the n-term. This is due to the fact that we have combined several kinds of worst cases in our analysis of the average behaviour. The methods of Chapter 3 are not suitable for improving our results or for deriving lower bounds. Also it is not possible to derive detailed information on the average behaviour based on the use of special distributions.

Karl Heinz Borgwardt

Chapter 5. Problems with Nonnegativity Constraints

Abstract

Now we deal with linear programming problems of the type

$$ _{\begin{subarray}{l} subject\;to\quad a_1^T \leqslant 1, \ldots, a_m^Tx \leqslant 1,x \geqslant 0 \\ where\;\quad \quad x,{a_{{1,}}} \ldots, {a_m},v \in {\mathbb{R}^n} \end{subarray} }^{{Maximize\quad {v^T}x}} $$

. Here the feasibility region will be denoted by X^. The origin is — in any case — a vertex of X^ and can be used as an initial vertex. Hence Phase I is superfluous.

Karl Heinz Borgwardt

Chapter 6. Appendix

Karl Heinz Borgwardt

Backmatter

Titel: The Simplex Method
verfasst von: Prof. Dr. Karl Heinz Borgwardt
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-61578-8
Print ISBN: 978-3-540-17096-9
DOI: https://doi.org/10.1007/978-3-642-61578-8

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Chapter 0. Introduction

Chapter 1. The Shadow-Vertex Algorithm

Chapter 2. The Average Number of Pivot Steps

Chapter 3. The Polynomiality of the Expected Number of Steps

Chapter 4. Asymptotic Results

Chapter 5. Problems with Nonnegativity Constraints

Chapter 6. Appendix

Backmatter