Лекції - Теорія систем і системний аналіз
Тема 1.Лекція 1_Вводная.doc (1 стор.)
Тема 2.Лекція 2_Основние понятія.doc (1 стор.)
Тема 3_Реалізація СА, показателі.doc (1 стор.)
Тема 4_Вибор.doc (1 стор.)
Тема 5.Лекція 5_ЛП.doc (1 стор.)
Тема 5.Лекція 6_НП.doc (1 стор.)
Тема 6_Лекція 7_ Багатокритеріальні задачі.doc (1 стор.)
Тема 7_Лекція 8_Вибор в умовах ріска.doc (1 стор.)
Тема 8-9_Лекція 10_Ігра з природою, СА істочніков.doc (1 стор.)
Тема 8_Лекція 9_Теорія ігр.doc (1 стор.)
Оригінал Тема 5. л екция 6. нелінійне програмування (НП)
Постановка задачі НП
Еколого-економічна інтерпретація задачі НП
Геометрична інтерпретація задачі НП
Метод множників Лагранжа (ММЛ)
Огляд розглянутих методів.
1. Постановка задачі НП У загальному вигляді задача НП складається у визначенні max / min значення
f (x 1, x 2,... x n) (1) за умови, що її змінні задовольняють співвідношенням
g
i (x
1, x
2,..., x
n) b
i (i = 1, k)
g
i (x
1, x
2,..., x
n) = b
i (i = k + 1, m),
де f і g
i деякі відомі функції n змінних, а b
i - задані числа.
Мається на увазі, що в результаті рішення задачі буде визначена точка
Х * = (х 1 *, х 2 *, ... х n *), координати якої задовольняють співвідношенню (2), причому для всякої іншої точки, що відповідає умовам (2), виконується
F * (x *
1, x *
2,... x *
n) f (x
1, x
2,... x
n) Якщо f і g
i - лінійні функції, то це буде задача лінійного програмування.
Співвідношення (2), що утворюють систему обмежень, включають в себе і умови невід'ємності змінних, якщо такі є. Останні можуть бути задані і окремо.
У евклідовому просторі
En система обмежень (2) визначає ОДР.
На відміну від задачі ЛП вона не завжди є опуклою. Якщо визначена ОДР, то знаходження рішення задачі НП зводиться до визначення такої точки цієї області, через яку проходить гіперповерхні найвищого (найнижчого) рівня:
f (x 1, x 2,... x n) = h, причому ця точка може знаходитися як на кордоні ОДР, так і всередині неї.
2. Еколого-економічна інтерпретація задач НП На проведення заходів по підвищенню екологічності виробництва підприємство має в своєму розпорядженні 220 тис. руб. Ці кошти можуть бути розподілені між трьома підрозділами. Кожен варіант розподілу знижує певною мірою збиток від забруднення навколишнього середовища і дає певний ефект, рівний запобігання шкоді. Потрібно визначити такий варіант розподілу капіталовкладень, при якому ефект, одержуваний підприємством буде максимальним.
Подраз-ділення
| Капітало-вкладення, тис.р.
| Ефект, тис. руб.
| Капітало-вкладення, тис.р.
| Ефект, тис. руб.
| Капітало-вкладення, тис.р.
| Ефект, тис. руб.
|
I
| Від 10 до 30
| 7,3
| 30 ... 60
| 8,0
| 60
| 10
|
II
| Від 10 до 40
| 6,2
| 40 ... 70
| 8,6
| 70
| 9,1
|
III
| Від 10 до 50
| 9,1
| 50 ... 60
| 9,8
| 60
| 9,5
|
Математична модель Позначимо капіталовкладення, розподілені між трьома підрозділами х
1, х
2, х
3. Ефект по кожному підрозділу: З
1 (Х
1), С
2 (Х
2), С
3 (Х
3). F = C
1 (X
1) X
1 + C
2 (X
2) X
2 + C
3 (X
3) X
3 = f (X
1, X
2, X
3) max
X
1 + X
2 + X
3 = 220
X
1, X
2, X
3 0.
Відомо, що можна регулювати ступінь чистоти ОС шляхом нормування, тобто введення допустимого рівня забруднювача в середовищі. Таке регулювання можна здійснювати шляхом видачі виробнику ліцензій, умовою для отримання яких було б дотримання встановлених норм якості ОС. Природно, що кожне підприємство - джерело забруднення несе певні витрати на усунення забруднення.
Повні витрати (С) на усунення забруднення складаються з суми витрат С
i для кожного забруднюючої середовище:

,
де Q
i - маса усунутого забруднюючої речовини i-м підприємствам.
Для забезпечення встановленого рівня якості ОС повна маса забруднюючої речовини Q, що підлягає усуненню, визначається як:

Оскільки витрати підприємств на усунення забруднень лягають також і на споживачів продукції (подорожчання її), то суспільству в цілому вигідна мінімізація повних витрат на забезпечення якості ОС.
Таким чином цільова функція

.
Обмеження:

.
У загальному випадку це завдання з розмірністю 2. Їх рішення зводиться до мінімізації так званої функції Лагранжа

.
3. Геометрична інтерпретація задачі нелінійного програмування При числі змінних не більше двох задачу НП можна вирішити геометричним способом.
Процес знаходження рішення задачі НП (1), (2) з використанням її геометричної інтерпретації включає наступні етапи:
Знаходять ОДР задачі, яка визначається співвідношенням (2); якщо вона порожня, то завдання не має рішення.
Будують гіперповерхні f (x 1, x 2,... x n) = h.
Визначають гіперповерхні найвищого (найнижчого) рівня або встановлюють нерозв'язність завдання через необмеженість функції (1) зверху (знизу) на безлічі припустимих рішень.
Знаходять точку ОДР, через яку проходить гіперповерхні найвищого (найнижчого) рівня, і визначають значення функції (1).
Приклад. Знайти max функції f = x
2 x
1 2 + 6x
1 (3)
При умовах
2х
1 + 3х
2 24
х
1 + 2х
2 15
3х
1 + 2х
2 24
х
2 4,
х
1, х
2 0.
Рішення: F нелінійна, отже, це завдання НП;
ОАВС - ОДР
Отже, потрібно визначити таку точку багатокутника ОАВС, в якій функція приймає max значення.
Побудуємо лінію рівня F = x 2 x 2 січня +6 x 1 = h,
де h - деяка постійна, і досліджуємо її поведінку при різних h. При кожному h одержуємо параболу, яка тим вище щодо ОХ, чим більше h.
Дійсно,
F = x
2 x
2 січень +6 x
1 = h = парабола x
2 = x
1 2 - 6x
1 - h або х
2 = (х
1 - 3)
2 + h-9.
Р

ассмотрім h = 9 х
2 = (х
1 - 3)
2 h = 11 х
2 = (х
1 - 3)
2 +
2 h = 13 х
2 = (х
1 - 3)
2 + 4
Функція F приймає максимальне значення в точці дотику однієї з парабол з кордоном багатокутника ОАВС. В даному випадку це точка Д, в якій лінія рівня F = x
2 x
2 січень +6 x
1 = 13 стосується сторони багатокутника ОАВС.
П

ри кожному h одержуємо параболу, яка тим вище отн. ОХ, чим більше h.
Дійсно,
F = x
2 x
2 січень +6 x
1 = h = парабола x
2 = x
1 2 - 6x
1 - h або х
2 = (х
1 - 3)
2 + h-9
Розглянемо h = 9 х
2 = (х
1 - 3)
2 h = 11 х
2 = (х
1 - 3)
2 +
2 h = 13 х
2 = (х
1 - 3)
2 + 4
Координати точки D знаходимо з рівнянь, відповідних перетвореним обмеженням (1) і (2):
x
2 x
2 січня +6 x
1 = 13, х
2 = 4, звідки х
1 * = 3; х
2 * = 4.
U
max, F
max = 13 при х * = (3, 4).
Таким чином в цьому завданні точка F
max не є вершиною трикутника рішень. Тому процедура перебору вершин, яка використана в задачах ЛП непридатна.
4. Метод множників Лагранжа Математична постановка. Розглянемо окремий випадок загальної задачі НП (1), (2), припускаючи, що система обмежень (2) містить тільки рівняння, відсутні умови невід'ємності змінних, і f (X
1, X
2... X
n) і q
i ( X
1, X
2,... X
n) - функції, неперервні разом зі своїми частинними похідними.
f (X 1, X 2... X n) max (min) q i (X 1, X 2,... X n) = b i (I = 1, m). Це так звана задача на умовний екстремум або класична задача оптимізації.
Щоб знайти рішення цієї задачі, вводять набір змінних
1,
2,...
n, званих множниками Лагранжа, складають функцію Лагранжа.
f (X 1, X 2... X n, 1, 2,... n) = f (X 1, X 2... X n) +
знаходять приватні похідні.

і розглядають систему n + m рівнянь.

з
n + m невідомими
Х 1, Х 2,... Х n, n, 1, 2,... m. Усяке рішення цієї системи рівнянь визначає точку
Х * = (Х 1 *, Х 2,... Х n), в якій може мати місце екстремум функції
f (x 1, x 2,... x n). Отже, вирішивши систему рівнянь, отримують всі крапки, в яких функція
f (x 1, x 2,... x n) може мати екстремальні значення.
Таким чином, визначення екстремальних точок задачі НП методом множників Лагранжа включають наступні етапи:
Складають функцію Лагранжа.
Знаходять приватні похідні від функції Лагранжа по змінним Х 1 і 1 і прирівнюють їх нулю.
Вирішуючи отриману систему рівнянь, знаходять точки, в яких цільова функція задачі може мати екстремум.
Серед точок, підозрілих на екстремум, знаходять такі, в яких досягається екстремум, а обчислюють значення цільової функції в цих точках.
Приклад: За планом виробництва підприємству необхідно виготовити 180 виробів. Ці вироби можуть бути виготовлені двома технологічними способами. При виробництві Х
1 виробів I способом приведена маса токсичних відмов дорівнює 4Х
1 + Х
1 2 кг, а при виготовленні Х
2 виробів II способом вони складають 8х
2 + х
2 2 кг.
Визначити, скільки виробів кожним із способів слід виготовити, щоб загальна маса відходів була мінімальною.
Рішення: Математична постановка задачі полягає у визначенні мінімального значення функції
f = 4x
1 + x
1 2 + 8x
2 + x
2 лютого при умовах х
1 + х
2 = 180, х
1, х
2 0.
Тепер вирішимо завдання, використовуючи метод множників Лагранжа. Знайдемо min цільової функції за умови х
1 + х
2 = 180, але без урахування вимог невід'ємних змінних.
Складемо функцію Лагранжа:
F (x
1, x
2, ) = 4x
1 + x
2 січня +8 x
2 + x
2 2 + (180-x
1 - x
2) 
Обчислюємо приватні похідні і прирівнюємо до нуля:
Переносячи в праві частини перших двох рівнянь і прирівнюючи їх ліві частини:
4 + 2х
1 = 8 +2 х
2 або х
1 - х
2 =
2 Вирішуючи це рівняння спільно з останнім:
х
1 - х
2 =
2 180-х
1-х 2 = 0, знаходимо: х
2 = х
1 -2
180-х
1 - х
1 +2 = 0 х
1 = 91; х
2 = 89.
Цей результат і був отриманий вище, однак ММЛ більш універсальний, тому що застосуємо при n 2.
5. Огляд розглянутих методів. Математичне програмування та дослідження операцій Розглянуті нами методи лінійного і нелінійного програмування (а також цілочисельне програмування, динамічне програмування) об'єднуються поняттям математичне програмування. Математичне програмування як і інші методи вирішення екстремальних задач складають основу апарату
дослідження операцій - дисципліни, яка є одним із витоків системного аналізу. Фактично, основні концепції, принципи аналізу систем є розвитком теорії дослідження операцій, і її методи є сьогодні однією з основних глав системного аналізу.
Сам термін «дослідження операцій» виник у повоєнні роки, коли стало ясно, що завдання широкого класу, що виникли в самих різних сферах людської діяльності, мають, незважаючи на їх якісне розходження, одне спільне - вони зводяться
до вибору способу дії, варіанти плану, параметрів конструкції тощо, тобто до прийняття рішень, і цього загального достатньо для побудови єдиної теорії і єдиної системи методів. Створення складних технічних систем, проектування складних народногосподарських комплексів, аналіз екологічних ситуацій і багато інших напрямків інженерної, наукової та господарської діяльності вимагали розвитку міждисциплінарних, системних досліджень. У цих умовах виник і дуже загальний термін -
«операція», що означає
будь цілеспрямована дія. Говорячи про операції, ми завжди пов'язуємо з нею деякого суб'єкта (що оперує сторону), який формулює мету операції і в інтересах якого остання проводиться. Мета операції - зазвичай деякий зовнішній (екзогенний) елемент - вважається заданою.
Поряд із суб'єктом, тобто з оперує стороною, ми завжди маємо справу ще й з
дослідником операції. Він діє в інтересах оперує боку, і його завдання полягає в тому, щоб знайти спосіб використання ресурсу (тобто можливостей оперує боку), що забезпечує досягнення мети.
Вище було сказано, що математичне програмування як і інші методи вирішення екстремальних задач складають основу апарату дослідження операцій, однак сама теорія дослідження операцій не може бути зведена до вирішення екстремальних задач. Більш того, дослідження операцій не є суто математичною дисципліною і головні складності аналізу конкретних операцій, як правило, полягають не в математичних труднощах.
Першим кроком дослідження операцій є формалізація операції, її опис за допомогою мови математики. Від того, як буде формалізована задача, залежатиме доля дослідження. Так простий опис робить і аналіз більш простим, але якщо модель не буде в достатній мірі адекватна реальності, то ми отримаємо сумнівну достовірність результатів. Навпаки, переусложненная завдання, враховує різноманітні деталі процесу і з великими подробицями описує реальність, може призвести до такої витраті машинного часу (великі системи), яку навіть висока точність результату не зможе виправдати.
Ще більш складні проблеми виникають при формуванні критерію - способу оцінки якості наших дій, коли необхідно порівнювати різні варіанти стратегій, різні альтернативи. Тут типова ситуація, коли операція оцінюється декількома показниками. У цьому випадку говорять про
невизначеність цілей. (М.М. Моїсєєв Математичні задачі системного аналізу. М.: Наука, 1981.)