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

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

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

 

 

Рис. 20

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

а величина

(7)

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

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

(8)

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