با روش گرافیکی برای حل مسائل LP، ما در واقع از مجموعه رئوس متعلق به مرز مجموعه راه حل های سیستم نامساوی، راسی را انتخاب کردیم که در آن مقدار تابع هدف به حداکثر (حداقل) خود رسید. در مورد دو متغیر، این روش کاملاً شهودی است و به شما امکان می دهد به سرعت راه حلی برای مشکل پیدا کنید.
اگر سه یا چند متغیر در مشکل وجود داشته باشد و در مشکلات اقتصادی واقعی دقیقاً همین وضعیت وجود داشته باشد، تجسم حوزه راه‌حل‌ها برای سیستم محدودیت‌ها دشوار است. چنین وظایفی با استفاده از حل می شوند روش سیمپلکس یا با روش بهبود پی در پی. ایده روش ساده است و به شرح زیر است.
طبق یک قاعده مشخص، پلان مرجع اولیه پیدا می شود (مقداری از راس ناحیه محدودیت). بررسی می شود که آیا طرح بهینه است. اگر بله، پس مشکل حل شده است. اگر نه، پس به برنامه بهبود یافته دیگری بروید - به اوج دیگری. مقدار تابع هدف در این پلان (در این راس) بدیهی است که نسبت به قبلی بهتر است. الگوریتم انتقال با استفاده از چند مرحله محاسباتی انجام می شود که به راحتی در قالب جداول نوشته می شود. جداول سیمپلکس ... از آنجایی که تعداد رئوس محدود است، پس در تعداد محدودی از مراحل به جواب بهینه می رسیم.
بیایید روش سیمپلکس را با استفاده از یک مثال خاص از مسئله ترسیم یک طرح در نظر بگیریم.
مجدداً توجه داشته باشید که روش سیمپلکس برای حل مسائل LP متعارف کاهش یافته به شکل خاصی کاربرد دارد، یعنی دارای یک مبنا، سمت راست مثبت و یک تابع هدف که بر حسب متغیرهای غیر پایه بیان می شود. اگر کار به یک فرم خاص کاهش نیابد، مراحل اضافی مورد نیاز است که بعداً در مورد آن صحبت خواهیم کرد.
اجازه دهید مشکل طرح تولید را در نظر بگیریم، که قبلاً یک مدل ساخته بودیم و آن را به شکل خاصی کاهش می دادیم.
وظیفه.
برای تولید محصولات آو Vانبار نمی تواند بیش از 80 واحد مواد خام آزاد کند. علاوه بر این، برای ساخت محصول آدو واحد مصرف می شود و محصولات V- یک واحد مواد اولیه باید برنامه ریزی تولید به گونه ای انجام شود که بیشترین سود در صورت تولید محصولات تضمین شود آساخت بیش از 50 قطعه و محصولات مورد نیاز است V- حداکثر 40 عدد علاوه بر این، سود حاصل از فروش یک محصول آ- 5 روبل و از V- 3 روبل.
اجازه دهید یک مدل ریاضی بسازیم که نشان دهنده for است ایکس 1 تعداد محصول A در طرح، برای ایکس 2 - تعداد محصولات V... سپس سیستم محدودیت ها به صورت زیر خواهد بود:
اجازه دهید با معرفی متغیرهای اضافی، مسئله را به شکل متعارفی برسانیم:
(3.10)
F = -5x 1 - 3x2 → min.
این مشکل شکل خاصی دارد (با پایه، سمت راست غیر منفی است). با استفاده از روش سیمپلکس قابل حل است.
منصحنه.نوشتن مسئله در جدول سیمپلکس بین سیستم محدودیت های مسئله (3.10) و جدول سیمپلکس مطابقت یک به یک وجود دارد. تعداد سطرها در جدول به تعداد مساوات در سیستم محدودیت وجود دارد و به تعداد متغیرهای آزاد ستون وجود دارد. متغیرهای پایه ستون اول را پر می کنند، متغیرهای آزاد - ردیف بالای جدول. خط پایین، خط شاخص نامیده می شود؛ این خط شامل ضرایب متغیرهای تابع هدف است. اگر عبارت آزاد در تابع وجود نداشته باشد ابتدا 0 در گوشه سمت راست پایین نوشته می شود. اگر وجود دارد، آن را با علامت مخالف می نویسیم. در این مکان (در گوشه پایین سمت راست) مقدار تابع هدف وجود خواهد داشت که هنگام حرکت از یک جدول به جدول دیگر، باید مدول آن افزایش یابد. بنابراین، سیستم محدودیت های ما با جدول 3.4 مطابقت دارد و می توانیم به مرحله دوم راه حل برویم.
جدول 3.4
|
خط پایه |
رایگان |
||
IIصحنه... بررسی طرح پشتیبانی برای بهینه بودن
این جدول 3.4 با طرح پایه زیر مطابقت دارد:
(ایکس 1 , ایکس 2 , ایکس 3 , ایکس 4 , ایکس 5) = (0, 0, 50, 40, 80).
متغیرهای رایگان ایکس 1 , ایکس 2 برابر با 0 است. ایکس 1 = 0, ایکس 2 = 0. و متغیرهای اساسی ایکس 3 , ایکس 4 , ایکس 5 ارزش ها را در نظر بگیرید ایکس 3 = 50, ایکس 4 = 40, ایکس 5 = 80 - از ستون اعضای آزاد. مقدار تابع هدف:
-اف = - 5ایکس 1 - 3ایکس 2 = -5 0 - 3 0 = 0.
وظیفه ما این است که بررسی کنیم آیا یک طرح پایه داده شده بهینه است یا خیر. برای این، شما باید خط شاخص - خط تابع هدف را مشاهده کنید اف.
شرایط مختلف ممکن است.
1. در شاخص اف-رشته هیچ عنصر منفی ندارد. این بدان معنی است که طرح بهینه است، شما می توانید راه حل مشکل را بنویسید. تابع هدف به مقدار بهینه خود برابر با عددی که در گوشه سمت راست پایین با علامت مخالف گرفته شده است، رسیده است. به مرحله IV می رویم.
2. ردیف شاخص حداقل یک عنصر منفی دارد که ستون آن هیچ عنصر مثبتی ندارد. سپس نتیجه می گیریم که تابع هدف اف→ ∞ بی حد و حصر کاهش می یابد.
3. ردیف شاخص حاوی یک عنصر منفی با حداقل یک عنصر مثبت در ستون آن است. سپس به مرحله سوم بعدی می رویم. محاسبه مجدد جدول، بهبود خط مبنا.
IIIصحنه... بهبود خط پایه
از عناصر شاخص منفی اف- سطرها بزرگترین مدول را انتخاب می کنند، ستون مربوطه را Resolving فراخوانی کرده و "" را علامت گذاری می کنند.
برای انتخاب ردیف حل، باید نسبت عناصر ستون عضو آزاد محاسبه شود فقطبه مثبتعناصر ستون مجاز حداقل را از روابط به دست آمده انتخاب کنید. عنصر متناظری که در آن به حداقل رسیده است، مجاز نامیده می شود. ما آن را با یک مربع برجسته می کنیم.
در مثال ما، 
، عنصر 2 مجاز است. خط مربوط به این عنصر را حل نیز می نامند (جدول 3.5).
جدول 3.5
با انتخاب عنصر حل، جدول را طبق قوانین دوباره محاسبه می کنیم:
1. در جدول جدید با همان ابعاد قبلی، متغیرهای سطر و ستون حل شونده مبادله می شوند که مربوط به انتقال به یک مبنای جدید است. در مثال ما: ایکس 1 در پایه گنجانده شده است، به جای ایکس 5، که پایه را ترک می کند و اکنون رایگان است (جدول 3.6).
جدول 3.6
|
خط پایه |
رایگان |
||
2. به جای حل عنصر 2، عدد معکوس آن را بنویسید.
3. عناصر خط تفکیک به عنصر تفکیک کننده تقسیم می شوند.
4. عناصر ستون تفکیک کننده به عنصر تفکیک کننده تقسیم می شوند و با علامت مخالف نوشته می شوند.
5. برای پر کردن عناصر باقی مانده از جدول 3.6، طبق قانون مستطیل دوباره محاسبه می کنیم. فرض کنید می خواهیم عنصر را در موقعیت 50 بشماریم.
ما این عنصر را به صورت ذهنی با حل کننده وصل می کنیم، محصول را پیدا می کنیم، حاصلضرب عناصر واقع در مورب دیگر مستطیل حاصل را کم می کنیم. ما تفاوت را بر عنصر حل کننده تقسیم می کنیم.
بنابراین، . به جایی که 50 بود عدد 10 را می نویسیم. به همین ترتیب :
, 
, , 
.
جدول 3.7
ما یک جدول جدید 3.7 داریم، متغیرهای اصلی اکنون متغیرها هستند (x 3، x 4، x 1). مقدار تابع هدف برابر 200- شد، یعنی کاهش یافت. برای بررسی بهینه بودن این راه حل اساسی، لازم است دوباره به مرحله دوم بروید. فرآیند به وضوح متناهی است، معیارهای توقف، نقاط 1 و 2 مرحله II است.
راه حل مشکل را تا انتها خواهیم آورد. برای انجام این کار، ردیف شاخص را بررسی کنید و با مشاهده یک عنصر منفی در آن، ستون مربوطه را حل کنید و طبق مرحله III، جدول را دوباره محاسبه کنید. پس از جمع آوری روابط و انتخاب از بین آنها حداقل = 40، عنصر حل کننده 1 را تعیین کردیم. اکنون محاسبه مجدد را طبق قوانین 2-5 انجام می دهیم.
جدول 3.8
|
خط پایه |
رایگان |
||
|
x 3 = 30، ایکس 2 = 40, ایکس 1 = 20. متغیرهای رایگان 0 هستند، ایکس 5 = 0, ایکس 4 = 0. تابع هدف مقدار آخرین عنصر ستون اعضای آزاد را با علامت مخالف می گیرد: - اف = -220 اف = 220، در مثال ما تابع برای min و در ابتدا مورد بررسی قرار گرفت افحداکثر، بنابراین علامت در واقع دو بار تغییر کرد. بنابراین، ایکس* = (20, 40, 30, 0, 0), اف* = 220. پاسخ مسئله: شامل 20 محصول از نوع ضروری است آ، 40 محصول از نوع B، در حالی که سود حداکثر و برابر با 220 روبل خواهد بود. در پایان این بخش، نمودار بلوکی الگوریتم روش سیمپلکس را ارائه می دهیم که دقیقاً مراحل را تکرار می کند، اما، شاید، برای برخی از خوانندگان استفاده از آن راحت تر باشد، زیرا فلش ها جهت روشن عمل را نشان می دهند. پیوندهای بالای مستطیل ها در فلوچارت نشان می دهد که گروه تبدیل مربوطه به کدام مرحله یا زیرمجموعه تعلق دارد. قانون برای یافتن طرح پایه اولیه در بند 3.7 فرموله خواهد شد.
سوالاتی برای خودکنترلی 1. جدول سیمپلکس چگونه ساخته می شود؟ 2. تغییر مبنا چگونه در جدول منعکس می شود؟ 3. یک معیار توقف برای روش سیمپلکس فرموله کنید. 4. چگونه محاسبه مجدد جدول را سازماندهی کنیم؟ 5. شروع محاسبه مجدد جدول از کدام خط راحت است؟ |
... الگوریتم روش سیمپلکس
مثال 5.1.مسئله برنامه ریزی خطی زیر را با استفاده از روش سیمپلکس حل کنید:
راه حل:
من تکرار:
x3, x4, x5, x6 x1,x2... بیایید متغیرهای اصلی را بر حسب متغیرهای آزاد بیان کنیم:
اجازه دهید تابع هدف را به شکل زیر بیاوریم:
بر اساس مسئله به دست آمده، جدول سیمپلکس اولیه را تشکیل می دهیم:
جدول 5.3
جدول سیمپلکس منبع
روابط ارزش گذاری |
||||
طبق تعریف راه حل پایه، متغیرهای آزاد برابر با صفر و مقادیر متغیرهای پایه برابر با مقادیر متناظر اعداد آزاد هستند، یعنی:
مرحله 3: بررسی سازگاری سیستم محدودیت LPP.
در این تکرار (در جدول 5.3)، علامت ناسازگاری سیستم محدودیت ها (علامت 1) مشخص نشد (یعنی هیچ ردیفی با عدد آزاد منفی (به جز خط تابع هدف) وجود ندارد که این کار را انجام می دهد. حاوی حداقل یک عنصر منفی (یعنی ضریب منفی در یک متغیر آزاد)).
در این تکرار (در جدول 5.3)، علامت نامحدود بودن تابع هدف (علامت 2) مشخص نشد (یعنی هیچ ستونی با عنصر منفی در خط تابع هدف وجود ندارد (به جز ستون آزاد). اعداد)، که در آن حداقل یک عنصر مثبت وجود نخواهد داشت) ...
از آنجایی که محلول پایه یافت شده حاوی اجزای منفی نیست، قابل قبول است.
مرحله 6: بررسی بهینه بودن.
راه حل پایه یافت شده بهینه نیست، زیرا با توجه به معیار بهینه (ویژگی 4) نباید هیچ عنصر منفی در خط تابع هدف وجود داشته باشد (تعداد آزاد این خط در هنگام در نظر گرفتن این ویژگی در نظر گرفته نمی شود). بنابراین طبق الگوریتم روش سیمپلکس به مرحله هشتم می رویم.
از آنجایی که راه حل اصلی یافت شده قابل قبول است، جستجوی ستون حل مطابق با طرح زیر انجام می شود: ما ستون هایی را با عناصر منفی در خط تابع هدف تعیین می کنیم (به جز ستون اعداد آزاد). مطابق جدول 5.3، دو ستون از این قبیل وجود دارد: ستون " x1"و ستون" x2". از بین این ستون ها، ستونی انتخاب می شود که کوچکترین عنصر در خط تابع هدف را داشته باشد. او حل خواهد شد گوینده " x2"حاوی کوچکترین عنصر (-3) در مقایسه با ستون" x1
برای تعیین خط حل، نسبت های ارزیابی مثبت اعداد آزاد به عناصر ستون حل را پیدا می کنیم، خطی که مربوط به کوچکترین نسبت ارزیابی مثبت است، به عنوان مجاز در نظر گرفته می شود.
جدول 5.4
جدول سیمپلکس منبع
در جدول 5.4، کوچکترین نسبت تخمینی مثبت مربوط به خط " x5"، بنابراین، حل خواهد شد.
عنصری که در تقاطع ستون مجوز و خط مجاز قرار دارد به عنوان مجاز پذیرفته می شود. در مثال ما، این عنصری است که در تقاطع خط " x5"و ستون ها" x2».
عنصر حل‌کننده یک متغیر پایه و یک متغیر آزاد را نشان می‌دهد که باید در جدول سیمپلکس مبادله شوند تا به یک راه‌حل پایه "بهبود" جدید منتقل شوند. در این مورد، اینها متغیر هستند x5و x2، در جدول جدید سیمپلکس (جدول 5.5) آنها را با هم عوض می کنیم.
9.1. تبدیل عنصر رزولوشن
عنصر مجاز جدول 5.4 به صورت زیر تبدیل می شود:
ما نتیجه به دست آمده را در یک سلول مشابه در جدول 5.5 وارد می کنیم.
9.2. رشته رزولوشن را تبدیل کنید
ما عناصر خط حل جدول 5.4 را بر عنصر حل این جدول سیمپلکس تقسیم می کنیم، نتایج در سلول های مشابه جدول سیمپلکس جدید قرار می گیرند (جدول 5.5). تبدیل عناصر خط تفکیک در جدول 5.5 آورده شده است.
9.3. تبدیل ستون رزولوشن
عناصر ستون حل جدول 5.4 بر عنصر تفکیک کننده جدول سیمپلکس داده شده تقسیم می شوند و نتیجه با علامت مخالف گرفته می شود. نتایج به‌دست‌آمده در سلول‌های مشابه جدول سیمپلکس جدید قرار می‌گیرد (جدول 5.5). تبدیل عناصر ستون تفکیک کننده در جدول 5.5 نشان داده شده است.
9.4. بقیه عناصر جدول سیمپلکس را تبدیل کنید.
تبدیل عناصر باقی مانده از جدول سیمپلکس (یعنی عناصری که در خط حل و ستون تفکیک قرار ندارند) طبق قانون "مستطیل" انجام می شود.
به عنوان مثال، تبدیل یک عنصر واقع در تقاطع رشته را در نظر بگیرید " x3"و ستون" "، ما به طور معمول آن را به عنوان" x3". در جدول 5.4، به صورت ذهنی یک مستطیل رسم کنید که یک راس آن در سلول قرار دارد، مقدار آن را تبدیل می کنیم (یعنی در سلول " x3»)، و دیگری (راس مورب) در سلول با عنصر تفکیک کننده است. دو راس دیگر (مورب دوم) به طور منحصر به فرد تعیین می شوند. سپس مقدار تبدیل شده سلول " x3برابر با مقدار قبلی این خانه منهای کسری خواهد بود که در مخرج آن یک عنصر تفکیک کننده (از جدول 5.4) و در صورتگر حاصل ضرب دو راس استفاده نشده دیگر وجود دارد، یعنی:
« x3»: .
مقادیر سایر سلول ها به طور مشابه تغییر می کنند:
« x3 x1»: ;
« x4»: 
;
« x4 x1»: ;
« x6»: 
;
« x6 x1»: ;
«»: 
;
« x1»: 
.
در نتیجه این تبدیل ها، یک جدول سیمپلکس جدید به دست آمد (جدول 5.5).
II تکرار:
مرحله 1: تهیه جدول سیمپلکس.
جدول 5.5
میز سیمپلکسII تکرارها
تخمین زده ارتباط |
||||
| ||||
|
|
مرحله 2: تعیین راه حل اساسی.
در نتیجه تبدیل های سیمپلکس، یک راه حل اساسی جدید به دست آمد (جدول 5.5):
همانطور که می بینید، با این راه حل پایه، مقدار تابع هدف = 15، که بیشتر از راه حل اولیه قبلی است.
ناسازگاری سیستم محدودیت ها مطابق با ویژگی 1 در جدول 5.5 آشکار نشد.
مرحله 4: بررسی محدودیت تابع هدف.
نامحدود بودن تابع هدف مطابق با ویژگی 2 در جدول 5.5 آشکار نشد.
مرحله 5: بررسی قابل قبول بودن راه حل اساسی یافت شده.
راه حل اصلی یافت شده مطابق با ویژگی 4 بهینه نیست، زیرا خط تابع هدف جدول سیمپلکس (جدول 5.5) حاوی یک عنصر منفی است: -2 (عدد آزاد این خط در هنگام در نظر گرفتن این مورد در نظر گرفته نمی شود. ویژگی). بنابراین به مرحله 8 می رویم.
مرحله 8: تعیین عنصر تفکیک کننده.
8.1. تعریف ستون رزولوشن
راه حل اصلی یافت شده قابل قبول است، ما ستون ها را با عناصر منفی در خط تابع هدف تعریف می کنیم (به جز ستون اعداد آزاد). مطابق جدول 5.5، تنها یک ستون چنین ستونی است: x1". بنابراین ما آن را به عنوان مجاز می پذیریم.
8.2. تعیین رشته مجوز
با توجه به مقادیر به‌دست‌آمده نسبت‌های ارزیابی مثبت در جدول 5.6، حداقل، نسبت مربوط به خط «است. x3". بنابراین ما آن را به عنوان مجاز می پذیریم.
جدول 5.6
میز سیمپلکسII تکرارها
تخمین زده ارتباط |
||||
3/1 = 3 - دقیقه |
||||
مرحله 9: تبدیل جدول سیمپلکس.
تبدیل های جدول ساده (جدول 5.6) به همان روشی که در تکرار قبلی انجام شد انجام می شود. نتایج تبدیل عناصر یک جدول سیمپلکس در جدول 5.7 نشان داده شده است.
III تکرار
بر اساس نتایج تبدیل سیمپلکس تکرار قبلی، یک جدول سیمپلکس جدید ایجاد می کنیم:
جدول 5.7
میز سیمپلکسIII تکرارها
تخمین زده ارتباط |
||||
| ||||
|
|
مرحله 2: تعیین راه حل اساسی.
در نتیجه تبدیل های سیمپلکس، یک راه حل اساسی جدید به دست آمد (جدول 5.7):
مرحله 3: بررسی سازگاری سیستم محدودیت ها.
ناسازگاری سیستم محدودیت ها مطابق با ویژگی 1 در جدول 5.7 آشکار نشد.
مرحله 4: بررسی محدودیت تابع هدف.
نامحدود بودن تابع هدف مطابق با ویژگی 2 در جدول 5.7 آشکار نشد.
مرحله 5: بررسی قابل قبول بودن راه حل اساسی یافت شده.
راه حل اساسی یافت شده مطابق با ویژگی 3 قابل قبول است، زیرا حاوی اجزای منفی نیست.
مرحله 6: بررسی بهینه بودن راه حل اساسی یافت شده.
راه حل اصلی یافت شده مطابق با ویژگی 4 بهینه نیست، زیرا خط تابع هدف جدول سیمپلکس (جدول 5.7) حاوی یک عنصر منفی است: -3 (عدد آزاد این خط در هنگام در نظر گرفتن این مورد در نظر گرفته نمی شود. ویژگی). بنابراین به مرحله 8 می رویم.
مرحله 8: تعیین عنصر تفکیک کننده.
8.1. تعریف ستون رزولوشن
راه حل اصلی یافت شده قابل قبول است، ما ستون ها را با عناصر منفی در خط تابع هدف تعریف می کنیم (به جز ستون اعداد آزاد). مطابق جدول 5.7، تنها یک ستون چنین ستونی است: x5". بنابراین ما آن را به عنوان مجاز می پذیریم.
8.2. تعیین رشته مجوز
با توجه به مقادیر به‌دست‌آمده نسبت‌های ارزیابی مثبت در جدول 5.8، حداقل، نسبت مربوط به خط «است. x4". بنابراین ما آن را به عنوان مجاز می پذیریم.
جدول 5.8
میز سیمپلکسIII تکرارها
تخمین زده ارتباط |
||||
5/5 = 1 - دقیقه |
||||
مرحله 9: تبدیل جدول سیمپلکس.
تبدیل های جدول سیمپلکس (جدول 5.8) به همان روشی که در تکرار قبلی انجام شد انجام می شود. نتایج تبدیل عناصر یک جدول سیمپلکس در جدول 5.9 نشان داده شده است.
IV تکرار
مرحله 1: ساخت جدول سیمپلکس جدید.
بر اساس نتایج تبدیل سیمپلکس تکرار قبلی، یک جدول سیمپلکس جدید ایجاد می کنیم:
جدول 5.9
میز سیمپلکسIV تکرارها
تخمین زده ارتباط |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
مرحله 2: تعیین راه حل اساسی.
در نتیجه تبدیل های سیمپلکس، یک راه حل اساسی جدید به دست آمد که مطابق جدول 5.9، جواب به شرح زیر است:
مرحله 3: بررسی سازگاری سیستم محدودیت ها.
ناسازگاری سیستم محدودیت ها مطابق با ویژگی 1 در جدول 5.9 آشکار نشد.
مرحله 4: بررسی محدودیت تابع هدف.
نامحدود بودن تابع هدف مطابق با ویژگی 2 در جدول 5.9 آشکار نشد.
مرحله 5: بررسی قابل قبول بودن راه حل اساسی یافت شده.
راه حل اساسی یافت شده مطابق با ویژگی 3 قابل قبول است، زیرا حاوی اجزای منفی نیست.
مرحله 6: بررسی بهینه بودن راه حل اساسی یافت شده.
راه حل اساسی یافت شده مطابق با ویژگی 4 بهینه است، زیرا هیچ عنصر منفی در خط تابع هدف جدول سیمپلکس (جدول 5.9) وجود ندارد (عدد آزاد این خط در هنگام در نظر گرفتن این ویژگی در نظر گرفته نمی شود) .
مرحله 7: بررسی جایگزین راه حل.
راه حل یافت شده تنها راه حل است، زیرا هیچ عنصر صفر در خط تابع هدف وجود ندارد (جدول 5.9) (عدد آزاد این خط در هنگام در نظر گرفتن این ویژگی در نظر گرفته نمی شود).
پاسخ: مقدار بهینه تابع هدف مسئله در نظر گرفته شده = 24 است که در آن به دست می آید.
مثال 5.2.مشکل برنامه ریزی خطی بالا را با این شرط حل کنید که تابع هدف حداقل باشد:
راه حل:
من تکرار:
مرحله 1: تشکیل جدول سیمپلکس اولیه.
مسئله برنامه ریزی خطی اصلی به صورت استاندارد ارائه شده است. اجازه دهید با وارد کردن یک متغیر غیر منفی اضافی در هر یک از محدودیت‌های نابرابری، آن را به شکل متعارف خود برسانیم.
در سیستم معادلات حاصل، متغیرهای مجاز (پایه) را در نظر می گیریم x3, x4, x5, x6، سپس متغیرهای رایگان خواهند بود x1,x2... اجازه دهید متغیرهای اساسی را بر حسب متغیرهای آزاد بیان کنیم.
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | |||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| - | x 1 | + | x 2 | - | S 1 | + | R 1 | = | 1 | |||||||||||
| x 1 | +3 | x 2 | + | S 2 | = | 15 | ||||||||||||||
| - | 2 | x 1 | + | x 2 | + | S 3 | = | 4 |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | St. عضو | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W - 0 |
| - | x 1 | + | x 2 | - | S 1 | = | 1 | ||||||||||
| 4 | x 1 | + | 3 | S 1 | + | S 2 | = | 12 | |||||||||
| - | x 1 | + | S 1 | + | S 3 | = | 3 |
| x 1 | x 2 | S 1 | S 2 | S 3 | St. عضو | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F - 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F - 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F - 13 = 0 => F = 13 |
هدف خدمات... این سرویس برای حل آنلاین مسائل برنامه نویسی خطی (LPP) با استفاده از روش سیمپلکس در اشکال نمادگذاری زیر طراحی شده است:
- در قالب یک جدول سیمپلکس (روش تبدیل جردن)؛ شکل اولیه ثبت؛
- روش سیمپلکس اصلاح شده؛ به شکل ستونی؛ به صورت خطی
دستورالعمل. تعداد متغیرها و تعداد خطوط (تعداد محدودیت) را انتخاب کنید. راه حل به دست آمده در یک فایل Word و Excel ذخیره می شود.
در این مورد، محدودیت های نوع x i ≥ 0 را در نظر نگیرید. اگر در کار برای برخی از x i هیچ محدودیتی وجود ندارد، LPP باید به CLP آورده شود یا از این سرویس استفاده کنید. راه حل به طور خودکار استفاده از روش M(روش ساده با پایه مصنوعی) و روش سیمپلکس دو مرحله ای.موارد زیر نیز با این ماشین حساب استفاده می شود:
روش گرافیکی برای حل LPP
راه حل مشکل حمل و نقل
راه حل بازی ماتریس
با استفاده از سرویس آنلاین، می توانید قیمت یک بازی ماتریسی (کران های پایین و بالا) را تعیین کنید، وجود یک نقطه زینتی را بررسی کنید، با استفاده از روش های زیر راه حلی برای استراتژی ترکیبی پیدا کنید: مینی ماکس، روش سیمپلکس، گرافیکی (هندسی) روش، روش براون.
حداکثر یک تابع از دو متغیر
مشکلات برنامه نویسی پویا
5 کالای همگن را بین سه بازار توزیع کنید تا حداکثر درآمد را از فروش آنها بدست آورید. درآمد حاصل از فروش در هر بازار G (X) به تعداد انبوه کالاهای فروخته شده X بستگی دارد و در جدول ارائه شده است.
| حجم کالا X (در لات) | درآمد G (X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
الگوریتم روش سیمپلکسشامل مراحل زیر است:
- ترسیم اولین طرح پایه انتقال به شکل متعارف مسئله برنامه ریزی خطی با معرفی متغیرهای تعادل اضافی غیر منفی.
- بررسی بهینه بودن طرح... اگر حداقل یک ضریب ردیف شاخص کمتر از صفر باشد، طرح بهینه نیست و نیاز به بهبود دارد.
- تعریف ستون و ردیف پیشرو... از ضرایب منفی ردیف شاخص، بزرگترین ضرایب در مقدار مطلق انتخاب می شود. سپس عناصر ستون اعضای آزاد جدول سیمپلکس به عناصری از همان علامت ستون پیشرو تقسیم می شوند.
- ساختن یک طرح مرجع جدید... انتقال به یک طرح جدید در نتیجه محاسبه مجدد جدول سیمپلکس با استفاده از روش جردن-گاوس انجام می شود.
اگر لازم است حد فاصل تابع هدف را پیدا کنیم، در این صورت ما در مورد یافتن مقدار حداقل (F (x) → min، به مثال حل کمینه سازی تابع) و مقدار حداکثر ((F (x) → صحبت می کنیم. max، مثال حل تابع بیشینه سازی را ببینید)
راه حل شدید در مرز ناحیه راه حل های امکان پذیر در یکی از رئوس نقاط گوشه چند ضلعی، یا در بخش بین دو نقطه گوشه مجاور به دست می آید.
قضیه اساسی برنامه ریزی خطی... اگر تابع هدف LPP در نقطه ای در منطقه راه حل های امکان پذیر به یک مقدار شدید برسد، آنگاه این مقدار را در نقطه گوشه می گیرد. اگر تابع هدف LPP در بیش از یک نقطه گوشه به مقدار نهایی خود برسد، در هر یک از ترکیب خطی محدب این نقاط همان مقدار را می گیرد.
ماهیت روش سیمپلکس... حرکت به نقطه بهینه با حرکت از یک نقطه گوشه به نقطه همسایه انجام می شود که به X opt نزدیکتر و سریعتر است. چنین طرحی برای شمارش نقاط، روش سیمپلکس نامیده می شود، پیشنهاد شده توسط R. Danzig.
نقاط گوشه با m متغیرهای پایه مشخص می شوند، بنابراین، انتقال از یک نقطه گوشه به نقطه همسایه را می توان با تغییر در پایه تنها یک متغیر اساسی به یک متغیر از غیر مبنا انجام داد.
اجرای روش سیمپلکس با توجه به ویژگی‌ها و فرمول‌بندی‌های مختلف مسائل LP، تغییرات مختلفی دارد.
ساخت جداول سیمپلکس تا رسیدن به یک راه حل بهینه ادامه می یابد. چگونه می توان از جدول سیمپلکس برای تعیین بهینه بودن راه حل یک مسئله برنامه ریزی خطی استفاده کرد؟
اگر خط آخر (مقادیر تابع هدف) حاوی عناصر منفی نباشد، طرح بهینه را پیدا می کند.
نکته 1. اگر یکی از متغیرهای اساسی برابر با صفر باشد، نقطه انتهایی مربوط به چنین راه حل اساسی منحط است. انحطاط زمانی رخ می دهد که در انتخاب راهنمای خط ابهامی وجود داشته باشد. اگر خط دیگری را به عنوان راهنما انتخاب کنید، ممکن است اصلا متوجه انحطاط مشکل نشوید. در صورت ابهام، ردیفی را که کمترین شاخص را دارد انتخاب کنید تا از حلقه زدن جلوگیری شود.
نکته 2. فرض کنید که در یک نقطه افراطی همه تفاوت های سیمپلکس غیر منفی D k ³ 0 (k = 1..n + m) هستند، یعنی. یک راه حل بهینه به دست می آید، و یک بردار غیرمبنا - A k وجود دارد که برای آن D k = 0 است. سپس حداکثر در دو نقطه به دست می آید، یعنی: یک بهینه جایگزین وجود دارد. اگر این متغیر x k را به مبنا وارد کنیم، مقدار تابع هدف تغییر نخواهد کرد.
نکته 3. راه حل مسئله دوگانه در آخرین جدول سیمپلکس یافت می شود. آخرین m مولفه های بردار تفاوت های سیمپلکس (در ستون های متغیرهای تعادل) راه حل بهینه برای مسئله دوگانه است. مقادیر توابع هدف مسائل مستقیم و دوگانه در نقاط بهینه منطبق هستند.
نکته 4. هنگام حل مسئله کمینه سازی، بردار با بزرگترین اختلاف سیمپلکس مثبت به پایه وارد می شود. علاوه بر این، همان الگوریتم برای مسئله بیشینه سازی اعمال می شود.
اگر شرط "لازم است که مواد خام نوع III به طور کامل مصرف شود"، شرط مربوطه برابری است.
مشکلات برنامه نویسی خطی این در یک ساختار متوالی است که فرآیند مورد بررسی را مشخص می کند. راه حل به سه مرحله اصلی تقسیم می شود: انتخاب متغیرها، ساختن سیستمی از محدودیت ها و جستجوی تابع هدف.
بر اساس این تقسیم، شرط مسئله را می توان به صورت زیر بازنویسی کرد: حد فاصل تابع هدف Z (X) = f (x1, x2, ..., xn) → max (min) و متغیرهای مربوطه، در صورت وجود معلوم است که آنها سیستم قیود را برآورده می کنند: Φ_i (x1, x2,…, xn) = 0 برای i = 1, 2,…, k؛ Φ_i (x1, x2,…, xn)) 0 برای i = k + 1 , k + 2,…, m.
نظام محدودیت ها باید به شکل متعارف درآید، یعنی. به سیستم معادلات خطی، که در آن تعداد متغیرها از تعداد معادلات بیشتر است (m> k). در این سیستم مطمئناً متغیرهایی وجود خواهند داشت که می توان آنها را در قالب متغیرهای دیگر بیان کرد و اگر اینطور نیست، می توان آنها را به صورت مصنوعی معرفی کرد. در این صورت به اولی مبنا یا مبنا مصنوعی و دومی را آزاد می گویند.
در نظر گرفتن روش سیمپلکس با استفاده از یک مثال خاص راحت تر است. فرض کنید یک تابع خطی f (x) = 6x1 + 5x2 + 9x3 و سیستمی از قیود داده شود: 5x1 + 2x2 + 3x3 ≤ 25؛ x1 + 6x2 + 2x3 ≤ 20؛ 4x1 + 3x3 ≤ 18 مورد نیاز است. حداکثر مقدار تابع f (x).
راه حل در مرحله اول، راه حل اولیه (پشتیبانی) سیستم معادلات را به صورت کاملا دلخواه مشخص کنید، که باید سیستم محدودیت های داده شده را برآورده کند. در این مورد، معرفی یک مصنوعی مورد نیاز است، یعنی. متغیرهای پایه x4، x5 و x6 به شرح زیر است: 5x1 + 2x2 + 3x3 + x4 = 25؛ x1 + 6x2 + 2x3 + x5 = 20؛ 4x1 + 3x3 + x6 = 18.
همانطور که می بینید، نابرابری ها به لطف متغیرهای اضافه شده x4، x5، x6 که مقادیر غیر منفی هستند، به برابری تبدیل شده اند. بنابراین، شما سیستم را به یک شکل متعارف رسانده اید. متغیر x4 در معادله اول با ضریب 1 و در دو - با ضریب 0 ظاهر می شود، همین امر برای متغیرهای x5، x6 و معادلات مربوطه که مطابق با تعریف مبنا است، صادق است.
شما سیستم را آماده کرده اید و راه حل پشتیبانی اولیه را پیدا کرده اید - X0 = (0، 0، 0، 25، 20، 18). حال ضرایب متغیرها و عبارات آزاد معادلات (اعداد سمت راست علامت "=") را در قالب جدول برای بهینه سازی محاسبات بیشتر ارائه دهید (شکل را ببینید).
ماهیت روش سیمپلکس این است که این جدول را به شکلی بیاوریم که در آن تمام ارقام ردیف L مقادیر غیر منفی باشند. اگر معلوم شد که این غیرممکن است، سیستم به هیچ وجه راه حل بهینه ای ندارد. ابتدا کوچکترین عنصر این خط را انتخاب کنید، این -9 است. عدد در ستون سوم است. متغیر مربوطه x3 را به پایه یک تبدیل کنید. برای انجام این کار، خط را بر 3 تقسیم کنید تا 1 در سلول به دست آید.
حالا باید سلول ها را به 0 تبدیل کنید. برای این کار، از ارقام مربوط به ردیف سوم 3 کم کنید. از عناصر ردیف دوم - عناصر سوم، ضرب در 2. و در نهایت، از عناصر خط L - ضرب در (-9). شما راه حل مرجع دوم را دریافت کردید: f (x) = L = 54 در x1 = (0، 0، 6، 7، 8، 0).
