The Simplex Method: A Probabilistic Analysis

اکنون بیش از 35 سال است که روش سیمپلکس جورج ب. دانتسیگ کارآمدترین ابزار ریاضی برای حل مسائل برنامه ریزی خطی بوده است. احتمالاً این الگوریتم ریاضی است که بیشترین زمان محاسباتی را روی رایانه ها برای آن صرف می کند. این واقعیت نشان دهنده علاقه زیاد متخصصان و عموم مردم به درک روش و کارایی آن است. اما مسائل برنامه ریزی خطی وجود دارد که با یک نوع معین از روش سیمپلکس در زمان قابل قبولی حل نمی شوند. اختلاف بین این نتیجه نظری (منفی) و رفتار عملی خوب روش، برای سال‌ها جذابیت زیادی را ایجاد کرده است. در حالی که "تحلیل بدترین حالت" برخی از انواع روش نشان می دهد که این الگوریتم "خوب" به معنای معمول نظریه پیچیدگی نیست، به نظر می رسد استفاده از معیارهای دیگر برای قضاوت در مورد این روش مفید باشد. کیفیت الگوریتم یکی از این معیارها میانگین زمان محاسبات است که معادل یک تحلیل مقعدی از میانگین تعداد محاسبات ریاضی ابتدایی و تعداد مراحل محوری است. تجزیه و تحلیل سفت و سخت از رفتار متوسط ​​ممکن است برای تصمیم گیری که کدام الگوریتم و کدام نوع باید در کاربردهای عملی استفاده شود بسیار مفید باشد. موضوع و هدف این کتاب تبیین کارایی زیاد در عمل با فرض توزیع‌های معین بر روی مشکلات «دنیای واقعی» است. سایر مدل های تصادفی نیز واقع بینانه هستند و بنابراین این تحلیل باید به عنوان یکی از بسیاری از احتمالات در نظر گرفته شود.

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.