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

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

در روش بهینه‌سازی جورج دانتزیگ الگوریتم غیر مرکب یکی از بهترین الگوریتم‌ها برای برنامه‌ریزی خطی است.[۱][۲][۳][۴][۵]

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

مرور[ویرایش]

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

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

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

\mathbf{A}\mathbf{x} = \mathbf{b},\, x_i \ge 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 \ge 0. یک شیوه ی مستقیم برای تبدیل هر برنامه خطی به حالت استاندارد وجود دارد که این در از بین رفتن عمومیت تاثیری ندارد. در اصطلاحات هندسی، منطقه محتمل

\mathbf{A}\mathbf{x} = \mathbf{b},\, x_i \ge 0

یک (به احتمالی بیکران) پولی توپ محدب است. یک توصیف صفاتی ساده از نقاط کرانی راس های این پولی توپ وجود دارد ، \scriptstyle x \;=\; (x_1,\, \dots,\, x_n) یک نقطه کرانی است اگر و فقط اگر ستون بردارهای\scriptstyle A_i، جایی که به صورت خطی غیر مستقل باشند. در این مبحث، چنین نقطه ای به عنوان یک راه حل پایه ای امکان پذیر(BFS) شناخته می [۱۲] شود.

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

همچنین می توان نشان داد که اگر یک نقطه کرانی، نقطه کمینه تابع مقصود نیست، در نتیجه یک گوشه ای وجود دارد که نقطه را در بر می گیرد به شکلی که تابع مقصود اکیداً نزولی است بر روی گوشه ای که از نقطه دور می شود.[۱۵] اگر گوشه کراندار باشد، گوشه به نقطه ای دیگر در جایی که تابع مقصود مقدار کمتری دارد، متصل می شود، در غیر این صورت تابع مقصود زیر گوشه بی کران است و برنامه خطی هیچ راه حلی ندارد. الگوریتم غیر مرکب، این بینش را با گذشتن از تمامی گوشه های پولی توپ به نقطه های کرانی با مقادیر کمر تابعی، به وجود می آورد.این ادامه پیدا می کند تا وقتی که به مقدار کمینه دست پیدا کند، یا یک راس بی کران، مشاهده شود، این کار ادامه پیدا می کند، و این نتیجه گیری می شود که مسئله جوابی ندارد.الگوریتم همیشه به مام می رسد به این دلیل که تعداد راس های پولی توپ، متناهی است؛ همچنین به خاطر این که بین رئوس در یک جهت پرش می کنیم، امید داریم که تعداد رئوس پیمایش شده، کم باشد.[۱۵] راه حل یک برنامه خطی در دو مرحله به اجرا می رسد. در مرحله اول، که به فاز شناخته می شود، یک نقطه کرانی برای شروع جستجو ی شود.وابسته به طبیعت برنامه، این ممکن است کاری ناچیز باشد ولی عموماً با ارائه الگوریتم غیر مرکب به یک نسخه تصحیح شده نسبت به برنامه اولیه، این مسئله قابل حل است. نتایج محتمل فاز 1، یا یک راه حل پایه ای عملی که پیدا می شود یا این که ناحیه محتمل خالی است. در مرحله دوم، فاز 2، الگوریتم غیرمرکب به این گونه اعمال می شود که راه حل پایه ای عملی در فاز 1 به عنوان نقطه شروع به آن داده می شود. نتایج محتمل در فاز 2 یا یک راه حل پایه ای و عملی بهینه است یا یک گوشه بی کران که تابع مقصود در زیر آن بی کران است.[۳][۱۶][۱۷]

فرم استاندارد[ویرایش]

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

x_1 \ge 5

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

\begin{align}
  y_1 = x_1 - 5\\
  x_1 = y_1 + 5
\end{align}

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

\begin{align}
  x_2 + 2x_3 &\le 3\\
 -x_4 + 3x_5 &\ge 2
\end{align}

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

\begin{align}
  x_2 + 2x_3 + s_1 &= 3\\
 -x_4 + 3x_5 - s_2 &= 2\\
  s_1,\, s_2 &\ge 0
\end{align}

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

\begin{align}
  &z_1 = z_1^+ - z_1^-\\
  &z_1^+,\, z_1^- \ge 0
\end{align}

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

\mathbf{A}\mathbf{x} = \mathbf{b},\, x_i \ge 0

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

جدول مخروطی[ویرایش]

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


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

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

بگذارید


  \begin{bmatrix}
    1 & -\mathbf{c}^T_B & -\mathbf{c}^T_D & 0 \\
    0 & I & \mathbf{D} & \mathbf{b}
  \end{bmatrix}

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


  \begin{bmatrix}
    1 & 0 & -\bar{\mathbf{c}}^T_D & z_B \\
    0 & I & \mathbf{D} & \mathbf{b}
  \end{bmatrix}

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

عملیات محوری[ویرایش]

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

پانویس[ویرایش]

  1. Murty, Katta G. (1983). Linear programming. New York: John Wiley & Sons Inc.. pp. xix+482. ISBN 0-471-09725-X. MR 720547. 
  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)
  3. ۳٫۰ ۳٫۱ George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.
  4. George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.
  5. Michael J. Todd (February 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
  7. Murty (1983, Comment 2.2)
  8. Murty (1983, Note 3.9)
  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. جی‌استور 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. جی‌استور 2031443. MR 1124362. 
  11. 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 '''883185'''. 
  12. Murty (1983, Theorem 3.1)
  13. Murty (1983, Theorem 3.3)
  14. Murty (1983, Section 3.13)
  15. ۱۵٫۰ ۱۵٫۱ Murty (1983, Section 3.8)
  16. ۱۶٫۰ ۱۶٫۱ ۱۶٫۲ Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)
  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, p. 173)
  20. Murty (1983, section 2.3.2)
  21. Murty (1983, section 3.12)

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

برای مطالعه بیشتر[ویرایش]