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

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

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

ایده یک راه حل اساسی عملی در این مرحله مطرح می شود.

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

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

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

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

درک راه حل اساسی اساسی

تعریف رسمی:

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

یک راه حل اساسی امکان پذیر (BFS) یک ایده کلیدی در برنامه ریزی خطی است که به یافتن بهترین راه حل ها کمک می کند.

یک BFS راه حلی با کمترین تعداد ممکن متغیر غیر صفر است.

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

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

یافتن یک راه حل اساسی بهینه امکان پذیر

برای یافتن بهترین BFS، باید موارد زیر را انجام دهیم:

• برنامه را به شکل استاندارد برای یک دنباله خطی بنویسید.
• سیستم نابرابری ها را به یک ماتریس افزوده تبدیل کنید.
• مشخص کنید که کدام متغیرها پایه هستند و کدام نیستند.
• متغیرهای اساسی را بر حسب سایر متغیرها مشخص کنید.
• این عبارات را در تابع هدف قرار دهید تا تابعی از متغیرهایی که پایه نیستند به دست آورید.
• یک متغیر غیر پایه پیدا کنید که بتوان آن را بدون شکستن هیچ محدودیتی افزایش داد و تابع هدف را بهتر کرد.

این متغیر اکنون یک متغیر پایه است و یکی از متغیرهای پایه دیگر دیگر متغیر پایه نیست.

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

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

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

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

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

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

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

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

چرا راه حل های عملی اساسی برای حل مسائل پیچیده مهندسی بسیار مهم هستند؟

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

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

از این گذشته، چه کسی به بهینه سازی نیاز دارد وقتی که هرج و مرج بسیار سرگرم کننده تر است؟ به دنیای متغیرهای غیرمنفی خوش آمدید، جایی که همه چیز فقط یک پیشنهاد است و شکست تقریباً قطعی است.

یا آن؟

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

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

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

یافتن راه حل اساسی اساسی

یک راه حل اساسی امکان پذیر (BFS) راه حلی برای یک مسئله بهینه سازی خطی است که تمام محدودیت ها را برآورده می کند و دارای کمترین تعداد متغیر غیر صفر است.

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

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

در این مقاله، ما در مورد چگونگی پیدا کردن یک راه‌حل اولیه اولیه، نحوه یافتن همه راه‌حل‌های امکان‌پذیر اولیه، و چگونگی یافتن یک راه‌حل عملی اساسی بدون متغیرهای سستی صحبت خواهیم کرد.

پیدا کردن یک راه حل اولیه اولیه

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

یک راه این است که متغیرهای Slack را به محدودیت‌های نابرابری اضافه کنید و بقیه متغیرها را صفر کنید.

متغیرهای Slack به متغیرهای پایه تبدیل می شوند و بقیه متغیرهای غیر پایه هستند.

روش دو فازی سیمپلکس راه دیگری برای حل مشکل است.

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

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

یافتن همه راه حل های اساسی امکان پذیر

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

ما می‌توانیم با اضافه کردن متغیرهای Slack، سیستم را تغییر دهیم و سپس از سیستم جدید برای یافتن تمام راه‌حل‌های اساسی برای یک برنامه خطی استفاده کنیم.

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

یافتن یک راه حل اساسی امکان پذیر بدون متغیرهای Slack

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

یک متغیر Slack فقط تفاوت بین سمت راست یک محدودیت و سمت چپ است.

به عنوان مثال، برای اولین محدودیت، یک متغیر slack تعریف می کنیم x4 = 14 - 2x1 - x2 - x3. از نظر این متغیر جدید، اولین محدودیت به سادگی معادل x4 ≥ 0 است که یک محدودیت مثبت برای x4 است.

وقتی این متغیرهای slack را اضافه می کنیم، یک برنامه خطی به دست می آوریم که همان برنامه اصلی است، با این تفاوت که همه محدودیت ها یا معادلات هستند یا محدودیت هایی که می گویند چیزی مثبت است.

به مجموعه ای از متغیرهای پایه که در جواب پایه مقادیری غیر از صفر دارند، مبنا می گویند.

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

برای یافتن بهترین راه حل، باید بردار x را پیدا کنیم که تمام قوانین را رعایت کند و بزرگترین یا کوچکترین مقدار را برای هدف دریافت کند.

اما یافتن بهترین راه‌حل گام‌های بیشتری نسبت به یافتن راه‌حلی که کار می‌کند و متغیرهای سستی ندارد، طول می‌کشد.

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

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

ویژگی ها و اهمیت راه حل اساسی

ویژگی های راه حل اساسی امکان پذیر

یک راه حل عملی اساسی حداکثر دارای m متغیرهایی است که صفر نیستند و حداقل متغیرهای nm صفر هستند که n تعداد متغیرهای تصمیم و m تعداد محدودیت ها است.

یک BFS گوشه ای از چند وجهی راه حل های ممکن است و هر BFS دارای n محدودیت فعال است که به صورت خطی مستقل هستند.

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

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

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

الگوریتم Simplex تمام راه حل های اساسی ممکن را به صورت سازمان یافته جستجو می کند تا بهترین راه حل را پیدا کند.

اهمیت راه حل اساسی

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

همچنین به الگوریتم‌های پیچیده مکانی برای شروع می‌دهد و می‌توان از آن برای فهمیدن اینکه آیا یک برنامه خطی امکان‌پذیر است یا خیر، استفاده کرد.

برای یافتن تمام راه‌حل‌های اساسی برای یک برنامه خطی، می‌توانید با اضافه کردن متغیرهای Slack، سیستم را تغییر دهید و سپس از سیستم تغییر یافته برای یافتن همه راه‌حل‌های عملی اولیه استفاده کنید.

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

ویدئو: راه حل های اساسی امکان پذیر

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

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

نتیجه

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

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

اما بیشتر از اینکه فقط مفید باشند، نشان می‌دهند که ریاضیات چقدر ظریف و زیبا هستند.

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

یادآوری خوبی است که مهندسی تماماً در مورد حل مسائل است و با استفاده از قدرت ریاضی می توانیم پاسخ هایی را پیدا کنیم که زمانی تصور می شد غیرممکن است.

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

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

کتاب ها:

• برنامه ریزی خطی: مبانی و الحاقات
• برنامه ریزی خطی: نظریه و کاربردها