Лекції - Теорія систем і системний аналіз

Тема 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. Постановка задачі НП

  2. Еколого-економічна інтерпретація задачі НП

  3. Геометрична інтерпретація задачі НП

  4. Метод множників Лагранжа (ММЛ)

  5. Огляд розглянутих методів.


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.

Ефект по кожному підрозділу: З 11), С 22), С 33).

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) з використанням її геометричної інтерпретації включає наступні етапи:

  1. Знаходять ОДР задачі, яка визначається співвідношенням (2); якщо вона порожня, то завдання не має рішення.

  2. Будують гіперповерхні f (x 1, x 2,... x n) = h.

  3. Визначають гіперповерхні найвищого (найнижчого) рівня або встановлюють нерозв'язність завдання через необмеженість функції (1) зверху (знизу) на безлічі припустимих рішень.

  4. Знаходять точку ОДР, через яку проходить гіперповерхні найвищого (найнижчого) рівня, і визначають значення функції (1).


Приклад.

Знайти max функції f = x 2  x 1 2 + 6x 1 (3)

При умовах

1 + 3х 2  24

х 1 + 2х 2  15

1 + 2х 2  24

х 2  4,

х 1, х 2  0.

Рішення: F нелінійна, отже, це завдання НП;

  1. ОАВС - ОДР

Отже, потрібно визначити таку точку багатокутника ОАВС, в якій функція приймає max значення.

  1. Побудуємо лінію рівня 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. Складають функцію Лагранжа.

  2. Знаходять приватні похідні від функції Лагранжа по змінним Х 1 і  1 і прирівнюють їх нулю.

  3. Вирішуючи отриману систему рівнянь, знаходять точки, в яких цільова функція задачі може мати екстремум.

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


Приклад:

За планом виробництва підприємству необхідно виготовити 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, але без урахування вимог невід'ємних змінних.


  1. Складемо функцію Лагранжа:


F (x 1, x 2, ) = 4x 1 + x 2 січня +8 x 2 + x 2 2 +  (180-x 1 - x 2)



  1. Обчислюємо приватні похідні і прирівнюємо до нуля:



Переносячи в праві частини перших двох рівнянь  і прирівнюючи їх ліві частини:

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.)
Навчальний матеріал
© uadoc.zavantag.com
При копіюванні вкажіть посилання.
звернутися до адміністрації