الگوریتم کارمارکار
الگوریتم کارمارکار توسط نراندرا کارمارکار در سال ۱۹۸۴ برای حل مسایلبرنامهریزی خطی ارائه شد. این الگوریتم اولین الگوریتم کارا برای حل این مسایل در زمان چندجملهای بود. روش بیضی نیز زمان اجرای چندجملهای دارد،
ولی روش کارایی نیست.
اگر تعداد متغیرها و تعداد بیتهای ورودی به الگوریتم باشد، الگوریتم کارمارکار به عمل روی اعداد رقمی احتیاج دارد، درحالی که در روش بیضی به عمل نیاز است.
زمان اجرای الگوریتم کارمارکار به صورت زیر است
که در آن از ضرب به روش تبدیل سریع فوریه استفاده میکند.
الگوریتم کارمارکار از جمله روشهای نقطهٔ داخلی است: حدس فعلی شرایط مجموعهٔ ممکن را برخلاف روش سیمپلکس رعایت نمیکند و با استفاده از کسر معین در هر تکرار، دقت جواب بهینه را بهبود میدهد.[1]
الگوریتم
یک مسئلهٔ برنامهریزی خطی را در شکل ماتریسی در نظر بگیرید:
maximize cTx | |
subject to | Ax ≤ b. |
که در آن c برداری n بعدی و b برداری m بعدی و ماتریس m × n)، A) بعدی است.
الگوریتم کارماکار کمی پیچیده است. یک مدل سادهتر که به آن روش affine-scaling گفته میشود، که به طور مختصر به شرح زیر است. دقت داشته باشید که این الگوریتم در حالی که در عمل کارا است ولی الگوریتم با زمان چندجملهای نیست.[2]
Algorithm Affine-Scalling Input: A, b, c, , stopping criterion, .
do while stopping criterion not satisfied if then return unbounded end if end do
منابع
- 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. Unknown parameter
|month=
ignored (help) - Robert J. Vanderbei (1986). "A Modification of Karmarkar's Linear Programming Algorithm". Algorithmica. 1: 395–407. doi:10.1007/BF01840454. Unknown parameter
|coauthors=
ignored (|author=
suggested) (help)