برنامه‌نویسی محدب، بخشی از برنامه‌نویسی ریاضی، که در آن مشکل به حداکثر رساندن یک تابع هدف مقعر f (x) از یک آرگومان برداری x = (x 1، ...، xn) که محدودیت‌های gi (x) ≥ 0، x را برآورده می‌کند. Є X، i = 1، ...، m، که در آن gi توابع مقعر هستند، X یک مجموعه محدب است. نقطه x که این محدودیت ها را برآورده کند، مجاز نامیده می شود. نتیجه اصلی نظریه برنامه نویسی محدب قضیه نقطه زینی است: برای بهینه بودن یک نقطه قابل قبول x * از یک مسئله برنامه ریزی محدب، وجود بردار y * = (در شرایط نسبتاً گسترده) ضروری و کافی است. y * 1، ...، ym *) با مولفه های غیر منفی y * به طوری که نقطه (x *، y *) یک نقطه زین برای تابع لاگرانژ باشد.
مسائل برنامه نویسی محدب، یعنی برای هر x Є X و y با مولفه های غیر منفی، نابرابری ها
تعدادی از روش های برنامه نویسی محدب بر اساس قضیه نقطه زینی هستند که در آن تابع φ (y 1, ..., ym) = max x Є XL (x, y) برای yi ≥ 0, i = 1 به حداقل می رسد. ، .. .، m یا نقطه زینی مستقیماً یافت می شود و به جای تابع لاگرانژ گاهی از برخی اصلاحات آن استفاده می شود. رویکرد دیگر برای حل مسئله برنامه نویسی محدب با جستجوی جهت های احتمالی حرکت یک نقطه مجاز x است که از مجموعه نقاط مجاز مشتق نشده اند و هنگام حرکت در امتداد آن، تابع هدف افزایش می یابد. این رویکرد با استفاده از دنباله ای از تکرارها اجرا می شود. در هر تکرار، جهت ممکن خروجی از نقطه بعدی محاسبه می شود، پس از آن یک تغییر در این جهت با فاصله معینی به نقطه بعدی ایجاد می شود. روش‌هایی برای حل مسائل برنامه‌نویسی محدب وجود دارد که به‌ویژه برای مواردی که تابع هدف غیرخطی و محدودیت‌ها خطی هستند سازگار شده‌اند. به طور معمول، روش های برنامه نویسی محدب به تعداد بی نهایت تکرار برای تعیین دقیق نقطه بهینه نیاز دارند. استثناء مسائل برنامه نویسی درجه دوم (تابع هدف مجموع توابع مقعر درجه دوم و خطی است، محدودیت ها خطی هستند) و برنامه ریزی خطی (تابع هدف و محدودیت ها خطی هستند) که عمدتاً از روش های محدود استفاده می شود. بسیاری از روش های محاسباتی برنامه نویسی محدب در قالب برنامه های کامپیوتری پیاده سازی می شوند. بسته های نرم افزاری نیز وجود دارد که برنامه نویسی خطی و مسائل برنامه نویسی محدب را پوشش می دهد. همچنین به تحقیق در عملیات مراجعه کنید.
متن: برنامه نویسی محدب گلشتاین E.G. عناصر نظریه. م.، 1970; برنامه نویسی غیرخطی Zangwill W.I. یک رویکرد. م.، 1973.
بررسی این دسته از مشکلات معمولاً با ارائه شروع می شود روش ضرایب لاگرانژ نامعینبرای این کار می گذاریم که / (x، ...، ایکس")و g (x b ...، ایکس")- توابع پیوسته همراه با مشتقات جزئی آنها، فعلاً شرایط منفی نبودن متغیرها را حذف می کنیم و مسئله زیر را برای اکسترمم شرطی فرموله می کنیم:
برای یافتن راه حل آن را معرفی می کنیم ضریب لاگرانژ y b / = 1, تیو به اصطلاح تصنیف کنید تابع لاگرانژ:
مشتقات جزئی آن را با توجه به همه متغیرها بیابید و معادل صفر کنید
با دریافت سیستم n + tمعادلات مجهولات x b x n
Uy -، U -
اگر تابع f (x h ..., ایکس")در نقطه 
یک اکسترموم دارد، سپس یک بردار Y وجود دارد (0> = (y، 0، ...، y °) که نقطه (Ag (0)، F (0)) راه حلی برای سیستم (2.23) است. بنابراین، با حل سیستم (2.23)، نقاطی را به دست می آوریم که در آن تابع (2.20) می تواند یک اکستروم داشته باشد. علاوه بر این، نقاط یافت شده به همان روشی که هنگام حل مشکل برای یک اکسترم بی قید و شرط بررسی می شود.
بنابراین روش ضریب لاگرانژ شامل مراحل زیر می باشد.
- 1. تابع لاگرانژ را بسازید.
- 2. مشتقات جزئی را با توجه به Xjو y،از تابع لاگرانژ و آنها را با صفر برابر کنید.
- 3. حل سیستم (2.23)، نقاطی را که تابع هدف می تواند در آنها اکسترموم داشته باشد، پیدا کنید.
- 4. از میان امتیازهای کاندید برای اکستروم، آنهایی را پیدا کنید که در آنها به اکستروم رسیده است و مقادیر تابع را محاسبه کنید. f (x ..., ایکس")در این نقاط
روش توصیف شده برای مسائل برنامه نویسی محدب قابل استفاده است، به عنوان مثال. به مواردی که در آنها تابع هدف محدب (یا مقعر) است و ناحیه راه حل های امکان پذیر تعیین شده توسط قیود نیز محدب است.
تعریف 1.عملکرد f (x,..., x n)بر روی یک مجموعه محدب داده شده است ایکس،اگر برای هر نقطه ای محدب نامیده می شود X، X 2از جانب هیبرای هر شماره ایکس، 0 X 1 نابرابری
تعریف 2.عملکرد/(*، ایکس«) بر روی مجموعه محدب تعریف شده است ایکس،اگر برای هر نقطه ای مقعر نامیده می شود ایکسایکس، X 2از جانب هیبرای هر شماره ایکس، 0 X
تعریف 3.مجموعه راه حل های امکان پذیر یک مسئله برنامه ریزی محدب شرط نظم را برآورده می کند اگر حداقل یک نقطه وجود داشته باشد. Xj،متعلق به منطقه راه حل های امکان پذیر که برای آن g ^ XJ) =b h i = 1, تی.
قضیه 1.هر اکستروم محلی یک مشکل برنامه نویسی محدب جهانی است.
تعریف 4.تابع لاگرانژ یک مسئله برنامه نویسی محدب تابع است
جایی که y ضریب لاگرانژ است.
تعریف 5.نقطه (X (0) T (0)) = (x, °, ..., ایکس ('،y، 0،...، y" ) تماس گرفت نقطه زین تابع لاگرانژ،اگر
ما دو قضیه کوتاه از یک کاراکتر کمکی را ارائه می کنیم.
قضیه 2.طرح بهینه X (0)وظایف NP- آی تی
که در آن DA) یک تابع متمایز غیرخطی است که شرایط را برآورده می کند
شیب تابع کجاست /
در نقطه A "(0).
اثبات
تابع هدف را در یک سری تیلور در همسایگی نقطه بسط دهید ایکس (())
جایی که اوه- بردار افزایش های کوچک X (0);
I - تعیین هنجار (طول) بردار.
از عبارت (2.26) چنین می شود که اگر مقداری از مختصات بردار x | 0)> 0، سپس مشتق
، زیرا در غیر این صورت مختصات x بهمی توان،
با مقادیر ثابت متغیرهای باقیمانده، به کمینه کردن تابع هدف ادامه دهید، مقدار x [0 را کاهش دهید، اگر مشتق بزرگتر از صفر باشد، یا افزایش یابد. xfاگر مشتق کمتر باشد
خراش اگر x | 0) = 0، پس باید وجود داشته باشد 
تا جایی که
در غیر این صورت امکان کاهش ارزش وجود دارد f (X m)،افزایش 4 0) با مقدار Dx *، بدون تغییر مقادیر سایر متغیرها. بنابراین، برای هر بهبرابری برقرار است:
قضیه ثابت می شود.
اکنون شرایط لازم و کافی برای وجود نقطه زینی تابع لاگرانژ را تعریف می کنیم.
قضیه 3.به طوری که نقطه (A 10 *, I 0)) با مختصات غیر منفی نقطه زین تابع قابل تفکیک است. L (X، Y)،شرایط زیر باید رعایت شود:
اثبات
1) نیاز داشتن.بگذارید (X (0)، Y "(0)) یک نقطه زین باشد، به عنوان مثال:
فرمول (2.29) معادل عبارت است
بر اساس (2.29) و (2.30) شرایط (2.27) و (2.28) برقرار است. بنابراین ضرورت آن ثابت می شود.
- 2) کفایت.ما فرض می کنیم که شرایط (2.27) و (2.28) برآورده شده است. تابع را گسترش دهید L (X, Y)در سری تیلور در مجاورت نقطه
از بسط (2.31) و با در نظر گرفتن شرایط (2.27) و (2.28) نتیجه می شود که
دو عبارت آخر معادل فرمول (2.29) هستند. قضیه ثابت می شود.
پس از قضایای فوق، قضیه اکنون عملاً آشکار کوهن - تاکر را فرموله می کنیم.
قضیه 4 (Kuhn - Tucker).برای مسئله برنامه نویسی محدب (2.20) - (2.21) که مجموعه راه حل های امکان پذیر آن دارای خاصیت منظم بودن، نقطه X (0) =(xj 0 *، ...، x '0))، x، - 0>> 0، / = 1، پیک طرح بهینه است اگر و فقط اگر چنین بردار وجود داشته باشد T = (y 1 (0)، ...، yi 0))، Y / 0)> 0، / = 1، تی،که نقطه (T (0)، H 0>) یک نقطه زینی تابع لاگرانژ است.
اگر در مسئله برنامه نویسی محدب (2.20) - (2.21) تابع هدف و قیود به طور پیوسته قابل تمایز هستند، می توان قضیه کوهن - تاکر را با عبارات تحلیلی تکمیل کرد که شرایط لازم و کافی را برای نقطه (X (0)، Y i تعریف می کند. (l)، ) نقطه زینی تابع لاگرانژ بود، یعنی. راه حلی برای یک مشکل برنامه نویسی محدب بود. این عبارات (2.27) و (2.28) هستند. آنها از مسئله برنامه نویسی درجه دوم راضی هستند. برای فرمول نهایی آن چند تعریف و یک قضیه ارائه می کنیم.
تعریف 6.یک فرم درجه دوم با توجه به متغیرهای X [، ...، ایکس"تابع عددی این متغیرها نامیده می شود که به شکل زیر است:
تعریف 7.فرم درجه دوم افمثبت / منفی قطعی اگر نامیده می شود F (X)> 0/ F (X) 0 برای همه مقادیر متغیرهایی که بردار را تشکیل می دهند ایکس.
تعریف 8.فرم درجه دوم افمثبت / منفی نیمه معین اگر نامیده می شود F (X ")>О / YES ") X، و علاوه بر این، چنین مجموعه ای از متغیرها وجود دارد - اجزای بردار ایکس "،چی F (X") = 0.
قضیه 5.یک شکل درجه دوم یک تابع محدب / مقعر است اگر مثبت / منفی نیمه معین باشد.
تعریف 9. وظیفه کمینه کردن / حداکثر کردن مقدار یک تابع
با محدودیت
جایی که یک شکل درجه دوم نیمه معین مثبت / منفی نامیده می شود مشکل برنامه نویسی درجه دوم(RFQ).
برای این کار، تابع لاگرانژ به شکل زیر است:
اگر تابع لاگرانژ یک نقطه زینی داشته باشد، شرایط (2.27)، (2.28) در آن برآورده می شود. حال با معرفی متغیرهای اضافی که نابرابری ها را به برابری تبدیل می کنند (از این تکنیک در حل مسائل LP نیز استفاده می شود)، این شرایط را به شکل زیر می نویسیم:
برای یافتن جواب ZKP لازم است جواب غیر منفی سیستم معادلات جبری خطی (2.32) تعیین شود. چنین راه حلی می توان یافت روش پایه مصنوعی،برای یافتن حداقل مقدار تابع هدف مصنوعی اعمال می شود F = ^ Pj،که در آن p متغیرهای مصنوعی هستند. روش به عنوان -
مشخص است که در تعداد محدودی از مراحل، طرح بهینه را پیدا می کند یا حل نشدنی مسئله را مشخص می کند.
بنابراین، فرآیند یافتن راه حل برای RFQ شامل مراحل زیر است.
- 1. تابع لاگرانژ را بسازید.
- 2. شرایط لازم و کافی برای وجود نقطه زینی تابع لاگرانژ به صورت عبارات (2.27)، (2.28) نوشته شده است.
- 3. با استفاده از روش یک پایه مصنوعی، عدم وجود یک نقطه زین برای تابع لاگرانژ را تعیین کنید یا مختصات آن را پیدا کنید.
- 4. راه حل بهینه مسئله اصلی را بنویسید و مقدار تابع هدف را بیابید.
ابتدایی را در نظر بگیرید مثال عددی(№ 1) از کتاب I. L. Akulich "برنامه ریزی ریاضی در مثال ها و مسائل". بر اساس برنامه تولید، این شرکت باید 180 محصول تولید کند. آنها را می توان با استفاده از دو فناوری تولید کرد. در تولید ایکسمحصولات در راه 1، هزینه ها بود xf+ 4x، مالش، و در حین ساخت x 2محصولات در راه دوم برابر هستند x + 8x2 روبل. تعیین کنید که هر روش چند مورد باید ساخته شود تا هزینه سفارش به حداقل برسد.
راه حل.عملکرد زیر باید به حداقل برسد:
تحت شرایط: 
تابع لاگرانژ در این مورد به صورت زیر خواهد بود:
اجازه دهید مشتقات جزئی این تابع را با توجه به محاسبه کنیم X، x 2، yو آنها را با صفر برابر کنید: 
حمل در معادله اول و دوم دردر سمت راست و با معادل سازی اضلاع چپ، پس از اختصارات آشکار می گیریم:
با حل این معادله همراه با معادله سوم سیستم، متوجه می شویم که 
این یک امتیاز است - یک مدعی برای افراط.
با استفاده از مشتقات جزئی دوم، به راحتی می توان نشان داد که نقطه یافت شده حداقل شرطی تابع / است.
مشکلاتی مشابه آنچه که در بالا مورد بحث قرار گرفت، از طرق مختلف توسط عملکرد اقتصادی مطرح شده است. درست است، مسائل واقعی، به عنوان یک قاعده، حاوی تعداد زیادی متغیر و محدودیت هستند، که حل آنها را بدون استفاده از رایانه غیرممکن می کند. با این حال، اثربخشی استفاده از نرم افزار استاندارد شده با دانش محقق از ماهیت تبدیل های انجام شده توسط کامپیوتر تعیین می شود. این به او کمک می کند تا در مجموعه روش ها، رویه های محاسباتی و سیستم های نرم افزاری پیشنهادی برای حل مسائل بهینه سازی به درستی حرکت کند.
برای تجمیع موضوع، یکی دیگر را در نظر بگیرید مثال عددی(شماره 2). حداکثر مقدار یک تابع را بیابید
تحت شرایط:
راه حل.تابع / مقعر است، زیرا مجموع یک تابع خطی است f = 2x 2 + 4x bکه می توان آن را مقعر و درجه دوم دانست / 2 = -x -2x1،که به صورت منفی تعریف شده است. محدودیت ها فقط شامل قیود خطی هستند. در نتیجه می توان از قضیه کوهن - تاکر و طرح حل CSP استفاده کرد.
1. بیایید تابع لاگرانژ را بسازیم:
2. شرایط لازم و کافی برای وجود نقطه زینی تابع را بنویسیم L.
3. وارد سیستم نابرابری های خطی، متغیرهای غیر منفی اضافی vb V2، w, w 2,تبدیل نابرابری ها به برابری ما سیستم معادلات را بدست می آوریم:
البته در این مورد شرایط زیر وجود دارد:
برای تعیین مختصات نقطه زین تابع لاگرانژ باید جواب اصلی سیستم معادلات (2.33) را یافت. برای این منظور از روش پایه مصنوعی استفاده خواهیم کرد. به حداقل رساندن تابع هدف مصنوعی
جایی که زی، زی- متغیرهای مصنوعی، تحت شرایط:
در اینجا، راه حل عملی اساسی بدیهی به نظر می رسد:
تابع هدف افبیان از طریق متغیرهای غیر پایه:
پس از پایان استدلال، توجه می کنیم که برای Xj (0) = 1، = 1 و سایر متغیرها با مقادیر صفر ناپدید می شود. بنابراین، T (0) = (1، 1) طرح بهینه مسئله اصلی است،
(سند)
n1.doc
برنامه نویسی محدب قضیه کوهن تاکر. شرایط کوهن تاکر
تحت شرایط
(1.3)
توابع کجا هستند 
محدب فرض می شوند.
اگر 
و توابع مقعر هستند، پس ما مشکل بیشینه سازی را داریم 
با محدودیت 
و 
بیایید تابع لاگرانژ را برای این مشکل بسازیم:
اگر نقطه یک نقطه حداقل تابع باشد، نقطه زینی تابع (1.4) نامیده می شود 
و نقطه حداکثر نقطه تابع است. به عبارت دیگر، برای یک نقطه زینتی برای همه 
و 
رابطه برقرار است
(1.5)
قضیه 1 (قضیه کوهن تاکر). بگذارید حداقل یک نکته وجود داشته باشد 
، برای کدام 
... سپس شرط لازم و کافی برای بهینه بودن بردار 
متعلق به حوزه راه حل های امکان پذیر مسئله (1.1) - (1.5) وجود چنین بردار است. 
که برای همه و 
نابرابری ها (1.5)
ما این قضیه را بدون اثبات می پذیریم.
به قضیه کوهن تاکر، قضیه نقطه زینی نیز گفته می شود.
اگر 
و 
توابع قابل تمایز هستند، پس نابرابری های موجود در (1.5) معادل شرایط محلی کوهن تاکر زیر هستند:
این عبارات به این معنی است که مقادیر مشتقات در نقطه گرفته می شود 
.
1.2. برنامه نویسی درجه دوم روش بارانکین دورفمن.
یک مورد خاص از یک مسئله برنامه نویسی محدب، یک مسئله برنامه نویسی درجه دوم است. مشکل اصلی در برنامه نویسی درجه دوم مشکل کمینه سازی تابع Z است که مجموع یک تابع خطی و یک تابع درجه دوم است:
تحت محدودیت های خطی
ماتریس D متقارن و معین غیرمنفی فرض می شود. در این حالت تابع (2.1) محدب خواهد بود.
اجازه دهید برای مسئله (2.1) - (2.3) شرایط محلی کوهن تاکر (1.6) - (1.7) را بسازیم که شرایط لازم و کافی برای بهینه بودن حل مسئله (2.1) - (2.3) هستند.
تابع لاگرانژ در این مورد به صورت زیر است:
بیایید مشتقات جزئی این تابع را پیدا کنیم:
نشان می دهیم
با در نظر گرفتن این نمادها، روابط (2.4) و (2.5)، شرایط کوهن تاکر (1.6) - (1.7) به شکل زیر است.
معادلات (2.6) و (2.7) سیستمی از N = n + m معادلات خطی با 2N = 2 (n + m) مجهول تشکیل می دهند:.
بنابراین، مطابق با قضیه کوهن تاکر، راه حل 
مسئله (2.1) - (2.3) برنامه نویسی درجه دوم بهینه است اگر و فقط اگر همراه با راه حل 
راه حل هایی وجود دارد 
و 
به گونه ای که راه حلی برای سیستم (2.6) - (2.8) در شرایطی است که برابری (2.9) برقرار است.
شرط (2.9) برای مسئله (2.1) - (2.3) معادل تحقق شرط است.
روش های مختلفی برای حل مسئله برنامه نویسی درجه دوم وجود دارد. بیایید یکی از آنها را در نظر بگیریم - روش Barankin-Dorfman.
با این روش ابتدا سیستم معادلات (2.6) - (2.7) به شکل زیر کاهش می یابد:
جایی که 
(متغیرهای پایه) و 
(متغیرهای آزاد) عناصر مختلف برخی از جایگشت متغیرها و همه هستند 
اعداد غیر منفی هستند (i = 1,2,…, N).
سپس از سیستم (2.11) راه حل پشتیبانی اولیه پیدا می شود
سیستم های (2.6) - (2.8)، و اجزای بردار 
به ترتیب مرتب شده است
اگر برای راه حل 
شرط (2.10) ارضا می شود، سپس مسئله (2.1) - (2.3) حل می شود و راه حل بهینه آن 
از اجزای مربوطه بردار یافت می شود.
اگر برای شرط (2.10) برآورده نشد، برای انتقال به راه حل مرجع دیگر جدول زیر ترسیم می شود (جدول 2.1). بدنه این جدول شامل سطرهای همه متغیرها به ترتیب است. برای متغیرهای پایه، عناصر ردیف‌ها از سیستم (2.11) و برای متغیرهای آزاد، از روابط گرفته می‌شوند.
پارامترهای قسمت اضافی جدول 2.1 به شرح زیر است:
آ) 
از فرمول پیدا می شود 
جایی که 
- بردار متشکل از عناصر ستون s بخش اصلی جدول.
ب) برای کسانی که برای آنها 
، پارامترهای باقی مانده محاسبه می شوند: 
(عناصر ستون های مربوطه حداقل را ارائه می دهند 
، با ستاره مشخص شده است) 
.
ستونی که با کوچکترین منفی مطابقت دارد 
، به عنوان یک ستون مجاز اختصاص داده می شود، یک ردیف با عنصر ستاره دار این ستون یک خط مجاز است و این عنصر خود یک عنصر مجاز است و با کمک آنها تبدیل سیمپلکس جدول 2.1 انجام می شود.
که در آن:
در نتیجه راه حل پشتیبانی جدید سیستم (2.6) - (2.8) به دست می آید. این روند تا زمانی که شرط (2.10) برآورده شود ادامه می یابد. اگر همه 
، آ 
، سپس راه حل دیگری به عنوان راه حل اولیه انتخاب می شود.
1.3 مثالی از حل مسئله به روش بارانکین-دورفمن
به حداقل رساندن عملکرد
با محدودیت:
; 
.
راه حل
راه حل پشتیبانی اولیه سیستم (2.12) را پیدا کنید. در این حالت مقدار تابع هدف برابر است با.
سپس شرط (2.10) برآورده نمی شود و بنابراین راه حل بهینه نیست.
اجازه دهید جدول 2.2 را بسازیم تا به راه حل پشتیبانی جدید سیستم (2.12) - (2.13) برویم. قسمت اصلی این جدول را با استفاده از سیستم (2.12) پر می کنیم.
الف) برای قسمت اضافی جدول، می یابیم:
ب) برای مثبت 
و 
بقیه پارامترها را محاسبه کنید:
ستون چهارم با کوچکترین منفی 
، ما ستون حل، سطر را با عنصر 3 این ستون - خط حل کننده و خود عنصر 3 - عنصر حل کننده را اختصاص می دهیم و با کمک آنها تبدیل سیمپلکس جدول 2.2 را انجام می دهیم.
در نتیجه، جدول 2.3 را دریافت می کنیم که حاوی راه حل پشتیبانی جدید است.
برای این راه حل
بنابراین، قسمت اضافی جدول 2.3 را مانند مورد قبلی پر می کنیم تا به راه حل مرجع جدید سیستم (2.12) - (2.13) منتقل شویم.
با قرار دادن جدول 2.3 به تبدیل سیمپلکس با عنصر وضوح در 13.30، جدول دیگری با یک راه حل مرجع دریافت می کنیم که برای آن 
.
بنابراین، یک راه حل بهینه پیدا شده است 
، که در آن تابع هدف Z مسئله داده شده به حداقل می رسد. که در آن 
1.4 تکلیف انفرادی: حل مسئله با استفاده از روش بارانکین دورفمن
;
راه حل
از روابط (2.6) - (2.7) سیستم معادلات زیر را بدست می آوریم:
پس از تبدیل های ساده، این سیستم را به شکل زیر در می آوریم:
(2.14)
از آنجا، با در نظر گرفتن غیر منفی
راه حل اولیه اولیه را پیدا کنید 
سیستم (2.14). در این حالت مقدار تابع هدف است 
.
از آنجایی که شرط (2.10) برآورده نمی شود و بنابراین راه حل بهینه نیست.
اجازه دهید جدول 2.4 را بسازیم تا به راه حل اساسی جدید سیستم (2.14) - (2.15) برویم.
جدول 2.4
| 1 | -  | -  | -  |
||||
| | 0 | -1 | 0 | 0 |
|||
| | 0 | 0 | -1 | 0 |
|||
 | 4 | 1 | -2 | 0 |
|||
| | 0 | 0 | 0 | -1 |
|||
 | 2 | 4 * | -6 | -2 |
|||
 | 4 | 2 | 0 | -1 |
|||
 | 32 | ||||||
 | 12 | -10 | -4 |
||||
 | 4 | ||||||
 | 1/2 | جدول 2.5 | 0 | 0 | -1 |
||
| | 0 | -1 | 0 | 0 |
|||
| | 3 | -1/2 | 3 * | 0 |
|||
| | 110,25 | ||||||
| | -2,5 | 9 | -2 |
||||
| | -3 |
سخنرانی 11.برنامه نویسی محدب
تعریف 1. ز با برنامه نویسی محدب یک مسئله برنامه نویسی غیر خطی است که در آن همه توابع محدب هستند.
بنابراین، یک مسئله برنامه‌نویسی محدب یک مسئله کمینه‌سازی شرطی است، که در آن تابع هدف محدب است و دامنه امکان‌پذیر مجموعه‌ای محدب است که توسط سیستمی از نابرابری‌های محدب تشکیل شده است. بنابراین، عباراتی که قبلاً در بخش 6 به دست آمد برای مسئله برنامه ریزی محدب معتبر است. در این بخش، این نتایج کلی را مشخص می کنیم و آنها را به شکلی می آوریم که برای مطالعه و حل مسئله برنامه نویسی محدب زیر راحت تر باشد:
(1)
,
(2)
.
(3)
ما به چند سازه کمکی در فضا نیاز خواهیم داشت 
بردارها 
... وکتور از اول 
جزء نقطه ای 
مشخص خواهد شد 
... بنابراین، 
.
برای مسئله (1) - (3)، مجموعه را تعریف کنید
جایی که 
.
لما
.
برای مسئله برنامه نویسی محدب (1) - (3)
یک دسته از
محدب.
اثبات
ما بردارهای دلخواه را انتخاب می کنیم 
از انبوه 
و شماره 
... سپس نکاتی وجود دارد 
و 
از جانب
مانند و. ما این نابرابری ها را در ضرب می کنیم 
و 
به ترتیب، و آنها را اضافه کنید. از آنجایی که همه توابع محدب هستند، به دست می آوریم
نابرابری های به دست آمده حاکی از تحدب مجموعه است 
.
قضیه 1.
(قضیه کوهن تاکر به شکل نقطه زین تابع لاگرانژ یک مسئله برنامه ریزی محدب
) فرض کنید در مسئله برنامه ریزی محدب (1) - (3) سیستم (2) شرط اسلاتر را با توجه به 
راه حلی برای مسئله (1) - (3) بود، وجود بردار غیرمنفی لازم و کافی است 
به طوری که 
نقطه زین تابع لاگرانژ است.
اثبات از آنجایی که کفایت این شرط قبلاً برای یک مسئله برنامه ریزی غیرخطی دلخواه ثابت شده است (به قضیه 2.6 مقدمه مراجعه کنید)، تنها برای اثبات ضرورت باقی می ماند.
نیاز داشتن.
اجازه دهید
- راه حل مسئله (1) - (3). ما گذاشتیم 
... بدیهی است که 
، زیرا
,
و
.
بیایید مطمئن شویم که 
... برعکس را فرض کنید. این به این معنی است که یک نکته وجود دارد 
به طوری که 
... از این رو، 
- چنین نقطه مجاز، مقدار تابع هدف که در آن کمتر از حداقل است. ما با این واقعیت تناقض داریم
- حل مسئله برنامه نویسی محدب.
بنابراین، 
... با توجه به لم، مجموعه 
محدب در نتیجه، تمام الزامات قضیه 8.2 برآورده شده است. بنابراین، یک غیر صفر وجود دارد
بردار 
نقطه محوری 
به انبوه 
:
اجازه دهید بیشتر بررسی کنیم که همه مختصات بردار 
مثبت نیستند برعکس را فرض کنید. بگذارید یک مختصات وجود داشته باشد 
... اجازه دهید بردار را درست کنیم 
همه اجزا به جز 
-اوه سپس با در نظر گرفتن اینکه محصول 
می تواند مقادیر زیادی دلخواه بگیرد (زیرا مختصات از بالا نامحدود هستند) 
) یک تناقض با نابرابری بدست می آوریم (4).
دیدن آن برای هر کسی آسان است 
بردارها 
در بسیاری گنجانده شده است 
... سپس از (4) داریم:
بگذارید این را نشان دهیم 
... بگذار اینطور نباشد. سپس 
... از این رو، 
... در شرایط اسلاتر، یک بردار وجود دارد 
به طوری که 
... بنابراین 
... تضاد حاصل به این معنی است 
.
نشان می دهیم 
... اجازه دهید نشان دهیم که بردار ساخته شده است 
بردار مورد نیاز ضرایب لاگرانژ است. بدیهی است که 
و از (5) بدست می آوریم
از این رو، در
باید
.
(7)
از سوی دیگر، از آنجایی که 
(تا جایی که 
) و 
، نابرابری را بدست می آوریم
... از این و (7) نتیجه می شود که در نقطه 
شرایط سستی تکمیلی برآورده می شود:
.
(8)
از (6) و (8) داریم
یا، که همان است،
علاوه بر این، اجازه دهید 
... سپس 
... از این و (8) نابرابری را بدست می آوریم
نابرابری های (9)، (10) و معنی آن 
آیا نقطه زین تابع لاگرانژ مسئله محدب است
لوگوی برنامه نویسی که مورد نیاز بود.
قبل از آشنایی با نسخه دیگری از قضیه کوهن تاکر، قضیه زیر را ارائه می کنیم که یک معیار حداقل شرطی از نظر مخروط های بردار پشتیبان است.
قضیه 2.
اجازه دهید 
- محدب و متمایز بر روی 
عملکرد، مجموعه 
محدب سپس به منظور نقطه
حداقل شرطی تابع بود 
در مجموعه 
، برای شمول لازم و کافی است
.
(11)
اثبات مستقیماً از قضیه 6.5 و تعریف مخروط به دست می آید 
بردارهای پشتیبانی در نقطه 
به انبوه
.
قضیه
3.
(قضیه کوهن تاکر به شکل دیفرانسیل برای یک مسئله برنامه ریزی محدب
) اجازه دهید یک مسئله برنامه نویسی محدب به شکل (1)، (2) داده شود، که در آن همه توابع وجود دارد 
به طور مداوم قابل تمایز هستند، سیستم (2) شرایط اسلاتر را برآورده می کند. سپس به منظور بردار 
حل مسئله (1)، (2) بود، وجود بردار غیر منفی لازم و کافی است 
به گونه ای که شرایط
,
(12)
.
اثبات
اجازه دهید نشان دهیم که شرایط (12) و (13) معادل گنجاندن (11) هستند. بگذارید نکته 
به گونه ای است که 
... سپس 
و 
.
بگذار حالا 
... سپس از قضایای 2 و 10.5 چنین بر می آید که شرط لازم و کافی برای افراط، وجود چنین عواملی است. 
,
برای کدام 
... ما گذاشتیم 
برای همه 
و از آخرین شرایط برابری (12) و (13) به دست می آوریم. که مورد نیاز بود.
برای پایان دادن به این بخش، فرمول‌بندی دو قضیه کوهن تاکر را برای مسئله ارائه می‌کنیم
برنامه نویسی محدب با محدودیت های خطی
قضیه 4.
اجازه دهید سیستم قیود (2) در مسئله برنامه نویسی محدب (1) - (3) شکل داشته باشد. 
، b بردار بعد است 
... سپس، به منظور یک بردار غیر منفی
راه حل مشکل بود، لازم و کافی است
یک بردار غیر منفی وجود دارد
به طوری که
آیا نقطه زین تابع لاگرانژ مسئله داده شده است.
توجه داشته باشید که در این حالت تابع لاگرانژ دارای فرم است.
قضیه
5.
اجازه دهید در مسئله برنامه ریزی محدب (1)، (2) تابع هدف
به طور پیوسته قابل تمایز است، سیستم قیود (2) شکل دارد 
، که در آن A یک ماتریس بعد است 
، b بردار بعد است 
.
سپس به منظور بردار 
راه حلی برای مشکل بود، وجود بردار غیر منفی لازم و کافی است
به گونه ای که شرایط
,
.
توجه داشته باشید که در قضایای 4 و 5 تحقق شرط اسلاتر الزامی نیست، بنابراین آنها موارد خاصی از قضایای 1 و 3 نیستند و نیاز به اثبات مستقل دارند.
اجازه دهید یک سیستم از نابرابری های شکل
(4.3) و تابع
Z = f (x 1، x 2، ...، x n)، (4.4)
علاوه بر این، همه توابع در مجموعه محدب M محدب هستند و تابع Z یا در مجموعه M محدب است یا مقعر.
مشکل برنامه نویسی محدب یافتن راه حلی برای سیستم قیود (4.3) است که در آن تابع هدف Z به حداقل مقدار خود برسد یا تابع مقعر Z به حداکثر مقدار خود برسد. (شرایط غیرمنفی بودن متغیرها را می توان در سیستم (4.3) گنجانده شد).
با توجه به ویژگی 3 0، هر مسئله برنامه ریزی خطی یک مورد خاص از یک مسئله برنامه ریزی محدب است. به طور کلی، مسائل برنامه نویسی محدب، مسائل برنامه ریزی غیرخطی هستند. جداسازی مسائل برنامه نویسی محدب به یک کلاس خاص با ویژگی های فوق العاده توابع محدب توضیح داده می شود: هر حداقل محلی یک تابع محدب (حداکثر محلی یک تابع مقعر) به طور همزمان جهانی است. علاوه بر این، با توجه به ویژگی 2 0، یک تابع محدب (مقعر) تعریف شده بر روی یک مجموعه محدود بسته به حداکثر جهانی و یک حداقل جهانی در این مجموعه می رسد. از این رو نتیجه می شود که اگر تابع هدف Z کاملا محدب باشد (به شدت مقعر) و اگر حوزه حل سیستم محدودیت ها خالی و محدود نباشد، آنگاه مسئله برنامه ریزی محدب همیشه یک راه حل منحصر به فرد دارد..
تابع F (X) = F (x 1, x 2, ..., x n) فراخوانی می شود قابل تفکیک، اگر بتوان آن را به عنوان مجموع توابع نشان داد که هر کدام از آنها فقط به یک متغیر بستگی دارد، یعنی. اگر
(این امکان وجود دارد که F i (x i) = 0 برای برخی i).
اجازه دهید یک سیستم از محدودیت ها (4.3) و یک تابع هدف (4.4) در یک مسئله برنامه نویسی محدب داده شود، و تابع هدف Z و همه محدودیت ها قابل تفکیک هستند. سپس مشکل به نظر می رسد:
حداقل تابع محدب (حداکثر - مقعر) را بیابید
با محدودیت
ایده روش تقریب خطی تکه ای این است که همه f i و همه با خطوط شکسته متشکل از بخش های خط مستقیم جایگزین می شوند. در این مورد، مسئله برنامه ریزی محدب اصلی با یک مسئله تقریبی جدید جایگزین می شود که یک مسئله برنامه ریزی خطی است. این مشکل معمولاً با روش سیمپلکس حل می شود و راه حل آن یک راه حل تقریبی برای مسئله اصلی برنامه نویسی محدب است.
شکل 12. حل مسئله برنامه ریزی محدب با روش تقریب خطی تکه ای
برای ساختن یک مسئله تقریبی، یک تقریب خطی تکه تکه از تابع یک متغیر h (x) داده شده در یک بازه را در نظر بگیرید. این بخش را با نقاط x 0 به قسمت r تقسیم کنید معادله پاره خط بین نقاط (x k؛ h k) و (x k + 1؛ h k + 1) شکل (معادله یک خط مستقیم در امتداد دو نقطه) دارد. اگر هر یک از روابط در این برابری با نشان داده شود، به دست می آید: توجه داشته باشید که برای هر یک مقدار منحصر به فرد وجود دارد که شرایط را ارضا می کند (4.7). دلالت را می توان به شکل (4.7) بازنویسی کرد: [معادلات (4.8) معادلات پارامتریک قطعه نامیده می شوند. اگر h (x) = 0 باشد، دومی از این معادلات به هویت 0 = 0 تبدیل می شود و اولین شکل (4.1) - معادله قطعه ای که روی آبسیسا قرار دارد] می شود. بنابراین، برای هر معادله ای از خط شکسته می توان به شکل زیر نوشت: و فقط دو مقدار همیشه غیر صفر هستند (اگر x یک نقطه داخلی از k-امین بخش پارتیشن باشد) یا یک (اگر x با انتهای قطعه منطبق باشد). با بازگشت به مسئله برنامه نویسی محدب با توابع قابل تفکیک، توجه می کنیم که اول از همه (بسته به سیستم محدودیت ها) لازم است فاصله تغییرات هر متغیر x j تعیین شود. سپس هر یک از این بازه با نقاط x jk به قطعات تقسیم شده و با استفاده از فرمول (4.9) تقریب خطی تکه ای برای توابع f j ساخته می شود. پس از آن، برای مشکل اصلی (4.6)، می توانیم مشکل تقریبی را یادداشت کنیم: حداکثر یک تابع را پیدا کنید مشمول محدودیت ها (4.10) از آنجایی که مسئله تقریبی (4.10) یک مسئله برنامه ریزی خطی است که معمولاً با روش سیمپلکس حل می شود، شرایط برای غیر منفی بودن متغیرها جدا از بقیه محدودیت ها نوشته می شود. تفاوت بین مسئله به‌دست‌آمده (4.10) و مسئله برنامه‌ریزی خطی معمول در این است که برای هر x j بیش از دو غیر صفر مجاور وجود ندارد و بنابراین نمی‌توان دو متغیر پایه را با j یکسان و k غیر مجاور در نظر گرفت. به این نکته نیز توجه داشته باشید که البته برای شرایط غیرمنفی بودن متغیرهای f j (xj) و (در صورت وجود) نیازی به تقریب خطی تکه‌ای نیست. این فصل تنها تعدادی از تکنیک های بهینه سازی مورد استفاده توسط مدیران را برای تصمیم گیری موثر در شرکت ها بررسی کرده است. با این حال، تکنیک های توصیف شده درک اصل اساسی استفاده از دستگاه ریاضی در اقتصاد را امکان پذیر می کند، که به شما امکان می دهد از بین گزینه های مختلف جایگزین که برای یک مورد یا موقعیت خاص بهینه است، انتخاب کنید.
