Лекції - Теорія систем і системний аналіз
Тема 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 стор.)
Оригінал
- Шпаргалка - Теорія систем і системний аналіз. Контрольна робота
- Курсова робота - Системний аналіз підприємства Lex
- Лекції - Теорія систем і системний аналіз
Тема 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.)