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

نظریه مختصر

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

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

اگر محدودیت ها و تابع هدف شامل بیش از دو متغیر باشد، لازم است (یا با روش بهبود متوالی راه حل) - جهانی است و می تواند برای حل هر LPP استفاده شود. برای برخی از مسائل برنامه ریزی خطی کاربردی، مانند روش های حل ویژه توسعه داده شده است.

نمونه ای از حل مشکل

وظیفه

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

ضروری:

• یک مدل ریاضی از مسئله بسازید.
• طرحی برای تولید محصولاتی تهیه کنید که حداکثر درآمد حاصل از فروش آنها را با استفاده از روش گرافیکی برای حل مسئله برنامه ریزی خطی فراهم کند.

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

راه حل مشکل

ساخت مدل

از طریق و تعداد محصولات تولید شده از نوع 1 و 2 را نشان می دهیم.

سپس محدودیت منابع عبارتند از:

علاوه بر این، در معنای مسئله

تابع هدف مدل اقتصادی و ریاضی که عواید حاصل از فروش را بیان می کند:

مدل اقتصادی و ریاضی زیر را بدست می آوریم:

ساخت منطقه راه حل های امکان پذیر

بیایید مشکل برنامه ریزی خطی حاصل را به صورت گرافیکی حل کنیم:

برای ساختن ناحیه راه‌حل‌های امکان‌پذیر، خطوط مرزی مربوط به این محدودیت‌های نابرابری را در سیستم مختصات می‌سازیم:

بیایید نقاطی را که خطوط از آنها عبور می کنند پیدا کنیم:

راه حل هر نابرابری از سیستم محدودیت های LPP یک نیم صفحه است که حاوی خط مرزی است و در یک طرف آن قرار دارد.

برای تعریف نیم صفحه، هر نقطه را انتخاب کنید، مثلاً به خط مستقیم (1) تعلق ندارد، مختصات (0؛ 0) را در نابرابری مربوطه جایگزین کنید. زیرا نابرابری درست است:

دامنه حل نابرابری 1 مربوطه با نیم صفحه سمت چپ مطابقت دارد

هر نقطه ای را در نظر بگیرید، مثلاً به خط مستقیم (2) تعلق ندارد، مختصات (0؛ 0) را در نابرابری مربوطه جایگزین کنید. زیرا نابرابری درست است:

هر نقطه ای را در نظر بگیرید، مثلاً به خط مستقیم (3) تعلق ندارد، مختصات (0؛ 0) را در نابرابری مربوطه جایگزین کنید. زیرا نابرابری درست است:

دامنه حل نابرابری دوم مربوطه با نیم صفحه سمت چپ مطابقت دارد

مساحت راه حل های قابل قبول شکل است.

یافتن راه حلی برای مشکل LP

برداری می سازیم که مختصات آن متناسب با ضرایب تابع هدف باشد. در اینجا ضریب تناسب است.

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

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

پاسخ

بنابراین تولید 56 قلم از نوع 1 و 64 قلم از نوع 2 ضروری است. در این صورت عواید حاصل از فروش محصولات حداکثر و 5104 واحد پولی خواهد بود.

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

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

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

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

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

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

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

مبانی نظری روش گرافیکی

بنابراین، یک مسئله برنامه ریزی خطی. یافتن مقادیر غیرمنفی متغیرها و ارضای سیستم نابرابری ها الزامی است.

که در آن شکل خطی مقدار بهینه را می گیرد.

مثال 3.

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

ما به حل مشکلات به صورت گرافیکی با هم ادامه می دهیم

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

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

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

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

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

ساده ترین و شهودی ترین روش برنامه ریزی خطی (LP) روش گرافیکی است. برای حل مسائل LP با دو متغیر استفاده می شود. مشکل LP را به شکل استاندارد در نظر بگیرید:

حداکثر f (x 1 ، x 2، ...، x n) = ,

, i = 1، 2، ...، m،

x j 0، j = 1، 2،…، n.

ما گذاشتیم n = 2و ما مشکل را در هواپیما بررسی خواهیم کرد. بگذارید سیستم نابرابری ها سازگار باشد (حداقل یک راه حل داشته باشد).

هر نابرابری این سیستم از نظر هندسی نیم صفحه ای را با خط مرزی a i 1 x 1 + a i 2 x 2 = b i, i = 1, 2 تعریف می کند. …, متر شرایط غیرمنفی به ترتیب نیم صفحات با خطوط مرزی x 1 = 0، x 2 = 0 را تعریف می کند. این سیستم سازگار است، بنابراین، نیم صفحه ها، به عنوان مجموعه های محدب، متقاطع، یک قسمت مشترک را تشکیل می دهند که مجموعه ای محدب است و مجموعه ای از نقاط است که مختصات هر نقطه راه حلی برای این سیستم است. مجموعه این نقاط را چندضلعی تصمیم می گویند. این می تواند یک نقطه، خط، پرتو، چند ضلعی محدود و نامحدود باشد.

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

یک معادله خطی مجموعه ای از نقاط را توصیف می کند که روی یک خط مستقیم قرار دارند. نابرابری خطی ناحیه خاصی را در صفحه توصیف می کند. اجازه دهید تعیین کنیم که کدام قسمت از صفحه با نابرابری 2x 1 + 3x 2 12 توصیف می شود.

ابتدا یک خط 2x1 + بسازید Zx 2= 12. از نقاط (6; 0) و (0; 4) عبور می کند. برای تعیین اینکه کدام نیم صفحه نابرابری را برآورده می کند، باید هر نقطه از نمودار را که متعلق به یک خط مستقیم نیست انتخاب کرد و مختصات آن را به نامساوی جایگزین کرد. اگر نابرابری برقرار باشد، این نقطه یک راه حل امکان پذیر است و نیم صفحه حاوی نقطه نابرابری را برآورده می کند. برای جایگزینی در نابرابری، استفاده از نقطه مبدا راحت است. x 1 = x 2 = 0 را به نامعادله 2x 1 + 3x 2 12 جایگزین کنید. ما 2x0 + 3x0 12 را به دست می آوریم. این عبارت درست است، بنابراین، نابرابری 2x 1 + 3x2 12 مربوط به نیم صفحه پایینی حاوی نقطه است. (0; 0). این در نمودار نشان داده شده در شکل منعکس شده است. 1.1.

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

راه حل هر نابرابری از سیستم محدودیت های LPP یک نیم صفحه است که حاوی خط مرزی است و در یک طرف آن قرار دارد. تقاطع نیم صفحه‌ها که هر کدام از آنها با نابرابری متناظر سیستم تعیین می‌شود، ناحیه حل‌های امکان‌پذیر یا ناحیه تعریف نامیده می‌شود. باید به خاطر داشت که منطقه راه حل های امکان پذیر شرایط غیر منفی را برآورده می کند ( x j 0, j = 1، 2، ...، n). مختصات هر نقطه ای که به حوزه تعریف تعلق دارد یک راه حل عملی برای مسئله است.

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

این بردار جهت سریعترین تغییر در تابع هدف را نشان می دهد. مستقیم با 1 * 1 + با 2 * 2 = f (x 0)عمود بر بردار گرادیان، خط تراز تابع هدف است. در هر نقطه از خط تراز، تابع هدف همان مقدار را می گیرد. اجازه دهید تابع هدف را با یک مقدار ثابت برابر کنیم "آ"... با تغییر مقدار "a"، خانواده ای از خطوط مستقیم موازی را دریافت می کنیم که هر یک از آنها خطی از سطح تابع هدف هستند.

یکی از ویژگی های مهم خط تراز یک تابع خطی این است که وقتی خط به طور موازی در یک جهت جابه جا می شود، تراز فقط افزایش می یابد و هنگامی که در جهت دیگر جابجا می شود، فقط کاهش می یابد.

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

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

1. ناحیه چند ضلعی راه حل های امکان پذیر (ODS) LPP ساخته شده است.

2. بردار گرادیان تابع هدف (CF) در نقطه ای x 0 متعلق به ODR ساخته شده است:

3. خط تراز c 1 x 1 + c 2 x 2 = a (a یک ثابت است) - یک خط مستقیم عمود بر بردار گرادیان - در صورت به حداکثر رساندن f (x 1, x) در جهت این بردار حرکت می کند. 2) تا زمانی که از محدوده ODR خارج شود. نقطه (یا نقاط) محدود منطقه در طول این حرکت حداکثر نقطه f (x 1, x 2) است.

4. برای یافتن مختصات نقطه حداکثر کافی است دو معادله خطوط مستقیم که از قیود مربوطه به دست آمده و حداکثر نقطه را در تقاطع به دست می آورند، حل کنیم. مقدار f (x 1, x 2) که در نقطه حاصل یافت می شود حداکثر است.

هنگام کمینه سازی (بیشینه سازی) تابع f (x 1، x 2)، خط تراز در جهت مخالف بردار گرادیان حرکت می کند. اگر خط مستقیم مربوط به خط تراز در طول حرکت خود ODR را ترک نکند، حداقل (حداکثر) تابع f (x 1, x 2) وجود ندارد.

اگر خط تراز موازی با برخی از محدودیت‌های عملکردی مسئله باشد، مقدار بهینه CF در هر نقطه از این محدودیت که بین دو نقطه گوشه بهینه قرار دارد به دست می‌آید و بر این اساس، هر یک از این نقاط راه‌حل بهینه برای LPP موقعیت های ممکن برای حل گرافیکی مسائل LP در جدول ارائه شده است. 1.3.

جدول 1.3

№	نوع ODR	نوع محلول بهینه	یادداشت ها (ویرایش)
	چند ضلعی بسته است	فقط تصمیم
	فقط تصمیم
	چند ضلعی	ZF از پایین محدود نمی شود
	CF از بالا محدود نمی شود
	چند ضلعی باز	فقط تصمیم
	تعداد بی پایان راه حل
	بخش	فقط تصمیم

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

مثال 1.1. برنامه ریزی تولید یک شرکت خیاطی (مشکل کت و شلوار).

قرار است دو نوع کت و شلوار - مردانه و زنانه عرضه شود. یک کت و شلوار زنانه به 1 متر پشم، 2 متر لوسان و 1 نفر در روز زایمان نیاز دارد. برای کت و شلوار مردانه - 3.5 متر پشم، 0.5 متر لوسان و 1 نفر در روز زایمان. در مجموع 350 متر پشم، 240 متر لوسان و 150 نفر در روز هزینه کار وجود دارد. در صورتی که سود حاصل از فروش کت و شلوار زنانه 10 واحد ارزی و از کت و شلوار مردانه 20 واحد ارزی باشد باید مشخص شود که چه تعداد کت و شلوار از هر نوع باید دوخته شود تا حداکثر سود حاصل شود. باید در نظر داشت که حداقل 60 کت و شلوار مردانه باید دوخته شود.

بیایید نام های زیر را معرفی کنیم: x 1 - تعداد کت و شلوارهای زنانه؛ x 2 - تعداد کت و شلوار مردانه. سود حاصل از فروش کت و شلوار زنانه 10×1 و از فروش کت و شلوار مردانه 20×2 است، یعنی. حداکثر کردن تابع هدف ضروری است:

10x1 + 20x2

محدودیت های وظیفه به شرح زیر است:

x 1 + x 2 150،

2 x 1 + 0.5x 2 240،

x 1 + 3.5x 2 350،

x 2 60,

x 1 0.

اولین محدودیت کار x 1 + x 2 150. خط مستقیم x 1 + x 2 = 150 از نقاط (150؛ 0) و (0؛ 150) عبور می کند (شکل 1.2).

محدودیت دوم در lavsan 2 x 1 + 0.5x 2 240 است. خط مستقیم 2 x 1 + 0.5x 2 = 240 از نقاط (120؛ 0) و (0؛ 480) می گذرد. محدودیت سوم در پشم x 1 + 3.5 x 2 350. اجازه دهید محدودیت چهارم در تعداد کت و شلوار مردانه x 2 را اضافه کنیم. 60. راه حل این نابرابری نیم صفحه ای است که بالای خط مستقیم قرار دارد x 2 = 60. در شکل. 1.3 ناحیه محلول های قابل قبول سایه دار است. برای تعیین جهت حرکت به سمت بهینه، یک بردار گرادیان می سازیم که مختصات آن مشتقات جزئی تابع هدف هستند، یعنی.

برای ساختن چنین برداری، باید نقطه (10؛ 20) را به مبدا متصل کنید. هنگام به حداکثر رساندن تابع هدف، باید در جهت بردار گرادیان حرکت کرد و در زمان کمینه کردن، در جهت مخالف حرکت کرد. برای راحتی، می توانید بردار متناسب با بردار بسازید. بنابراین، در شکل. 1.4 بردار گرادیان را نشان می دهد (30؛ 60).

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

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

x 1 + 3.5x 2 = 350،

x 1 + x 2 = 150.

از اینجا به راحتی می توان راه حل LPP اصلی را یادداشت کرد: حداکثر f (x)= 2300 و در x 1 = 70 و x 2 = 80 به دست می آید (شکل 1.4 را ببینید).

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

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

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

عناصر صفحه نمایش اکسل پس از راه اندازی اکسل، جدولی روی صفحه ظاهر می شود که نمای آن در شکل 1.5 نشان داده شده است.

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

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

1) علامت مساوی؛

2) مجموعه ای از مقادیر یا مراجع در سلول هایی که محاسبات با آنها انجام می شود.

3) اپراتورها

4) اگر علامت مساوی وجود نداشته باشد، اکسل داده ها را نه به عنوان یک فرمول، بلکه به عنوان ورود داده به یک سلول تفسیر می کند. فرمول ها را می توان مستقیماً در یک سلول یا در نوار فرمول - متن یا اعداد وارد کرد. در این صورت باید موارد زیر را انجام دهید:

· سلولی که باید حاوی فرمول باشد را انتخاب کرده و علامت (=) را وارد کنید.

یک اپراتور یا یک علامت عمل را وارد کنید.

· سلول دیگری را برای گنجاندن در فرمول انتخاب کنید.

· کلید Enter را فشار دهید.

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

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

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

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

یافتن راه حل یک افزونه اکسل است که به شما امکان می دهد مشکلات بهینه سازی را حل کنید. اگر دستور Find a solution در منوی Tools وجود ندارد، باید این افزونه را بارگیری کنید. Tools => Add-Ins را انتخاب کرده و افزونه Find Solution را فعال کنید. اگر این افزونه در کادر محاوره ای افزونه ها نیست، باید به کنترل پنل ویندوز بروید، روی نماد افزودن یا حذف برنامه ها کلیک کنید و از برنامه تنظیم اکسل (یا آفیس) برای نصب Find Solution استفاده کنید. افزودنی

پس از انتخاب Tools => Find Solution، کادر محاوره ای Find Solution ظاهر می شود.

سه گزینه اصلی در کادر گفتگوی Find Solution وجود دارد.

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

با تغییر سلول ها

محدودیت های.

ابتدا باید فیلد Set Target Cell را پر کنید. در تمام وظایف ابزار Solver، نتیجه در یکی از سلول های کاربرگ بهینه می شود. سلول هدف با استفاده از فرمول ها به سلول های دیگر در این کاربرگ متصل می شود. Solution Finder از فرمول هایی استفاده می کند که نتیجه ای را در سلول هدف ایجاد می کند تا راه حل های ممکن را آزمایش کند. شما می توانید انتخاب کنید که برای سلول هدف کوچکترین یا بزرگترین مقدار را جستجو کنید یا مقدار خاصی را تعیین کنید.

دومین پارامتر مهم ابزار Solver، پارامتر Modify Cells است. در اینجا شما سلول هایی را مشخص می کنید که مقادیر آنها برای بهینه سازی نتیجه در سلول هدف تغییر می کند. شما می توانید تا 200 سلول قابل تغییر را برای جستجوی راه حل مشخص کنید. دو الزام اصلی برای این سلول ها وجود دارد: آنها نباید حاوی فرمول باشند و تغییرات در مقادیر آنها باید در تغییر نتیجه در سلول هدف منعکس شود. به عبارت دیگر، سلول هدف به سلول هایی که باید تغییر کنند بستگی دارد.

سومین پارامتری که باید در تب Solve وارد شود، محدودیت ها است.

برای حل مشکل باید:

1) آدرس سلول هایی را که نتیجه راه حل در آنها قرار می گیرد (سلول های متغیر) نشان دهید.

2) داده های اولیه را وارد کنید.

3) یک وابستگی برای تابع هدف معرفی کنید.

4) وابستگی هایی را برای محدود کردن معرفی کنید،

5) دستور Search for solutions را اجرا کنید.

6) یک سلول را به تابع هدف اختصاص دهید (سلول هدف را تنظیم کنید).

7) ایجاد محدودیت

8) پارامترهای حل LPP را وارد کنید.

فناوری راه حل را با استفاده از شرایط مثال 1.1 (مسئله کت و شلوار) در نظر بگیرید.

مدل اقتصادی و ریاضی مسئله

اجازه دهید x 1 تعداد کت و شلوارهای زنانه باشد. x 2 - تعداد کت و شلوارهای مردانه،

حداکثر 10 x 1 + 20 x 2 حداکثر

محدودیت های وظیفه به شرح زیر است:

x 1 + x 2 150 - محدودیت های کار.

2 x 1 + 0.5 x ایکس 2 240 - محدودیت در لاوسان;

x 1 + 3.5 x 2 350 - محدودیت پشم.

x 2 60 - محدودیت در کت و شلوار مردانه;

x 1 0 - محدودیت در کت و شلوار زنانه.

1. آدرس سلول هایی را که نتیجه راه حل در آنها قرار می گیرد (سلول های اصلاح شده) مشخص کنید.

برچسب x 1، x 2 برای تعداد کت و شلوار از هر نوع. در مشکل ما، مقادیر بهینه بردار = (x 1، x 2) در سلول های A2 قرار می گیرد: B2، مقدار بهینه تابع هدف - در سلول C3.

2. داده های اولیه را وارد کنید.

همانطور که در شکل نشان داده شده است، داده های اولیه کار را وارد کنید. 1.6.

3. وابستگی تابع هدف را معرفی کنید.

· مکان نما را در سلول "NW" قرار دهید، سلول برجسته می شود.

· مکان نما را روی دکمه Function Wizard واقع در نوار ابزار قرار دهید.

· Enter را وارد کنید. کادر محاوره ای Function Wizard Step 1 of 2 روی صفحه ظاهر می شود.

· در پنجره Functions خط SUMPRODUCT را انتخاب کنید (شکل 1.7). روی صفحه نمایش

· کادر محاوره ای SUMPRODUCT ظاهر می شود (شکل 1.8).

در خط آرایه 1 وارد کنید A2: B2.

· در خط آرایه 2 AZ: VZ را وارد کنید.

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

5. وابستگی ها را برای محدودیت ها معرفی کنید (شکل 1.10).

· مکان نما را در سلول SZ قرار دهید.

· در نوار ابزار، دکمه کپی در کلیپ بورد.

· مکان نما را در سلول C4 قرار دهید.

· مکان نما را در سلول C5 قرار دهید.

· در نوار ابزار، دکمه چسباندن از کلیپ بورد.

· مکان نما را در سلول Sat قرار دهید.

· در نوار ابزار، دکمه چسباندن از کلیپ بورد.

· مکان نما را در سلول C7 قرار دهید.

· در نوار ابزار، روی دکمه Paste from clipboard کلیک کنید. (محتوای سلول های C4-C7 باید بررسی شود. آنها باید حاوی اطلاعات باشند، همانطور که برای مثال در شکل 1.11 نشان داده شده است؛ محتویات سلول C5 به عنوان مثال نشان داده شده است.)

· در نوار منو، نشانگر ماوس را روی Service قرار دهید. در منوی باز شده، دستور Find solution را انتخاب کنید. کادر گفتگوی Search for a solution ظاهر می شود (شکل 1.12).

5. دستور Find solution را اجرا کنید.

6. یک سلول برای تابع هدف اختصاص دهید (سلول هدف را تنظیم کنید)، آدرس سلول هایی را که باید تغییر کنند را مشخص کنید.

· مکان نما را روی خط Set سلول هدف قرار دهید.

· آدرس سلول $ C $ 3 را وارد کنید.

· نوع تابع هدف را بسته به شرایط مشکل خود وارد کنید. برای انجام این کار، مشخص کنید که آیا تابع هدف برابر با مقدار Maximum یا مقدار Minimum است.

· مکان نما را در یک ردیف در حال تغییر سلول ها قرار دهید.

· آدرس متغیرهای مورد نیاز A $ 2: B $ 2 را وارد کنید (شکل 1.13).

7. ایجاد محدودیت.

· نشانگر ماوس را روی دکمه افزودن حرکت دهید. کادر محاوره ای Add Constraint ظاهر می شود.

· یک علامت محدودیت معرفی کنید.

· در خط محدودیت، آدرس $ D $ 4 را وارد کنید (شکل 1.14).

· نشانگر ماوس را روی دکمه افزودن حرکت دهید. کادر محاوره ای Add Constraint دوباره روی صفحه ظاهر می شود.

· بقیه قیود مسئله را طبق الگوریتم بالا معرفی کنید.

· پس از اعمال آخرین محدودیت بر روی دکمه OK کلیک کنید. کادر گفتگوی Search for a solution با شرایط وارد شده روی صفحه ظاهر می شود (شکل 1.15).

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

· در کادر محاوره ای، نشانگر ماوس را روی دکمه Options قرار دهید. کادر محاوره ای پارامترهای جستجوی راه حل روی صفحه ظاهر می شود (شکل 1.16).

· چک باکس ها را در جعبه های مدل Linear (این کار استفاده از روش سیمپلکس را تضمین می کند) و مقادیر غیر منفی را تنظیم کنید.

· نشانگر ماوس را روی دکمه OK حرکت دهید. کادر محاوره ای Find Solution ظاهر می شود.

· نشانگر ماوس را روی دکمه Run قرار دهید.

پس از مدت کوتاهی، کادر محاوره ای نتایج جستجوی راه حل و جدول اصلی با سلول های AZ پر شده ظاهر می شود: VZ برای مقادیر x i و سلول C3 با حداکثر مقدار تابع هدف (شکل 1.17).

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

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

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

در سال 1975 هموطن ما L.V. کانتوروویچ جایزه نوبل اقتصاد (به همراه اقتصاددان آمریکایی تی. کوپمنز) را برای توسعه نظریه استفاده بهینه از منابع دریافت کرد (به پیوست 1 مراجعه کنید).

ارتباط نزدیک با هر مسئله برنامه ریزی خطی، مسئله خطی دیگری است که به آن دوگانه می گویند. وظیفه اولیه، اولیه یا مستقیم نامیده می شود. ارتباط بین مسائل اصلی و دوگانه، به ویژه در این واقعیت نهفته است که راه حل یکی از آنها را می توان مستقیماً از راه حل دیگری به دست آورد.

متغیرهای مسئله دوگانه y i برآوردهای تعیین شده عینی، یا برآوردهای دوگانه، یا "قیمت" منابع، یا قیمت های سایه نامیده می شوند.

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

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

1) تابع هدف مسئله اصلی برای حداکثر، و تابع هدف مسئله دوگانه - برای حداقل، فرموله می شود، در حالی که در مسئله برای حداکثر، همه نابرابری ها در قیود تابعی شکل ()، در مسئله دارند. برای حداقل - فرم ( );

2) ماتریس A، متشکل از ضرایب در محدودیت های ناشناخته در سیستم مسئله اصلی، و ماتریس مشابه A T در مسئله دوگانه با جابجایی از یکدیگر به دست می آیند.

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

4) ضرایب مجهولات در تابع هدف مسئله دوگانه عبارت‌های آزاد در سیستم قیود مسئله اصلی هستند و سمت راست در قیود مسئله دوگانه ضرایب مجهولات در تابع هدف هستند. اصلی؛ j 0.

این دو مسئله یک جفت مسئله دوگانه متقارن را تشکیل می دهند. عبارات اصلی در مورد مسائل دوگانه متقابل در دو قضیه بعدی آمده است.

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

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

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

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

4. هر دو مشکل مورد بررسی دارای مجموعه های قابل قبول خالی هستند.

قضیه دوگانگی دوم (قضیه سستی مکمل). بگذار = ( x 1، x 2, ..., xn) یک راه حل قابل قبول برای مسئله مستقیم است، a = (y 1, y 2,…, y m) یک راه حل قابل قبول برای مسئله دوگانه است. برای اینکه آنها به ترتیب راه حل های بهینه برای مسائل مستقیم و دوگانه باشند، لازم و کافی است که روابط زیر برقرار باشد:

(1.4)

(1.5)

شرایط (1.4) و (1.5) اجازه می دهد تا با دانستن راه حل بهینه برای یکی از مسائل دوگانه متقابل، راه حل بهینه را برای یک مسئله دیگر بیابید.

یک قضیه دیگر را در نظر بگیرید که از نتایج آن در موارد زیر استفاده خواهد شد.

قضیه تخمین. مقادیر متغیرهای y i در حل بهینه مسئله دوگانه تخمین‌هایی از تأثیر عبارت‌های آزاد b i از سیستم محدودیت‌ها (نابرابری‌ها) مسئله مستقیم بر مقدار است.

با حل LPP با استفاده از روش سیمپلکس، ما به طور همزمان LPP دوگانه را حل می کنیم. متغیرهای مسئله دوگانه y i را برآوردهای تعیین شده عینی می نامند.

اجازه دهید تفسیر اقتصادی مسئله دوگانه را با استفاده از مثال مسئله فرش در نظر بگیریم.

مثال 1 .2. با استفاده از بیان مسئله فرش، کارهای زیر را تکمیل کنید.

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

2. با استفاده از جستجوی راه حل، طرح تولیدی را بیابید که هزینه کل تولید را به حداکثر برساند.

3. یک مدل اقتصادی و ریاضی از مسئله دوگانه به مسئله فرش تدوین کنید.

4. طرح بهینه مسئله دوگانه را بیابید، با استفاده از قضیه دوگانگی، برابری صفر X 1 و X 4 را توضیح دهید.

5. با استفاده از پروتکل های جستجوی راه حل، راه حل بهینه به دست آمده برای مسئله اصلی را تجزیه و تحلیل کنید.

6. تعیین کنید که چگونه هزینه کل و برنامه تولید با افزایش ذخیره منبع لوله به میزان 12 واحد تغییر خواهد کرد.

1. اجازه دهید یک مدل اقتصادی و ریاضی مسئله را فرموله کنیم.

بیایید از طریق X 1، X 2، X 3، X 4 تعداد فرش های هر نوع را مشخص کنیم. تابع هدف دارای فرم است

F (X) = ZX 1 + 4X 2 + ZX 3 + X 4 حداکثر،

و محدودیت منابع

7X 1 + 2X 2 + 2X 3 + 6X 4 80,

5X 1 + 8X 2 + 4 X 3 + ZX 4 480,

2X 1 + 4 X 2 + X 3 + 8X 4 130،

X 1، X 2، X 3، X 4 0.

2. یافتن طرح آزادسازی بهینه.

ما مشکل را با استفاده از افزونه اکسل Search for a solution حل خواهیم کرد. فن آوری برای حل مشکل به طور مفصل در مسئله در مورد کت و شلوار مورد بحث قرار گرفت. در مشکل ما، مقادیر بهینه بردار X = (X 1، X 2، X 3، X 4) در سلول های ВЗ: ЕЗ، مقدار بهینه تابع هدف - در سلول قرار می گیرد. F4.

بیایید داده های اولیه را وارد کنیم. ابتدا تابع هدف را با استفاده از تابع - SUMPRODUCT توصیف می کنیم (شکل 1.19). و سپس داده هایی را برای سمت چپ محدودیت ها وارد می کنیم. در جستجوی راه حل، جهت تابع هدف، آدرس متغیرهای جستجو شده را معرفی می کنیم و محدودیت هایی را اضافه می کنیم. کادر گفتگوی Search for a solution با شرایط وارد شده روی صفحه ظاهر می شود (شکل 1.20).

پس از وارد کردن پارامترهای حل LPP، روی دکمه Execute کلیک کنید. پیامی بر روی صفحه ظاهر می شود که راه حل پیدا شده است (شکل 1.21).

راه حل حاصل به این معنی است که حداکثر درآمد 150 هزار روبل است. کارخانه می تواند 30 فرش از نوع دوم و 10 فرش از نوع سوم را پس از رهاسازی تهیه کند. در این صورت از منابع "کار" و "تجهیزات" به طور کامل استفاده می شود و 280 کیلوگرم از 480 کیلوگرم نخ (منبع "خام") استفاده می شود.

تولید گزارش بر اساس نتایج جستجوی راه حل. اکسل به شما امکان می دهد نتایج جستجوی یک راه حل را در قالب یک گزارش ارائه دهید (جدول 1.4). سه نوع از این گونه گزارش ها وجود دارد:

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

· ثبات (حساسیت). گزارشی که اطلاعاتی در مورد حساسیت یک راه حل به تغییرات کوچک در سلول های تغییر یافته یا در فرمول های محدودیت ارائه می دهد.

· محدودیت ها علاوه بر مقادیر منبع و هدف سلول‌های اصلاح‌شده و هدف، این گزارش شامل مرزهای بالایی و پایینی مقادیری است که سلول‌های تأثیرگذار می‌توانند با توجه به محدودیت‌ها فرض کنند.

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

یک مسئله برنامه ریزی خطی را با دو متغیر در نظر بگیرید و:
(1.1) ;
(1.2)
در اینجا، اعداد دلخواه وجود دارد. وظیفه می تواند هم یافتن حداکثر (حداکثر) و هم یافتن حداقل (min) باشد. در نظام محدودیت ها هم نشانه ها و هم نشانه ها می تواند وجود داشته باشد.

ساخت منطقه راه حل های امکان پذیر

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

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

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

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

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

اگر حداقل یک نابرابری ارضا نشد، نقطه دیگری را انتخاب می کنیم. و به همین ترتیب، تا زمانی که یک نقطه پیدا شود که مختصات آن سیستم (1.2) را برآورده کند.

یافتن منتهی الیه تابع هدف

بنابراین، ما ناحیه سایه‌دار راه‌حل‌های امکان‌پذیر (ODS) را داریم. توسط یک چند خط متشکل از قطعات و پرتوهای متعلق به خطوط مستقیم ساخته شده محدود شده است (2). ODR همیشه یک مجموعه محدب است. این می تواند یک مجموعه محدود باشد یا در امتداد برخی جهات محدود نشده باشد.

اکنون می‌توانیم حداکثر تابع هدف را جستجو کنیم
(1.1) .

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

بنابراین، برای یافتن حداکثر مقدار تابع هدف، لازم است یک خط مستقیم به موازات خط مستقیم (3) ترسیم شود که دورترین خط از آن در جهت افزایش مقادیر، و حداقل از یک نقطه عبور کند. ODR برای یافتن حداقل مقدار تابع هدف، لازم است یک خط مستقیم به موازات خط مستقیم (3) و دورترین خط از آن در جهت کاهش مقادیر ترسیم شود و حداقل از یک نقطه ODR عبور کند.

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

حالتی را در نظر بگیرید که یک خط مستقیم شدید موازی با یک خط مستقیم دلخواه شکل (3) از یک راس چند ضلعی ODR عبور کند. از روی نمودار مختصات این راس را مشخص می کنیم. سپس حداکثر (حداقل) مقدار تابع هدف با فرمول تعیین می شود:
.
راه حل مشکل این است
.

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

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

وظیفه

این شرکت لباس هایی از دو مدل A و B تولید می کند که در این مورد از سه نوع پارچه استفاده می شود. تولید یک لباس مدل الف به 2 متر پارچه نوع اول، 1 متر پارچه نوع دوم و 2 متر پارچه نوع سوم نیاز دارد. تولید یک لباس مدل B نیاز به 3 متر پارچه نوع اول، 1 متر پارچه نوع دوم، 2 متر پارچه نوع سوم دارد. ذخایر پارچه نوع اول 21 متر، نوع دوم 10 متر، نوع سوم 16 متر است. عرضه یک محصول نوع A 400 دمن درآمد به همراه دارد. واحد، یک محصول از نوع B - 300 den. واحدها

یک برنامه تولیدی تهیه کنید که بیشترین درآمد را برای شرکت فراهم کند. مشکل را گرافیکی حل کنید.

راه حل

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

سپس مدل اقتصادی و ریاضی مسئله به شکل زیر است:

ما آن را به صورت گرافیکی حل می کنیم.
محورهای مختصات و.

ما یک خط مستقیم می سازیم.
در .
در .
از میان نقاط (0؛ 7) و (10.5؛ 0) یک خط مستقیم بکشید.

ما یک خط مستقیم می سازیم.
در .
در .
از میان نقاط (0; 10) و (10; 0) یک خط مستقیم بکشید.

ما یک خط مستقیم می سازیم.
در .
در .
از میان نقاط (0; 8) و (8; 0) یک خط مستقیم بکشید.

ناحیه را به گونه ای سایه بزنید که نقطه (2؛ 2) در قسمت سایه دار بیفتد. یک OABC چهار ضلعی می گیریم.

(A1.1) .
در .
در .
از میان نقاط (0; 4) و (3; 0) یک خط مستقیم بکشید.

علاوه بر این، توجه می کنیم که از آنجایی که ضرایب در و تابع هدف مثبت هستند (400 و 300)، پس با افزایش و افزایش می یابد. یک خط مستقیم به موازات خط مستقیم (A1.1) ترسیم می کنیم که بیشترین فاصله از آن در جهت صعودی است و حداقل از یک نقطه OABC چهار ضلعی می گذرد. چنین خط مستقیمی از نقطه C می گذرد. ​​از روی ساخت مختصات آن را تعیین می کنیم.
.

راه حل مشکل: ;

پاسخ

.
یعنی برای به دست آوردن بالاترین درآمد باید 8 لباس از مدل A تهیه کرد که در این صورت درآمد 3200 den خواهد بود. واحدها

مثال 2

وظیفه

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

راه حل

ما آن را به صورت گرافیکی حل می کنیم.
محورهای مختصات و.

ما یک خط مستقیم می سازیم.
در .
در .
از میان نقاط (0; 6) و (6; 0) یک خط مستقیم بکشید.

ما یک خط مستقیم می سازیم.
از اینجا.
در .
در .
از طریق نقاط (3; 0) و (7; 2) یک خط مستقیم بکشید.

ما یک خط مستقیم می سازیم.
یک خط مستقیم می سازیم (محور آبسیسا).

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

منطقه را در امتداد مرزهای خطوط ساخته شده سایه می زنیم تا نقطه (4؛ 1) در قسمت سایه دار بیفتد. یک مثلث ABC بدست می آوریم.

ما یک خط دلخواه از سطح تابع هدف می سازیم، برای مثال،
.
در .
در .
یک خط مستقیم از سطح را از طریق نقاط (0; 6) و (4; 0) ترسیم می کنیم.
از آنجایی که تابع هدف با افزایش افزایش می یابد و سپس یک خط مستقیم موازی با خط تراز و تا حد امکان از آن در جهت افزایش و عبور از حداقل یک نقطه از مثلث ABC رسم می کنیم. چنین خط مستقیمی از نقطه C می گذرد. ​​از روی ساخت مختصات آن را تعیین می کنیم.
.

راه حل مشکل: ;

پاسخ

نمونه ای از عدم راه حل

وظیفه

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

راه حل

ما مشکل را به صورت گرافیکی حل می کنیم.
محورهای مختصات و.

ما یک خط مستقیم می سازیم.
در .
در .
از میان نقاط (0؛ 8) و (2667؛ 0) یک خط مستقیم بکشید.

ما یک خط مستقیم می سازیم.
در .
در .
از طریق نقاط (0; 3) و (6; 0) یک خط مستقیم بکشید.

ما یک خط مستقیم می سازیم.
در .
در .
از طریق نقاط (3؛ 0) و (6؛ 3) یک خط مستقیم بکشید.

خطوط مستقیم محورهای مختصات هستند.

مساحت راه حل های قابل قبول (ODS) توسط خطوط مستقیم ساخته شده و محورهای مختصات محدود می شود. برای اینکه بفهمیم از کدام طرف، متوجه می‌شویم که نقطه متعلق به ODR است، زیرا سیستم نابرابری‌ها را برآورده می‌کند:

منطقه را طوری سایه می زنیم که نقطه (3; 3) در قسمت سایه دار بیفتد. یک ناحیه نامحدود می گیریم که توسط چند خط ABCDE محدود شده است.

ما یک خط دلخواه از سطح تابع هدف می سازیم، برای مثال،
(A3.1) .
در .
در .
از میان نقاط (0; 7) و (7; 0) یک خط مستقیم بکشید.
از آنجایی که ضرایب در و مثبت هستند، با افزایش و افزایش می یابد.

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

ما به دنبال حداقل هستیم. یک خط مستقیم به موازات خط مستقیم (A3.1) و دورترین خط از آن در جهت کاهش می کشیم و حداقل از یک نقطه از منطقه ABCDE عبور می کنیم. چنین خط مستقیمی از نقطه C می گذرد. ​​از روی ساخت مختصات آن را تعیین می کنیم.
.
حداقل مقدار تابع هدف:

پاسخ

حداکثر مقدار وجود ندارد.
حداقل ارزش
.

اجازه دهید ابتدا ساده ترین حالت را در نظر بگیریم، زمانی که دقیقاً دو متغیر در LPP گنجانده شده است:

هر یک از نابرابری های (a) - (b) سیستم قیود مسئله (3.8) از نظر هندسی نیم صفحه ای با خطوط مرزی، به ترتیب X 1 = 0 و X 2 = 0، تعریف می کند. هر یک از خطوط مرزی صفحه x 1 Ox 2 را به دو نیم صفحه تقسیم می کند. همه راه حل های نابرابری اصلی در یکی از نیم صفحه های تشکیل شده قرار دارند (همه نقاط نیم صفحه) و بنابراین، وقتی مختصات هر یک از نقاط آن به نابرابری مربوطه جایگزین شود، آن را به یک هویت واقعی تبدیل می کند. . با در نظر گرفتن این، نیم صفحه ای تعیین می شود که راه حل های نابرابری در آن قرار دارند، یعنی. با انتخاب هر نقطه از هر نیم صفحه و جایگزینی مختصات آن در نابرابری مربوطه. اگر نابرابری برای یک نقطه معین برقرار باشد، آنگاه برای هر نقطه دیگری از همان نیم صفحه صادق است. در غیر این صورت، راه حل های نابرابری در نیم صفحه دیگری نهفته است.

اگر سیستم نابرابری های (a) - (b) سازگار باشد، دامنه راه حل های آن مجموعه ای از نقاط متعلق به تمام نیم صفحه های نشان داده شده است. از آنجایی که مجموعه نقاط تقاطع این نیم صفحه ها محدب است، حوزه راه حل های امکان پذیر برای مسئله (3.8) یک مجموعه محدب است که به آن چندضلعی راه حل ها می گویند (اصطلاح قبلاً معرفی شده "چند توپی راه حل ها" معمولاً در صورتی استفاده می شود که n 3). اضلاع این چند ضلعی بر روی خطوط مستقیمی قرار دارند که معادلات آن از سیستم محدودیت های اصلی با جایگزینی علائم نابرابری با علائم تساوی دقیق به دست آمده است.

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

این نقطه زمانی وجود دارد که چندضلعی حل خالی نباشد و تابع هدف از بالا روی آن محدود شده باشد. در این شرایط، در یکی از رئوس چندضلعی تصمیم، تابع هدف حداکثر مقدار خود را می گیرد. برای تعیین این راس، یک خط تراز L ساخته می شود: c 1 x 1 + c 2 x 2 = h (که h مقداری ثابت است)، عمود بر بردار گرادیان و از چند ضلعی محلول عبور می کند و آن را به موازات شیب حرکت می دهد. بردار تا زمانی که از آخرین نقطه تقاطع مشترک خود با چند ضلعی راه حل ها عبور کند (هنگام ساختن بردار گرادیان، یک نقطه در صفحه x 1 Ox 2 رها می شود (c 1; c 2) و یک قطعه جهت دار رسم می شود. به آن از مبدأ مختصات). مختصات نقطه مشخص شده طرح بهینه را برای این کار تعیین می کند.

با خلاصه کردن تمام موارد فوق، الگوریتمی برای روش گرافیکی برای حل LPP ارائه می کنیم.

الگوریتم روش گرافیکی برای حل LPP

1. یک چند ضلعی از راه حل های داده شده توسط سیستم محدودیت های LPP اصلی بسازید.

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

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

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

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