Алгоритм ПП розв’язку задачі

Теоретичне обґрунтування алгоритму зворотньої прогонки для розв’язку задачі про найм робочої сили

Оскільки маємо задачу з фіксованим початком, то рекомендується застосовувати алгоритм зворотньої прогонки.

Нехай - мінімальні витрати за періоди від -го до -го включно, при кількості робітників на початок -го періоду (в () - му періоді) людей (рис. 20). І нехай в -му періоді підприємець вирішує мати в штаті робітників.

Рис. 20

Тоді вартість поточного кроку складе:

а величина

(7)

є мінімальними витратами за періоди від -го до -го включно, за умови, що на початок -го періоду було людей, а в -му періоді задіяно робітників. Вираз (7) – умовно мінімальні витрати для стану при кількості робітників в -му періоді.

Мінімізуємо (7) по всіх можливих значеннях , отримаємо:

(8)

Вираз (8) справедливий, якщо прийняти, що

Визначимо основні елементи моделі динамічного програмування.

Ø Етап відповідає -му періоду.

Ø Кожному етапу ставиться у відповідність своя керована змінна .

Ø На кожному етапі (крім етапу ) можливі стани (значення числа робітників ): ÷ .

Ø У кожному стані можливі розв’язки – найм/звільнення якоїсь кількості робітників або збереження їхньої чисельності. При цьому обраний розв’язок однозначно визначає значення керованої змінної – число робітників поточного періоду.

Ø Для кожного стану кожного етапу знаходимо

Ø Наша мета – знайти .

Отже, алгоритм розв’язання задачі такий:

1. Покласти ; .

2. Планування кроку .

2.1 Виділити всі можливі стани , які можуть мати місце на початку кроку (кількість робітників на початку кроку ):

: [ ; ]

: = .

2.2 Для кожного можливого стану (кількість робітників на початку кроку ) визначити можливі розв’язки на цьому етапі:

[ ; ]

2.3. Для кожного значення знаходимо мінімальне значення витрат на кроках від -го до -го включно

,

запам'ятати, при якому був досягнутий мінімум.

3. . Якщо l, то повернутися до п. 2.Інакше – перейти до п.4.

4. Формування оптимального розв’язку.

!	Можливі значення (число робітників на поточному кроці) починаючи від збільшуючи із кроком 1, досить перебирати доти, поки не “спіймаємо” мінімум виразу .

Дата добавления: 2014-11-29