Чи забезпечує принцип оптимальності незалежність наступних розв’язків від здобутих раніше?

Чи забезпечує принцип оптимальності незалежність наступних розв’язків від здобутих раніше?

 

Будь-яку багатокрокову задачу можна розв’язувати по-різ­ному:

- або знаходити одразу всі елементи розв’язку на всіх кроках, -

-або будувати оптимальне управління поступово, крок за кроком – Тобто на кожному етапі розрахунків оптимізуючи лише один крок.

 

Як правило, другий спосіб оптимізації є значно прості­шим, ніж перший.

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

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

Отже можна сказати, що для прийняття оптимального рішення на k -му кроці багатокрокового процесу потрібна оптимальність рішень на всіх його попередніх кроках, а сукупність усіх рішень дає оптимальний розв’язок задачі лише в тому разі, коли на кожному кроці приймається оптимальне рішення, що залежить від параметра етапу , визначеного на попередньому кроці.

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

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

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

Як вибрати розв’язуваний елемент?

Перетином напрямного стовпчика та напрямного рядка визначається елемент симплексної таблиці a_lk, який називають розв’язувальним елементом. За допомогою елемента a_lk і методу Жордана—Гаусса розраховують нову симплексну таблицю, що визначатиме наступний опорний план задачі.

 

Суть методу Жордана-Гаусса.

Симплекс-метод — це ітераційна обчислювальна процедура, яка дає змогу, починаючи з певного опорного плану, за скінченну кількість кроків отримати оптимальний план задачі лінійного програмування. Визначення нових опорних планів полягає у виборі вектора, який слід ввести в базис, і вектора, який необхідно вивести з базису. Така процедура відповідає переходу від одного базису до іншого за допомогою методу Жордана—Гаусса - будь-який вектор, що не входить у базис, розкласти за базисними векторами, а потім визначити таке , для якого один з векторів виключається з базису.

Як обчислюють потенціали?.

Транспортна задача є задачею лінійного програмування, яку можна розв’язати симплекс-методом. Але специфічна структура транспортної задачі дає змогу використовувати для її розв’я­зування ефективніший метод, який повторює, по суті, кроки симплекс-алгоритму. Таким є метод потенціалів.

Алгоритм методу потенціалів складається з таких етапів.

1. Визначення типу транспортної задачі (відкрита чи закрита).

2. Побудова першого опорного плану транспортної задачі.

3. Перевірка плану транспортної задачі на оптимальність.

4. Якщо умова оптимальності виконується, то маємо оптимальний розв’язок транспортної задачі. Якщо ж умова оптимальності не виконується, необхідно перейти до наступного опорного плану.

5. Новий план знову перевіряють на оптимальність, тобто повторюють дії п. 3, і т. д. Розглянемо докладно кожний етап цього алгоритму.

 

Чи забезпечує принцип оптимальності незалежність наступних розв’язків від здобутих раніше?

 

Будь-яку багатокрокову задачу можна розв’язувати по-різ­ному:

- або знаходити одразу всі елементи розв’язку на всіх кроках, -

-або будувати оптимальне управління поступово, крок за кроком – Тобто на кожному етапі розрахунків оптимізуючи лише один крок.

 

Як правило, другий спосіб оптимізації є значно прості­шим, ніж перший.

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

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

Отже можна сказати, що для прийняття оптимального рішення на k -му кроці багатокрокового процесу потрібна оптимальність рішень на всіх його попередніх кроках, а сукупність усіх рішень дає оптимальний розв’язок задачі лише в тому разі, коли на кожному кроці приймається оптимальне рішення, що залежить від параметра етапу , визначеного на попередньому кроці.

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