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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم کارمارکار توسط نراندرا کارمارکار در سال ۱۹۸۴ برای حل مسایلبرنامه ریزی خطی ارائه شد. این الگوریتم اولین الگوریتم کارا برای حل این مسایل در زمان چند جمله‌ای بود.روش بیضی نیز زمان اجرای چند جمله‌ای دارد،
ولی روش کارایی نیست.

اگر n تعداد متغیرها و L تعداد بیت‌های ورودی به الگوریتم باشد، الگوریتم کارمارکار به  O(n^{3.5} L) عمل روی اعداد  O(L) رقمی احتیاج دارد، درحالی که در روش بیضی به  O(n^6 L) عمل نیاز است.
زمان اجرای الگوریتم کارمارکار به صورت زیر است

O(n^{3.5} L^2 \cdot \log L \cdot \log \log L)

که در آن از ضرب به روش تبدیل سریع فوریه استفاده می‌کند.

الگوریتم کارمارکار از جمله روش‌های نقطه‌ی داخلی است: حدس فعلی شرایط مجموعه‌ی ممکن را برخلاف روش سیمپلکس رعایت نمی‌کند و با استفاده از کسر معین در هر تکرار، دقت جواب بهینه را بهبود می‌دهد.[۱]

الگوریتم[ویرایش]

یک مساله‌ی برنامه‌ریزی خطی را در شکل ماتریسی در نظر بگیرید :

maximize cTx
subject to Ax ≤ b.

کﻪ ﺩﺭ ﺁﻥ c ﺑﺮﺩﺍﺭی n ﺑﻌﺪی و b ﺑﺮﺩﺍﺭی m ﺑﻌﺪی و ﻣﺎﺗﺮﯾﺲ m × n) ، A) ﺑﻌﺪی است.
الگوریتم کارماکار کمی پیچیده است. یک مدل ساده‌تر که به آن روش affine-scaling گفته می‌شود، که به طور مختصر به شرح زیر است. دقت داشته باشید که این الگوریتم در حالی که در عمل کارا است ولی الگوریتم با زمان چند جمله‌ای نیست.[۲]

Algorithm Affine-Scalling
  Input:  A, b, c, x^0, stopping criterion, \gamma.
   k \leftarrow 0 
  do while stopping criterion not satisfied
     v^k \leftarrow b-Ax^k
     D_v \leftarrow \operatorname{diag}(v_1^k,\ldots,v_m^k)
     h_x\leftarrow (A^TD_v^{-2}A)^{-1}c
     h_v\leftarrow -Ah_x
     if h_v \ge 0 then
        return unbounded
     end if
     \alpha \leftarrow \gamma\cdot \min\{-v_i^k/(h_v)_i \,\,|\,\, (h_v)_i <0,\, i=1,\ldots,m\}
     x^{k+1}\leftarrow x^k + \alpha h_x
     k\leftarrow k+1
  end do

منابع[ویرایش]

  1. Strang, Gilbert (1 June 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 '''883185'''. 
  2. Robert J. Vanderbei; Meketon, Marc, Freedman, Barry (1986). "A Modification of Karmarkar's Linear Programming Algorithm". Algorithmica 1: 395–407. doi:10.1007/BF01840454.