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

راه حل:

من تکرار:

x3, x4, x5, x6 x1,x2. بیایید متغیرهای اصلی را بر حسب متغیرهای آزاد بیان کنیم:

اجازه دهید تابع هدف را به شکل زیر کاهش دهیم:

بر اساس مسئله به دست آمده، جدول سیمپلکس اولیه را تشکیل می دهیم:

جدول 5.3

میز سیمپلکس اصلی

طبق تعریف راه حل پایه، متغیرهای آزاد برابر با صفر و مقادیر متغیرهای پایه برابر با مقادیر متناظر اعداد آزاد هستند، یعنی:

مرحله 3: بررسی سازگاری سیستم محدودیت PAP.

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

در این تکرار (در جدول 5.3)، علامت نامحدود بودن تابع هدف (علامت 2) مشخص نشد (یعنی هیچ ستونی با عنصر منفی در ردیف تابع هدف وجود ندارد (به جز ستون اعداد آزاد ) که در آن حداقل یک عنصر مثبت وجود نخواهد داشت).

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

مرحله 6: بررسی بهینه

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

از آنجایی که راه حل اصلی یافت شده قابل قبول است، ما ستون حل را مطابق طرح زیر جستجو می کنیم: ستون هایی را با عناصر منفی در ردیف تابع هدف تعیین می کنیم (به جز ستون اعداد آزاد). طبق جدول 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 تکرارها

مرحله 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 تکرارها

مرحله 9: تبدیل جدول سیمپلکس.

تبدیل جدول سیمپلکس (جدول 5.8) به همان روشی که در تکرار قبلی انجام شد انجام می شود. نتایج تبدیل عناصر جدول سیمپلکس در جدول 5.9 آورده شده است.

IV تکرار

مرحله 1: ساخت جدول سیمپلکس جدید.

بر اساس نتایج تبدیل سیمپلکس تکرار قبلی، ما یک جدول سیمپلکس جدید ایجاد می کنیم:

جدول 5.9

میز سیمپلکسIV تکرارها

مرحله 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. اجازه دهید متغیرهای اساسی را بر حسب متغیرهای آزاد بیان کنیم.

نظریه مختصر

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

در ارتباط با قضیه اصلی برنامه‌ریزی خطی، طبیعتاً فکر راه حل زیر برای حل LLP با هر تعداد متغیر مطرح می‌شود. به نوعی تمام نقاط انتهایی چند وجهی پلان ها را بیابید (از آنها بیشتر نیست) و مقادیر تابع هدف را در آنها مقایسه کنید. چنین راه حلی، حتی با تعداد نسبتاً کمی متغیر و محدودیت، عملاً غیرممکن است، زیرا فرآیند یافتن نقاط افراطی از نظر دشواری با حل مسئله اصلی قابل مقایسه است و علاوه بر این، تعداد نقاط انتهایی چند وجهی پلان ها می تواند معلوم می شود بسیار بزرگ است. در ارتباط با این مشکلات، مشکل شمارش منطقی نقاط افراطی مطرح شد.

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

1. توانایی یافتن یک طرح مرجع اولیه؛
2. وجود نشانه ای از بهینه بودن طرح مرجع؛
3. توانایی حرکت به غیر بدترین طرح مرجع.

نمونه ای از راه حل مسئله

وضعیت مشکل

برای فروش سه گروه کالا، یک بنگاه تجاری دارای سه نوع منابع محدود مادی و پولی به میزان , , , واحد است. در همان زمان، برای فروش 1 گروه کالا به قیمت 1000 روبل. گردش کالا، منبع نوع اول را به تعداد واحد، منبع نوع دوم را به تعداد واحد، منبع نوع سوم را به تعداد واحد مصرف می کند. برای فروش 2 و 3 گروه کالا به قیمت 1 هزار روبل. گردش کالا با توجه به منبع نوع اول به مبلغ، واحد، منابع نوع دوم به مبلغ، واحد، منابع نوع سوم به مبلغ، واحد هزینه می شود. سود حاصل از فروش سه گروه کالا به مبلغ 1000 روبل. گردش مالی به ترتیب هزار روبل است.

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

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

راه حل مشکل

ساختمان نمونه

اجازه دهید به ترتیب گردش کالاهای 1، 2 و سوم را مشخص کنیم.

سپس تابع هدف بیانگر سود دریافتی است:

محدودیت منابع مادی و پولی:

علاوه بر این، با توجه به معنای تکلیف

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

کاهش به شکل متعارف ZLP

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

اگر سمت راست غیر منفی باشد، محدودیت شکل ارجح دارد سمت چپدارای یک متغیر شامل ضریب برابر با یک، و قیود برابری باقیمانده - با ضریب برابر با صفر است. در مورد ما، محدودیت های 1، 2، 3 دارای شکل ترجیحی با متغیرهای اساسی مربوطه هستند.

حل با روش سیمپلکس

جدول سیمپلکس تکرار 0 را پر می کنیم.

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

به صورت زیر به تکرار بعدی می رویم:

ستون پیشرو مربوط به .

ردیف کلید با حداقل نسبت عبارات آزاد و اعضای ستون اصلی (روابط ساده):

در تقاطع ستون کلید و ردیف کلید، عنصر فعال کننده، یعنی 7 را پیدا می کنیم.

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

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

جدول تکرار اول را دریافت می کنیم:

ستون کلید برای تکرار 1 با .

ما خط کلید را پیدا می کنیم، برای این تعریف می کنیم:

در تقاطع ستون کلید و ردیف کلید، عنصر فعال کننده را پیدا می کنیم، یعنی. 31/7.

بردار از مبنا گرفته شده و بردار معرفی می شود.

جدول تکرار دوم را دریافت می کنیم:

در ردیف شاخص، همه عبارت ها غیر منفی هستند، بنابراین راه حل زیر برای مسئله برنامه ریزی خطی به دست می آید (آن را از ستون عبارت های آزاد می نویسیم):

بنابراین، لازم است 7.1 هزار روبل بفروشید. کالاهای نوع 1 و 45.2 هزار روبل. کالاهای نوع 3 فروش یک محصول از نوع 2 به صرفه نیست. در این مورد، سود حداکثر و 237.4 هزار روبل خواهد بود. در صورت اجرای طرح بهینه، منبع باقی مانده از نوع 3 701 واحد خواهد بود.

مشکل LP دوگانه

اجازه دهید مدلی از مسئله دوگانه را بنویسیم.

برای ایجاد یک مسئله دوگانه، باید از قوانین زیر استفاده کنید:

1) اگر مشکل مستقیم به حداکثر حل شود، مشکل دوگانه به حداقل حل می شود و بالعکس.

2) در مسئله حداکثر، قیود نابرابری معنی ≤ و در مسئله کمینه سازی معنی ≥ دارند.

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

4) ماتریس سیستم محدودیت های مسئله دوگانه از ماتریس سیستم محدودیت های مسئله اصلی با جابجایی به دست می آید.

5) شرایط آزاد سیستم قیود مسئله مستقیم ضرایب متغیرهای متناظر تابع هدف مسئله دوگانه است و بالعکس.

6) اگر یک شرط غیر منفی بر متغیر مسئله مستقیم تحمیل شود، قید متناظر مسئله دوگانه به عنوان یک قید نابرابری نوشته می شود، اگر نه، پس به عنوان یک قید برابری نوشته می شود.

7) اگر هر محدودیتی از مسئله مستقیم به عنوان یک برابری نوشته شود، آنگاه شرط عدم منفی بر متغیر متناظر مسئله دوگانه اعمال نمی شود.

ماتریس مسئله اصلی را جابجا می کنیم:

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

حل مشکل LP دوگانه

مطابقت بین متغیرهای مسئله اصلی و دوگانه:

بر اساس جدول سیمپلکس، راه حل زیر برای مسئله برنامه ریزی خطی دوگانه به دست آمد (آن را از خط پایین می نویسیم):

بنابراین، منبع نوع اول کمیاب ترین است. امتیاز آن حداکثر و برابر است. منبع نوع سوم اضافی است - مقدار دوگانه آن صفر است. هر واحد اضافی از کالاهای گروه دوم فروخته شده باعث کاهش سود بهینه می شود
یک روش گرافیکی برای حل یک مسئله برنامه ریزی خطی (LPP) با دو متغیر در نظر گرفته شده است. نمونه ای از تکلیف آورده شده است شرح مفصلساختن نقاشی و یافتن راه حل

حل مشکل حمل و نقل
مسئله حمل و نقل، مدل ریاضی و روش‌های حل آن به تفصیل در نظر گرفته شده است - یافتن طرح مرجع با روش حداقل عنصر و جستجوی راه‌حل بهینه با روش پتانسیل.

تصمیم گیری در شرایط عدم قطعیت
حل یک بازی ماتریس آماری در شرایط عدم قطعیت با استفاده از معیارهای Wald، Savage، Hurwitz، Laplace و Bayes در نظر گرفته می‌شود. با استفاده از یک مسئله مثال، ساخت یک ماتریس پرداخت و یک ماتریس ریسک با جزئیات نشان داده شده است.

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

تابع هدف:

2x 1 +5x 2 +3x 3 +8x 4 → دقیقه

شرایط محدودیت:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

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

از آنجایی که مشکل ما یک مشکل کمینه سازی است، باید آن را به یک مشکل جستجوی حداکثر تبدیل کنیم. برای این کار، علائم ضرایب تابع هدف را به ضرایب مخالف تغییر می دهیم. عناصر اولین نابرابری را بدون تغییر می نویسیم، یک متغیر اضافی x 5 اضافه می کنیم و علامت "≤" را به "=" تغییر می دهیم. از آنجایی که نابرابری های دوم و سوم دارای علامت "≥" هستند، لازم است علائم ضرایب آنها معکوس شود و متغیرهای اضافی x 6 و x 7 به ترتیب وارد آنها شود. در نتیجه، یک مشکل معادل دریافت می کنیم:

3x 1 + 6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

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

از آنجایی که هیچ عنصر منفی در ستون اصطلاحات آزاد وجود ندارد، یک راه حل قابل قبول در ردیف F یافت شده است که به این معنی است که راه حل بهینه نیست. بیایید ستون اصلی را تعریف کنیم. برای انجام این کار، ما در ردیف F عنصر منفی را با حداکثر مدول خواهیم یافت - این -1.988 است. سطر پیشرو همانی خواهد بود که نسبت جمله آزاد به عنصر مربوطه ستون اصلی برای آن حداقل است. ردیف اول X2 و عنصر پیشرو: 0.313 است.

از آنجایی که هیچ عنصر منفی در رشته F وجود ندارد، متوجه شدیم راه حل بهینه. از آنجایی که وظیفه اصلی یافتن حداقل بود، راه حل بهینه عبارت آزاد رشته F خواهد بود که با علامت مخالف گرفته می شود. F=1.924
با مقادیر متغیر برابر: x 3 = 0.539، x 1 = 0.153. متغیرهای x 2 و x 4 در مبنا گنجانده نشده اند، بنابراین x 2 = 0 x 4 = 0.

در اینجا یک راه حل دستی (نه اپلت) دو مسئله با استفاده از روش سیمپلکس (مشابه حل اپلت) همراه با توضیحات مفصل به منظور درک الگوریتم حل مسائل با استفاده از روش سیمپلکس آورده شده است. مسئله اول فقط شامل علائم نابرابری "≤" (مسئله با پایه اولیه) است، دومی می تواند شامل علائم "≥"، "≤" یا "=" (مشکل با مبنای مصنوعی) باشد، آنها به طور متفاوت حل می شوند.

روش سیمپلکس، حل مسئله با پایه اولیه

1)روش سیمپلکسبرای مسئله ای با پایه اولیه (همه نشانه های محدودیت های نابرابری "≤").

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

این سیستم یک سیستم با مبنا است (مبنای s 1, s 2, s 3 که هر کدام تنها در یک معادله سیستم با ضریب 1 قرار می گیرند)، x 1 و x 2 متغیرهای آزاد هستند. مسائلی که باید با استفاده از روش سیمپلکس حل شوند باید دارای دو ویژگی زیر باشند: - سیستم قیود باید سیستمی از معادلات با پایه باشد. -ترجمه های آزاد تمامی معادلات در سیستم باید غیر منفی باشند.

سیستم به دست آمده یک سیستم با مبنا و شرایط رایگان آن غیر منفی است، بنابراین می توانیم اعمال کنیم روش سیمپلکس. بیایید اولین جدول سیمپلکس (تکرار 0) را برای حل مسئله ایجاد کنیم روش سیمپلکس، یعنی جدول ضرایب تابع هدف و سیستم معادلات برای متغیرهای مربوطه. در اینجا "BP" به معنای ستون متغیرهای اساسی است، "Solution" به معنای ستون سمت راست معادلات سیستم است. راه حل بهینه نیست، زیرا ضرایب منفی در ردیف z وجود دارد.

تکرار روش سیمپلکس 0

برای بهبود راه حل، اجازه دهید به تکرار بعدی برویم روش سیمپلکس، جدول سیمپلکس زیر را بدست می آوریم. برای انجام این کار باید انتخاب کنید فعال کردن ستون، یعنی متغیری که در تکرار بعدی روش سیمپلکس در پایه قرار می گیرد. با بزرگترین ضریب منفی مطلق در ردیف z (در حداکثر مسئله) انتخاب می شود - در تکرار اولیه روش سیمپلکس این ستون x 2 است (ضریب -6).

سپس انتخاب کنید رشته را فعال کنید، یعنی متغیری که در تکرار بعدی روش سیمپلکس پایه را ترک خواهد کرد. با کوچکترین نسبت ستون "تصمیم" به عناصر مثبت مربوط به ستون وضوح (ستون "نسبت") انتخاب می شود - در تکرار اولیه این ردیف s 3 است (ضریب 20).

عنصر مجازدر تقاطع ستون حل و ردیف حل است، سلول آن با رنگ برجسته شده است، برابر با 1. بنابراین، در تکرار بعدی روش سیمپلکس، متغیر x 2 جایگزین s 1 در پایه می شود. توجه داشته باشید که این رابطه در رشته z جستجو نشده است. اگر حداقل روابط یکسان وجود داشته باشد، هر یک از آنها انتخاب می شود. اگر همه ضرایب در ستون تفکیک کمتر یا مساوی 0 باشند، جواب مسئله بی نهایت است.

بیایید جدول زیر "تکرار 1" را پر کنیم. ما آن را از جدول "تکرار 0" دریافت خواهیم کرد. هدف از تبدیل های بیشتر تبدیل ستون وضوح x2 به یک ستون واحد است (با یک به جای عنصر وضوح و صفر به جای عناصر باقی مانده).

1) ردیف x 2 جدول "تکرار 1" را محاسبه کنید. ابتدا همه اعضای سطر حل s 3 جدول "تکرار 0" را بر عنصر حل کننده (در این مورد برابر با 1) این جدول تقسیم می کنیم، در جدول "تکرار 1" ردیف x 2 به دست می آید. . چون عنصر حل کننده در این حالت برابر با 1 است، سپس ردیف s 3 جدول "تکرار 0" با ردیف x 2 از جدول "تکرار 1" منطبق خواهد شد. ردیف x 2 از جدول تکرار 1 ما 0 1 0 0 1 20 دریافت کردیم، سطرهای باقی مانده از جدول تکرار 1 از این ردیف و ردیف های جدول تکرار 0 به صورت زیر به دست می آیند:

2) محاسبه ردیف z جدول "تکرار 1". به جای 6- در سطر اول (ردیف z) در ستون x2 جدول تکرار 0، باید 0 در سطر اول جدول تکرار 1 وجود داشته باشد. برای انجام این کار، تمام عناصر ردیف x 2 جدول "تکرار 1" 0 1 0 0 1 20 را در 6 ضرب می کنیم، 0 6 0 0 6 120 به دست می آوریم و این ردیف را با ردیف اول اضافه می کنیم (ردیف z -) از جدول "تکرار 0" -4 -6 0 0 0 0، -4 0 0 0 6 120 می گیریم. صفر 0 در ستون x 2 ظاهر می شود، هدف حاصل می شود. عناصر ستون وضوح x 2 با رنگ قرمز مشخص شده اند.

3) محاسبه ردیف s 1 جدول "تکرار 1". به جای 1 در ردیف 1 جدول "تکرار 0" باید یک عدد 0 در جدول "تکرار 1" وجود داشته باشد. برای انجام این کار، تمام عناصر ردیف x 2 جدول "تکرار 1" 0 1 0 0 1 20 را در -1 ضرب کنید، 0 -1 0 0 -1 -20 را بدست آورید و این ردیف را با s 1 - ردیف اضافه کنید. جدول "تکرار 0" 2 1 1 0 0 64، ردیف 2 0 1 0 -1 44 را دریافت می کنیم. در ستون x 2 0 مورد نیاز را دریافت می کنیم.

4) ردیف s 2 جدول "تکرار 1" را محاسبه کنید. در جای 3 در ردیف دوم جدول "تکرار 0" باید 0 در جدول "تکرار 1" وجود داشته باشد. برای انجام این کار، تمام عناصر ردیف x 2 جدول "تکرار 1" 0 1 0 0 1 20 را در -3 ضرب کنید، 0 -3 0 0 -3 -60 بدست آورید و این سطر را با s 1 - ردیف جدول اضافه کنید. "تکرار 0" 1 3 0 1 0 72، ردیف 1 0 0 1 -3 12 را دریافت می کنیم. در ستون x 2، 0 مورد نیاز در جدول "تکرار 1" به دست می آید ، شامل یکی 1 و بقیه 0 است.

ردیف های جدول "تکرار 1" طبق قانون زیر به دست می آیند:

ردیف جدید = ردیف قدیمی – (ضریب ستون وضوح ردیف قدیمی)*(ردیف وضوح جدید).

به عنوان مثال، برای یک رشته z داریم:

رشته z قدیمی (-4 -6 0 0 0 0) -(-6)*رشته حل جدید -(0 -6 0 0 -6 -120) = رشته z جدید (-4 0 0 0 6 120).

برای جداول زیر، محاسبه مجدد عناصر جدول به روش مشابه انجام می شود، بنابراین آن را حذف می کنیم.

تکرار روش سیمپلکس 1

حل ستون x 1، حل ردیف s 2، s 2 از پایه خارج می شود، x 1 وارد پایه می شود. دقیقاً به همین ترتیب، جداول سیمپلکس باقیمانده را به دست می آوریم تا زمانی که جدولی با تمام ضرایب مثبت در ردیف z بدست آوریم. این نشانه یک جدول بهینه است.

تکرار روش سیمپلکس 2

حل ستون s 3، حل سطر s 1، s 1 از پایه خارج می شود، s 3 وارد پایه می شود.

تکرار روش سیمپلکس 3

در ردیف z، همه ضرایب غیر منفی هستند، بنابراین، راه حل بهینه x 1 = 24، x 2 = 16، z max = 192 به دست می آید.

11.4. روش DUAL SIMPLEX

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

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

همانطور که نشان داده شد، هنگام حل یک مسئله مستقیم در هر تکرار، تفاوت، یعنی بزرگی -ضریب متغیر، برابر است با تفاوت بین سمت راست و چپ محدودیت متناظر مسئله دوگانه. اگر هنگام حل یک مسئله مستقیم با یک تابع هدف حداکثر شده، تکرار به یک راه حل بهینه منتهی نشود، حداقل برای یک متغیر و تنها در بهینه برای همه.تفاوت .

با در نظر گرفتن این شرط با در نظر گرفتن دوگانگی می توان نوشت

.

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

این امکان ایجاد یک روش جدید برای حل مسائل برنامه ریزی خطی را فراهم کرد، که ابتدا یک راه حل غیرقابل قبول، اما "بهتر از بهینه" تولید می کند (در روش معمول سیمپلکس، ابتدا می توان یافت قابل قبول، اما نابهینهراه حل). روش جدید، تماس گرفت روش دو سیمپلکس، تحقق شرایط بهینه بودن راه حل و "تقریبا" سیستماتیک آن به منطقه راه حل های امکان پذیر را تضمین می کند. هنگامی که راه حل به دست آمده امکان پذیر است، فرآیند تکراری محاسبات به پایان می رسد، زیرا این راه حل نیز بهینه است.

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

مثال. حداقل یک تابع را پیدا کنید

تحت محدودیت

.

بیایید به شکل متعارف برویم:

تحت محدودیت

جدول سیمپلکس اولیه دارای فرم است

راه حل پایه اولیهبهینه، اما قابل قبول نیست.

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

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

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

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

در این مثال، متغیر حذف شده است. نسبت های محاسبه شده برای تعیین متغیر پایه جدید در جدول زیر آورده شده است:

متغیر شامل انتخاب شده است x 2. تبدیل رشته بعدی منجر به یک جدول سیمپلکس جدید می شود:

راه حل جدید همچنین بهینه، اما هنوز غیر قابل قبول است. ما به عنوان یک متغیر جدید حذف شده انتخاب می کنیم (به طور خودسرانه) x 3. بیایید متغیری را که باید گنجانده شود را تعریف کنیم.