برنامه‌ریزی خطی و مختصري از روش الگوريتم سيمپلكس

[donya88]

برنامه‌ریزی خطی


برنامه‌ریزی خطی، یا همان بهینه‌سازی خطی، روشی در [فقط کاربران سایت توانایی دیدن لینکها را دارند] است که به پیدا کردن مقدار کمینه یا بیشینه از یک [فقط کاربران سایت توانایی دیدن لینکها را دارند] روی یک [فقط کاربران سایت توانایی دیدن لینکها را دارند] [فقط کاربران سایت توانایی دیدن لینکها را دارند] می‌پردازد این چندضلعی محدب در حقیقت نمایش [فقط کاربران سایت توانایی دیدن لینکها را دارند] تعدادی محدودیت از نوع [فقط کاربران سایت توانایی دیدن لینکها را دارند] روی [فقط کاربران سایت توانایی دیدن لینکها را دارند] تابع است. به بیان ساده‌تر به وسیله برنامه‌سازی خطی می‌توان بهترین نتیجه (مثلاً بیشترین سود یا کمترین هزینه) را در شرایط خاص و با محدودیت‌های خاص به دست آورد. محل اصلی استفاده برنامه‌ریزی خطی در [فقط کاربران سایت توانایی دیدن لینکها را دارند] است، اما در [فقط کاربران سایت توانایی دیدن لینکها را دارند] نیز کاربردهای فراوانی دارد. می‌توان گفت حدود یک‌چهارم کل محاسبات علمی که بر روی [فقط کاربران سایت توانایی دیدن لینکها را دارند] انجام گرفته‌است، به برنامه‌ریزی خطی و مشتقات آن مربوط می‌شود



تاریخچه

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


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


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