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

حفره دهان

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

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

ما خطوط مستقیم را در سیستم مختصات x 1 x 2 می سازیم

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

یک بردار و یک خط سطح صفر عمود بر آن می سازیم.

با حرکت خط مستقیم (5) در جهت بردار و می بینیم که حداکثر نقطه منطقه در نقطه A از تقاطع خط مستقیم (3) و خط مستقیم (2) خواهد بود. ما جواب سیستم معادلات را پیدا می کنیم:

این یعنی ما به نقطه (13;11) و.

با حرکت خط مستقیم (5) در جهت بردار و می بینیم که حداقل نقطه منطقه در نقطه B از تقاطع خط مستقیم (1) و خط مستقیم (4) خواهد بود. ما جواب سیستم معادلات را پیدا می کنیم:

این یعنی ما به نقطه (6;6) و.

2. یک شرکت مبلمان، کابینت و میز کامپیوتر ترکیبی تولید می کند. تولید آنها به دلیل در دسترس بودن مواد خام (تخته های با کیفیت بالا، اتصالات) و زمان کار ماشین آلات پردازش آنها محدود است. هر کابینت به 5 متر مربع تخته نیاز دارد، برای یک میز - 2 متر مربع. یراق آلات برای یک کابینت 10 دلار و برای یک میز 8 دلار هزینه دارند. این شرکت می تواند ماهانه تا 600 متر مربع تخته و لوازم جانبی به ارزش 2000 دلار از تامین کنندگان خود دریافت کند. هر کابینت به 7 ساعت کارکرد دستگاه نیاز دارد و جدول به 3 ساعت زمان نیاز دارد. در مجموع می توان از 840 ساعت کار ماشین در ماه استفاده کرد.

اگر یک کابینت 100 دلار و هر میز 50 دلار سود داشته باشد، یک شرکت باید چند کابینت ترکیبی و میز کامپیوتر در ماه تولید کند تا سود را به حداکثر برساند؟

1. تالیف کنید مدل ریاضیمشکل را با استفاده از روش سیمپلکس حل کنید.
2. یک مدل ریاضی از مسئله دوگانه ایجاد کنید، راه حل آن را بر اساس راه حل اصلی یادداشت کنید.
3. تعیین میزان کمبود منابع مورد استفاده و توجیه سودآوری طرح بهینه.
4. احتمالات افزایش بیشتر بازده تولید را بسته به استفاده از هر نوع منبع بررسی کنید.
5. ارزیابی امکان سنجی معرفی نوع جدیدی از محصول - قفسه کتاب، در صورتی که ساخت یک قفسه 1 متر مربع تخته و لوازم جانبی به ارزش 5 دلار هزینه داشته باشد و لازم است 0.25 ساعت کارکرد دستگاه و سود حاصل از فروش صرف شود. یک قفسه 20 دلار است.
1. بیایید یک مدل ریاضی برای این مسئله بسازیم:

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

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

بیایید داده های وظیفه را در قالب یک جدول بنویسیم:

میز 1

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

کار کنترلی روی نظم و انضباط:

"روش های راه حل های بهینه"

گزینه شماره 8

1. تصميم گرفتن روش گرافیکیمشکل برنامه ریزی خطی حداکثر و حداقل تابع  را با محدودیت های داده شده پیدا کنید:

راه حل

لازم است که مقدار حداقل تابع هدف و حداکثر را در سیستم محدودیت ها پیدا کنید:

9x 1 +3x 2 ≥30، (1)

X 1 +x 2 ≤4، (2)

x 1 + x 2 ≤8، (3)

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

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

بیایید یک خط مستقیم مطابق با مقدار تابع F = 0 بسازیم: F = 2x 1 +3x 2 = 0. بردار گرادیان که از ضرایب تابع هدف تشکیل شده است، جهت کمینه سازی F(X) را نشان می دهد. ابتدای بردار نقطه (0؛ 0) و انتهای آن نقطه (2؛ 3) است. این خط مستقیم را به صورت موازی حرکت خواهیم داد. از آنجایی که ما به حداقل راه حل علاقه مندیم، بنابراین خط مستقیم را حرکت می دهیم تا ابتدا ناحیه تعیین شده را لمس کند. در نمودار، این خط مستقیم با یک خط نقطه نشان داده شده است.

سر راست
منطقه را در نقطه C قطع می کند. از آنجایی که نقطه C در نتیجه تلاقی خطوط (4) و (1) به دست می آید، مختصات آن معادلات این خطوط را برآورده می کند:
.

پس از حل سیستم معادلات، به دست می آوریم: x 1 = 3.3333، x 2 = 0.

چگونه می توانیم مقدار حداقل تابع هدف را پیدا کنیم: .

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

بیایید یک خط مستقیم مطابق با مقدار تابع F = 0 بسازیم: F = 2x 1 +3x 2 = 0. بردار گرادیان که از ضرایب تابع هدف تشکیل شده است، جهت بیشینه سازی F(X) را نشان می دهد. ابتدای بردار نقطه (0؛ 0) و انتهای آن نقطه (2؛ 3) است. این خط مستقیم را به صورت موازی حرکت خواهیم داد. از آنجایی که ما به حداکثر راه حل علاقه مند هستیم، بنابراین خط مستقیم را تا آخرین لمس منطقه تعیین شده حرکت می دهیم. در نمودار، این خط مستقیم با یک خط نقطه نشان داده شده است.

سر راست
منطقه را در نقطه B قطع می کند. از آنجایی که نقطه B در نتیجه تقاطع خطوط (2) و (3) به دست می آید، مختصات آن معادلات این خطوط را برآورده می کند:

.

چگونه می توانیم حداکثر مقدار تابع هدف را پیدا کنیم: .

پاسخ:
و
.

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

راه حل

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

بیایید مقدار حداقل تابع هدف را تعیین کنیم
تحت شرایط زیر - محدودیت:
.

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

در نابرابری 1 معنی (≥) متغیر پایه را معرفی می کنیم ایکس 3 با علامت منفی در نابرابری دوم معنی (≤) متغیر پایه را معرفی می کنیم ایکس 4 . در نابرابری سوم معنی (≤) متغیر پایه x 5 را معرفی می کنیم.

بیایید متغیرهای مصنوعی را معرفی کنیم : در برابری اول یک متغیر معرفی می کنیم ایکس 6 ;

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

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

مبنای حاصل را مصنوعی و روش حل را روش پایه مصنوعی می نامند.

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

از معادلات، متغیرهای مصنوعی را بیان می کنیم: x 6 = 4-x 1 -x 2 +x 3، که آنها را به تابع هدف جایگزین می کنیم: یا.

ماتریس ضریب
این سیستم معادلات به شکل زیر است:
.

بیایید سیستم معادلات متغیرهای اصلی را حل کنیم: ایکس 6 ، ایکس 4 ، ایکس 5.

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

X1 = (0,0,0,2,10,4)

راه حل اساسی اگر غیر منفی باشد، قابل قبول نامیده می شود.

	ایکس 1	ایکس 2	ایکس 3	ایکس 4	ایکس 5	ایکس 6
ایکس 6
ایکس 4
ایکس 5

طرح مرجع فعلی بهینه نیست زیرا ضرایب مثبت در خط شاخص وجود دارد. به عنوان ستون اصلی، ستون مربوط به متغیر x 2 را انتخاب می کنیم، زیرا این بزرگترین ضریب است. بیایید مقادیر را محاسبه کنیم D من و از بین آنها کوچکترین را انتخاب می کنیم: min(4: 1، 2: 2، 10: 2) = 1.

بنابراین، خط 2 پیشرو است.

عنصر تفکیک کننده برابر با (2) است و در تقاطع ستون اصلی و ردیف جلو قرار دارد.

	ایکس 1	ایکس 2	ایکس 3	ایکس 4	ایکس 5	ایکس 6
ایکس 6
ایکس 4
ایکس 5

قسمت بعدی جدول سیمپلکس را تشکیل می دهیم. به جای متغیر x 4، طرح 1 شامل متغیر x 2 می شود.

ردیف مربوط به متغیر x 2 در پلان 1 با تقسیم تمام عناصر ردیف x 4 پلان 0 بر عنصر تفکیک کننده RE = 2 به دست می آید. به جای عنصر حل کننده 1 می گیریم. در سلول های باقی مانده از ستون x 2 صفر می نویسیم.

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

	ایکس 1	ایکس 2	ایکس 3	ایکس 4	ایکس 5	ایکس 6
ایکس 6
ایکس 2
ایکس 5
	1 1/2 + 1 1/2 M

طرح مرجع فعلی بهینه نیست زیرا ضرایب مثبت در ردیف شاخص وجود دارد. به عنوان ستون اصلی، ستون مربوط به متغیر x 1 را انتخاب می کنیم، زیرا این بزرگترین ضریب است. بیایید مقادیر را محاسبه کنیم D منبر اساس ردیف به عنوان ضریب تقسیم: و از بین آنها کوچکترین را انتخاب می کنیم: min (3: 1 1 / 2، -، 8: 2) = 2.

بنابراین، خط 1 پیشرو است.

عنصر تفکیک کننده برابر است با (1 1/2) و در تقاطع ستون اصلی و ردیف جلو قرار دارد.

	ایکس 1	ایکس 2	ایکس 3	ایکس 4	ایکس 5	ایکس 6
ایکس 6	1 1 / 2
ایکس 2
ایکس 5
	-1 1 / 2 +1 1 / 2 م

قسمت بعدی جدول سیمپلکس را تشکیل می دهیم. به جای متغیر x 6، طرح 2 شامل متغیر x 1 می شود.

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

	ایکس 1	ایکس 2	ایکس 3	ایکس 4	ایکس 5	ایکس 6
ایکس 1
ایکس 2
ایکس 5

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

نسخه نهایی جدول سیمپلکس:

	ایکس 1	ایکس 2	ایکس 3	ایکس 4	ایکس 5	ایکس 6
ایکس 1
ایکس 2
ایکس 5

از آنجایی که هیچ متغیر مصنوعی در جواب بهینه وجود ندارد (برابر صفر هستند)، این جواب قابل قبول است.

طرح بهینه را می توان به صورت زیر نوشت: x 1 = 2، x 2 = 2:.

پاسخ:
,
.

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

طرح حمل و نقلی را بیابید که کمترین هزینه های پولی را داشته باشد (طرح حمل و نقل اولیه را با استفاده از روش "گوشه شمال غربی" انجام دهید).

راه حل

اجازه دهید شرایط لازم و کافی برای حل شدن مسئله را بررسی کنیم:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

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

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





نیاز دارد

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

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

عنصر مورد نیاز 4 است. برای این عنصر، موجودی ها 300، نیازمندی ها 250 است. چون حداقل 250 است، آن را کم می کنیم: .

			300 - 250 = 50


250 - 250 = 0

عنصر مورد نیاز برابر است با 2. برای این عنصر موجودی 50، مورد نیاز 400 است. چون حداقل 50 است، آن را کم می کنیم: .

			50 - 50 = 0


	400 - 50 = 350

عنصر مورد نیاز 5 است. برای این عنصر، موجودی 300، مورد نیاز 350 است. از آنجایی که حداقل 300 است، آن را کم می کنیم:


			300 - 300 = 0

	350 - 300 = 50

عنصری که به دنبال آن هستید 3 است. برای این عنصر، موجودی ها 200، مورد نیاز 50 است. از آنجایی که حداقل 50 است، آن را کم می کنیم:



			200 - 50 = 150
	50 - 50 = 0

عنصر مورد نیاز 6 است. برای این عنصر، موجودی 150، مورد نیاز 150 است. از آنجایی که حداقل 150 است، آن را کم می کنیم:



			150 - 150 = 0
		150 - 150 = 0





نیاز دارد

کار آزمایشگاهی شماره 1. حل مسائل برنامه ریزی خطی

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

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

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

مثال. حداکثر مقدار تابع هدف را بیابید L=2ایکس 1 +2ایکس 2 تحت محدودیت های داده شده

راه حل.اجازه دهید دامنه حل سیستم قیود را بسازیم و علائم نابرابری را به علائم برابری دقیق تغییر دهیم:

ل 1: 3ایکس 1 -2ایکس 2 +6=0,

ل 2: 3ایکس 1 +ایکس 2 -3=0,

ل 3:ایکس 1 -3=0.

Dبا

2 0 1 3 ایکس 1

(ل 1) (ل 3)

سر راست ل 1 هواپیما را تقسیم می کند ایکسدر باره دربه دو نیم صفحه، که از بین آنها باید یکی را انتخاب کنید که اولین نابرابری در سیستم (3) را برآورده کند. برای انجام این کار، بیایید t را در نظر بگیریم. در باره(0; 0) و آن را به نامساوی جایگزین کنید. اگر درست باشد، پس باید نیم صفحه را از خط مستقیمی که به اصطلاح در آن قرار دارد سایه بزنید. در باره(0; 0). همین کار را با خطوط مستقیم انجام دهید. ل 2 و ل 3. دامنه راه حل های نامساوی (3) یک چند ضلعی است ABCD. برای هر نقطه از صفحه تابع Lیک مقدار ثابت می گیرد L=L 1 . مجموعه تمام نقاط فعلی یک خط مستقیم است L=ج 1 ایکس 1 +ج 2 ایکس 2 (در مورد ما L=2ایکس 1 +2ایکس 2) عمود بر بردار با(با 1 ;با 2) (با(2؛ 2))، که از مبدأ آمده است. اگر این خط در جهت مثبت بردار حرکت کند با، سپس تابع هدف Lافزایش می یابد، در غیر این صورت کاهش می یابد. بنابراین، در مورد ما، خط مستقیم در خروجی از چند ضلعی ABCDتصمیمات از طریق به اصطلاح که در(3؛ 7.5)، و بنابراین شامل. که درتابع هدف حداکثر مقدار را می گیرد، یعنی. Lحداکثر =2ּ3+2ּ7.5=21. به طور مشابه، مشخص می شود که حداقل مقداری که تابع می گیرد است D(1; 0) و L min =2ּ1+2ּ0=2.

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

1. وظیفه عمومیبرنامه‌ریزی خطی با معرفی به تعداد متغیرهای کمکی به تعداد نابرابری‌ها در سیستم محدودیت‌ها، به یک مسئله متعارف کاهش می‌یابد (محدودیت‌ها دارای علائم مساوی هستند).

2. تابع هدف از طریق متغیرهای اساسی و کمکی بیان می شود.

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

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

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

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

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

8. تبدیل جداول سیمپلکس تا حصول طرح بهینه انجام می شود.

مثال. حداکثر مقدار یک تابع را بیابید
، اگر متغیر باشد
ارضای سیستم محدودیت ها:

راه حل. 1. متغیرهای جدید را معرفی کنید
، که به کمک آن نابرابری های سیستم را به معادله تبدیل می کنیم:

علامت ضرایب تابع هدف را تغییر می دهیم یا در فرم می نویسیم
. اولین جدول سیمپلکس را در خط صفر که می نویسیم پر می کنیم ایکس 1 ,ایکس 2 و (شانس رایگان). در ستون صفر - ایکس 3 ,ایکس 4 ,ایکس 5 و اف. این جدول را با استفاده از سیستم معادلات حاصل و تابع هدف تبدیل شده پر می کنیم.

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

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

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

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

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

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

	ایکس 1	ایکس 4		ایکس 3	ایکس 2
ایکس 3			ایکس 1
ایکس 2			ایکس 2
ایکس 5			ایکس 5

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

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

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

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

برای حل مسائل برنامه نویسی خطی، از افزونه Solution Search استفاده کنید. ابتدا باید مطمئن شوید که این افزونه در برگه Data در گروه Analysis وجود دارد (برای سال 2003، به ابزارها مراجعه کنید). اگر دستور Find a Solution یا گروه Analysis وجود ندارد، باید این افزونه را دانلود کنید.

برای انجام این کار، روی Microsoft Office File (2010) کلیک کنید، سپس روی دکمه Excel Options کلیک کنید. در پنجره Excel Options که ظاهر می شود، کادر Add-ins را در سمت چپ انتخاب کنید. در سمت راست پنجره، مقدار فیلد Control باید بر روی Excel Add-ins تنظیم شود، روی دکمه “Go” که در کنار این فیلد قرار دارد کلیک کنید. در پنجره Add-Ins، کادر کنار Find a solution را انتخاب کرده و OK را کلیک کنید. سپس می توانید با افزونه Search for Solutions نصب شده کار کنید.

قبل از فراخوانی Search for a Solution، باید داده هایی را برای حل یک مسئله برنامه ریزی خطی (از یک مدل ریاضی) در یک کاربرگ آماده کنید:

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

2) یک وابستگی به سلول های متغیر برای تابع هدف و یک وابستگی به سلول های متغیر برای قسمت های چپ سیستم محدودیت در سلول های آزاد باقی مانده معرفی کنید. برای معرفی فرمول های وابستگی، استفاده از تابع ریاضی SUMPRODUCT راحت است.

در مرحله بعد، باید از افزونه Search for a solution استفاده کنید. در تب Data، در گروه Analysis، Find a Solution را انتخاب کنید. کادر گفتگوی Search for Solution ظاهر می شود که باید به صورت زیر تکمیل شود:

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

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

3) کادر انتخاب «متغیرهای نامحدود را غیرمنفی کنید» علامت بزنید. روش حل «جستجوی راه حل برای مسائل خطی با استفاده از روش سیمپلکس» را انتخاب کنید. پس از کلیک بر روی دکمه "یافتن راه حل"، روند حل مشکل شروع می شود. در نتیجه، کادر محاوره ای "نتایج جستجوی راه حل" و جدول اصلی با سلول های پر شده برای مقادیر متغیر و مقدار بهینه تابع هدف ظاهر می شود.

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

;

,
.

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

ما وابستگی هایی را برای تابع هدف و سیستم محدودیت ها معرفی می کنیم. برای این کار فرمول =SUMPRODUCT(A2:B2;A3:B3) را در سلول C2 وارد کنید. در سلول های C4 و C5، به ترتیب، فرمول ها عبارتند از: =SUMPRODUCT(A2:B2,A4:B4) و =SUMPRODUCT(A2:B2,A5:B5). در نتیجه یک جدول بدست می آوریم.

دستور “Search for a solution” را اجرا کنید و پنجره Search for a solution را که به صورت زیر ظاهر می شود پر کنید. در قسمت "بهینه سازی تابع هدف" سلول C2 را وارد کنید. بهینه سازی مقدار سلول هدف "حداکثر" را انتخاب کنید.

در قسمت "تغییر سلول های متغیر"، سلول های در حال تغییر A2:B2 را وارد کنید. در قسمت "مطابق با محدودیت ها" با استفاده از دکمه "افزودن" محدودیت های مشخص شده را وارد کنید. ارجاع به سلول $C$4:$C$5 ارجاع به محدودیت =$D$4:$D$5 بین آنها علامت<= затем кнопку «ОК».

کادر انتخاب «متغیرهای نامحدود را غیرمنفی کنید» علامت بزنید. روش حل «جستجوی راه حل برای مسائل خطی با استفاده از روش سیمپلکس» را انتخاب کنید.

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

در کادر محاوره ای "نتایج جستجوی راه حل"، نتیجه x1=0.75، x2=0.75، F=1.5 را ذخیره کنید - برابر با حداکثر مقدار تابع هدف.

وظایف برای کار مستقل

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

1. اف(ایکس)=10ایکس 1 +5ایکس 2 2. اف(ایکس)=3ایکس 1 -2ایکس 2

3. اف(ایکس)=3ایکس 1 +5ایکس 2 4. اف(ایکس)=3ایکس 1 +3ایکس 2

5. اف(ایکس)=4ایکس 1 -3ایکس 2 6. اف(ایکس)=2ایکس 1 -ایکس 2

7. اف(ایکس)=-2ایکس 1 +4ایکس 2 8. اف(ایکس)=4ایکس 1 -3ایکس 2

9. اف(ایکس)=5ایکس 1 +10ایکس 2 10. اف(ایکس)=2ایکس 1 +ایکس 2

11. اف(ایکس)=ایکس 1 +ایکس 2 12. اف(ایکس)=3ایکس 1 +ایکس 2

13. اف(ایکس)=4ایکس 1 +5ایکس 2 14. اف(ایکس)=3ایکس 1 +2ایکس 2

15. اف(ایکس)=-ایکس 1 -ایکس 2 16. اف(ایکس)=-3ایکس 1 -5ایکس 2

17. اف(ایکس)=2ایکس 1 +3ایکس 2 18. اف(ایکس)=4ایکس 1 +3ایکس 2

19. اف(ایکس)=-3ایکس 1 -2ایکس 2 20. اف(ایکس)=-3ایکس 1 +4ایکس 2

21. اف(ایکس)=5ایکس 1 -2ایکس 2 22. اف(ایکس)=-2ایکس 1 +3ایکس 3

23. اف(ایکس)=2ایکس 1 +3ایکس 2 24. اف(ایکس)=4ایکس 1 +3ایکس 2

25. اف(ایکس)=-3ایکس 1 -2ایکس 2 26. اف(ایکس)=-3ایکس 1 +4ایکس 2

27. اف(ایکس)=-2ایکس 1 +4ایکس 2 28. اف(ایکس)=4ایکس 1 -3ایکس 2

29. اف(ایکس)=-ایکس 1 -ایکس 2 30. اف(ایکس)=-3ایکس 1 -5ایکس 2

کنترل سوالات

1. به چه مسائلی مسائل برنامه ریزی خطی می گویند؟

2. مثال هایی از مسائل برنامه ریزی خطی بزنید.

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

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

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

آژانس فدرال آموزش

موسسه آموزشی بودجه دولتی

آموزش عالی حرفه ای

"دانشگاه فنی دولتی اومسک"

محاسبات و کارهای گرافیکی

بر اساس رشته "تئوری کنترل بهینه »

در مورد موضوع "روشهای بهینه سازی و تحقیق در عملیات »

گزینه 7

تکمیل شد:

دانشجوی مکاتبه ای

گروه سال چهارم ZA-419

نام کامل: Kuzhelev S. A.

بررسی شد:

دویاتریکووا M. V.

اومسک - 2012
^

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

7) 7ایکس 1 + 6ایکس 2 → حداکثر

20ایکس 1 + 6ایکس 2 ≤ 15

16ایکس 1 − 2ایکس 2 ≤ 18

8ایکس 1 + 4ایکس 2 ≤ 20

13ایکس 1 + 3ایکس 2 ≤ 4

ایکس 1 , ایکس 2 ≥ 0.

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

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

اولین محدودیت مدل دارای فرم است . با جایگزینی علامت ≤ در آن با علامت = معادله را بدست می آوریم . در شکل 1.1 یک خط مستقیم را تعریف می کند (1)، که صفحه را به دو نیم صفحه تقسیم می کند، در این مورد بالای خط و زیر آن. برای انتخاب اینکه کدام یک نابرابری را ارضا می کند ، مختصات هر نقطه ای را که روی یک خط معین قرار ندارد جایگزین کنید (مثلاً مبدا ایکس 1 = 0, ایکس 2 = 0). از آنجایی که عبارت صحیح را به دست می آوریم (20 0 + 6 0 = 0 ≤15)، پس نیم صفحه حاوی مبدا مختصات (که با یک فلش مشخص شده است) نابرابری را برآورده می کند. در غیر این صورت یک نیم هواپیما دیگر.

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

مرحله 2. رسم یک خط تراز خط سطح تابع هدف مجموعه نقاطی از صفحه است که در آن تابع هدف مقدار ثابتی می گیرد. چنین مجموعه ای با معادله به دست می آید f ( ایکس) = پایان. برای مثال بگذاریم پایان = 0 و یک خط در سطح بکشید f ( ایکس) = 0، یعنی در مورد ما خط مستقیم 7 ایکس 1 + 6ایکس 2 = 0.

این خط از مبدا می گذرد و عمود بر بردار است. این بردار گرادیان تابع هدف در نقطه (0,0) است. گرادیان یک تابع بردار مقادیر مشتقات جزئی یک تابع معین در نقطه مورد نظر است. در مورد مسئله LP، مشتقات جزئی تابع هدف برابر با ضرایب هستند. سیمن، j = 1 , ..., n.

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

در محل تقاطع خطوط (2) و (3) قرار دارد (شکل 1 را ببینید) و راه حل بهینه را مشخص می کند.

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