Перелік питань для самоперевірки

1. Основні поняття теорії ігор. Гра двох гравців з нульовою сумою, правила гри, ціна гри, пара оптимальних стратегій для двох осіб. Платіжна матриця.

2. Основна теорема теорії ігор. Принцип мінімаксу. Розв’язання ігор у чистих та змішаних стратегіях. Геометрична інтерпретація гри 2х2 (2хn, nх2).

3. Зведення матричної гри до задачі лінійного програмування.

Змістовий модуль 4

Задачі нелінійного програмування.

Задачі динамічного програмування

Лекція 7

Тема 8. Нелінійне програмування

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

8.1. Задачі нелінійного програмування з лінійною цільовою

функцією та нелінійною системою обмежень

Обмежимося рішенням задачі з двома змінними. Як і в лінійному програмуванні, такі задачі можна розв’язати геометричним методом.

Задача 8.1. Знайти глобальні екстремуми функції при обмеженнях:

Рішення

Побудуємо множину точок, що задовольняють першому обмеженню . Межа цієї множини коло радіусу 4 з центром на початку координат. Область допустимих значень – частина круга, яка розташована в першій чверті (рис. 8.1).

Лініями рівня цільової функції є паралельні прямі з кутовим коефіцієнтом . Глобальний мінімум досягається в точці (0;0),, глобальний максимум – у точці, точці дотику лінії рівня і круг. Знайдемо координати точки. Для цього складемо систему, яка містить рівняння прямоїі рівняння кола. Прямаперпендикулярна лінії рівня, тому її кутовий коефіцієнт. Оскільки прямапроходить через початок координат, то її рівняння. Розв’язуючи систему

одержимо та,.

Таким чином, глобальний мінімум досягається в точці (0;0), , глобальний максимум – у точці,.

Рис. 8.1

8.2. Задачі нелінійного програмування з нелінійною цільовою функцією та лінійною системою обмежень

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

Задача 8.2. Знайти глобальні екстремуми функції за таких обмежень:

Рішення

Чотирикутник є областю допустимих рішень (рис. 8.2). Лінії рівня є колами з центром в точці А(2;3) та радіусом . З рис. 8.2 видно, що і досягається в точці А, а досягається в точці . Координати точки є координатами точки перетину прямої з віссю , тобто і .

Перелік питань для самоперевірки

1. Постановка задачі нелінійного програмування, математична модель.

2. Графічний метод розв’язування задач нелінійного програмування.

Лекція 8

Тема 9. Динамічне програмування

Динамічне програмування (ДП) – метод оптимізації, пристосований до операцій, у яких процес прийняття рішення може бути розподілений на етапи (кроки).

Загальна постановка задачі ДП. Розглядається процес управління деякою системою S. Це може бути, наприклад, економічний процес розподілу коштів між підприємствами, використання ресурсів протягом ряду років, заміни облад-нання і таке інше. У результаті управління X система (об’єкт управління) S переводиться з початкового стану в кінцевий стан. Припустимо, що управлінняX можна розбити на n кроків, тобто рішення приймається послідовно на кожному кроці, і являє собою сукупність n покрокових управлінь . Позначаючи черезстан системи післяk-го кроку управління, одержуємо послідовність станів (рис. 9.1).

Рис. 9.1

Метод динамічного програмування передбачає, що стан системи наприкінціk-го кроку залежить тільки від попереднього стану і управління на k-му кроці (відсутність післядії), тобто

, k=1, 2,…, n. (9.1)

Рівняння (9.1) називають рівняннями станів.

Показник ефективності управління Z – цільова функція задачі – є адитивним, тобто складається з показників ефективності кожного кроку. Позначимо показник ефективності k-го кроку через

, k=1, 2,…, n,

тоді

. (9.2)

Задача покрокової оптимізації ДП: визначити таке допустиме управління X, що переводить систему S зі стану в стан, при якому цільова функція(9.2) набуває найбільшого (найменшого) значення.

Метод розв’язання задачі ДП базується на принципі оптимальності (Беллмана): Яким би не був стан s системи в результаті якого-небудь числа кроків, на найближчому кроці потрібно вибирати управління так, щоб воно в сукупності з оптимальним управлінням на всіх наступних кроках приводило до оптимального виграшу на всіх кроках, що залишилися, включаючи даний.

Формальним виразом цього принципу є рівняння Беллмана. У задачі максимізації цільової функції вони мають вид:

, , k=n–1, n–2, …, 2, 1.

(9.3)

Величина називаєтьсяумовним максимумом цільової функції, що одержується при оптимальному управлінні на n–k+1 кроках, починаючи з k-го до кінця, за умови, що напередодні k-го кроку система перебувала в стані . Управління наk-му кроці, при якому досягається , позначається черезі називаєтьсяумовним оптимальним управлінням на k-му кроці, k=n, n–1, …, 1.

Схема застосування методу ДП

1. Вибирають спосіб розподілу процесу управління на кроки.

2. Визначають параметри стану і змінні управлінняна кожному кроці.

3. Записують рівняння станів.

4. Вводять цільові функції k-го кроку і сумарну цільову функцію.

5. Вводять у розгляд умовні максимуми (мінімуми) і умовне оптимальне управління наk-му кроці: ,k=n, n–1, …, 1.

6. Записують рівняння Беллмана для і,k=n–1, …, 1.

7. Розв’язують послідовно рівняння Беллмана (умовна оптимізація) і одержують дві послідовності функцій: {} і {}.

8. Знаходять оптимальне рішення для конкретного початкового стану :

а) ;

б) .

(Стрілка означає використання рівнянь стану, а стрілка– послідовності умовних оптимальних управлінь через розв’язок рівнянь Беллмана);

в) оптимальне управління: .