الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.
قیمت
قیمت این مقاله: 38000 تومان
(ایران ترجمه - Irantarjomeh)
توضیح
بخش زیادی از این مقاله بصورت رایگان ذیلا قابل مطالعه می باشد.
شماره
۱۳
کد مقاله
ACC13
مترجم
گروه مترجمین ایران ترجمه – irantarjomeh
نام فارسی
الگوریتم حل محاسباتی پایدار برای برنامه‌های خطی
نام انگلیسی
A Computationally stable solution algorithm for linear programs
یک حوزه فعال تحقیقاتی برای برنامه نویسی خطی، ایجاد جدول ساده یا سیمپلکس اولیه‌ای می‌باشد که به راه حل بهینه نزدیک بوده و بطور موثر بتواند نسبت به اصلاح راهکارهای انتخابی محوری اقدام نماید. در این مقاله، روش جدیدی را برای مسئله مقداردهی اولیه و قوانین محوری ارائه می‌دهیم: این الگوریتم که تحت عنوان «روشهای M– بزرگ» شناخته می‌شود، فاقد هر متغیر مصنوعی و محدودیت مصنوعی است. بنابراین، با تهیه روش سیمپلکس بدون استفاده از هر عدد بزرگ، نتیجه، از نظر محاسباتی پایدار شده و اساس یا پایه اولیه بهتری را فراهم می‌کند تا عدد بازده تکرارهای محوری را کاهش دهد. یک الگوریتم حلی از نوع سیمپلکس سه فازی برای حل برنامه‌های خطی عمومی ایجاد می‌شود. در فاز ۱، بیشتر محدودیتها اعمال نمی‌شوند و مسئله از مبدا، شروع به حل شدن می‌کند. اگر تابع هدف نامحدود باشد، برای داشتن حل محدود و ممکن، اصلاح می‌شود. سپس، در فاز ۲، بیشتر محدودیتها به چارچوب ساده دو گانه وارد می‌شوند. به دنبال آن، در این مورد تابع هدف اولیه اصلاح می‌شود، فاز ۳ در تابع هدف اولیه، بهینه‌سازی می‌شود. این الگوریتم از نظر عددی پایدار است و با متغیرهای نتیجه اصلی عمل می‌کند. تحقیقات تجربی اولیه ما، نشان می‌دهد که الگوریتم ارائه شده از نظر تعداد تکرارها هم از الگوریتم سیمپلکس اولیه (اصلی) و هم از الگوریتم سیمپلکس دوگانه، مناسب‌تر است.
یکی از حوزه‌های فعال برنامه نویسی خطی، ایجاد جدول سیمپلکس اولیه و اصلاح موثر راهکارهای انتخاب محوری می‌باشد. به عنوان مثال ویرا و لینز [۱ و مراجع مرتبط] را نگاه کنید. در این مقاله، یک راه حل جدید برای مسئله مقدار دهی اولیه و قوانین محوری ارائه شده است. این الگوریتم که تحت عنوان «روشهای M– بزرگ» شناخته می‌شود، فاقد هر متغیر تصنعی و محدودیت مصنوعی مربوط بدان است. بنابراین، بکارگیری روش ساده بدون استفاده از اعداد بزرگ، نتیجه، از نظر محاسباتی پایدار است و پایه اولیه بهتری را برای کاهش عدد بازده تکرارهای محوری فراهم می‌نماید.
گروه روشهای سیمپلکس
روشهای سیمپلکس اولیه و دوگانه از روش عمومی یکسانی پیروی می‌کنند. در مرحله اول، یک پایه کامل ایجاد می‌شود. در مراحل پیشرفت از یک حل پایه تا حل دیگر حرکت می‌کنیم در این حال سعی می‌کنیم تا درجه غیر ممکن بودن مسئله (اصلی) و دوگانه را بترتیب کاهش دهیم.
روش سیمپلکس اولیه با حل پایه اولیه x = 0 شروع می‌شود، فاز اول شروع به یافتن یک حل ممکن می‌کند (نقطه نهائی). اگر این جستجو موفقیت‌آمیز نباشد، روش با عبارت «حل ممکن نیست» خاتمه می‌یابد، در غیر این صورت فاز دوم با یک احتمال پایه شروع می‌شود. یک نوع روش سیمپلکس اصلی (اولیه) که تحت عنوان «روش دو فازی» شناخته می‌شود، یک تابع هدف مصنوعی را معرفی می‌کند که مجموع متغیرهای مصنوعی است، در حالی که نوع دیگر، عبارات اخطاری را اضافه می‌کند که مجموع متغیرهای مصنوعی با ضرایب خیلی بزرگ می‌باشد. روش اخیر تحت عنوان «روش M– بزرگ» شناخته می‌شود.
گروه دوم روشهای سیمپلکس، روشی است که شامل الگوریتم سیمپلکس دوگانه می‌باشد. هنگامی که بعضی از ضرایب در تابع هدف مثبت هستند (یعنی بدون امکان(احتمال) دوگانه)، ما باید جدول محدودیت مصنوعی از نوع با M >> 0 را اضافه نماییم و این مجموع، تمام متغیرهای نتیجه (تصمیم) را با ضرایب مثبت در تابع هدف، در نظر می‌گیرد.
هر دو گروه، هنگامی که شرایط آغازی مربوط نقص می‌شوند، به ابزارهای مخصوص جهت راه‌اندازی الگوریتم نیاز دارند. روش سیمپلکس اولیه با شرایط احتمالی رضایت‌بخش شروع می‌شود و کوشش می‌شود تا به شرایط بهینه دست یافته شود. هنگامی که شرایط احتمالی اولیه رضایت‌بخش نیست، باید عبارات متغیرهای مصنوعی، با بعضی محدودیتها و اخطارها (یعنی M– بزرگ)، را در تابع هدف وارد کرد. بعنوان مثال [۲] را نگاه کنید.
در سیمپلکس دوگانه، عکس این امر صادق است. این الگوریتم با شرایط بهینه رضایت‌بخش شروع می‌شود و کوشش می‌شود تا به شرایط احتمالی (ممکن) دست یافته شود. هنگامی که شرایط دوگانه احتمالی رضایت‌بخش نیست، باید یک محدودیت مصنوعی با عدد مثبت بزرگ در RHS آن وارد کرد. هر دو گروه شامل تمام محدودیتها در جدول اولیه‌شان می‌باشند. تمام این روشهای M– بزرگ خیلی بزرگ می‌توانند لبریز- محاسباتی نقطه شناوری را ایجاد نمایند، که صحت عددی را از بین می‌برد.
ما الگوریتم ملی جدیدی را در فصل ۲ ارائه داده و مقیاسی از محدودیت را عرضه می‌نماییم. بخش ۳ به جنبههای محاسباتی الگوریتم می‌پردازد و مثالهایی برای توضیح تمام جنبههای الگوریتم ارائه می‌دهد. بخش ۴ آخرین ملاحظات و راستای تحقیقات آینده را ارائه می‌دهد.
الگوریتم حل محاسباتی پایدار برای برنامه‌های خطی
۲- الگوریتم حلی ارائه شده
الگوریتم حلی ارائه شده زیر یک روش از نوع سیمپلکس سه فازی است که از بکار بردن اعداد بزرگ اجتناب می‌کند و تحت عنوان «روش M– بزرگ» شناخته می‌شود. این روش، سیمپلکس اولیه و دوگانه را با هم ترکیب می‌کند اما هر وقت لازم باشد از اجزای تابع هدف به عنوان یک تابع هدف دلخواه برای تعیین نقطه کناری استفاده می‌کند. در فاز ۱ بعضی از محدودیتها اعمال نمی‌شوند (در حال آسایش هستند) تا امکان یا احتمال اصلی ایجاد شود (در صورت امکان). پس از حل مسئله بصورت آسایشی با استفاده از حل اخیر، به عنوان نقطه شروع، فاز ۲، سیمپلکس دوگانه را برای حل مسئله اصلی بکار می‌گیرد در حالیکه فاز ۳، سیمپلکس اولیه را بکار می‌گیرد. هر وقت ناحیه احتمالی نامحدود شود، مبدا در فاز ۱ به عنوان نقطه شروع برای فاز ۲ عمل می‌کند تا با استفاده از تابع هدف «موقت» یک نقطه کناری مناسب ایجاد نماید. فاز ۳ تابع هدف اولیه را اصلاح می‌کند و قانون سیمپلکس اولیه را برای نتیجه‌گیر بکار می‌گیرد.
تحقق تجربی اولیه ما با بعضی مسائل در اندازه‌های کوچک نشان می‌دهد که الگوریتم ارائه شده از نظر تعداد تکرارها، هم از سیمپلکس اولیه و هم از سیمپلکس دوگانه مناسب‌تر است.
۱-۲- مقدمات
متغیرهای نامحدود (نامعین) را به متغیرهای غیر منفی تبدیل کنید (اگر وجود داشته باشد).
تمام RHS را غیر منفی کنید.
محدودیتهای تساوی (اگر وجود داشته باشد) به جفت محدودیت ³ و £ تبدیل کنید.
محدودیتهای £ را که در آن تمام ضرایب غیر مثبت هستند، حذف کنید. این کار محدودیتهایی را که زائد بر محدودیت رابع دایره اول می‌باشد، حذف می‌کند.
وجود هر محدودیت ³ که در آن تمام ضرایب غیر مثبت هستند و RHS مثبت است، نشان می‌دهد که این مسئله غیر ممکن (محال) است.
تمام محدودیتهای نامساوی £ با ۰ = RHS به ۰ ³ تبدیل کنید. این کار از چندگانگی در مبدا اجتناب می‌کند. در زیر یک بررسی کلی از راهکار الگوریتمی که اغلب موارد عمومی مهم را در نظر می‌گیرد (مخلوطی از محدودیتهای ³ و £) ارائه می‌شود. این بررسی کلی، چارچوبی را ایجاد می‌کند که ما آن را به عمومیت کامل گسترش می‌دهیم. ما بصورت زیر عمل می‌کنیم:
فاز ۱: محدودیتهای ³ را اعمال نکنید و مسئله کاهش یافته را با سیمپلکس متداول حل کنید. در اغلب موارد، یک جدول سیمپلکس بهینه یعنی جدولی که هم شرایط بهینه‌سازی و هم شرایط احتمالی (ممکن) را برآورده می‌کند، به دست می‌آوریم. (بحث درباره چندین مورد خاص چند لحظه به تعویق می‌افتد).
فاز ۲: اگر حل، تمام محدودیتهای اعمال نشده (در حال آسایش) را برآورده سازد، کار را تمام می‌کنیم. در غیر این صورت اغلب محدودیتهای «نقص شده» را بصورت جدول در می‌آوریم و جهت اصلاح احتمال (امکان) از سیمپلکس دوگانه استفاده می‌کنیم. این فرآیند تکرار می‌شود تا تمام محدودیتها رضایت‌بخش شوند (برآورده شوند). این مرحله شامل چندین مورد خاص است که پس از مواد اولیه (اصلی) مورد بحث قرار می‌گیرند.
فاز ۳: تابع هدف اصلی را به شرح ذیل اصلاح کنید (اگر لازم باشد). ردیف آخر جدول اخیر را بامقادیر اصلی آن جایگزین کنید و آنها را در نظر بگیرید. سیمپلکس متداول را اجرا کنید. اگر این کار موفقیت‌آمیز نباشد، مسئله نامحدود می‌شود، در غیر این صورت جدول اخیر شامل حل بهینه است. حل بهینه (بهترین حل) و حلهای چندگانه را (اگر وجود داشته باشد) استخراج کنید.
۲-۲- موارد خاص
سه مورد خاص در فاز ۱ روی می‌دهد که ممکن است به رفتار خاصی نیاز داشته باشند. اگر تمام محدودیتها ³ باشند، این ناحیه غیر ممکن (غیر محتمل) است و اگر یک Cj مثبت وجود داشته باشد، باید آن را به صفر تغییر دهیم. این کار به اصلاح تابع هدف اصلی نیاز دارد و در فاز ۳ انجام می‌شود.
توجه کنید که برخلاف سیمپلکس و سیمپلکس دوگانه، به جای انتقال تمام محدودیتها به جدول اولیه و تمام جدولهای بعدی، بر روی اکثر محدودیتهای فعال تمرکز می‌کنیم. ما محدودیتهای ³ را یک به یک به جداول خود وارد می‌کنیم. این کار می‌تواند تلاش محاسباتی را نیز کاهش دهد.
۳-۲ فرآیند جزء به جزء
۱-۳-۲- فاز ۱
سه مورد را به شرح ذیل شناسایی کنید:
مرحله ۱-۱ FLAG = 0 قرار دهید. این، نشان می‌دهد که تابع هدف اصلی هنوز در حال استفاده است. وجود محدودیتهای £ و علامت Cjs را بررسی کنید.
در اینجا سه احتمال را تشخیص دهید:
الف) حداقل یک محدودیت £ وجود دارد. به مرحله ۲-۱ بروید.
ب) هیچ محدودیت £ وجود ندارد و هیچ یک از Cjsها مثبت نیست. به مرحله ۵-۲ بروید.
ج) هیچ محدودیت £ وجود ندارد و حداقل یکی از Cjsها مثبت است (یعنی A = 0 و برای حداقل یکC j = 0 ) به مرحله ۴-۱ بروید.
۲-۲-۳- فاز ۲
محدودیتهای آسایش یافته را به شرح ذیل اقامه کنید (احیا کنید) (اگر لازم باشد):
مرحله ۱-۲ اگر محدودیت(های) آسایش یافته باقیمانده‌ای وجود داشته باشد، به مرحله ۲-۲ بروید. در غیر این صورت به فاز ۳ بروید.
مرحله ۲-۲ آیا حل بهینه اخیر تمام محدودیتهای هنوز آسایش یافته را برآورده می‌سازد (رضایت‌بخش می‌سازد)؟ اگر جواب مثبت است به فاز ۳ بروید. در غیر این صورت به مرحله ۳-۲ بروید.
الگوریتم حل محاسباتی پایدار برای برنامه‌های خطی
۳- کاربردها و مثالهای عددی توضیحی
این بخش با مثالهای عددی به جنبههای محاسباتی الگوریتم می‌پردازد تا تمام جنبههای الگوریتم را نشان دهد.
الگوریتم حل محاسباتی پایدار برای برنامه‌های خطی
۴- ملاحظات نهایی
یک الگوریتم حلی جدید برای برنامه‌های خطی عمومی ارائه گردیده است. این الگوریتم بصورتی مطلوب هم با روشهای سیمپلکس دوگانه شامل تمام محدودیتها در ابتدا و تمام جداول بعدی می‌باشند. ما فقط با یک محدودیت شروع می‌کنیم و محدودیتها را یک به یک وارد جدول‌ها می‌کنیم. این کار، غالبا تلاش محاسباتی را کاهش می‌دهد. الگوریتم ارائه شده ساده است، ظرفیت پذیرش گسترده دارد و به تمام موارد می‌پردازد.
کاملا معلوم است که حل اصلی اولیه بوسیله سیمپلکس اولیه متداول و سیمپلکس دوگانه می‌تواند از حل بهینه دور باشد، بعنوان مثال [۱۱] را نگاه کنید. این امر سبب آسایش بعضی از محدودیتها می‌شود. بدیهی است که کاربرد آسایش برای مسائل بزرگ مقیاس، پیچیدگی کمتری دارد، بعنوان مثال [۱۲] را ببنید، اما این عیب را دارد که سرعت همگرایی در آن می‌تواند خیلی آهسته باشد. ایده‌های مشابه ارائه شده در [۳] بعنوان جایگزینی برای معیار انتخاب محدودیت، پذیرفته می‌شوند. با این وجود، روش استفاده از آن، به محدودیتهای دارای تمام ۰ ³RHS محدود می‌شود.
حلهای متعدد به معنی داشتن بیش از یک جواب بهینه است. مثلا در یک مورد، تصمیم‌ساز (تصمیم‌گیرنده) ممکن است بخواهد نسبت به آنچه حل کننده گزارش می‌دهد، انتخاب بیشتری انجام دهد یا انتخاب را کاملا رها کند. بعنوان مثال، روشهای نقطه داخلی، غالبا، یک تخریب خطی از حلهای اصلی بهینه را گزارش می‌دهند. حل بهینه متعدد و چندگانگی، مفاهیم متفاوتی هستند. داشتن حلهای بهینه متعدد به این معنی است که مسئله دوگانه، یک حل چندگانه دارد اما ممکن است حل بهینه غیر چندگانه متعدد یا یک حل واحد که چندگانه است داشته باشد، یا حتی یک ترکیب که موردی برای مسئله جالب فوق می‌باشد، داشته باشد.
حوزه دیگر مرتبط با تحقیقات فوری آینده، توسعه کد مناسبی برای اجرای این روش و انجام یک تحقیق گسترده با بازده محاسباتی مقایسه شده با روشهای موجود می‌باشد. این عملکرد می‌بایست بجای کاربرد نوع- جدولی از عملیات فنی جدید استفاده کند. در این مرحله، ارزیابی متقاعد کننده برای خواننده، کاربرد این روش برای حل مسئله‌ای است که ممکن است بوسیله هر روش دیگری بتوان آن را حل نمود.
لطفا به جای کپی مقالات با خرید آنها به قیمتی بسیار متناسب مشخص شده ما را در ارانه هر چه بیشتر مقالات و مضامین ترجمه شده علمی و بهبود محتویات سایت ایران ترجمه یاری دهید.
