الگوریتم غیرمرکب

در روش بهینه‌سازی جورج دانتزیگ الگوریتم غیر مرکب یکی از بهترین الگوریتم‌ها برای برنامه‌ریزی خطی است.

در بهینه‌سازی ریاضیاتی، الگوریتم غیر مرکب دانتزیگ، (یا روش غیر مرکب) یک الگوریتم محبوب برای برنامه‌نویسی خطی است. مجله پردازش در علوم و مهندسی این الگوریتم را به عنوان یکی از ۱۰ الگوریتم برتر در قرن بیستم معرفی کرده‌است. نام این الگوریتم از مفهوم یک غیر مرکب برگرفته شده و توسط ت.س.موتزگین پیشتهاد شده‌است. سیمپلیس‌ها در واقع در این الگوریتم مورد استفاده قرار نگرفته‌اند، ولی یک تفسیر از آن این است بر روی مخروط‌های سیمپلیسی، و اینها سیمپلیس‌هایی منتاسب با محدویت‌های اضافی می‌شوند. مخروط‌های سیمپلیسی مورد سؤال، گوشه‌های (یعنی در همسایگی راس‌ها) یک شی هندسی که یک پولی توپ نامیده می‌شوند. شکل این پولی توپ توسط قیدهای ایجاد شده در تابع هدف، مشخص می‌شود.

مرور

الگوریتم غیر مرکب بر روی برنامه‌هایی در فرم استاندارد عمل می‌کند؛ مسئله‌های خطی به این فرم، کمینه شده

$\mathbf {c} \cdot \mathbf {x}$

مشروط بر این که:

$\mathbf {A} \mathbf {x} =\mathbf {b} ,\,x_{i}\geq 0$

$\scriptstyle x\;=\;(x_{1},\,\dots ,\,x_{n})$

با وجود متغیرهای مسئله،

\scriptstyle c\;=\;(c_{1},\,\dots ,\,c_{n})

ضریب‌های تابع گفته شده می‌باشند، ماتریس A، یک ماتریس p*n می‌باشد و ثابت‌های

\scriptstyle b\;=\;(b_{1},\,\dots ,\,b_{p})

که

b_{j}\geq 0

. یک شیوهٔ مستقیم برای تبدیل هر برنامه خطی به حالت استاندارد وجود دارد که این در از بین رفتن عمومیت تأثیری ندارد. در اصطلاحات هندسی، منطقه محتمل

$\mathbf {A} \mathbf {x} =\mathbf {b} ,\,x_{i}\geq 0$

یک (به احتمالی بیکران) پولی توپ محدب است. یک توصیف صفاتی ساده از نقاط کرانی رأس‌های این پولی توپ وجود دارد ، $\scriptstyle x\;=\;(x_{1},\,\dots ,\,x_{n})$

یک نقطه کرانی است اگر و فقط اگر ستون بردارهای

\scriptstyle A_{i}

، جایی که به صورت خطی غیر مستقل باشند. در این مبحث، چنین نقطه‌ای به عنوان یک راه حل پایه‌ای امکان‌پذیر(BFS) شناخته می شود.

می‌توان نشان داد که برای یک برنامه خطی در فرم استاندارد، اگر تابع مقصود یک مقدار کمینه در منطقه محتمل داشته باشد، در نتیجه این مقدار را روی (حداقل) یکی از نقاط کرانی خواهد داشت. این در عنوان خودش مسئله را به یک پردازش با حالت محدود تبدیل می‌کند، زیرا تعداد محدودی از نقاط کرانی وجود دارند، در هر حال تعداد نقاط کرانی به‌طور غیرقابل کنترلی برای کوچکترین برنامه‌های خطی نیز بزرگ است.

همچنین می‌توان نشان داد که اگر یک نقطه کرانی، نقطه کمینه تابع مقصود نیست، در نتیجه یک گوشه‌ای وجود دارد که نقطه را در بر می‌گیرد به شکلی که تابع مقصود اکیداً نزولی است بر روی گوشه‌ای که از نقطه دور می‌شود. اگر گوشه کراندار باشد، گوشه به نقطه‌ای دیگر در جایی که تابع مقصود مقدار کمتری دارد، متصل می‌شود، در غیر این صورت تابع مقصود زیر گوشه بی‌کران است و برنامه خطی هیچ راه حلی ندارد. الگوریتم غیر مرکب، این بینش را با گذشتن از تمامی گوشه‌های پولی توپ به نقطه‌های کرانی با مقادیر کمر تابعی، به وجود می‌آورد. این ادامه پیدا می‌کند تا وقتی که به مقدار کمینه دست پیدا کند، یا یک راس بی‌کران، مشاهده شود، این کار ادامه پیدا می‌کند، و این نتیجه‌گیری می‌شود که مسئله جوابی ندارد. الگوریتم همیشه به مام می‌رسد به این دلیل که تعداد رأس‌های پولی توپ، متناهی است؛ همچنین به خاطر این که بین رئوس در یک جهت پرش می‌کنیم، امید داریم که تعداد رئوس پیمایش شده، کم باشد. راه حل یک برنامه خطی در دو مرحله به اجرا می‌رسد. در مرحله اول، که به فاز شناخته می‌شود، یک نقطه کرانی برای شروع جستجو ی شود. وابسته به طبیعت برنامه، این ممکن است کاری ناچیز باشد ولی عموماً با ارائه الگوریتم غیر مرکب به یک نسخه تصحیح شده نسبت به برنامه اولیه، این مسئله قابل حل است. نتایج محتمل فاز ۱، یا یک راه حل پایه‌ای عملی که پیدا می‌شود یا این که ناحیه محتمل خالی است. در مرحله دوم، فاز ۲، الگوریتم غیرمرکب به این گونه اعمال می‌شود که راه حل پایه‌ای عملی در فاز ۱ به عنوان نقطه شروع به آن داده می‌شود. نتایج محتمل در فاز ۲ یا یک راه حل پایه‌ای و عملی بهینه است یا یک گوشه بی‌کران که تابع مقصود در زیر آن بی‌کران است.

فرم استاندارد

تبدیل یک برنامه خطی به یکی به حالت استاندارد، می‌تواند به صورت مقابل اعمال شود. ابتدا برای هر متغیر با یک کران پایین‌تر به غیر از صفر، یک متغیر جدید معرفی می‌شود که نشانگر تفاوت بین متغیر و حد می‌باشد. متغیر اولیه می‌تواند پس از آن با جایگزینی حذف شود. برای مثال، داده شده با این محدودیت

x_{1}\geq 5

با متغیر جدید، y_۱، که برابر است با

{\begin{aligned}y_{1}=x_{1}-5\\x_{1}=y_{1}+5\end{aligned}}

تساوی دوم برای حذف x_۱ از برنامه خطی استفاده می‌شود. در این روش، تمامی قیدهای با کران پایین تبدیل به محدودیت‌های غیر منفی می‌شوند. دوم، برای هر قید باقی‌مانده، یک متغیر جدید به نام متغیر اسلَک، معرفی می‌شود که هر قید را به یک قید تساوی تبدیل می‌کند. این متغیر نشانگر تفاوت بین دو طرف نامساوی است و غیر منفی در نظر گرفته شده‌است. برای مثال این نامساوی‌ها

{\begin{aligned}x_{2}+2x_{3}&\leq 3\\-x_{4}+3x_{5}&\geq 2\end{aligned}}

با این جایگزین می‌شود

{\begin{aligned}x_{2}+2x_{3}+s_{1}&=3\\-x_{4}+3x_{5}-s_{2}&=2\\s_{1},\,s_{2}&\geq 0\end{aligned}}

راه آسانتر این است که دستکاری جبری بر روی نامساوی‌ها در این فرم انجام شود. در نامساوی‌هایی که ≥ وجود دارد مانند نامساوی دوم، بعضی نویسندگان ارجاع می‌دهند به متغیری که به متغیر surplus معروف است. سوم، هر متغیر غیر محدود، از برنامه خطی حذف می‌شود. این می‌تواند به دو راه انجام شود، یکی با حل کردن مسئله برای متغیری در یکی از تساوی‌ها یی که وجود دارد و سپس حذف متغیر با جایگزینی. راه دیگر این است که متغیر را با تفاوت دو متغیر محدود جایگزین کرد. برای مثال اگر z_۱ بدون قید است کس می‌نویسیم

{\begin{aligned}&z_{1}=z_{1}^{+}-z_{1}^{-}\\&z_{1}^{+},\,z_{1}^{-}\geq 0\end{aligned}}

این تساوی برای حذف z_۱ از برنامه خطی استفاده می‌شود. زمانی که پروسه به اتمام می‌رسد، منطقه محتمل به فرم زیر خواهد بود Ax=b,x_i≥۰ همچنین بهتر است که درچه A را تعداد ردیف‌ها در نظر بگیریم. این به هیچ وجه باعث از بین رفتن عمومیت نمی‌شود، زیرا در هر حال یا:

$\mathbf {A} \mathbf {x} =\mathbf {b} ,\,x_{i}\geq 0$

دارای تساوی‌های اضافی است که می‌توان آن‌ها را حذف کرد، یا سیستم متناقض است و دستگاه خطی هیچ راه حلی ندارد.

جدول مخروطی

یک دستگاه خطی به فرم استاندارد می‌تواند به صورت ماتریسزیر نمایش داده شود

{\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {b} \end{bmatrix}}

ردیف اول نمایانگر تابع مقصود و باقی ردیف‌ها نشانگر قیدها هستند. (در نظر داشته باشید، نویسنده‌های مختلف، روش‌های مختلفی برای برای نوشتن این دستگاه استفاده می‌کنند)اگر ستون‌های A بتوانندبه گونه‌ای چیده شوند که دربر گیرنده ماتریس هویت باشند که از درجه Pاست (تعداد سطرها در A)در نتیجه جدول یا ماتریس در حالت مخروطی قرار دارد. متغیرهای نظیر ستون‌های ماتریس هویت، متغیرهای پایه‌ای نامیده می‌شوند، در حالی که باقی متغیرها غیرپایه ای یا متغیرهای آزاد هستند. اگر متغیرهای غیر پایه‌ای صفر در نظر گرفته شوند، مقادیر متغیرهای پایه‌ای به راحتی قابل بدست آمدن هستند، به این گونه که با گرفتن ورودی‌هایی در b ، راه حل یک راه حل پایه‌ای محتمل است. برعکس، با داشتن یک راه حل امکان‌پذیر، ستون‌های نظیر متغیرهای غیر صفر می‌توانند به یک ماتریس غیر منفرد ارتقا داد. اگر ماتریس متناظر در امعکوس این ماتریس ضرب شود، نتیجه یک جدول یا ماتریس به فرم.

بگذارید

{\begin{bmatrix}1&-\mathbf {c} _{B}^{T}&-\mathbf {c} _{D}^{T}&0\\0&I&\mathbf {D} &\mathbf {b} \end{bmatrix}}

یک جدول به فرم مخروطی باشد. تغییر شکل اضافی جمع سطرها می‌تواند برای حذف ثابت‌های c _B از تابع مقصود به کار می‌رود. این روش به بیرون کشی قیمت معروف است و یک جدول مخروطی را به جای می‌گذارد.

{\begin{bmatrix}1&0&-{\bar {\mathbf {c} }}_{D}^{T}&z_{B}\\0&I&\mathbf {D} &\mathbf {b} \end{bmatrix}}

جایی که z_B مقدار تابع مقصود در راه حل محتمل متناظر است. ضریب‌های به روز شده، که با نام ضریب‌های متناسب هزینه اینیز شناخته می‌شوند، نرخ تغییرات تابع مقصود با توجه به متغیرهای غیر پایه‌ای، هستند.

عملیات محوری

عملیات هندسی جابجایی از یک راه حل محتمل به یک راه حل پایه‌ای محتمل همجوار، با عملیات محوری پیاده‌سازی می‌شود. ابتدا، یک عنصر محوری غیر صفر در یک ستون غیر پایه‌ای انتخاب می‌شود. ردیفی که این عنصر را دربردارد ضربدر معکوس آن می‌شود تا این عنصر به ۱ تبدیل شود، و سپس ضرب شده‌های ردیف با ردیف‌های دیگر برای تغییر ورودی‌های ستون به صفر، جمع می‌شوند. نتیجه این می‌شود که، اگر عنصر محوری در ردیف r قرار دارد، در نتیجه ستون، r امین ستون ماتریس هویت خواهد بود. متغیر این ستون الان یک متغیر پایه‌ای است که با متغیری که متناظر با ستون r ام ماتریس هویت، جابجا می‌شود، البته قبل از عملیات. در حقیقت، متغیر متناظر با ستون محوری وارد دستهٔ متغیرهای پایه‌ای شده و نام آن می‌شود متغیر رونده. جدول همچنان به فرم مخروطی است ولی با مجموعه‌ای از متغیرهای پایه‌ای که با یک عنصر تغییر پیدا کرده‌اند.

پانویس

↑ Murty, Katta G. (1983). Linear programming. New York: John Wiley & Sons Inc. pp. xix+482. ISBN 0-471-09725-X. MR 0720547.
↑ Richard W. Cottle, ed. The Basic George B. Dantzig. Stanford Business Books, Stanford University Press, Stanford, California, 2003. (Selected papers by George B. Dantzig)
↑ George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.
↑ George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.
↑ Michael J. Todd (2002). "The many facets of linear programming". Mathematical Programming. 91 (3). (Invited survey, from the International Symposium on Mathematical Programming.)
↑ Computing in Science and Engineering, volume 2, no. 1, 2000
↑ (Murty 1983، Comment 2.2)
↑ (Murty 1983، Note 3.9)
↑ Stone, Richard E.; Tovey, Craig A. (1991). "The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (2): 220–237. doi:10.1137/1033049. JSTOR 2031142. MR 1124362.
↑ Stone, Richard E.; Tovey, Craig A. (1991). "Erratum: The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (3): 461. doi:10.1137/1033100. JSTOR 2031443. MR 1124362.
↑ Strang, Gilbert (1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. New York: Springer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185.
↑ (Murty 1983، Theorem 3.1)
↑ (Murty 1983، Theorem 3.3)
↑ (Murty 1983، ص. 143، Section 3.13)
↑ (Murty 1983، ص. 137، Section 3.8)
↑ Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)
↑ Robert J. Vanderbei, Linear Programming: Foundations and Extensions, 3rd ed. , International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. ISBN 978-0-387-74387-5.
↑ (Murty 1983، Section 2.2)
↑ (Murty 1983، ص. 173)
↑ (Murty 1983، section 2.3.2)
↑ (Murty 1983، section 3.12)

منابع

Murty, Katta G. (1983). Linear programming. New York: John Wiley & Sons, Inc. pp. xix+482. ISBN 0-471-09725-X. MR 0720547.

برای مطالعه بیشتر

توماس اچ کورمن، Charles E. Leiserson, رونالد ریوست، and کلیفورد استین. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 29.3: The simplex algorithm, pp. 790–804.
Frederick S. Hillier and Gerald J. Lieberman: Introduction to Operations Research, 8th edition. McGraw-Hill. ISBN 0-07-123828-X
Rardin, Ronald L. (1997). Optimization in operations research. Prentice Hall. p. 919. ISBN 0-02-398415-5.

[Murty-1] Murty, Katta G. (1983). Linear programming. New York: John Wiley & Sons Inc. pp. xix+482. ISBN 0-471-09725-X. MR 0720547.

[BasicDantzig-2] Richard W. Cottle, ed. The Basic George B. Dantzig. Stanford Business Books, Stanford University Press, Stanford, California, 2003. (Selected papers by George B. Dantzig)

[DantzigThapa1-3] George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.

[DantzigThapa2-4] George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.

[Todd-5] Michael J. Todd (2002). "The many facets of linear programming". Mathematical Programming. 91 (3). (Invited survey, from the International Symposium on Mathematical Programming.)

[6] Computing in Science and Engineering, volume 2, no. 1, 2000

[Murty22-7] (Murty 1983، Comment 2.2)

[Murty39-8] (Murty 1983، Note 3.9)

[StoneTovey-9] Stone, Richard E.; Tovey, Craig A. (1991). "The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (2): 220–237. doi:10.1137/1033049. JSTOR 2031142. MR 1124362.

[10] Stone, Richard E.; Tovey, Craig A. (1991). "Erratum: The simplex and projective scaling algorithms as iteratively reweighted least squares methods". SIAM Review. 33 (3): 461. doi:10.1137/1033100. JSTOR 2031443. MR 1124362.

[Strang-11] Strang, Gilbert (1987). "Karmarkar's algorithm and its place in applied mathematics". The Mathematical Intelligencer. New York: Springer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185.

[12] (Murty 1983، Theorem 3.1)

[13] (Murty 1983، Theorem 3.3)

[14] (Murty 1983، ص. 143، Section 3.13)

[Murty137-15] (Murty 1983، ص. 137، Section 3.8)

[NeringTucker-16] Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)

[Vanderbei-17] Robert J. Vanderbei, Linear Programming: Foundations and Extensions, 3rd ed. , International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. ISBN 978-0-387-74387-5.

[18] (Murty 1983، Section 2.2)

[19] (Murty 1983، ص. 173)

[20] (Murty 1983، section 2.3.2)

[21] (Murty 1983، section 3.12)