معرفی

روش Simplex رویکردی برای حل مدل های برنامه نویسی خطی با استفاده از متغیرهای SLACK ، Tableaus و متغیرهای محوری به عنوان ابزاری برای یافتن راه حل بهینه یک مشکل بهینه سازی است. یک برنامه خطی روشی برای دستیابی به بهترین نتیجه با حداکثر یا حداقل معادله با محدودیت های خطی است. بیشتر برنامه های خطی را می توان با استفاده از یک حل کننده آنلاین مانند MATLAB حل کرد ، اما روش Simplex یک تکنیک برای حل برنامه های خطی با دست است. برای حل یک مدل برنامه نویسی خطی با استفاده از روش Simplex مراحل زیر ضروری است:

● معرفی متغیرهای SLACK

● ایجاد تابلو

● ایجاد یک تابلو جدید

● بررسی بهینه

مقادیر بهینه را شناسایی کنید

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

مرحله 1: فرم استاندارد

فرم استاندارد فرمت پایه برای کلیه برنامه های خطی قبل از حل برای راه حل بهینه است و سه مورد نیاز دارد: (1) باید یک مشکل حداکثر باشد ، (2) تمام محدودیت های خطی باید در یک نابرابری کمتر از یا یا برابر باشد، (3) همه متغیرها غیر منفی هستند. این الزامات همیشه با تبدیل هر برنامه خطی معین با استفاده از جبر اساسی و تعویض می توانند برآورده شوند. یک فرم استاندارد لازم است زیرا یک نقطه شروع ایده آل برای حل روش Simplex تا حد امکان و همچنین سایر روش های حل مشکلات بهینه سازی ایجاد می کند.

برای تبدیل یک مدل برنامه خطی به حداقل رساندن به یک مدل برنامه خطی حداکثر ، به سادگی هر دو طرف سمت چپ و راست عملکرد هدف را ب ا-1 ضرب کنید.

تبدیل محدودیت های خطی از یک نابرابری بیشتر از یا یا یک نابرابری به نابرابری کمتر از یا یک برابر تا نابرابری می تواند به طور مشابه با آنچه در عملکرد هدف انجام شد انجام شود. با ضرب در هر دو طر ف-1 ، نابرابری را می توان به کمتر از یا یک برابر تغییر داد.

هنگامی که مدل به صورت استاندارد است ، متغیرهای Slack را می توان همانطور که در مرحله 2 روش Simplex نشان داده شده است اضافه کنید.

مرحله 2: متغیرهای Slack را تعیین کنید

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

پس از معرفی متغیرهای Slack ، می توان تابلو را تنظیم کرد تا بهینه سازی را که در مرحله 3 توضیح داده شده است ، بررسی کند.

مرحله 3: تنظیم تابلو

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

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

مرحله 4: بهینه سازی را بررسی کنید

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

مرحله 5: متغیر محوری را شناسایی کنید

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

در مثال نشان داده شده در زیر ، -10 کوچکترین منفی در ردیف آخر است. این ستون X2 را برای حاوی متغیر محوری تعیین می کند. حل این شاخص مقدار 10/3 را برای اولین محدودیت و مقدار 8/5 برای محدودیت دوم به ما می دهد. به دلیل کوچکترین شاخص غیر منفی ، مقدار محوری در ردیف دوم خواهد بود و مقدار 5 دارد.

اکنون که متغیر Pivot جدید مشخص شده است ، می توان Tableau جدید را در مرحله 6 ایجاد کرد تا متغیر را بهینه کند و راه حل بهینه جدید را پیدا کند.

مرحله ششم: Tableau جدید را ایجاد کنید

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

I. برای بهینه سازی متغیر محوری ، باید به یک مقدار واحد (مقدار 1) تبدیل شود. برای تبدیل مقدار ، سطر حاوی متغیر محوری را با متقابل مقدار محوری ضرب کنید. در مثال زیر ، متغیر محوری در ابتدا 5 است ، بنابراین کل ردیف را 1/5 ضرب کنید

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

iiiبرای نگه داشتن معادل Tableau ، متغیرهای دیگر موجود در ستون محوری یا ردیف محوری باید با استفاده از مقادیر محوری جدید محاسبه شوند. برای هر مقدار جدید ، منفی مقدار را در ستون Pivot قدیمی با مقدار در ردیف محوری جدید که مربوط به مقدار محاسبه شده است ، ضرب کنید. سپس این مقدار را از Tableau قدیمی به مقدار قدیمی اضافه کنید تا مقدار جدید برای Tableau جدید تولید شود. این مرحله را می توان در صفحه بعد به معادله متراکم کرد:

مقدار جدید Tableau = (مقدار منفی در ستون Pivot Old Tableau) x (مقدار در ردیف محوری Tableau جدید) + (مقدار Tableau قدیمی)

Tableau قدیمی:

تابلو جدید:

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

مثالهای عددی:

I. برای یافتن مقدار S2 در ردیف 1:

مقدار جدید Tableau = (مقدار منفی در ستون Pivot Old Tableau) * (مقدار در ردیف جدید Tableau Pivot) + (مقدار Tableau قدیمی)

مقدار جدید Tableau = (-3) * (1/5) + 0 =-3/5

II. برای یافتن متغیر X1 در ردیف 3:

مقدار جدید Tableau = (مقدار منفی در ستون Pivot Old Tableau) * (مقدار در ردیف جدید Tableau Pivot) + (مقدار Tableau قدیمی)

مقدار جدید = (10) * (1/5) + -8 = -6

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

مرحله 7: Optimality را بررسی کنید

همانطور که در مرحله 4 توضیح داده شد، راه حل بهینه یک مدل برنامه ریزی خطی بیشینه سازی، مقادیری هستند که به متغیرهای تابع هدف اختصاص داده می شوند تا بزرگترین مقدار زتا را به دست آورند. بهینه بودن باید بعد از هر تابلوی جدید بررسی شود تا ببینیم آیا یک متغیر محوری جدید باید شناسایی شود یا خیر. یک راه حل بهینه در نظر گرفته می شود اگر همه مقادیر در ردیف پایین بزرگتر یا مساوی صفر باشند. اگر همه مقادیر بزرگتر یا مساوی صفر باشند، راه حل بهینه در نظر گرفته می شود و مراحل 8 تا 11 را می توان نادیده گرفت. اگر مقادیر منفی وجود داشته باشد، راه حل هنوز بهینه نیست و یک نقطه محوری جدید باید تعیین شود که در مرحله 8 نشان داده شده است.

مرحله 8: متغیر Pivot جدید را شناسایی کنید

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

با شناسایی متغیر محوری جدید، تابلوی جدید را می توان در مرحله 9 ایجاد کرد.

مرحله 9: جدول جدید ایجاد کنید

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

I. با ضرب سطر حاوی متغیر محوری در متقابل مقدار پیوت، متغیر محوری را 1 کنید. در جدول زیر، مقدار محوری 1/5 بود، بنابراین همه چیز در 5 ضرب می شود.

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

مرحله 10: Optimality را بررسی کنید

با استفاده از تابلوی جدید، بهینه بودن را بررسی کنید. در مرحله 4 توضیح داده شد، یک راه حل بهینه زمانی ظاهر می شود که همه مقادیر در ردیف پایین بزرگتر یا مساوی صفر باشند. اگر همه مقادیر بزرگتر یا مساوی صفر هستند، به مرحله 12 بروید زیرا بهینه رسیده است. اگر مقادیر منفی هنوز وجود دارد، مراحل 8 و 9 را تکرار کنید تا به یک راه حل بهینه برسید.

مرحله 11: مقادیر بهینه را شناسایی کنید

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

متغیرهای اساسی: X1 ، S1 ، Z

متغیرهای غیر مبتدی: x2 ، x3 ، s2

برای متغیر X1 ، 1 در ردیف دوم یافت می شود. این نشان می دهد که مقدار بهینه X1 در ردیف دوم مقادیر بتا ، که 8 است ، یافت می شود.

متغیر S1 دارای 1 مقدار در ردیف اول است که مقدار بهینه 2 را از ستون بتا نشان می دهد. با توجه به اینکه S1 یک متغیر SLACK است ، در واقع در راه حل بهینه گنجانده نشده است زیرا متغیر در عملکرد هدف موجود نیست.

متغیر Zeta دارای 1 در ردیف آخر است. این نشان می دهد که حداکثر مقدار هدف از ستون بتا 64 خواهد بود.

راه حل نهایی هر یک از متغیرهای دارای مقادیر:

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

حداکثر مقدار بهینه 64 است و در (8 ، 0 ، 0) از عملکرد هدف یافت می شود.

نتیجه

روش Simplex رویکردی برای تعیین مقدار بهینه یک برنامه خطی با دست است. این روش یک راه حل بهینه برای برآورده کردن محدودیت های داده شده و تولید حداکثر مقدار زتا تولید می کند. برای استفاده از روش SIMPLEX ، یک مدل برنامه نویسی خطی معین باید به صورت استاندارد باشد ، که در آن می توان متغیرهای Slack را معرفی کرد. با استفاده از متغیرهای Tableau و Pivot ، می توان به یک راه حل بهینه رسید. از نمونه ای که در طول این سند کار کرده است ، می توان مشخص کرد که مقدار بهینه هدف 64 است و می توان وقتی x1 = 8 ، x2 = 0 و x3 = 0 پیدا کرد.

واژه نامه

متغیرهای اساسی متغیرهایی هستند که از نظر راه حل بهینه غیر منفی هستند.

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

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

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

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

راه حل بهینه از یک مدل برنامه نویسی خطی حداکثر ، مقادیری است که به متغیرها در عملکرد هدف اختصاص داده شده است تا به بزرگترین مقدار Zeta ارائه شود. راه حل بهینه در نقاط گوشه نمودار کل مدل وجود دارد.

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

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

Simplex Tableau برای انجام عملیات ردیف در مدل برنامه نویسی خطی و همچنین برای بررسی بهینه استفاده می شود.

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

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