الگوریتم غیرمرکب: تفاوت میان نسخهها
جز MohammadtheEditor صفحهٔ الگوریتم غیر مرکب را به الگوریتم غیرمرکب منتقل کرد: درخواست انتقال - غیرمرکب مرکب است:) |
جز ربات: جایگزینی پیوند جادویی شابک با الگو شابک |
||
خط ۲۸: | خط ۲۸: | ||
همچنین می توان نشان داد که اگر یک نقطه کرانی، نقطه کمینه تابع مقصود نیست، در نتیجه یک گوشه ای وجود دارد که نقطه را در بر می گیرد به شکلی که تابع مقصود اکیداً نزولی است بر روی گوشه ای که از نقطه دور می شود.<ref name="Murty137">{{harvtxt|Murty|1983|loc=Section 3.8|p=137}}</ref> اگر گوشه کراندار باشد، گوشه به نقطه ای دیگر در جایی که تابع مقصود مقدار کمتری دارد، متصل می شود، در غیر این صورت تابع مقصود زیر گوشه بی کران است و برنامه خطی هیچ راه حلی ندارد. الگوریتم غیر مرکب، این بینش را با گذشتن از تمامی گوشه های پولی توپ به نقطه های کرانی با مقادیر کمر تابعی، به وجود می آورد.این ادامه پیدا می کند تا وقتی که به مقدار کمینه دست پیدا کند، یا یک راس بی کران، مشاهده شود، این کار ادامه پیدا می کند، و این نتیجه گیری می شود که مسئله جوابی ندارد.الگوریتم همیشه به مام می رسد به این دلیل که تعداد راس های پولی توپ، متناهی است؛ همچنین به خاطر این که بین رئوس در یک جهت پرش می کنیم، امید داریم که تعداد رئوس پیمایش شده، کم باشد.<ref name="Murty137"/> |
همچنین می توان نشان داد که اگر یک نقطه کرانی، نقطه کمینه تابع مقصود نیست، در نتیجه یک گوشه ای وجود دارد که نقطه را در بر می گیرد به شکلی که تابع مقصود اکیداً نزولی است بر روی گوشه ای که از نقطه دور می شود.<ref name="Murty137">{{harvtxt|Murty|1983|loc=Section 3.8|p=137}}</ref> اگر گوشه کراندار باشد، گوشه به نقطه ای دیگر در جایی که تابع مقصود مقدار کمتری دارد، متصل می شود، در غیر این صورت تابع مقصود زیر گوشه بی کران است و برنامه خطی هیچ راه حلی ندارد. الگوریتم غیر مرکب، این بینش را با گذشتن از تمامی گوشه های پولی توپ به نقطه های کرانی با مقادیر کمر تابعی، به وجود می آورد.این ادامه پیدا می کند تا وقتی که به مقدار کمینه دست پیدا کند، یا یک راس بی کران، مشاهده شود، این کار ادامه پیدا می کند، و این نتیجه گیری می شود که مسئله جوابی ندارد.الگوریتم همیشه به مام می رسد به این دلیل که تعداد راس های پولی توپ، متناهی است؛ همچنین به خاطر این که بین رئوس در یک جهت پرش می کنیم، امید داریم که تعداد رئوس پیمایش شده، کم باشد.<ref name="Murty137"/> |
||
راه حل یک برنامه خطی در دو مرحله به اجرا می رسد. در مرحله اول، که به فاز شناخته می شود، یک نقطه کرانی برای شروع جستجو ی شود.وابسته به طبیعت برنامه، این ممکن است کاری ناچیز باشد ولی عموماً با ارائه الگوریتم غیر مرکب به یک نسخه تصحیح شده نسبت به برنامه اولیه، این مسئله قابل حل است. نتایج محتمل فاز 1، یا یک راه حل پایه ای عملی که پیدا می شود یا این که ناحیه محتمل خالی است. در مرحله دوم، فاز 2، الگوریتم غیرمرکب به این گونه اعمال می شود که راه حل پایه ای عملی در فاز 1 به عنوان نقطه شروع به آن داده می شود. نتایج محتمل در فاز 2 یا یک راه حل پایه ای و عملی بهینه است یا یک گوشه بی کران که تابع مقصود در زیر آن بی کران است.<ref name="DantzigThapa1"/><ref name="NeringTucker"/><ref name="Vanderbei">Robert J. Vanderbei, [http://www.princeton.edu/~rvdb/LPbook/ ''Linear Programming: Foundations and Extensions''], 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. ISBN |
راه حل یک برنامه خطی در دو مرحله به اجرا می رسد. در مرحله اول، که به فاز شناخته می شود، یک نقطه کرانی برای شروع جستجو ی شود.وابسته به طبیعت برنامه، این ممکن است کاری ناچیز باشد ولی عموماً با ارائه الگوریتم غیر مرکب به یک نسخه تصحیح شده نسبت به برنامه اولیه، این مسئله قابل حل است. نتایج محتمل فاز 1، یا یک راه حل پایه ای عملی که پیدا می شود یا این که ناحیه محتمل خالی است. در مرحله دوم، فاز 2، الگوریتم غیرمرکب به این گونه اعمال می شود که راه حل پایه ای عملی در فاز 1 به عنوان نقطه شروع به آن داده می شود. نتایج محتمل در فاز 2 یا یک راه حل پایه ای و عملی بهینه است یا یک گوشه بی کران که تابع مقصود در زیر آن بی کران است.<ref name="DantzigThapa1"/><ref name="NeringTucker"/><ref name="Vanderbei">Robert J. Vanderbei, [http://www.princeton.edu/~rvdb/LPbook/ ''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|en}}. <!-- (An on-line second edition was formerly available. Vanderbei's site still contains extensive materials.) --></ref> |
||
== فرم استاندارد == |
== فرم استاندارد == |
نسخهٔ ۱۷ سپتامبر ۲۰۱۷، ساعت ۲۲:۰۰
در روش بهینهسازی جورج دانتزیگ الگوریتم غیر مرکب یکی از بهترین الگوریتمها برای برنامهریزی خطی است.[۱][۲][۳][۴][۵]
در بهینه سازی ریاضیاتی، الگوریتم غیر مرکب دانتزیگ،(یا روش غیر مرکب)یک الگوریتم محبوب برای برنامه نویسی خطی است. مجله پردازش در علوم و مهندسی این الگوریتم را به عنوان یکی از ۱۰ الگوریتم برتر در قرن بیستم معرفی کرده است.[۶] نام این الگوریتم از مفهوم یک غیر مرکب برگرفته شده و توسط ت.س.موتزگین[۷] پیشتهاد شده است. سیمپلیس ها در واقع در این الگوریتم مورد استفاده قرار نگرفته اند، ولی یک تفسیر از آن این است بر روی مخروط های سیمپلیسی، و اینها سیمپلیس هایی منتاسب با محدویت های اضافی می شوند.مخروط های سیمپلیسی مورد سؤال، گوشه های ( یعنی در همسایگی راس ها) یک شی هندسی که یک پولی توپ نامیده می شوند.[۸][۹][۱۰][۱۱] شکل این پولی توپ توسط قید های ایجاد شده در تابع مقصود، مشخص می شود.
مرور
الگوریتم غیر مرکب بر روی برنامه هایی در فرم استاندارد عمل می کند؛ مسئله های خطی به این فرم، کمینه شده
مشروط بر این که:
با وجود متغیر های مسئله، ضریب های تابع گفته شده می باشند، ماتریس A، یک ماتریس p*n میباشد و ثابت های که . یک شیوه ی مستقیم برای تبدیل هر برنامه خطی به حالت استاندارد وجود دارد که این در از بین رفتن عمومیت تاثیری ندارد. در اصطلاحات هندسی، منطقه محتمل
یک (به احتمالی بیکران) پولی توپ محدب است. یک توصیف صفاتی ساده از نقاط کرانی راس های این پولی توپ وجود دارد ، یک نقطه کرانی است اگر و فقط اگر ستون بردارهای، جایی که به صورت خطی غیر مستقل باشند. در این مبحث، چنین نقطه ای به عنوان یک راه حل پایه ای امکان پذیر(BFS) شناخته می [۱۲] شود.
می توان نشان داد که برای یک برنامه خطی در فرم استاندارد، اگر تابع مقصود یک مقدار کمینه در منطقه محتمل داشته باشد، در نتیجه این مقدار را روی (حداقل) یکی از نقاط کرانی خواهد داشت.[۱۳] این در عنوان خودش مسئله را به یک پردازش با حالت محدود تبدیل می کند، زیرا تعداد محدودی از نقاط کرانی وجود دارند، در هر حال تعداد نقاط کرانی به طور غیر قابل کنترلی برای کوچکترین برنامه های خطی نیز بزرگ است.[۱۴]
همچنین می توان نشان داد که اگر یک نقطه کرانی، نقطه کمینه تابع مقصود نیست، در نتیجه یک گوشه ای وجود دارد که نقطه را در بر می گیرد به شکلی که تابع مقصود اکیداً نزولی است بر روی گوشه ای که از نقطه دور می شود.[۱۵] اگر گوشه کراندار باشد، گوشه به نقطه ای دیگر در جایی که تابع مقصود مقدار کمتری دارد، متصل می شود، در غیر این صورت تابع مقصود زیر گوشه بی کران است و برنامه خطی هیچ راه حلی ندارد. الگوریتم غیر مرکب، این بینش را با گذشتن از تمامی گوشه های پولی توپ به نقطه های کرانی با مقادیر کمر تابعی، به وجود می آورد.این ادامه پیدا می کند تا وقتی که به مقدار کمینه دست پیدا کند، یا یک راس بی کران، مشاهده شود، این کار ادامه پیدا می کند، و این نتیجه گیری می شود که مسئله جوابی ندارد.الگوریتم همیشه به مام می رسد به این دلیل که تعداد راس های پولی توپ، متناهی است؛ همچنین به خاطر این که بین رئوس در یک جهت پرش می کنیم، امید داریم که تعداد رئوس پیمایش شده، کم باشد.[۱۵] راه حل یک برنامه خطی در دو مرحله به اجرا می رسد. در مرحله اول، که به فاز شناخته می شود، یک نقطه کرانی برای شروع جستجو ی شود.وابسته به طبیعت برنامه، این ممکن است کاری ناچیز باشد ولی عموماً با ارائه الگوریتم غیر مرکب به یک نسخه تصحیح شده نسبت به برنامه اولیه، این مسئله قابل حل است. نتایج محتمل فاز 1، یا یک راه حل پایه ای عملی که پیدا می شود یا این که ناحیه محتمل خالی است. در مرحله دوم، فاز 2، الگوریتم غیرمرکب به این گونه اعمال می شود که راه حل پایه ای عملی در فاز 1 به عنوان نقطه شروع به آن داده می شود. نتایج محتمل در فاز 2 یا یک راه حل پایه ای و عملی بهینه است یا یک گوشه بی کران که تابع مقصود در زیر آن بی کران است.[۳][۱۶][۱۷]
فرم استاندارد
تبدیل یک برنامه خطی به یکی به حالت استاندارد، می تواند به صورت مقابل اعمال شود.[۱۸] ابتدا برای هر متغیر با یک کران پایین تر به غیر از صفر، یک متغیر جدید معرفی می شود که نشانگر تفاوت بین متغیر و حد می باشد.متغیر اولیه می تواند پس از آن با جایگزینی حذف شود. برای مثال، داده شده با این محدودیت
با متغیر جدید، y۱، که برابر است با
تساوی دوم برای حذف x_۱ از برنامه خطی استفاده می شود.در این روش، تمامی قیدهای با کران پایین تبدیل به محدودیت های غیر منفی می شوند. دوم، برای هر قید باقیمانده، یک متغیر جدید به نام متغیر اسلَک، معرفی می شود که هر قید را به یک قید تساوی تبدیل می کند.این متغیر نشانگر تفاوت بین دو طرف نامساوی است و غیر منفی در نظر گرفته شده است. برای مثال این نامساوی ها
با این جایگزین می شود
راه آسانتر این است که دستکاری جبری بر روی نامساوی ها در این فرم انجام شود.در نامساوی هایی که ≥ وجود دارد مانند نامساوی دوم، بعضی نویسندگان ارجاع می دهند به متغیری که به متغیر surplus معروف است. سوم، هر متغیر غیر محدود، از برنامه خطی حذف می شود. این می تواند به دو راه انجام شود، یکی با حل کردن مسئله برای متغیری در یکی از تساوی ها یی که وجود دارد و سپس حذف متغیر با جایگزینی. راه دیگر این است که متغیر را با تفاوت دو متغیر محدود جایگزین کرد. برای مثال اگر z_۱ بدون قید است کس می نویسیم
این تساوی برای حذف z_۱ از برنامه خطی استفاده می شود. زمانی که پروسه به اتمام می رسد، منطقه محتمل به فرم زیر خواهد بود Ax=b،x_i≥۰ همچنین بهتر است که درچه A را تعداد ردیف ها در نظر بگیریم. این به هیچ وجه باعث از بین رفتن عمومیت نمیشود، زیرا در هر حال یا:
دارای تساوی های اضافی است که می توان آنها را حذف کرد، یا سیستم متناقض است و دستگاه خطی هیچ راه حلی ندارد.[۱۹]
جدول مخروطی
یک دستگاه خطی به فرم استاندارد میتواند به صورت ماتریسزیر نمایش داده شود
ردیف اول نمایانگر تابع مقصود و باقی ردیفها نشانگر قیدها هستند.(در نظر داشته باشید، نویسندههای مختلف، روشهای مختلفی برای برای نوشتن این دستگاه استفاده میکنند.)اگر ستونهای A بتوانندبه گونهای چیده شوند که دربر گیرنده ماتریس هویت باشند که از درجه Pاست (تعداد سطرها در A )در نتیجه جدول یا ماتریس در حالت مخروطی قرار دارد.[۲۰] متغیرهای نظیر ستونهای ماتریس هویت، متغیرهای پایهای نامیده میشوند، در حالی که باقی متغیرها غیرپایه ای یا متغیرهای آزاد هستند. اگر متغیرهای غیر پایهای صفر در نظر گرفته شوند، مقادیر متغیرهای پایهای به راحتی قابل بدست آمدن هستند، به این گونه که با گرفتن ورودیهایی در b ، راه حل یک راه حل پایهای محتمل است. برعکس، با داشتن یک راه حل امکان پذیر، ستونهای نظیر متغیرهای غیر صفر میتوانند به یک ماتریس غیر منفرد ارتقا داد. اگر ماتریس متناظر در امعکوس این ماتریس ضرب شود، نتیجه یک جدول یا ماتریس به فرم.[۲۱]
بگذارید
یک جدول به فرم مخروطی باشد. تغییر شکل اضافی جمع سطرها میتواند برای حذف ثابتهای c TB از تابع مقصود به کار میرود. این روش به بیرون کشی قیمت معروف است و یک جدول مخروطی را به جای میگذارد.
جایی که zB مقدار تابع مقصود در راه حل محتمل متناظر است. ضریبهای به روز شده، که با نام ضریبهای متناسب هزینه اینیز شناخته میشوند، نرخ تغییرات تابع مقصود با توجه به متغیرهای غیر پایهای، هستند.[۱۶]
عملیات محوری
عملیات هندسی جابجایی از یک راه حل محتمل به یک راه حل پایهای محتمل همجوار، با عملیات محوری پیاده سازی میشود.ابتدا، یک عنصر محوری غیر صفر در یک ستون غیر پایهای انتخاب میشود. ردیفی که این عنصر را در بر دارد ضربدر معکوس آن میشود تا این عنصر به ۱ تبدیل شود، و سپس ضرب شدههای ردیف با ردیفهای دیگر برای تغییر ورودیهای ستون به صفر، جمع میشوند. نتیجه این میشود که، اگر عنصر محوری در ردیف 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).
{{cite journal}}
: Unknown parameter|month=
ignored (help) (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 '''883185'''.
{{cite journal}}
: Check|mr=
value (help); Unknown parameter|month=
ignored (help) - ↑ (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.
{{cite book}}
: Unknown parameter|copyright=
ignored (help)