نمونه های روش لاگرانژ بهینه سازی مشروط

طبقه بندی مسائل برنامه ریزی ریاضی

برنامه نويسي

روش های حل مسائل غیرخطی

سوالات آزمون بخش 4

طرحی برای حل مشکل حمل و نقل

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

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

2. یک طرح مرجع بسازید.

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

4. طرح از نظر بهینه بررسی می شود.

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

1. منظور از تابع هدف در مدل ریاضی مسئله حمل و نقل چیست؟

2. منظور از محدودیت در مدل ریاضی مسئله حمل و نقل چیست؟

3. آیا می توان از روش بالقوه برای حل مشکل حمل و نقل باز (بسته نشده) استفاده کرد؟

4. چه تغییراتی باید در جدول حمل و نقل اصلی ایجاد شود تا بتوان مشکل را با روش بالقوه حل کرد؟

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

6. چگونه متوجه می شوید که طرح حمل و نقل بهینه است؟

7. در چه صورت و چگونه نیاز به توزیع مجدد لوازم از نظر حمل و نقل است؟

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

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

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

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

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

(5.2)

جایی که - توابع شناخته شده،

آ - ضرایب داده شده

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

اجازه دهید شرایط (5.2) را طوری تبدیل کنیم که در سمت چپ یا راست برابری ها وجود داشته باشد صفر:

(5.3)

بیایید تابع لاگرانژ را بسازیم. این شامل تابع هدف (5.1) و سمت راست قیود (5.3) است که به ترتیب با ضرایب گرفته شده است. . به همان تعداد ضرایب لاگرانژ وجود خواهد داشت که در مسئله محدودیت وجود دارد.

نقاط منتهی تابع (5.4) نقاط منتهی مسئله اصلی هستند و بالعکس: طرح بهینه مسئله (5.1)-(5.2) نقطه انتهایی سراسری تابع لاگرانژ است.

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

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

اجازه دهید مشتقات جزئی تابع (5.4) را تعریف کنیم.

,

.

پس از تساوی صفرمشتقات ما سیستم را دریافت می کنیم m+nمعادلات با m+nناشناخته

, (5.6)

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

اجازه دهید تابع در برخی از همسایگی های نقطه ثابت خود دو بار متمایز باشد (یعنی )). سپس:

آ) اگر،(5.8)

سپس نقطه حداکثر دقیق تابع است.

ب)اگر،(5.9)

سپس حداقل نقطه دقیق تابع است.

جی ) اگر،

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

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

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

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

,

در چند مرحله انجام می شود:

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

.

2. از نقاط ثابت، مواردی را انتخاب کنید که مختصات آنها شرایط را برآورده کند

3. با استفاده از روش لاگرانژ، مسئله را با قیود برابری (5.1)-(5.2) حل کنید.

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

مشکل 5.1اجازه دهید مسئله 1.3 را که در بخش اول در نظر گرفته شده است، با استفاده از روش لاگرانژ حل کنیم. توزیع بهینه منابع آب با یک مدل ریاضی توصیف شده است

.

بیایید تابع لاگرانژ را بسازیم

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

,

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

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

مقادیر در صدها هزار متر مکعب اندازه گیری می شود. - میزان درآمد خالص به ازای هر صد هزار متر مکعب آب آبیاری. بنابراین قیمت نهایی 1 متر مکعب آب آبیاری برابر است با لانه واحدها

حداکثر درآمد خالص اضافی حاصل از آبیاری خواهد بود

160·12.26 2 +7600·12.26-130·8.55 2 +5900·8.55-10·16.19 2 +4000·16.19=

172391.02 (دانشگاه واحد)

مشکل 5.2حل مسئله برنامه نویسی غیرخطی

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

.

بیایید تابع لاگرانژ را بسازیم و مشتقات جزئی آن را تعیین کنیم

.

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

روش ضریب لاگرانژ.

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

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

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

F(x 1،…x n)، اف (ایکس) → حداکثر

زمانی که شرایط برآورده شود

g j (x 1،…x n)≥0، g (ایکس) ≤ ب , ایکس ≥ 0

جایی که ایکس-بردار متغیرهای مورد نیاز.

اف (ایکس) -تابع هدف؛

g (ایکس) - تابع محدودیت (به طور مداوم قابل تمایز).

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

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

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

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

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

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

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

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

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

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

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

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

برای مشکل اکسترموم یک تابع f(x 1، x 2،...، x n) تحت شرایط (معادلات محدودیت) φ من(x 1، x 2، ...، x n) = 0, من= 1, 2,..., متر، تابع لاگرانژ شکل دارد

L(x 1, x 2… x n, λ 1, λ 2,… λm)=f(x 1, x 2… x n)+∑ i -1 m λ i φ i (x 1, x 2… x n)

ضرب کننده ها λ 1، λ 2، ...، λmتماس گرفت ضرب کننده های لاگرانژ

اگر مقادیر x 1، x 2، ...، x n، λ 1، λ 2، ...، λmماهیت راه حل های معادلاتی که نقاط ثابت تابع لاگرانژ را تعیین می کنند، یعنی برای توابع متمایز، راه حل هایی برای سیستم معادلات هستند.

سپس، تحت مفروضات نسبتاً کلی، x 1، x 2، ...، x n حداکثر تابع f را ارائه می دهد.

مسئله کمینه کردن تابعی از n متغیر را که تحت یک قید به شکل برابری در نظر می گیرند، در نظر بگیرید:

به حداقل رساندن f(x 1، x 2… x n) (1)

تحت محدودیت h 1 (x 1, x 2… x n) = 0 (2)

با توجه به روش ضریب لاگرانژ، این مسئله به مسئله بهینه سازی نامحدود زیر تبدیل می شود:

کوچک کردن L(x,λ)=f(x)-λ*h(x) (3)

که در آن تابع L(x;λ) تابع لاگرانژ نامیده می شود،

λ یک ثابت مجهول است که به آن ضریب لاگرانژ می گویند. هیچ الزامی برای علامت λ وجود ندارد.

اجازه دهید، برای یک مقدار معین λ=λ 0، حداقل نامشروط تابع L(x,λ) نسبت به x در نقطه x=x 0 حاصل شود و x 0 معادله h 1 (x 0)=0 را برآورده کند. . سپس، همانطور که به راحتی قابل مشاهده است، x 0 با در نظر گرفتن (2) (1) را به حداقل می رساند، زیرا برای تمام مقادیر x رضایت بخش (2)، h 1 (x)=0 و L(x,λ)=min f(x).

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

f(x)=x 1 2 +x 2 2 =0 را به حداقل برسانید

تحت محدودیت h 1 (x)=2x 1 +x2 -2=0=0

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

کوچک کردن L(x,λ)=x 1 2 + x 2 2 -λ(2x 1 +x 2 -2)

راه حل. با برابر کردن دو جزء گرادیان L با صفر، به دست می آوریم

→ x 1 0 =λ

→ x 2 0 =λ/2

برای بررسی اینکه آیا نقطه ثابت x° با حداقل مطابقت دارد یا خیر، عناصر ماتریس هسین تابع L(x;u) را محاسبه می کنیم که به عنوان تابعی از x در نظر گرفته می شود.

که معلوم می شود مثبت قطعی است.

این بدان معناست که L(x,u) تابع محدب x است. در نتیجه، مختصات x 1 0 =λ، ​​x 2 0 =λ/2 نقطه حداقل جهانی را تعیین می کند. مقدار بهینه λ با جایگزین کردن مقادیر x 1 0 و x 2 0 در معادله 2x 1 + x 2 =2 بدست می‌آید که از آن 2λ+λ/2=2 یا λ 0 =4/5 است. بنابراین، حداقل شرطی در x 1 0 = 4/5 و x 2 0 = 2/5 به دست می آید و برابر است با min f(x) = 4/5.

هنگام حل مسئله مثال، L(x;λ) را تابعی از دو متغیر x 1 و x 2 در نظر گرفتیم و علاوه بر این، فرض کردیم که مقدار پارامتر λ طوری انتخاب شده است که محدودیت برآورده شود. اگر راه حل سیستم

J=1,2,3,…,n

λ را نمی توان به صورت توابع صریح به دست آورد، سپس مقادیر x و λ با حل سیستم زیر متشکل از n+1 معادله با n+1 مجهول پیدا می شود:

J=1,2,3,…,n., h 1 (x)=0

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

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

به حداقل رساندن f(x)

تحت محدودیت h k = 0، k = 1، 2، ...، K.

تابع لاگرانژ به شکل زیر است:

اینجا λ 1، λ 2، ...، λk-ضریب لاگرانژ، یعنی. پارامترهای ناشناخته ای که مقادیر آنها باید تعیین شود. با معادل سازی مشتقات جزئی L نسبت به x به صفر، سیستم n معادله زیر را با n مجهول به دست می آوریم:

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

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

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

الگوریتم روش ضریب لاگرانژ

1. تابع لاگرانژ را بنویسید.

2. مشتقات جزئی تابع لاگرانژ را با توجه به متغیرهای x J ,λ i بیابید و آنها را با صفر برابر کنید.

3. سیستم معادلات (7) را حل می کنیم، نقاطی را می یابیم که تابع هدف مسئله می تواند در آن ها انتها داشته باشد.

4. در میان نقاط مشکوک برای یک اکستروم، نقاطی را می یابیم که در آنها به اکستروم رسیده است و مقادیر تابع (6) را در این نقاط محاسبه می کنیم.

مثال.

اطلاعات اولیه:طبق برنامه تولید، این شرکت نیاز به تولید 180 محصول دارد. این محصولات را می توان به دو روش تکنولوژیکی تولید کرد. هنگام تولید محصولات x 1 با استفاده از روش اول، هزینه ها 4x 1 + x 1 2 روبل و هنگام تولید محصولات x 2 با استفاده از روش دوم، 8x 2 + x 2 2 روبل است. تعیین کنید با استفاده از هر روش چه تعداد محصول باید تولید شود تا هزینه تولید حداقل باشد.

تابع هدف برای مسئله بیان شده دارای فرم است
® دقیقهتحت شرایط x 1 + x 2 = 180، x 2 ≥0.
1. تابع لاگرانژ را بنویسید
.
2. مشتقات جزئی را با توجه به x 1، x 2، λ محاسبه می کنیم و آنها را با صفر برابر می کنیم:

3. با حل سیستم معادلات حاصل، x 1 = 91، x 2 = 89 را پیدا می کنیم

4. پس از جایگزینی در تابع هدف x 2 = 180-x 1، تابعی از یک متغیر به دست می آوریم، یعنی f 1 = 4 x 1 + x 1 2 + 8 (180-x 1) + (180-x 1) ) 2

ما محاسبه می کنیم یا 4x 1 -364=0،

از این رو x 1 * = 91، x 2 * = 89 داریم.

پاسخ: تعداد محصولات تولید شده با روش اول x 1 = 91، به روش دوم x 2 = 89 است، در حالی که مقدار تابع هدف برابر با 17278 روبل است.

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

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

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

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

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

بنابراین، مطابق با روش ضرب‌کننده لاگرانژ، برای یافتن حداکثر تابع هدف در مجموعه مقادیر مجاز، تابع لاگرانژ L(x, λ) را می‌نویسم که بیشتر بهینه‌سازی می‌شود:

که در آن λ ˗ بردار متغیرهای اضافی به نام ضریب لاگرانژ نامشخص است.

بنابراین، مسئله یافتن حد فاصل شرطی تابع f(x) به مسئله یافتن حد فاصل غیرشرطی تابع L(x, λ) تقلیل یافته است.

و

شرط لازم برای حداکثر تابع لاگرانژ توسط یک سیستم معادلات ارائه می شود (سیستم از معادلات "n + m" تشکیل شده است):

حل این سیستم معادلات به ما امکان می دهد تا آرگومان های تابع (X) را تعیین کنیم که در آن مقدار تابع L(x, λ) و همچنین مقدار تابع هدف f(x) با اکستروموم مطابقت دارد.

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

چندین روش برای تعیین ماهیت حداکثر تابع حاصل وجود دارد:

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

اگر ، سپس حداکثر در نقطه وجود دارد.

اگر ، سپس حداقل در نقطه وجود دارد.

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

اگر در یک نقطه معین کمترین، اگر ، سپس تابع هدف f(x) یک شرطی دارد بیشترین.

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

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

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

2. برای اینکه دیفرانسیل دوم تابع لاگرانژ منفی باشد ، لازم است که مینورهای زاویه ای تابع متناوب باشند و اولین عنصر ماتریس باید negativesv باشد. در چنین شرایطی، تابع در این نقطه دارای حداکثر است.

منظور ما از مینور زاویه ای، مینور واقع در اولین k ردیف و k ستون ماتریس اصلی است.

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

روش محاسبه

1 مرحله: تابع لاگرانژ را از تابع هدف و سیستم محدودیت ها تعیین می کنیم:

رو به جلو

برای افزودن نظر خود به مقاله لطفا در سایت ثبت نام کنید.

روش لاگرانژ

روشی برای کاهش یک فرم درجه دوم به مجموع مربع ها، که در سال 1759 توسط J. Lagrange نشان داده شد. بگذار داده شود

از متغیرهای x 0 ، ایکس 1 ،...، x ص. با ضرایب از میدان کویژگی ها لازم است این فرم را به شکل متعارف برسانید. ذهن

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

1) برای برخی gمورب سپس

که در آن شکل f 1 (x) دارای متغیر نیست x g 2) اگر همه چیز ولی که

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

روشن شد: G a n t m a k h e r F. ر.،نظریه ماتریس ها، ویرایش دوم، M.، 1966; K u r o sh A. G., Course of Higher Algebra, 11th ed., M., 1975; الکساندروف پی اس، سخنرانی‌هایی درباره هندسه تحلیلی ...، M.، 1968. I. V. Proskuryakov.

دایره المعارف ریاضی. - م.: دایره المعارف شوروی. I. M. Vinogradov. 1977-1985.

ببینید "روش لاگرانژ" در فرهنگ های دیگر چیست:

روش لاگرانژ- روش لاگرانژ روشی برای حل تعدادی از کلاس های مسائل برنامه ریزی ریاضی با یافتن نقطه زینی (x*, λ*) تابع لاگرانژ است که با برابر کردن مشتقات جزئی این تابع نسبت به صفر به دست می آید. ...... فرهنگ لغت اقتصادی و ریاضی

روش لاگرانژ- روشی برای حل تعدادی از کلاس های مسائل برنامه ریزی ریاضی با یافتن نقطه زینی (x*, ?*) تابع لاگرانژ که با معادل سازی مشتقات جزئی این تابع نسبت به xi و?i به صفر به دست می آید. . رجوع به لاگرانژ شود. )