Stochastic Two-Stage Programming

Stochastic Programming offers models and methods for decision problems wheresome of the data are uncertain. These models have features and structural properties which are preferably exploited by SP methods within the solution process. This work contribute

  • PDF / 14,885,183 Bytes
  • 235 Pages / 481.89 x 685.984 pts Page_size
  • 60 Downloads / 228 Views

DOWNLOAD

REPORT


392

Karl Frauendorfer

Stochastic Two-Stage Programming

Springer-Verlag Berlin Heidelberg New York London Paris Tokyo Hong Kong Barcelona Budapest

Author Dr. Karl Frauendorfer Institute for Operations Research University of Zurich Moussonstr. 15 Ch-8044 Zurich

ISBN-13: 978-3-540-56097-5 DOl: 10.1007/978-3-642-95696-6

e-ISBN-13: 978-3-642-95696-6

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law.

© Springer-Verlag Berlin Heidelberg 1992 Typesetting: Camera ready by author/editor 42/3140-543210 - Printed on acid-free paper

PREFACE

Analysts of systems in economics, ecology, industry etc. are confronted with increasing complexity due to the progress achieved in these fields. For finding (almost) optimal decisions, analysts are faced firstly with the problem statement, secondly with the set-up of a model, and thirdly with the insertion of proper and efficient solution methods. Stochastic Programming (SP) offers models and methods that allow for application in decision problems where some of the problem data is uncertain, and known only in a probabilistic sense. SP models can be classified into single-

period models, two-stage models, models with probabilistic constraints and multiperiod models. These models are endowed with advantageous features and structural properties preferably exploited by SP methods within the solution process. This work contributes to the methodology for two-stage models within Stochastic Programming. In these models the objective function is given as an integral whose integrand depends on a random vector, on its probability measure and on a decision. The fact that the integrand is usually given implicitly as a value function of some parametric optimization problem, strongly complicates the integration with respect to the probability measure and the optimization of the associated expectation functional. The main results of this work have been derived with the intention to ease these difficulties, and are seen in chapters 2, 3. After introducing stochastic two-stage programs in chapter 1 we investigate duality relations for convex optimization problems with supply/demand and prices treated as parameters. Based on these results we state a stability criterion proving subdifferentiability of the value function under proper assumptions (chapter 2). In chapter 3 we derive bilinear approximates for the integrand of the underlying two-stage program with respect to specially shaped polytopes, socalled 'cross-simplices' (x-simplices). Employing the stability c