راه حل: حداکثر و حداقل مقدار تابع \(f (x, y)\) را تحت محدودیت‌های زیر پیدا کنید $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow حداکثر، حداقل \ \ \شروع (موارد) 2x+3y\geq 6 \\ 3x-2y\leq 18\\ -x+2y\leq 8\\ x,y\geq0\end (موارد) $$
روش گرافیکیاستفاده از حل مسئله برای مسائل دارای دو متغیر که به صورت متقارن نوشته شده اند و همچنین برای مسائل دارای متغیرهای زیاد به شرطی که نماد متعارف آنها بیش از دو متغیر آزاد نداشته باشد استفاده شود.

در این مورد، یک کار با دو متغیر.

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

1. بیایید دامنه راه حل های مجاز را در صفحه xOy بسازیم.
2. ناحیه راه حل های غیر منفی را انتخاب کنید.

4. اجازه دهید یک خانواده از توابع هدف بسازیم.
5. حداکثر (حداقل) مقدار را بیابید تابع هدف.

1. ما دامنه راه حل های قابل قبول مسئله \(D\) را می سازیم.

برای ایجاد منطقه راه حل های امکان پذیر:
1) ما خطوط مرزی می سازیم:
نابرابری ها را به تساوی تبدیل می کنیم و سپس به معادله یک خط مستقیم در پاره های محورهای شکل \(\frac(x)(a)+\frac(y)(b) = 1\)، سپس \ (x=a\) قطعه ای است که روی محور Ox قطع شده است، \(y=b\) - در محور Oy $$ \begin(cases) 2x+3y = 6 \\ 3x-2y = 18\\ - x+2y = 8 \end(موارد) => \begin(موارد) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac( y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ برای هر خط، بخش هایی را روی محورها کنار بگذارید و آنها را به هم وصل کنید. ما خطوط درست را دریافت کردیم.

2) نیم صفحه هایی را پیدا می کنیم که نابرابری های داده شده را برآورده می کنند:
برای نابرابری \(2x+3y\geq 6\) نیم صفحه ای است که بالای خط \(2x+3y = 6\) قرار دارد. مستقیم AC
برای نابرابری \(3x-2y\leq 18 => -3x+2y \geq -18\) یک نیم صفحه است که بالای خط \(3x-2y = 18\) قرار دارد. CB مستقیم
برای نابرابری \(-x+2y\leq 8\) نیم صفحه ای است که در زیر خط \(-x+2y = 8\ قرار دارد). مستقیم AB

دامنه راه حل های امکان پذیر به عنوان بخش مشترک سه نیمه صفحه مربوط به نابرابری های داده شده تعریف می شود. این ناحیه یک مثلث \(ABC\) است

ناحیه \(D\) مثلث \(ABC\) است به شکل.

2. ناحیه راه حل های غیر منفی را انتخاب کنید.

ناحیه راه حل های غیر منفی در ربع اول قرار دارد و جزء مشترک هر پنج نیم صفحه است که سه تای آن ناحیه \(D\) است که از نامساوی ها به دست می آید و دو نابرابری دیگر \(x \geq است. 0\) - نیمه صفحه بالایی (چهارم I و II) و \(y \geq 0\) - نیمه صفحه سمت راست (چهارم I و IV) که شرط منفی نبودن متغیرها را بیان می کند \( x;y\). منطقه مورد نظر از راه حل های غیر منفی \(DEBFG\) را به دست آورد.

3. مختصات رئوس منطقه را پیدا کنید.
مختصات چهار راس از قبل مشخص است (اینها نقاط تقاطع خطوط با محورها هستند).
بیایید این مختصات را بنویسیم:
\(D(0;2)\)، \(E(0;4)\)، \(F(6;0)\)، \(G(3;0)\)
مختصات نقطه \(B\) را به عنوان نقاط تقاطع خطوط \(-x+2y = 8\) و \(3x-2y = 18\) پیدا کنید. سیستم معادلات را حل کنید و مختصات این نقطه را پیدا کنید $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\\ 3x -2y = 18 \end(موارد)=> \شروع (موارد) x = 13\\ y =10.5\پایان (موارد)$$
مختصات نقطه \(B(13;10.5)\) را بدست آوردیم.

4. ما یک خانواده از توابع هدف می سازیم.
معادله \(f(x,y)=(x-4)^2 + (y-3)^2 \arrow max,min\) در صفحه xOy خانواده ای از دایره های متحدالمرکز را در مرکز نقطه با مختصات تعریف می کند. (Q(4 ;3)\)، که هر کدام با مقدار معینی از پارامتر \(f\) مطابقت دارد. همانطور که می دانید برای معادله یک دایره پارامتر \(f=R^2\).

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

5. حداکثر (حداقل) مقدار تابع هدف را بیابید.

حداقل مقدار تابع هدف: با افزایش تدریجی شعاع دایره به این نتیجه رسیدیم که اولین راسی که دایره از آن می گذرد نقطه \(G(3;0)\) است. تابع هدف در این نقطه حداقل و برابر با \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\) خواهد بود.

حداکثر مقدار تابع هدف: با افزایش بیشتر شعاع دایره، به این نتیجه رسیدیم که آخرین راسی که دایره از آن عبور خواهد کرد، نقطه \(B(13;10.5)\) است. تابع هدف در این نقطه حداکثر و برابر با \(f(13,10.5)=(13-4)^2 + (10.5-3)^2 = 137.25\) خواهد بود.

می توانید صحت راه حل را با جایگزین کردن مختصات رئوس باقی مانده در معادله تابع هدف تأیید کنید:
در راس \(D(0;2)\) مقدار تابع هدف برابر است با \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\)
در راس \(E(0;4)\) مقدار تابع هدف برابر است با \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\)
در راس \(F(6;0)\) مقدار تابع هدف \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\) است.
گرفتش

پاسخ:
حداقل مقدار تابع هدف \(f_(min) = 10\)
حداکثر مقدار تابع هدف \(f_(max) = 137.25\)

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

مثال ها

توابع صاف و سیستم های معادلات

مسئله حل هر سیستم معادلات

( F 1 (x 1 , x 2 , … , x M) = 0 F 2 (x 1 , x 2 , … , x M) = 0 … F N (x 1 , x 2 , … , x M) = 0 ( \displaystyle \left\((\begin(ماتریس)F_(1)(x_(1),x_(2),\ldots,x_(M))=0\\F_(2)(x_(1),x_ (2)،\ldots،x_(M))=0\\\lds \\F_(N)(x_(1)،x_(2)،\ldots،x_(M))=0\end (ماتریس) )\درست.)

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

S = ∑ j = 1 N F j 2 (x 1 , x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1)، x_(2)،\ldots، x_(M))\qquad(1))

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

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

برنامه ریزی خطی

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

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

یک مثال معمولی از تابع هدف ترکیبی، تابع هدف مسئله فروشنده دوره گرد است. این تابع برابر است با طول چرخه هامیلتونی در نمودار. بر روی مجموعه جایگشت n - 1 (\displaystyle n-1) از رئوس نمودار داده شده است و توسط ماتریس طول لبه نمودار تعیین می شود. راه حل دقیق چنین مشکلاتی اغلب به برشمردن گزینه ها ختم می شود.

فصل 1. بیان مسئله اصلی برنامه ریزی خطی

1. برنامه ریزی خطی

برنامه‌ریزی خطی شاخه‌ای از برنامه‌ریزی ریاضی است که روش‌هایی را برای حل مسائل فوق‌العاده که با رابطه خطی بین متغیرها و یک معیار خطی مشخص می‌شوند، مطالعه می‌کند. چنین مشکلاتی کاربردهای گسترده ای در زمینه های مختلف پیدا می کند. فعالیت انسانی. مطالعه سیستماتیک مسائل از این نوع در 1939-1940 آغاز شد. در آثار L.V. کانتوروویچ.

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

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

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

مشکل مخلوط ها (برنامه ریزی ترکیب محصولات)؛

مشکل یافتن ترکیب بهینه انواع مختلفمحصولات برای ذخیره سازی در انبارها (مدیریت موجودی یا)؛

وظایف حمل و نقل (تجزیه و تحلیل مکان شرکت، جابجایی کالا).

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

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

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

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

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

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

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

تابع هدف

(1.1) تحت محدودیت ها

(1.2) الزامات غیر منفی

(1.3) که در آن ایکس j- متغیرها (ناشناخته)؛

- ضرایب مسئله برنامه ریزی خطی.

مشکل یافتن مقدار بهینه تابع (1.1) با توجه به قیود (1.2) و (1.3) است.

سیستم قیود (1.2) را قیود تابعی مسئله و قیود (1.3) را قیود مستقیم می نامند.

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

1.2. روش ساده برای حل مسائل برنامه ریزی خطی

روش سیمپلکس برای اولین بار در سال 1947 توسط ریاضیدان آمریکایی J. Dantzig برای حل مسائل به کار گرفته شد.

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

یک راه حل قابل قبول (یک طرح قابل قبول) از مشکل LP ارائه شده است فرم استاندارد، مجموعه ای مرتب از اعداد (x1، x2، ...، xn) است که محدودیت ها را برآورده می کند. یک نقطه در فضای n بعدی است.

مجموعه راه حل های قابل قبول، ناحیه راه حل های قابل قبول (SDR) مسئله LP را تشکیل می دهد. ODR یک چند وجهی محدب (چند ضلعی) است.

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

اگر همه متغیرهای آزاد برابر با صفر باشند، راه حلی پایه نامیده می شود.

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

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

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

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

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

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

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

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

فرآیند بکارگیری روش سیمپلکس شامل اجرای سه عنصر اصلی آن است:

روشی برای تعیین برخی راه حل های اولیه امکان پذیر برای مسئله؛

قانون گذار به بهترین (به طور دقیق تر، نه بدترین) راه حل؛

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

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

6.1 مقدمه

بهينه سازي. قسمت 1

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

6.2. مبانی تئوری بهینه سازی

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

با در نظر گرفتن برخی از سیستم های دلخواه توصیف شده توسط m معادلات با n مجهول، می توانیم سه نوع اصلی از مسائل را تشخیص دهیم. اگر m=n باشد، مسئله جبری نامیده می شود. چنین مشکلی معمولا یک راه حل دارد. اگر m>n، مشکل دوباره تعریف می شود و به عنوان یک قاعده، راه حلی ندارد. در نهایت برای م

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

پارامترهای طراحی

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

X1، x2، x3،...، xn.

تابع هدف

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

M=M(x 1، x 2،...، x n).

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

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

تابع هدف در برخی موارد می تواند غیرمنتظره ترین شکل ها را به خود بگیرد. به عنوان مثال، همیشه نمی توان آن را بیان کرد

شکل 1. تابع هدف یک بعدی.

Fig.6.2. تابع هدف دو بعدی.

بسته فرم ریاضی، در موارد دیگر ممکن است

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

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

یافتن حداقل و حداکثر

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

فضای طراحی

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

شرایط مرتبط با ماهیت فیزیکی مشکل. محدودیت‌ها می‌توانند آنقدر قوی باشند که کار هیچ‌گونه نداشته باشد

شکل 6.3 تغییر علامت تابع هدف به عکس

حداکثر وظیفه به حداقل کار تبدیل می شود.

راه حل رضایت بخش قیود به دو گروه تقسیم می شوند: محدودیت ها - برابری ها و محدودیت ها - نابرابری ها.

محدودیت ها - برابری

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

C 1 (x 1، x 2،...، x n)=0،

C 2 (x 1، x 2،...، x n)=0،

..................

C j (x 1، x 2،...، x n)=0.

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

محدودیت ها - نابرابری ها

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

z 1 r 1 (x 1 , x 2 ,..., x n) Z 1

z 2 r 2 (x 1 , x 2 ,..., x n) Z 2

.......................

z k r k (x 1 , x 2 ,..., x n) Z k

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

بهینه محلی

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

شکل 6.4 یک تابع هدف دلخواه می تواند چندین تابع داشته باشد

بهینه محلی

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

بهینه جهانی

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

مثال 6.1

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

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

پارامترهای طراحی: x 1، x 2، x 3.

تابع هدف (که باید به حداقل برسد) مساحت سطح جانبی ظرف است:

A=2 (x 1 x 2 + x 2 x 3 + x 1 x 3)، m2.

محدودیت - برابری:

حجم \u003d x 1 x 2 x 3 \u003d 1m3.

محدودیت - نابرابری:

مشکلات برنامه نویسی خطی

برنامه ریزی خطی (LP)یکی از بخش‌های برنامه‌نویسی ریاضی است - رشته‌ای که مسائل شدید (بهینه‌سازی) را مطالعه می‌کند و روش‌هایی را برای حل آنها ایجاد می‌کند.

مشکل بهینه سازی- این هست مسئله ریاضیکه شامل یافتن مقدار بهینه (یعنی حداکثر یا حداقل) تابع هدف است و مقادیر متغیرها باید به محدوده معینی از مقادیر قابل قبول (ODV) تعلق داشته باشد.

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

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

AT نمای کلیمشکل LP به شکل زیر است:

, (5.1)

, , (5.2)

, , (5.3)

که در آن , , ثابت داده می شود.

تابع (5.1) تابع هدف نامیده می شود. سیستم های (5.2)، (5.3) - توسط سیستمی از محدودیت ها. شرط (5.4) شرط منفی نبودن پارامترهای طراحی است.

مجموعه ای از پارامترهای طراحی که محدودیت های (5.2)، (5.3) و (5.4) را برآورده می کند نامیده می شود. راه حل قابل قبولیا طرح.

راه حل بهینهیا طرح بهینهمسئله LP یک راه حل امکان پذیر نامیده می شود که در آن تابع هدف (5.1) مقدار بهینه (حداکثر یا حداقل) را می گیرد.

وظیفه استاندارد LP مشکل یافتن حداکثر (حداقل) مقدار تابع هدف (5.1) در شرایط (5.2) و (5.4) نامیده می شود، که در آن، , i.e. آن ها محدودیت‌ها فقط در قالب نابرابری‌ها (5.2) و همه پارامترهای طراحی شرط عدم منفی بودن را برآورده می‌کنند و هیچ شرایطی در قالب برابری وجود ندارد:

,

, , (5.5)

.

وظیفه متعارف (اصلی). LP مشکل یافتن حداکثر (حداقل) مقدار تابع هدف (5.1) تحت شرایط (5.3) و (5.4) نامیده می شود، که در آن، , i.e. آن ها محدودیت‌ها فقط در قالب برابری‌ها (5.3) و همه پارامترهای طراحی شرط عدم منفی بودن را برآورده می‌کنند و هیچ شرایطی به شکل نابرابری وجود ندارد:

,

.

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

شکل ماتریسی مسئله LP متعارف به شکل زیر است:

شکل برداری مسئله LP متعارف.

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

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

توجه!

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

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

گزینه 7. مقادیر حداکثر و حداقل را بیابیدتابع خطی Ф \u003d 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.

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

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

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

Ф min = 2 2 - 2 2 = 0.

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

Ф حداکثر \u003d 2 10 - 2 0 \u003d 20.

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

تابع خطی Ф \u003d 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;

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

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

برای مثال، روی یک خط مستقیم NP

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

Ф min = 4 + 0 = 4.

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

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

تابع خطی Ф \u003d 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).

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

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

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

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

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

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

گزینه 7. کمینه کردن تابع هدف Ф \u003d 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 \u003d 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 \u003d 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 \u003d 9 - x 1 - 6 x 6 (*)

x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6

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

Ф \u003d 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 \u003d x 3 \u003d x 6 \u003d 0 قرار دهیم ، در حالی که متغیرهای اصلی مقادیر x 2 \u003d 2 را می گیرند. x 4 \u003d 9; x 5 \u003d 6، یعنی اولین راه حل امکان پذیر (0؛ 2؛ 0؛ 9؛ 6؛ 0)، تابع هدف Ф 1 \u003d 13.

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

x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3

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

مقادیر صفر را به متغیرهای آزاد اختصاص دهید، یعنی x 1 \u003d x 2 \u003d x 3 \u003d 0، در حالی که x 6 \u003d 1, x 4 \u003d 3, x 5 \u003d 4، یعنی سوم راه حل معتبر (0؛ 0؛ 0؛ 3؛ 4؛ 1). در این مورد، Ф 3 \u003d 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 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

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

Ф \u003d 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 \u003d 5 (تا زمانی که x 5 ³ 0) امکان پذیر است. در این حالت، x 1 و x 4 مقادیر صفر را حفظ می کنند، مقادیر سایر متغیرها برابر با x 3 = 3/2 است. x 5 \u003d 0، x 6 \u003d 3/2، یعنی چهارمین راه حل معتبر (0؛ 5؛ 3/2؛ 0؛ 0؛ 3/2). در این مورد، Ф 4 \u003d 5/4.

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

x 2 \u003d 5 - 4 x 1 + x 4 - 2 x 5

x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

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

F \u003d - 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 \u003d 30;

x 3 + x 5 - 2 x 6 \u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \u003d 18;

راه حل:

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

x 1 \u003d 12 - x 5 - x 6;

x 2 \u003d 30 - 5 x 5 + x 6;

x 3 \u003d 6 - x 5 + 2 x 6;

x 4 \u003d 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 \u003d 12 - x 1 - x 5;

x 2 \u003d 42 - x 1 - 6 x 5;

x 3 \u003d 30 - 2 x 1 - 3 x 5;

x 4 \u003d 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 \u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \u003d 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. تابع هدف Ф \u003d x 2 + x 3 را به حداکثر برسانید

تحت محدودیت: x ​​1 - x 2 + x 3 \u003d 1,

x 2 - 2 x 3 + x 4 \u003d 2.

راه حل:

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

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

x 1 \u003d 1 + x 2 - x 3; (*)

x 4 \u003d 2 - x 2 + 2 x 3;

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

در x 2 \u003d 0 و x 3 \u003d 0، متغیرهای اصلی برابر با x 1 \u003d 1، x 4 \u003d 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 \u003d 1 - x 1 + x 2؛ (**)

x 4 \u003d 4 - 2 x 1 + x 2;

Ф \u003d x 2 + 1 - x 1 + x 2 \u003d 1 - x 1 + 2 x 2

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

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

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

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

وظیفه اصلی

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

با محدودیت: x ​​1 + x 2 \u003d 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 \u003d 5،

- x 1 + x 2 + x 3 + x 6 \u003d 8.

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

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

برای y 1 - y 3 ≥ 2,

y1 + y2 + y3 ≥ 0,

y 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

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

با محدودیت: x ​​1 + 2× x 2 - x 4 + x 5 \u003d 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)

راه حل:

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

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

F = S × X max F = B T × یمین

در A × X \u003d B در A T × Y ≥ C T

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

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

B \u003d 2، A \u003d 0 - 4 1 2 -1 0

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

0 1 0 0 ولت T \u003d (1; 2; 5)

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

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

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

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

2× y 1-4 × y 2 + 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 = S × X دقیقه F \u003d B T × Ymax

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

X ≥ 0 Y ≥ 0

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

C \u003d (1; 1; 1)، B \u003d 3، A \u003d 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 × y 2 + 8 × y 3 ≤ 1،

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

7× y 1 + 5 × y 2 + 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 مجهول داریم. x 1 , z 1 , z 3 را به عنوان 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 \u003d 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 \u003d 2.

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

جدول 1 تکرار I

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

X 1 \u003d (1; 0; 0; 0; 2; 0; 4) F 1 \u003d 2.

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

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z3	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 \u003d (14/8؛ 0؛ 0؛ 1/4؛ 0؛ 0؛ 4) Ф 2 \u003d 4.

تکرار III جدول 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x4	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 \u003d (1؛ 0؛ 6/7؛ 10/7؛ 0؛ 0؛ 0) Ф 3 \u003d 52/7.

جدول 4 تکرار IV

z1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	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 \u003d (0؛ 0؛ 25/14؛ 37/14؛ 1/2؛ 0؛ 0) F 4 \u003d 149/14.

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

پاسخ: Ф max = 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 \u003d 3,

x 2 + 2 x 4 \u003d 1,

راه حل:

تعداد متغیرها 4 است، رتبه ماتریس ​x 4 به عنوان متغیر آزاد، متغیرهای پایه x 1، x 2 را بر حسب آزاد بیان می کنیم و سیستم را به پایه واحد می آوریم:

x 2 \u003d 1 - 2 x 4،

x 1 \u003d 3 - x 2 - 2 x 3 + x 4 \u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 \u003d 2 - 2 x 3 + 3 x 4

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

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

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

Ф + 11 x 3 - 15 x 4 \u003d 10

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

جدول 1 تکرار I

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

X 1 \u003d (2; 1; 0; 0) F 1 \u003d 10.

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

x3	1	1/2	0	1	-3/2		3/4
x2	1	0	1	0			1/2
اف	— 1	— 11/2	0	0	3/2		— 3/4

X 2 \u003d (0; 1; 1; 0) F 2 \u003d -1.

تکرار III جدول 3

x3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
اف	— 7/4	— 11/2	— 3/4	0	0

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

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

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

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

گزینه 10. تابع هدف Ф \u003d x 1 + x 2 را به حداقل برسانید،

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

x 2 - x 3 + 2 x 4 \u003d 1,

راه حل:

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

x 1 - 2 x 3 + x 4 \u003d 2

x 2 - x 3 +2 x 4 \u003d 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 \u003d (2; 3; 0; 0; 5) F 1 \u003d 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 \u003d (3/2؛ 0؛ 0؛ 1/2؛ 11/2) F 2 \u003d 3/2.

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

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

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

ستون های پایه با ستون های تک مطابقت دارند.

محاسبه مقادیر باقیمانده جدول:

"BP - طرح اساسی":

; ;

"x1": ; ;

"x5": ; .

مقادیر ردیف شاخص غیر منفی است، بنابراین ما جواب بهینه را به دست می آوریم: , ; .

پاسخ:حداکثر سود حاصل از فروش محصولات تولیدی معادل 160/3 واحد با عرضه تنها محصولات نوع دوم به میزان 80/9 واحد تضمین می شود.

کار شماره 2

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

زیرا آخرین رقم رمز 8 است، سپس A=2. B=5.

زیرا رقم ماقبل آخر رمز 1 است، سپس باید کار شماره 1 را انتخاب کنید.

راه حل:

1) مساحتی را که سیستم نابرابری ها تعریف می کند رسم می کنیم.

این ناحیه یک مثلث ABC با مختصات رئوس است: A(0; 2); ب (4؛ 6) و ج (16/3؛ 14/3).

سطوح تابع هدف دایره هایی هستند که در مرکز نقطه (2؛ 5) قرار دارند. مربع های شعاع مقادیر تابع هدف خواهد بود. سپس شکل نشان می دهد که حداقل مقدار تابع هدف در نقطه H به دست می آید، حداکثر مقدار یا در نقطه A یا در نقطه C است.

مقدار تابع هدف در نقطه A: ;

مقدار تابع هدف در نقطه C: ;

به این معنی که حداکثر مقدار تابع در نقطه A(0; 2) به دست می آید و برابر با 13 است.

مختصات نقطه H را پیدا کنیم.

برای انجام این کار، سیستم را در نظر بگیرید:

ó

ó

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

سپس ; ; - حداقل مقدار تابع.

2) تابع لاگرانژ را برای یافتن حداقل راه حل بنویسید:

در ایکس 1 =2.5; ایکس 2 =4.5 ما گرفتیم:

ó

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

ما تابع لاگرانژ را برای یافتن حداکثر جواب می نویسیم:

شرایط کافی برای یک افراطی:

در ایکس 1 =0; ایکس 2 =2 ما گرفتیم:

ó ó

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

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

کار شماره 3

به دو شرکت وجوه در این مبلغ اختصاص یافته است دواحدها زمانی که به مدت یک سال به اولین شرکت اختصاص داده شود ایکسواحدهای وجوهی که درآمد حاصل می کند ک 1 ایکسواحدها و زمانی که به شرکت دوم تخصیص داده شود yواحدهای وجوه، درآمد را فراهم می کند ک 1 yواحدها مانده وجوه در پایان سال برای اولین شرکت برابر است nx، و برای دوم من. چگونه می توان تمام وجوه را در عرض 4 سال تقسیم کرد تا کل درآمد بیشترین باشد؟ با برنامه نویسی پویا مشکل را حل کنید.

i=8، k=1.

A=2200; k 1 = 6; k2=1; n=0.2; m=0.5.

راه حل:

کل دوره 4 ساله به 4 مرحله تقسیم می شود که هر مرحله معادل یک سال است. بیایید مراحل را از سال اول شماره گذاری کنیم. فرض کنید X k و Y k به ترتیب وجوه تخصیص یافته به شرکت های A و B در مرحله k-ام باشند. سپس مجموع X k + Y k =a k کل وجوه مصرف شده در مرحله k - آن مرحله و باقیمانده از مرحله قبلی k - 1 است. در مرحله اول تمام وجوه تخصیص یافته استفاده می شود و 1 = 2200 واحد است. درآمدی که در مرحله k دریافت می شود - آن مرحله، وقتی X k و Y k واحد تخصیص داده می شود، 6X k + 1Y k خواهد بود. حداکثر درآمد دریافت شده در مراحل آخر را از k شروع کنید - آن مرحله f k (a k) واحد است. بیایید معادله تابعی بلمن را بنویسیم که اصل بهینه بودن را بیان می کند: حالت اولیه و راه حل اولیه هر چه باشد، راه حل بعدی باید با توجه به حالت به دست آمده در نتیجه حالت اولیه بهینه باشد:

برای هر مرحله، باید مقدار X k و مقدار را انتخاب کنید Y k=aک- ایکسک. با در نظر گرفتن این موضوع، درآمد را در مرحله k-ام پیدا خواهیم کرد:

معادله تابعی بلمن به صورت زیر خواهد بود:

تمام مراحل را در نظر بگیرید، از آخرین مرحله شروع کنید.

(از آنجایی که حداکثر تابع خطی در انتهای بخش در x 4 = a 4 به دست می آید).

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

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

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

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

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

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

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

گزینه 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 را ببینید) و راه حل بهینه را تعیین می کند.

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

^ مرحله 3. تعیین مختصات حداکثر (حداقل) نقطه و مقدار بهینه تابع هدف.

برای یافتن مختصات نقطه C، لازم است سیستمی متشکل از معادلات مستقیم مربوطه (در این مورد، از معادلات 2 و 3) حل شود:

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

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

ما جواب بهینه = 1.33 را دریافت می کنیم.

^ مقدار بهینه تابع هدف f * = f (ایکس*) = 7 * 0 + 6 * 1,33 = 7,8