مقدمه ای بر راه حل های اساسی در مهندسی

اگر شما یک مهندس یا دانشجوی مهندسی هستید، ممکن است بدانید که بهینه سازی به چه معناست.

برای به دست آوردن بهترین نتیجه ممکن، یافتن بهترین راه برای انجام کارها مهم است.

در برنامه نویسی خطی می توانید از یک راه حل اساسی برای یافتن بهترین راه حل استفاده کنید.

اما راه حل اساسی چیست و چرا دانستن آنها برای مهندسان بسیار مهم است؟ در این مقاله، من در مورد اینکه راه حل های اساسی چیست، چرا در مهندسی اهمیت دارند و چگونه می توان از آنها برای به دست آوردن بهترین نتایج در موقعیت های مختلف استفاده کرد، صحبت خواهم کرد.

بنابراین دست و پنجه نرم کنید و آماده شوید تا به دنیای راه حل های اساسی شیرجه بزنید، جایی که من اسرار را از بین می برم و به شما نشان می دهم که این تکنیک چقدر می تواند قدرتمند باشد.

راه حل های اساسی در برنامه ریزی خطی

تعریف رسمی:

یک راه حل برای یک مدل برنامه خطی متشکل از m معادلات در n متغیر با حل m متغیر بر حسب متغیرهای باقی مانده (nm) و قرار دادن متغیرهای (nm) برابر با صفر به دست می آید.

یک راه حل اساسی در برنامه ریزی خطی راهی برای حل یک مسئله برنامه ریزی خطی است که الزامات فنی خاصی را برآورده می کند.

به طور خاص، اگر بردارهای {ai : xi = 0} به صورت خطی مستقل باشند، یک بردار x یک راه حل اساسی برای یک چندوجهی است.

این بدان معنی است که ستون های A که دارای متغیرهای xi هستند که صفر نیستند، به صورت خطی مستقل هستند.

راه حل اساسی با اجزای غیرمنفی راه حل اساسی قابل اجرا (BFS) (BFS) نامیده می شود.

یک BFS تمام قوانینی را که یک چند وجهی را تعریف می کنند، رعایت می کند.

هر BFS گوشه ای از چند وجهی راه حل های امکان پذیر از نقطه نظر هندسی است.

برای یافتن یک راه حل اساسی، باید متغیرهای nm که پایه نیستند را روی صفر قرار دهید و متغیرهای m را که پایه هستند حل کنید.

ممکن است پایه های مختلف به یک راه حل اساسی منتهی شوند، به این معنی که ممکن است بیش از یک راه برای حل یک مشکل وجود داشته باشد.

روش Simplex یک فرآیند تکراری است که از یک BFS به BFS بعدی منتقل می شود تا زمانی که بهترین BFS را پیدا کند.

پس از استفاده از روش سیمپلکس برای یافتن یک BFS، با دیدن اینکه آیا هر BFS دیگری در نزدیکی مقدار بهتری برای تابع هدف می دهد، می توانیم بگوییم که آیا راه حل بهترین است یا خیر.

اگر چنین BFS وجود نداشته باشد، BFS فعلی بهترین است.

مدل برنامه ریزی خطی

یک مدل برنامه ریزی خطی شامل سه جزء اصلی است: متغیرهای تصمیم، یک تابع هدف و محدودیت ها.

هم تابع هدف و هم قیود باید توابع خطی باشند و متغیرهای تصمیم باید پیوسته باشند.

تابع هدف برای افزایش یا کاهش عددی استفاده می شود که نشان دهنده سود، هزینه، تعداد محصولات ساخته شده و غیره است.

محدودیت‌ها محدودیت‌ها یا محدودیت‌هایی در مقدار کل یک منبع خاص هستند که برای انجام وظایفی که سطح موفقیت در متغیرهای تصمیم را تعیین می‌کنند مورد نیاز است.

علاوه بر این، برخی از برنامه های خطی مستلزم این هستند که همه متغیرهای تصمیم غیرمنفی باشند.

در مدل های برنامه نویسی خطی می توانید از متغیرهای عدد صحیح و باینری نیز استفاده کنید.

متغیرهای باینری فقط می توانند مقدار 0 یا 1 داشته باشند، بنابراین فقط می توانند مقدار 0 یا 1 داشته باشند.

روش سیمپلکس

یکی از پرکاربردترین روش ها برای حل مسائل برنامه ریزی خطی، روش سیمپلکس است.

راه حل های اساسی در روش سیمپلکس مهم هستند زیرا با نقاط گوشه منطقه امکان پذیر مطابقت دارند و روش سیمپلکس از گوشه ای به گوشه دیگر حرکت می کند تا یک راه حل بهینه پیدا شود.

روش سیمپلکس روشی سریع برای یافتن بهترین پاسخ برای یک مسئله برنامه ریزی خطی با استفاده از خواص راه حل های اساسی است.

برای استفاده از روش سیمپلکس برای یافتن بهترین BFS، باید پایه B را برای ماتریس محدودیت A پیدا کنیم و سیستم Ax = b را با همه متغیرهای غیر از مبنای صفر حل کنیم.

مقادیر حاصل برای متغیرهای پایه یک BFS را تشکیل می دهند.

اگر یک راه حل بهینه وجود داشته باشد، یک BFS بهینه وجود دارد.

روش Simplex از یک BFS به یک BFS مجاور حرکت می کند تا زمانی که با استفاده از رویه های محوری به BFS بهینه برسد.

مقایسه بین راه حل های اساسی و راه حل های امکان پذیر

تفاوت بین راه حل اساسی و راه حل عملی در این است که یک راه حل اساسی نیازی به رعایت هیچ شرایطی ندارد.

به طور خاص، باید بردارهایی داشته باشد که به صورت خطی مستقل باشند و مقادیر غیر صفر برای xi داشته باشند و x باید کمتر از 0 باشد.

از سوی دیگر، راه حل عملی، هر نقطه ای است که در محدوده مسئله قرار گیرد.

اما همه راه حل های عملی، راه حل های عملی اساسی نیستند.

راه‌حل‌های اساسی امکان‌پذیر (BFS) تنها آن‌هایی هستند که با گوشه‌های چندوجهی راه‌حل‌های امکان‌پذیر مطابقت دارند.

بازگشت به مبانی: باز کردن قدرت راه حل های اساسی در مهندسی

هنوز درک آن سخت است؟ اجازه دهید دیدگاه را کمی تغییر دهم:

آیا از استفاده از روش ها و الگوریتم های پیچیده برای حل مسائل سخت خسته شده اید؟ آیا ای کاش راه ساده‌تر و سرراست‌تری برای مقابله با مشکلات مدل برنامه خطی شما وجود داشت؟

خوب، نگران نباشید، زیرا پاسخ اینجاست: m متغیرها را بر حسب متغیرهای باقیمانده (nm) حل کنید و متغیرهای (nm) را صفر کنید.

وقتی بتوانید به اصول اولیه بازگردید، چه کسی به الگوریتم هایی نیاز دارد که به نظر فانتزی به نظر می رسند؟ بنابراین ماشین حساب های خود را کنار بگذارید و بیایید شروع به یادگیری راه حل های ساده کنیم.

خوب، این فقط یک شوخی بود که شبیه یک تبلیغ تلویزیونی بود.

حالا برگردیم به توضیح.

برنامه نویسی خطی راه حل پایه

نکته: در صورت نیاز دکمه زیرنویس را روشن کنید. اگر با زبان گفتاری آشنایی ندارید، در دکمه تنظیمات، «ترجمه خودکار» را انتخاب کنید. قبل از اینکه زبان مورد علاقه شما برای ترجمه در دسترس قرار گیرد، ممکن است لازم باشد ابتدا روی زبان ویدیو کلیک کنید.

موارد استفاده کنید

نتیجه

در پایان، ایده یک راه حل اساسی در زمینه مهندسی بسیار مهم است و می تواند به طرق مختلف مورد استفاده قرار گیرد.

با دانستن اینکه راه حل اساسی چیست و در برنامه ریزی خطی چه می کند، می توانیم راه حل ها را بهبود بخشیم، هزینه ها را کاهش دهیم و کارآمدتر کنیم.

اما مهم است که به یاد داشته باشید که راه حل اساسی یک راه حل یک اندازه نیست، حتی اگر یک ابزار قدرتمند است.

برای به دست آوردن بهترین نتایج، هر مشکلی باید به دقت بررسی شود و در مورد آن فکر شود.

به عنوان مهندس، ما باید به دنبال این باشیم که چگونه راه حل های اساسی و سایر تکنیک های بهینه سازی می توانند به ما در پیشرفت و ارائه ایده های جدید کمک کنند.

بنابراین، بیایید قدرت راه‌حل‌های ساده را بشناسیم و با استفاده از تکنیک‌ها و استراتژی‌های جدید، محدودیت‌های ممکن را دنبال کنیم.

پیوندها و مراجع

کتاب ها:

• برنامه نویسی خطی توسط Vasek Chvatal
• مدل سازی و حل برنامه ریزی خطی با R توسط Jose M. Sallan