تحقیق در عملیات (پژوهش عملیاتی) OR

سطر مولد (ایکس ۱ ) را از فرمول زیر میسازیم : قرینه وارون عدد لولا ( قرینه وارون عدد منفی دو که میشود منفی یک دوم) ضربدر سطر خروجی ( s2 جدول قبل)

مرحله چهارم : درست کردن سطر مولد

محل تلاقی سطر خروجی و ستون ورودی عدد لولا را مشخص مینماید که در مثال بالا عدد منفی ۲ عدد لولای ماست. نکته مهم : در سیمپلکس ثانویه عدد لولا حتما باید عددی منفی باشد و اعداد مثبت و صفر نمیتوانند بعنوان عدد لولا انتخاب شوند ( برعکس سیمپلکس ساده که اعداد منفی و صفر نمیتوانستند لولا باشند)

مرحله سوم : تعیین عدد لولا

برای تعیین ستون ورودی ، تمام اعداد منفی سطر خروجی را مشخص میکنیم، سپس اعداد متناظر با آنها را در داخل سطر زد پیدا کرده و در داخل قدر مطلق بر هم تقسیم میکنیم ( اعداد متناطر در سطر زد را بر اعداد منفی سطر خروجی تقسیم میکنیم) سپس کوچکترین حاصل تقسیم نشان دهنده ستون ورودی است در مثال بالا قدر مطلق حاصل تقسیم عدد منفی ۴ بر منفی دو کمتر شد بنابراین ستون x1 ورودی میشود

مرحله دوم : تعیین ستون ورودی

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

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

بعد از تشکیل اول از روی ضرایب (به همان روش سیمپلکس) مشاهده میکنیم که در سطر z با توجه به اینکه تابع min هست عدد مثبت وجود ندارد، ولی در ستون سمت راست دو ععد منفی (رنگ سبز) وجود دارد.

حالا مساله را استاندارد سازی میکنیم ( مثل سیمپلکس ساده)

بعد از ضرب محدودیت ها، مساله به این شکل در می اید

مساله بالا را در نظر بگیرید ، دارای دو محدودیت بزرگتر مساوی است. برای تبدیل محدودیت های بزرگتر مساوی کافی است انها را در منفی ضرب کنیم تا به کوچکتر مساوی تبدیل شوند.

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

❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️ 🔻🔻🔻حل مسائل ‌با سیمپلکس ثانویه🔻🔻🔻 @or_tips 🔵🔵🔵🔵🔵🔵

نکته مهم : از روش سیمپلکس ساده فقط در حل مسائلی میتوان استفاده کرد که کل محدودیت ها از جنس کوچکتر مساوی باشد ( max , min تفاوت ندارد)

بعد از حل کامل و ادامه جدولها به جواب بهینه میرسیم در جدول اخر و در سطر z عدد مثبتی دیده نمیشه پس مساله تمام شده ( جواب بهینه)

همینطور که در جدول تشکیلی میبینید مثبت ترین عدد به عنوان ستون ورودی انتخاب شد بعد از تقسیم اعداد ستون جواب rhs بر اعداد ستون لولا، کوچکترین جواب تقسیم هم بعنوان سطر خروجی انتخاب شد.

بدین منظور که استانداردسازی به مانند تابع max انجام میشود و فقط در دو جا متفاوت عمل میکنیم : ۱- مثبت ترین عدد به عنوان ستون ورودی یا ستون لولا انتخاب میشود. (برخلاف max که منفی ترین بود ) ۲- مساله وقتی جواب بهینه دارد و وقتی به اتمام میرسد که در سطر z عدد مثبت نداشته باشیم و همه اعداد سطر z منفی و صفر باشند. ( عدد rhs در سطر زد مد نظر نمیباشد)

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

❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️❇️ 🔻🔻🔻حل مسائل min با سیمپلکس🔻🔻🔻 روش دوم @or_tips 🔵🔵🔵🔵🔵🔵