PROGRESS IN MATHEMATICS Volume 11 Probability Theory, Mathematical Statistics, and Theoretical Cybernetics PROGRESS IN MATHEMATICS Translations of ltogi Nauki - Seriya Maternatika 1968: Volume 1 - Mathematical Analysis Volume 2 - Mathematical Analysis 1969: Volume 3 - Probability Theory, Mathematical Statistics, and Theoretical Cybernetics Volume 4 - Mathematical Analysis Volume 5 - Algebra 1970: Volume 6 - Topology and Geometry Volume 7 - Probability Theory, Mathematical Statistics, and Theoretical Cybernetics Volume 8 - Mathematical Analysis 1971 : Volume 9 - Algebra and Geometry Volume 10 - Mathematical Analysis Volume 11 - Probability Theory, Mathematical Statistics, and Theoretical Cybernetics In preparation: Volume 12 - Algebra and Geometry Volume 13 - Probability Theory, Mathematical Statistics, and Theoretical Cybernetics Volume 14 - Algebra, Geometry, and Topology PROGRESS IN MATHEMATICS Volume 11 Probability Theory, Mathematical Statistics, and Theoretical Cybernetics Edited by R. V. Gamkrelidze V. A. Steklov Mathematics Institute Academy of Sciences of the USSR, Moscow Translated from Russian by J. S. Wood c:E'PLENUM PRESS • NEW YORK-LONDON • 1971 The original Russian text was published for the All-Union Institute of Scientific and Technical Information in Moscow in 1970 as a volume of Itogi Nauki - Seriya Maternatika EDITORIAL BOARD R. V. Gamkrelidze, Editor-in-Chief N. M. Ostianu, Secretary P. S. Aleksandrov V. N. Latyshev N. G. Chudakov Yu. V. Linnik M. K. Kerimov M. A. Naimark A. N. Kolmogorov S. M. Nikol'skii L. D. Kudryavtsev N. Kh. Rozov G. F. Laptev V. K. Saul'ev Library of Congress Catalog Card Number 67-27902 ISBN-13: 978-1-4684-3311-1 e-ISBN-13: 978-1-4684-3309-8 DOl: 10.1007/978-1-4684-3309-8 The present translation is published under an agreement with Mezhdunarodnaya Kniga, the Soviet book export agency © 1971 Plenum Press, New York Softcover reprint of the hardcover 1st edition 1971 A Division of Plenum Publishing Corporation 227 West 17th Street, New York, N. Y. 10011 United Kingdom edition published by Plenum Press, London A Division of Plenum Publishing Company. Ltd. Davis House (4th Floor), 8 Scrubs Lane, Harlesden, NW10 6SE, England All rights reserved No part of this publication may be reproduced in any form without written permission from the publisher Preface This volume contains two review articles: "Stochastic Pro gramming" by Vo V. Kolbin, and "Application of Queueing-Theoretic Methods in Operations Research, " by N. Po Buslenko and A. P. Cherenkovo The first article covers almost all aspects of stochastic programming. Many of the results presented in it have not pre viously been surveyed in the Soviet literature and are of interest to both mathematicians and economists. The second article com prises an exhaustive treatise on the present state of the art of the statistical methods of queueing theory and the statistical modeling of queueing systems as applied to the analysis of complex systems. Contents STOCHASTIC PROGRAMMING V. V. Kolbin Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 § 1. The Geometry of Stochastic Linear Programming Problems. . . . . . . . . . . . . . . . . . . . 5 § 2. Chance-Constrained Problems . . . . . . . . . 8 § 3. Rigorous Statement of stochastic Linear Programming Problems . . . . . . . . . . 16 § 4. Game-Theoretic Statement of Stochastic Linear Programming Problems. . . . . . . . 18 § 5. Nonrigorous Statement of SLP Problems . . . 19 § 6. Existence of Domains of Stability of the Solutions of SLP Problems . . . . . . . . . 29 § 7. Stability of a Solution in the Mean. . . . . . . . . . . . 30 § 8. Dual Stochastic Linear Programming Problems. . . 37 § 9. Some Algorithms for the Solution of Stochastic Linear Programming Problems . . . . . . . . . . 40 § 10. Stochastic Nonlinear Programming: Some First Results . . . . . . . . . . . . . . . . . . . . . . 42 § 11. The Two-Stage SNLP Problem. . . . . . . . . . . . 47 § 12. Optimality and Existence of a Plan in Stochastic Nonlinear Programming Problems. 58 Literature Cited . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 APPLICATION OF QUEUEING-THEORETIC METHODS IN OP ERA TIONS RESEARC H N. P. Buselenko and A. P. Cherenkov ... 77 1. Use of the Analytical Methods of Queueing Theory in Operations Research. . . . . . . . . . ...... . 77 vii viii CONTENTS § 1. Application of Queueing-Theoretic Methods for the Analysis of Communication and Control System . . . . . . . . . . . . . . . . . . 78 §2. Transportation Problems . . . . . . . . . . . . . . . • . • 83 §3. Application of Queueing Theory in Production Scheduling . . . . . . • . . . . . . . . . • . . . . . . . 91 §4. Organization of Commerce and Food Services. . . . . 94 §5. Planning of Public Medical Services. . . . . . . . . • . 96 §6. other Applications: Monographs and Surveys. . . . . 97 II. Application of Statistic Modeling (Monte Carlo Method) for the Solution of Problems in Queueing Theory. • . . 98 § 1. General Considerations. . . . . . . . . . . . . . . . . . . . 98 §2. Production Technology and Scheduling. . . . . . . • .. 104 §3. Transportation . . . . . . . . . . . . . . . . . . . . . . . .. 106 §4. other Applications. . . . . . . . . . . . . . . . . . . . . .. 109 §5. Monographs . . . . . . . . . . . . . . . . . • . . . . . . . .. 111 Literature Cited . . . . . . . • . . . . . . . . . . . . . . . . . . . .. 111 Stochastic Programming V. V. Kolbin The present article is a general survey of the problems of stochastic programming. It is based on lectures delivered by the author to graduating students of the Cybernetics Section of the Econo mics Department of Leningrad State University (LGU) in 1967 and 1968. The author was aided substantially by LGU graduate students G. Tsel'mer, V. N. Tanskaya, and L. Bonits, to whom he extends his deepest appreciation. We shall abide by the earlier surveys [9, 12, 13] with regard to the description of terminology and classification. Our primary concern will be those areas of stochastic pro gramming which have not received warranted attention in the So viet literature, viz., duality considerations in stochastic linear programming (SLP) problems, special algorithms for the solution of stochastic programming problems, and, of course, stochastic nonlinear programming (SNLP). Introduction Almost any problem in applied mathematics may be assigned to one of the following two classes. The first class comprises "descriptive" problems, in which mathematical methods are used to process information on some investigated effect and to deduce certain laws of the effect from other laws. The second class includes "optimization" problems, in which the optimum, in some particular sense, is chosen from a set of fea sible solutions. 1 2 V. V. KOLBIN Besides the above division of applied mathematical problems, they can be classified by other criteria as well. In particular, a logical division recognizes deterministic and stochastic problems. In the course of solution of the latter an extensive mathematical discipline has emerged in the guise of probability theory. However, until lately probabilistic methods have been re stricted exclusively to the solution of problems of the descriptive type. Stochastic optimization problems have only begun to receive attention in the last decade. The same is true of the stochastic variants of optimal programming problems. Nevertheless, stochastic optimal programming is an exceed ingly important and promiSing branch of applied mathematics, cer tainly on no small account of the fact that solutions in practice are always subject to some measure of uncertainty. It is also clear that stochastic programming problems are bound to be far more com plex than their deterministic counterparts. In the development of optimal stochastic programming pro blems, therefore, it is totally unrealistic to hope for the rapid at tainment of sufficiently general and effective results. In light of the foregoing it is essential in the future treatment of stochastic programming to systematize the work published to date and to consolidate it into some kind of more or less unified mathematical theory. The present article represents an attempt in this direction. In the majority of practical mathematical programming prob lems the coefficients involved are subject to variations. The nature of these variations can be twofold: 1. The possible values of the coefficients are specified in the form of a function of one or more parameters with known domains of variation; the mathematical description of such problems is embodied in parametric linear program ming models. 2. The coefficients of the problems obey a certain probabilis tic distribution. The branch of applied mathematics that takes account of the aforementioned character of the variation of the coefficients has come to be known as stochastic programming. STOCHASTIC PROGRAMMING 3 The literature devoted to stochastic programming encom passes approximately two hundred journal articles. These may be divided into five groups according to the problem areas covered in the articles. The first group of articles is concerned with the search for various statements ofSLP problems. They include the papers of Dantzig [64, 65], Dantzig and Madansky [67], Madansky [111,112], Charnes and Cooper [48, 49, 50], Tintner [163, 164, 165], Kataoka [98], Vajda [173, 174], Bereanu [28, 29, 30], Yosifescu and Theo dorescu [199, 200], and others. The second group of articles is devoted to extensions of the concepts of the stability of solutions and duality to stochastic pro gramming problems. These problems have been treated in papers by Madansky [110, 114, 115], Tintner [166,167], Tintner, Sengupta, and Rao [170], Vajda [173, 174], Sengupta [136], Sengupta and Ku mar [137], Sengupta and Tintner [138], Hadley [89], Williams [194, 195], Bereanu [29, 30], Arbuzova [1,3], and Arbuzova and Danilov[4]. In the articles of the third group the authors have endeavored to reduce stochastic programming problems to deterministic pro blems devoid of random coefficients. These include papers by Dantzig [65], Ferguson and Dantzig [78], Charnes [43, 44], Charnes and Cooper [48], Elmaghraby [73-75], Vajda [173,174], Kataoka [98], Hadley [89], and Reiter [132]. In the fourth group of articles special algorithms have been developed for the solution of SLP problems; the authors include Dantzig [65], Ferguson and Dantzig [78], Madansky [114, 115], El maghraby [73-75], Williams [193-195], Soldatov [11-13], Karaoka [98], and others. Finally, the last group of papers is concerned with nonlinear stochastic programming. Only a few papers have been published in this area, chiefly those by Mangasarian [117], Mangasarian and Rosen [118], and Hanson [91]. Consider the set S = {X:AX:::; b, X? O}, where A = (aij) is an (m x n)-dimensional matrix, b = (~) is an m-dimensional vector, and x = (Xj) is a point in n-dimensional Euclidean space. The set S geometrically represents the intersection of m half-spaces and the positive hyperorthant. We shall assume that S is nonempty and bounded.