Лагранж функциясы

Операцияларды зерттеу пәні

Бұл материал 1-тапсырма бойынша жауап-конспект ретінде құрылымдалған. Мақсат — негізгі ұғымдарды жинақы түрде жүйелеу және кейінгі есептерді модельдеуге қажетті теориялық базаны қалыптастыру.

Негізгі бөлімдер

Дөңес программалау
Сызықтық емес программалау
Ақырлы өлшемді кеңістіктегі минимумдаудың сандық әдістері

Нені ерекше есте сақтау керек?

Көптеген оңтайландыру есептері үшін дөңестік шешуші рөл атқарады: ол локал минимумның жиі жағдайда глобал минимумға тең болуын қамтамасыз етеді және Кун–Таккер шарттары сияқты қажетті/жеткілікті критерийлерді қолдануға мүмкіндік береді.

Практикалық тұрғыдан: теория (дөңес талдау, Лагранж, ККТ) → модель → сандық әдіс (градиент, Ньютон, айыптық функциялар) тізбегімен жұмыс жасау тиімді.

1-тапсырма: Жауап-конспект

1) Дөңес программалау

Дөңес талдаудың элементтері

Дөңес функциялар және олардың анықтамалары.
Әлді (қатаң) дөңес функциялар: бірмәнді шешімдер мен тұрақтылыққа әсері.
Дөңес функциялардың негізгі қасиеттері (композиция, қосынды, шектеулер және т.б.).

Тегіс функциялар үшін критерийлер

Тегіс (дифференциалданатын) функция дөңестігінің критерийлері.
Тегіс функциялардың әлді дөңестігі үшін критерийлер.

Глобал минимум және тиімділік

Глобал минимум туралы теорема және оның мағынасы.
Тиімділік (оптималдық) критерийлері.
Математикалық программалау теориясының негізгі қағидалары.

Лагранж және ККТ

Дөңес программалаудағы Лагранж қағидасы және Лагранж функциясы.
Қайқы нүкте және қайқы нүкте туралы негізгі лемма.
Глобал минимум туралы негізгі теорема.
Кун–Таккер теоремалары (ККТ шарттары).
Слейтер шарты және оның рөлі (қатаң орындалатын шектеулер арқылы жеткіліктілікті негіздеу).
Дөңес программалаудағы түйіндестік (дуалдылық): бастапқы және дуал есептердің байланысы.

2) Сызықтық емес программалау

Мәселенің қойылуы

Мақсат функциясы және шектеулер арқылы оптималдау есебін формальды жазу.
Тиімділіктің қажетті шарттары

Стационарлық, шектеулердің орындалуы және қажет болғанда ККТ шарттарын қолдану.
Шешу алгоритмдері

Есептің түріне байланысты итерациялық әдістерді таңдау және тоқтау критерийлерін анықтау.

3) Ақырлы өлшемді кеңістіктегі минимумдаудың сандық әдістері

Бір айнымалы функцияны минимумдау

Кесіндіні қақ бөлу (дихотомия) әдісі.
Алтын қима әдісі.
Тиімді іздестіру қағидалары.
Сандық тізбектің қасиеті туралы лемма (итерациялар жинақтылығы үшін).

Көп айнымалы әдістер

Градиенттік әдіс.
Градиент проекциясы туралы теорема (шектеулі оптимизациядағы маңызы).
Ньютон әдісі (екінші туындыларға негізделген жедел жинақтылық).
Айыптық функциялар әдісі.
Лагранж көбейткіштер әдісі.

Сандық әдісті таңдағанда есептің дөңестік қасиеті, туындылардың қолжетімділігі, өлшемділік және дәлдік/есептеу құны арасындағы баланс ескеріледі.

2-тапсырма: Есептердің шығарылу жолын көрсету

Есеп №1

Бір өнімді тігу үшін матадан 6 түрлі деталь пішіп алу керек. Тігін фабрикасында матаны пішудің 10 нұсқасы қарастырылған. Кестеде әр нұсқа бойынша алынатын детальдар саны және бір кесудің шығын мөлшері берілген.

Берілгендер

Ай сайынғы мата қоры: 405.
Келесі айға жоспар: 90 өнім.
Әр өнімге қажет: 6 деталь (түрлері бойынша).

Талап

Келесі айға арналған тігу жоспарын ең аз шығынмен орындайтындай етіп, есептің математикалық моделін құру.

Кесте 2. Матаны кесудің нұсқалары (үзінді)

Пішу нұсқасы	Деталь 1	Деталь 2	Деталь 3	Деталь 4	Деталь 5	Деталь 6	Шығын (бір кесу)
1	60	0	90	40	70	90	0.5
2	80	35	20	78	15	0	0.35
Комплектілік (өнімге қажет)	1	2	2	2	2	2	—

Ескерту: бастапқы мәтінде 10 нұсқа көрсетілген, бірақ үлгі ретінде кестеде 1–2 нұсқаның деректері ғана берілген. Толық модель құру үшін 3–10 нұсқалар бойынша деректер қажет.

Модельді қалай құру керек (құрылымы)

Айнымалылар: әр пішу нұсқасын қанша рет қолданатынымыз (мысалы, x_j).
Мақсат функциясы: жалпы шығынды минималдау (кесулер шығындарының қосындысы).
Шектеулер: әр деталь түрі бойынша жеткілікті санды қамтамасыз ету (90 өнімге арналған комплектілік арқылы).
Қор шектеуі: қолданылған мата көлемі 405-тен аспауы керек (егер 405 мата бірлігі кесу санына/материал бірлігіне теңестірілсе).
Айнымалылардың табиғаты: әдетте x_j ≥ 0 және өндірістік мағынада көбіне бүтін.

Нақтылау қажет деректер

Модельді толық әрі дұрыс жазу үшін кестедегі 10 пішу нұсқасының барлығы бойынша: әр нұсқада алынатын 6 детальдың саны және бір кесудің шығыны қажет.