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

ما خطوط مستقیم را در سیستم مختصات 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 غیرممکن است و ما یک طرح بهینه به دست آورده ایم.

کار آزمایشگاهی شماره 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. یک الگوریتم برای حل مسائل برنامه ریزی خطی با استفاده از اکسل توضیح دهید.

موضوع: برنامه ریزی خطی

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

توجه!

این نسخه آزمایشی کار شماره 2073 است، قیمت نسخه اصلی 200 روبل است. در Microsoft Word طراحی شده است.

پرداخت. مخاطب.

گزینه 7. مقادیر حداکثر و حداقل را بیابیدتابع خطی Ф = 2x 1 - 2 x 2با محدودیت: x ​​1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0، i = 1.2.

راه حل:

با جایگزین کردن مشروط علائم نابرابری با علائم برابری، سیستمی از معادلات x1 + x2 = 4 را به دست می‌آوریم.

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

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

حداقل مقدار تابع

نقاط - در نقطه M(2; 2)

Ф min = 2·2 - 2·2 = 0.

حداکثر مقدار در نقطه N (10; 0) به دست می آید.

Ф max = 2·10 - 2·0 = 20.

گزینه 8. مقادیر حداکثر و حداقل را بیابید

تابع خطی Ф = x 1 + x 2

با محدودیت: x ​​1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0، i = 1.2.

راه حل:

با جایگزینی مشروط علائم نابرابری با علائم برابری، سیستمی از معادلات x1 - 4 x2 = 4 را به دست می آوریم.

3 x1 - x2 = 0;

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

حداقل مقدار تابع

برای مثال، در NP مستقیم

در نقطه P(4; 0)

Ф min = 4 + 0 = 4.

ODR از بالا محدود نمی شود، بنابراین، Ф max = + ∞.

گزینه 10. مقادیر حداکثر و حداقل را پیدا کنید

تابع خطی Ф = 2 x 1 - 3 x 2

با محدودیت: x ​​1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0، i = 1.2.

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

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

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

بیایید بردار Г(2; -3) را بسازیم و از مبدا مختصات ترسیم کنیم خط سطح- سر راست.

ما خط سطح را در جهت حرکت می دهیم، مقدار Ф افزایش می یابد. در نقطه S(7; 0) تابع هدف به حداکثر Ф max =2·7–3·0= = 14 می رسد. خط سطح را در جهت حرکت می دهیم، مقدار Ф کاهش می یابد. حداقل مقدار تابع در نقطه N(0; 5) است.

Ф min = 2·0 – 3·5 = –15.

وظیفه 2.B. حل مسئله برنامه ریزی خطی

روش سیمپلکس تحلیلی

گزینه 7. تابع هدف Ф = x 1 - x 2 + x 3 + x 4 + x 5 - x 6 را به حداقل برسانید

با محدودیت: x ​​1 + x 4 + 6 x 6 = 9،

3 x 1 + x 2 - 4 x 3 + 2 x 6 = 2،

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

راه حل:

تعداد مجهولات n=6، تعداد معادلات m=3. بنابراین، r = n-m = 3 مجهول را می توان آزاد در نظر گرفت. بیایید x 1، x 3 و x 6 را انتخاب کنیم.

متغیرهای پایه x 2، x 4 و x 5 را بر حسب متغیرهای آزاد بیان می کنیم و سیستم را به یک واحد کاهش می دهیم.

x 2 = 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 = 9 – x 1 – 6 x 6 (*)

x 5 = 6 – x 1 – 2 x 3 – 2 x 6

تابع هدف به صورت زیر خواهد بود:

Ф = x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 – x 1 – 6 x 6 +6 – x 1 – 2 x 3 – 2 x 6 – x 6 =

13 + 2 x 1 – 5 x 3 – 7 x 6

بیایید x 1 = x 3 = x 6 = 0 را قرار دهیم و متغیرهای اصلی مقادیر x 2 = 2 را خواهند گرفت. x 4 = 9; x 5 = 6، یعنی اولین راه حل امکان پذیر (0؛ 2؛ 0؛ 9؛ 6؛ 0)، تابع هدف Ф 1 = 13.

متغیرهای x 3 و x 6 با ضرایب منفی در تابع هدف قرار می گیرند، بنابراین با افزایش مقادیر آنها، مقدار Ф کاهش می یابد. برای مثال x 6 را در نظر بگیرید. از معادله 1 سیستم (*) مشخص است که افزایش مقدار x 6 تا x 6 = 1 امکان پذیر است (در حالی که x 2 ³ 0). در این حالت x 1 و x 3 برابر با صفر می مانند. اکنون x 4، x 5، x 6 را به عنوان متغیرهای پایه، و x 1، x 2، x 3 را به عنوان متغیرهای آزاد در نظر می گیریم. اجازه دهید متغیرهای پایه جدید را بر حسب متغیرهای رایگان جدید بیان کنیم. ما گرفتیم

x 6 = 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 = 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 = 4 + 2 x 1 + x 2 - 6 x 3

Ф = 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

بیایید مقادیر صفر را به متغیرهای آزاد اختصاص دهیم، یعنی x 1 = x 2 = x 3 = 0، در حالی که x 6 = 1، x 4 = 3، x 5 = 4، یعنی سومین راه حل امکان پذیر (0 ؛ 0؛ 0؛ 3؛ 4؛ 1). در این مورد Ф 3 = 6.

متغیر x 3 با ضریب منفی در تابع هدف قرار می گیرد، بنابراین افزایش x 3 نسبت به مقدار صفر منجر به کاهش F می شود. از معادله 2 مشخص می شود که x 3 می تواند به 1/4 افزایش یابد. ، از معادله 3 - تا 2/3. معادله دوم بحرانی تر است. اجازه دهید متغیر x 3 را به تعداد پایه و x 4 را به تعداد آزاد تبدیل کنیم.

اکنون x 1، x 2 و x 4 را به عنوان متغیرهای رایگان جدید در نظر می گیریم. اجازه دهید از طریق آنها متغیرهای پایه جدید x 3، x 5، x 6 را بیان کنیم. بیایید سیستم را دریافت کنیم

x 3 = 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 = 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 = 3/2 - 1/6 x 1 - 1/6 x 4

تابع هدف شکل خواهد گرفت

Ф = 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

متغیرهای x 1 و x 2 با ضرایب منفی در تابع هدف قرار می گیرند، بنابراین با افزایش مقادیر آنها، مقدار Ф کاهش می یابد. برای مثال x 2 را در نظر بگیرید. از معادله 2 سیستم مشخص است که افزایش مقدار x 2 تا x 2 = 5 (در حالی که x 5 ³ 0) امکان پذیر است. در این حالت، x 1 و x 4 صفر می مانند، مقادیر سایر متغیرها برابر با x 3 = 3/2 است. x 5 = 0، x 6 = 3/2، یعنی چهارمین راه حل امکان پذیر (0؛ 5؛ 3/2؛ 0؛ 0؛ 3/2). در این مورد Ф 4 = 5/4.

اکنون x 1، x 4 و x 5 را به عنوان متغیرهای رایگان جدید در نظر می گیریم. اجازه دهید از طریق آنها متغیرهای پایه جدید x 2، x 3، x 6 را بیان کنیم. بیایید سیستم را دریافت کنیم

x 2 = 5 – 4 x 1 + x 4 – 2 x 5

x 3 = 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 = 3/2 - 1/6 x 1 - 1/6 x 4

تابع هدف شکل خواهد گرفت

Ф = - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

ضرایب هر دو متغیر در عبارت Ф مثبت هستند، بنابراین کاهش بیشتر در مقدار Ф غیرممکن است.

یعنی حداقل مقدار Ф min = - 5، آخرین راه حل امکان پذیر (0؛ 5؛ 3/2؛ 0؛ 0؛ 3/2) بهینه است.

گزینه 8. تابع هدف Ф = 4 x 5 + 2 x 6 را به حداکثر برسانید

با محدودیت: x ​​1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 = 30;

x 3 + x 5 - 2 x 6 = 6;

2 x 4 + 3 x 5 - 2 x 6 = 18;

راه حل:

تعداد معادلات 4 و تعداد مجهولات 6 است. بنابراین، r = n – m = 6 – 4 = 2 متغیر را می توان به عنوان متغیر آزاد، 4 متغیر را به عنوان متغیر اصلی انتخاب کرد. x 5 و x 6 را به عنوان رایگان انتخاب می کنیم و x 1 , x 2 , x 3 , x 4 را به عنوان موارد پایه انتخاب می کنیم. اجازه دهید متغیرهای اساسی را بر حسب متغیرهای آزاد بیان کنیم و سیستم معادلات را به یک واحد تقلیل دهیم

x 1 = 12 - x 5 - x 6 ;

x 2 = 30 - 5 x 5 + x 6 ;

x 3 = 6 - x 5 + 2 x 6 ;

x 4 = 9 - 3/2 x 5 + x 6;

تابع هدف را به شکل Ф = 4 x 5 + 2 x 6 می نویسیم. بیایید مقادیر صفر را به متغیرهای آزاد x 5 = x 6 = 0 اختصاص دهیم. در این حالت، متغیرهای اصلی مقادیر x 1 = 12، x 2 = 30، x 3 = 6، x 4 = 9 را خواهند گرفت. ، یعنی اولین راه حل امکان پذیر (12، 30، 6، 9، 0،) و Ф 1 = 0 را دریافت می کنیم.

هر دو متغیر آزاد با ضرایب مثبت وارد تابع هدف می‌شوند، یعنی افزایش بیشتر در F امکان‌پذیر است. مثلاً x 6 را به تعداد ضرایب پایه تبدیل می‌کنیم. از رابطه (1) مشخص می شود که x 1 = 0 در x 5 = 12، در (2) ÷ (4) x 6 با ضرایب مثبت گنجانده شده است. بیایید به یک مبنای جدید برویم: متغیرهای پایه - x 6، x 2، x 3، x 4، رایگان - x 1، x 5. بیایید متغیرهای پایه جدید را بر حسب رایگان جدید بیان کنیم.

x 6 = 12 - x 1 - x 5;

x 2 = 42 - x 1 - 6 x 5;

x 3 = 30 - 2 x 1 - 3 x 5 ;

x 4 = 21 - x 1 - 5/2 x 5 ;

تابع هدف به شکل Ф = 24 - 2 x 1 + 2 x 5 خواهد بود.

بیایید مقادیر صفر را به متغیرهای آزاد x 1 = x 5 = 0 اختصاص دهیم. در این حالت، متغیرهای اصلی مقادیر x 6 = 12، x 2 = 42، x 3 = 30، x 4 = 21 را خواهند گرفت. ، یعنی دومین راه حل امکان پذیر (0، 42، 30، 21، 0، 12) و Ф 2 = 24 را دریافت می کنیم.

تابع هدف x 5 با یک ضریب مثبت گنجانده شده است، یعنی افزایش بیشتر در F امکان پذیر است. بیایید به یک پایه جدید برویم: متغیرهای اساسی - x 6، x 5، x 3، x 4، آزاد - x 1 ، x 2. بیایید متغیرهای پایه جدید را از طریق new free بیان کنیم

x 6 = 5 - 5/6 x 1 + 1/6 x 2;

x 5 = 7 - 1/6 x 1 - 1/6 x 2 ;

x 3 = 9 - 3/2 x 1 + 1/2 x 2 ;

x 4 = 7/2 - 7/12 x 1 + 5/12 x 5 ;

تابع هدف به شکل Ф = 38 – 7/2 x 1 – 1/3 x 2 خواهد بود.

بیایید مقادیر صفر را به متغیرهای آزاد x 1 = x 2 = 0 اختصاص دهیم. در این حالت، متغیرهای پایه مقادیر x 6 = 5، x 5 = 7، x 3 = 9، x 4 = 7 را خواهند گرفت. /2، یعنی سومین راه حل امکان پذیر X 3 = (0، 0، 9، 7/2، 7، 5) و Ф 3 = 38 را به دست می آوریم.

هر دو متغیر با ضرایب منفی وارد تابع هدف می شوند، یعنی افزایش بیشتر F غیرممکن است.

بنابراین، آخرین راه حل امکان پذیر بهینه است، یعنی X opt = (0، 0، 9، 7/2، 7، 5) و Ф max = 38.

گزینه 10. تابع هدف Ф = x 2 + x 3 را به حداکثر برسانید

با محدودیت: x ​​1 - x 2 + x 3 = 1،

x 2 - 2 x 3 + x 4 = 2.

راه حل:

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

بیایید x 2 و x 3 را به عنوان متغیر آزاد در نظر بگیریم سپس متغیرهای اصلی x 1 و x 2 خواهند بود که به صورت آزاد بیان می کنیم.

x 1 = 1 + x 2 - x 3 ; (*)

x 4 = 2 - x 2 + 2 x 3 ;

تابع هدف قبلاً بر حسب x 2 و x 3 بیان شده است، یعنی Ф = x 2 + x 3.

برای x 2 = 0 و x 3 = 0، متغیرهای پایه برابر با x 1 = 1، x 4 = 2 خواهند بود.

ما اولین راه حل عملی X 1 = (1، 0، 0، 2)، با Ф 1 = 0 را داریم.

افزایش F با افزایش مثلاً مقدار x 3 امکان پذیر است که در عبارت Ф با ضریب مثبت (x 2 برابر با صفر باقی می ماند) گنجانده شده است. اولین معادله سیستم (*) نشان می دهد که x 3 را می توان به 1 (از شرط x 1 ³0) افزایش داد، یعنی این معادله محدودیتی را در افزایش مقدار x 3 اعمال می کند. اولین معادله سیستم (*) حل می شود. بر اساس این معادله به یک مبنای جدید می رویم و x 1 و x 3 را مبادله می کنیم. حالا متغیرهای پایه x 3 و x 4 و متغیرهای آزاد x 1 و x 2 خواهند بود. اکنون x 3 و x 4 را بر حسب x 1 و x 2 بیان می کنیم.

دریافت می کنیم: x 3 = 1 - x 1 + x 2 ; (**)

x 4 = 4 - 2 x 1 + x 2 ;

Ф = x 2 + 1 - x 1 + x 2 = 1 - x 1 + 2 x 2

با برابر کردن متغیرهای آزاد با صفر، دومین راه حل پایه قابل قبول X 2 = (0؛ 0؛ 1؛ 4) را به دست می آوریم که برای آن Ф 2 = 1 است.

افزایش F با افزایش x2 امکان پذیر است. افزایش x 2، با قضاوت بر اساس آخرین سیستم معادلات (**)، محدود نیست. در نتیجه، Ф مقادیر مثبت فزاینده بزرگتری به خود می گیرد، یعنی Ф max = + ¥.

بنابراین، تابع هدف Ф از بالا محدود نمی شود، بنابراین هیچ راه حل بهینه ای وجود ندارد.

وظیفه 2.D. یک مسئله دوتایی به یک مورد داده شده بنویسید

وظیفه اصلی

گزینه 7. تابع هدف Ф = 2 را به حداکثر برسانید× x 1 - x 4

با محدودیت: x ​​1 + x 2 = 20،

x 2 + 2× x 4 ≥ 5،

x 1 + x 2 + x 3 ≤ 8،

x i ≥ 0 (i = 1، 2، 3، 4)

راه حل:

اجازه دهید با وارد کردن متغیرهای اضافی در معادلات 2 و 3، سیستم محدودیت ها را به یک شکل واحد، به عنوان مثال، متعارف برسانیم.

x 1 + x 2 = 20،

x 2 + 2 × x 4 - x 5 = 5،

- x 1 + x 2 + x 3 + x 6 = 8.

ما یک مسئله نامتقارن از نوع 2 به دست آورده ایم. مشکل دوگانه به این صورت خواهد بود:

تابع هدف F = 20 را به حداقل برسانید × y 1 + 5 × y2+8 × y 3

در سال 1 - سال 3 ≥ 2,

y 1 + y 2 + y 3 ≥ 0,

y 3 ≥ 0,

2× y 2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

گزینه 8. تابع هدف Ф = x 2 - x 4 - 3 را به حداکثر برسانید× x 5

با محدودیت: x ​​1 + 2× x 2 - x 4 + x 5 = 1،

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2،

3 × x 2 + x 5 + x 6 = 5،

x i ≥ 0, (من = 1, 6)

راه حل:

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

مشکل اصلی: مشکل دوگانه:

F = C × X max F = B T × Y دقیقه

در A × X = B در A T × Y ≥ C T

در مسئله اصلی، ماتریس ردیف ضرایب برای متغیرهای تابع هدف به شکل C = (0; 1; 0; -1; -3; 0) است.

ماتریس-ستون اصطلاحات آزاد و ماتریس ضرایب برای متغیرها در سیستم محدودیت ها شکل دارند.

B = 2، A = 0 - 4 1 2 -1 0

بیایید ماتریس جابجایی ضرایب، یک ماتریس ردیفی از ضرایب برای متغیرهای تابع هدف و یک ماتریس ستونی از عبارت‌های آزاد را پیدا کنیم.

0 1 0 0 ولت T = (1؛ 2؛ 5)

A T = -1 2 0 C T = -1

مسئله دوگانه به شکل زیر نوشته می شود:

حداقل مقدار تابع هدف F = y 1 + 2 را پیدا کنید × y2+5 × y 3

تحت محدودیت y 1 ≥ 0،

2× y 1 - 4 × y2+3 × y 3 ≥ 1،

- y 1 + 2 × y 2 ≥ -1،

y 1 - y 2 + y 3 ≥ -3،

گزینه 10. تابع Ф = x 1 + x 2 + x 3 را به حداقل برسانید

با محدودیت: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2،

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3،

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4،

راه حل:

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

مشکل اصلی مشکل دوگانه

F = C × X دقیقه F = B T × حداکثر Y

در A × ایکس ≥ B در A T × Y ≤ اس تی

X ≥ 0 Y ≥ 0

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

C = (1؛ 1؛ 1)، B = 3، A = 6 4 5

بیایید ماتریس های مسئله دوگانه را پیدا کنیم

B T = (2; 3; 4) C T = 3 A T = 9 4 2

مسئله دوگانه به صورت زیر فرموله شده است:

تابع هدف F = 2y 1 + 3y 2 + 4y 3 را به حداکثر برسانید

تحت محدودیت 3 × y 1 + 6 × y2+8 × y 3 ≤ 1،

9× y 1 + 4 × y2+2 × y 3 ≤ 1،

7× y 1 + 5 × y2+4 × y 3 ≤ 1،

y i ≥ 0 (i = 1، 2، 3)

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

گزینه 7. تابع هدف را حداکثر کنید Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

با محدودیت: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

راه حل:

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

2 x 1 + 3 x 2 – x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

ما یک سیستم 3 معادله با 7 مجهول داریم. اجازه دهید 3 متغیر x 1 , z 1 , z 3 را به عنوان متغیرهای پایه، x 2 , x 3 , x 4 , z 2 را به عنوان متغیرهای آزاد انتخاب کرده و متغیرهای اساسی را از طریق آنها بیان کنیم.

از (2) x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6 داریم

با (1) و (3) جایگزین می کنیم، دریافت می کنیم

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 = 2.

بیایید یک جدول سیمپلکس ایجاد کنیم

جدول 1 تکرار I

پایه ای AC	آزادی. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z 1	2	0	7	-11		1	2	0	1/ 4	1/8
z 3	4	0	18	-17	13	0	4	1	4/13	13/8
اف	2	0	— 3	7	— 8	0	— 2	0		1

X 1 = (1؛ 0؛ 0؛ 0؛ 2؛ 0؛ 4) Ф 1 = 2.

جدول تکرار دوم 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x 4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z 3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
اف	4	0	4	— 4	0	1	0	0		32/7

X 2 = (14/8؛ 0؛ 0؛ 1/4؛ 0؛ 0؛ 4) Ф 2 = 4.

تکرار III جدول 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x 4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
اف	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 = (1؛ 0؛ 6/7؛ 10/7؛ 0؛ 0؛ 0) F 3 = 52/7.

جدول 4 تکرار IV

z 1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x 4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
اف	149/14	45/14	15	0	0	0	3/14	19/14

X 4 = (0؛ 0؛ 25/14؛ 37/14؛ 1/2؛ 0؛ 0) F 4 = 149/14.

هیچ عدد منفی در خط شاخص آخرین جدول وجود ندارد، یعنی در عبارت تابع هدف تمام Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

پاسخ: Ф m تبر = 149/14،

راه حل بهینه (0؛ 0؛ 25/14؛ 37/14؛ 1/2؛ 0؛ 0)

گزینه 8. تابع هدف Ф = 5 x 1 - x 3 را به حداقل برسانید

تحت محدودیت: x ​​1 + x 2 + 2 x 3 - x 4 = 3،

x 2 + 2 x 4 = 1،

راه حل:

تعداد متغیرها 4 است، رتبه ماتریس 2 است، بنابراین تعداد متغیرهای آزاد r = 4 - 2 = 2، تعداد متغیرهای اساسی نیز 2 است. اجازه دهید x 3، x 4 را به عنوان مثال در نظر بگیریم. متغیرهای آزاد، متغیرهای پایه x 1، x 2 را بر حسب آزاد بیان کنید و اجازه دهید سیستم را به یک واحد کاهش دهیم:

x 2 = 1 - 2 x 4،

x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4

Ф = 5 x 1 - x 3 = 5 (2 - 2 x 3 + 3 x 4) - x 3 = 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

اجازه دهید سیستم معادلات و تابع هدف را به شکلی مناسب برای جدول سیمپلکس بنویسیم، یعنی x 2 + 2 x 4 = 1،

x 1 + 2 x 3 - 3 x 4 = 2

F + 11 x 3 - 15 x 4 = 10

بیا یه میز درست کنیم

جدول 1 تکرار I

پایه ای AC	آزادی. AC
X 1	2	1	0		— 3		1/2
X 2	1	0	1	0	2
اف	10	0	0	11	— 15		— 11/2

X 1 = (2؛ 1؛ 0؛ 0) Ф 1 = 10.

جدول تکرار دوم 2

X 3	1	1/2	0	1	-3/2		3/4
X 2	1	0	1	0			1/2
اف	— 1	— 11/2	0	0	3/2		— 3/4

X 2 = (0؛ 1؛ 1؛ 0) Ф 2 = -1.

تکرار III جدول 3

X 3	7/4	1/2	3/4	1	0
X 4	1/2	0	1/2	0	1
اف	— 7/4	— 11/2	— 3/4	0	0

X 3 = (0؛ 0؛ 7/4؛ 1/2) F 3 = -7/4.

هیچ اعداد مثبتی در خط شاخص آخرین جدول وجود ندارد، یعنی در عبارت تابع هدف همه Г i > 0 وجود دارد. حالت I داریم، بنابراین، آخرین راه حل پایه بهینه است.

پاسخ: Ф min = -7/4، راه حل بهینه (0؛ 0؛ 7/4؛ 1/2)

********************

گزینه 10. تابع هدف Ф = x 1 + x 2 را کمینه کنید،

تحت محدودیت: x ​​1 –2 x 3 + x 4 = 2،

x 2 - x 3 + 2 x 4 = 1،

راه حل:

تعداد متغیرها 5 است، رتبه ماتریس 3 است، بنابراین تعداد متغیرهای آزاد r = 6-3 = 2 است. بیایید x 3 و x 4 را به عنوان متغیر آزاد در نظر بگیریم، و x 1، x 2، x 5 به عنوان موارد اولیه. همه معادلات سیستم قبلاً به یک واحد کاهش یافته اند (متغیرهای اصلی بر حسب متغیرهای آزاد بیان می شوند) اما به شکلی نوشته شده اند که برای استفاده از جداول سیمپلکس مناسب نیست. اجازه دهید سیستم معادلات را به شکل بنویسیم

x 1 - 2 x 3 + x 4 = 2

x 2 - x 3 +2 x 4 = 1

x 5 + x 3 - x 4 . = 5

تابع هدف را بر حسب متغیرهای آزاد بیان می کنیم و به شکل Ф - 3 x 3 +3 x 4 = 3 می نویسیم.

بیا یه میز درست کنیم

جدول 1 تکرار I

پایه ای AC	آزادی. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
اف	3	0	0	-3	3	0		-3/2

X 1 = (2؛ 3؛ 0؛ 0؛ 5) F 1 = 3.

جدول 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
اف	3/2	0	-3/2	-3/2	0	0

X 2 = (3/2؛ 0؛ 0؛ 1/2؛ 11/2) F 2 = 3/2.

هیچ اعداد مثبتی در ردیف شاخص آخرین جدول وجود ندارد، یعنی در عبارت تابع هدف همه Gi > 0 وجود دارد. حالت 1 را داریم، بنابراین، آخرین جواب پایه بهینه است.

پاسخ: Ф min = 3/2، راه حل بهینه (3/2؛ 0؛ 0؛ 1/2؛ 11/2).

معرفی

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

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

1. بیان مسئله

تابع هدف حداقل

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

شکل 1 - چند ضلعی راه حل های مسئله

سیستم محدودیت ها و تابع هدف مسئله در زیر ارائه شده است:

حل مشکل با استفاده از روش های زیر ضروری است:

روش گرافیکی برای حل مسائل LP;

روش جبری برای حل مسائل LP;

روش ساده برای حل مسائل LP.

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

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

روش شاخه و کران برای حل مسائل LP عدد صحیح.

روش Gomori برای حل مسائل LP عدد صحیح.

روش Balazs برای حل مسائل بولین LP.

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

2. راه حل گرافیکیمشکلات برنامه ریزی خطی

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

برنج. 2 راه حل گرافیکی مسئله LP

حداقل امتیاز

معادله خطی که از دو نقطه A1 و A2 می گذرد:

AB: (0;1); (3; 3)

VS: (3;3); (4;1)

سی دی: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5; 2)

با محدودیت:

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

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

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

متغيرهاي اضافي را معرفي كنيد كه تعداد آنها برابر با تعداد نابرابريهاي موجود در سيستم محدوديتها است.

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

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

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

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

متغیرهای رایگان

خیابان لین - اضافی کیت

شرایط غیر منفی برآورده شده است، بنابراین، راه حل بهینه پیدا شده است.

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

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

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

ما یک جدول ساده می سازیم:

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

ما حداکثر عنصر مثبت را در ردیف F انتخاب می کنیم، با این تفاوت که این ستون کلی خواهد بود.

برای یافتن عنصر کلی، برای همه موارد مثبت رابطه ایجاد می کنیم. 3/3; 9/1;- حداقل نسبت در خط x3. بنابراین - رشته عمومی و = 3 - عنصر عمومی.

=1/=1/3 را پیدا می کنیم. ما آن را به گوشه پایین سلولی که عنصر عمومی در آن قرار دارد می آوریم.

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

گوشه های بالای خط کلی را انتخاب کنید.

در تمام گوشه های پایینی ستون عمومی، حاصل ضرب مقدار را در گوشه بالا با - وارد می کنیم و مقادیر حاصل را انتخاب می کنیم.

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

سپس یک جدول جدید می سازیم که در آن تعیین سلول های عناصر ستون و ردیف عمومی مبادله می شود (x2 و x3).

مقادیری که قبلاً در گوشه پایین قرار داشتند در گوشه بالایی سطر و ستون عمومی قبلی نوشته می شوند.

مجموع مقادیر گوشه های بالا و پایین این سلول ها در جدول قبلی در گوشه بالایی سلول های باقی مانده نوشته شده است.

4. حل مسئله برنامه ریزی خطی با یافتن راه حل قابل قبول

اجازه دهید یک سیستم معادلات جبری خطی داده شود:

می توانیم فرض کنیم که همه چیز است، در غیر این صورت معادله مربوطه را در -1 ضرب می کنیم.

ما متغیرهای کمکی را معرفی می کنیم:

ما همچنین یک تابع کمکی را معرفی می کنیم

ما سیستم را تحت محدودیت (2) و شرایط به حداقل می رسانیم.

قانون یافتن راه‌حل مجاز: برای یافتن راه‌حل قابل قبول برای سیستم (1)، شکل (3) را تحت محدودیت‌های (2) به حداقل می‌رسانیم، xj را به عنوان مجهولات آزاد در نظر می‌گیریم، و xj را به عنوان مجهولات پایه در نظر می‌گیریم.

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

min f=0، پس تمام i باید برابر با صفر باشد. و مقادیر حاصل از xj یک راه حل قابل قبول برای سیستم (1) خواهد بود.

min f>0، یعنی سیستم اصلی راه حل عملی ندارد.

سیستم منبع:

از شرط مسئله از مبحث قبل استفاده شده است.

بیایید متغیرهای اضافی را معرفی کنیم:

یک راه حل قابل قبول برای مسئله اصلی پیدا شده است: x1 = 3، x2 = 3، F = -12. بر اساس راه حل امکان پذیر به دست آمده، با استفاده از روش سیمپلکس، راه حل بهینه برای مسئله اصلی را پیدا خواهیم کرد. برای انجام این کار، یک جدول سیمپلکس جدید از جدول به دست آمده در بالا می سازیم و سطر و سطر با تابع هدف مسئله کمکی را حذف می کنیم:

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

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

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

با محدودیت:

راه حل: بیایید سیستم محدودیت ها را به یک فرم استاندارد بیاوریم:

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

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

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

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??دقیقه

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

مرحله دوم روش سیمپلکس

بنابراین، در مرحله سوم از روش سیمپلکس، یک راه حل بهینه برای مسئله کمینه سازی با نتایج زیر یافت شد: y2 = -7 /8، y1 = -11/8، Ф = 12. به منظور یافتن مقدار تابع هدف مسئله دوگانه، مقادیر یافت شده متغیرهای پایه و آزاد را با تابع بیشینه سازی جایگزین می کنیم:

Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

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

Fmin = Фmax = -12

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

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

چند ضلعی اولیه از راه حل های یک مسئله برنامه نویسی عدد صحیح.

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

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

در نتیجه راه حل، طرح بهینه برای مسئله پیدا شد: x1 = 9/4، x2 = 5/2، F = -41/4. این راه حل با شرط عدد صحیح تنظیم شده در مسئله مطابقت ندارد. بیایید چند ضلعی حل اصلی را به دو ناحیه تقسیم کنیم، منطقه 3 را از آن جدا کنیم

چند ضلعی حل مسئله اصلاح شده

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

سیستم محدودیت برای ناحیه چپ

ناحیه سمت راست نشان دهنده نقطه C است.

سیستم محدودیت ها برای منطقه تصمیم درست در زیر ارائه شده است.

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

در نتیجه راه حل، طرح بهینه برای مسئله پیدا شد: x1 = 3، x2 = 3، F = -12. این طرح شرط صحیح بودن متغیرهای مسئله را برآورده می کند و می تواند به عنوان طرح مرجع بهینه برای مسئله برنامه ریزی خطی عدد صحیح اصلی پذیرفته شود. هیچ فایده ای برای حل منطقه راه حل مناسب وجود ندارد. شکل زیر پیشرفت حل مسئله برنامه ریزی خطی عدد صحیح را به صورت درختی نشان می دهد.

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

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

باید یک جواب عدد صحیح برای سیستم (1) پیدا کرد که تابع هدف F را به حداقل می رساند و همه ضرایب اعداد صحیح هستند.

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

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

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

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

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

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

که در آن و به ترتیب بخش های کسری از ضرایب و آزاد هستند

عضو اجازه دهید یک متغیر کمکی را در محدودیت (3) معرفی کنیم:

اجازه دهید ضرایب و در محدودیت (4) را تعیین کنیم:

که و به ترتیب نزدیکترین اعداد صحیح از زیر برای و هستند.

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

راه حل: بیایید سیستم قیود خطی و تابع هدف را به شکل متعارف بیاوریم:

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

حل مسائل LP Boolean با استفاده از روش Balazs.

نسخه خود را برای یک مسئله برنامه ریزی خطی عدد صحیح با متغیرهای بولی، با در نظر گرفتن قوانین زیر ایجاد کنید: مسئله از حداقل 5 متغیر، حداقل 4 قید استفاده می کند، ضرایب محدودیت ها و تابع هدف به طور دلخواه انتخاب می شوند، اما در چنین مواردی روشی که سیستم محدودیت ها سازگار است. وظیفه حل LCLP با متغیرهای Boolean با استفاده از الگوریتم Balazs و تعیین کاهش پیچیدگی محاسبات در رابطه با حل مسئله با استفاده از روش جستجوی جامع است.

اجرای محدودیت ها

مقدار F

محدودیت فیلتر:

تعیین کاهش تلاش محاسباتی

راه حل مسئله با استفاده از روش جستجوی جامع 6*25=192 عبارت محاسبه شده است. راه حل مسئله با استفاده از روش بالاز 3*6+(25-3)=47 عبارت محاسبه شده است. کاهش کل در پیچیدگی محاسبات در رابطه با حل مسئله با استفاده از روش جستجوی جامع عبارت است از:

نتیجه

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

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

ادبیات:

1. لیاشچنکو I.N. برنامه نویسی خطی و غیر خطی / I.N. Lyashchenko، E.A. Karagodova، N.V. Chernikova، N.Z. Shor. - ک.: «دبیرستان»، 1975، 372 ص.

2. دستورالعمل تکمیل یک پروژه درسی در رشته "ریاضیات کاربردی" برای دانش آموزان تخصص "سیستم ها و شبکه های کامپیوتری" فرم های تحصیلی تمام وقت و نیمه وقت / گردآوری شده توسط: I.A. Balakireva, A.V. Skatkov - سواستوپل: SevNTU انتشارات، 2003. - 15 ص.

3. راهنمای مطالعه رشته "ریاضیات کاربردی"، بخش "روش های جستجوی جهانی و کمینه سازی یک بعدی" / Comp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Publishing House, 2000. - 31 p.

4. راهنمای مطالعه رشته "ریاضیات کاربردی" برای دانش آموزان تخصص "سیستم ها و شبکه های کامپیوتری" بخش "حل مسائل برنامه ریزی خطی عدد صحیح" برای آموزش تمام وقت و پاره وقت / گردآوری شده توسط: I.A. Balakireva, A.V. Skatkov - Sevastopol : Publishing House of SevNTU, 2000. - 13 p.

5. آکولیچ آی.ال. برنامه نویسی ریاضی در مثال ها و مسائل:

6. کتاب درسی کمک هزینه تحصیلی برای دانشجویان اقتصاد متخصص. دانشگاه ها.-م.: بالاتر. مدرسه، 1986.- 319 ص.

7. Andronov S.A. روش های طراحی بهینه: متن سخنرانی / SPbSUAP. سن پترزبورگ، 2001. 169 ص: بیمار.

اسناد مشابه

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

کار دوره، اضافه شده در 2012/03/21


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

تست، اضافه شده در 2016/04/05


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

کار دوره، اضافه شده در 12/09/2008


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

کار دوره، اضافه شده در 10/31/2014


ساخت یک مدل ریاضی به منظور کسب حداکثر سود برای شرکت، حل گرافیکی مسئله. حل مشکل با استفاده از افزونه SOLVER. تجزیه و تحلیل تغییرات در ذخایر منابع. تعیین حدود تغییر ضرایب تابع هدف.

کار دوره، اضافه شده در 2014/12/17


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

کار دوره، اضافه شده 10/13/2008


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

تست، اضافه شده در 2012/05/02


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

تست، اضافه شده در 04/11/2012


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

کار دوره، اضافه شده در 12/17/2012


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

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

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

گزینه شماره 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

نیاز دارد