Адитивність цільової функції і етапи задачі

Контрольні завдання

Розв’язати задачу про використання робочої сили. Вихідні дані наведені в табл. 8.

Таблиця 8

Варі-ант	Склад-ність							Витрати
по найму	на звільн.	на оплату прос-тоїв	на оп-лату понад-норм.
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	A
	B
	B
	B
	B
	B
	B
	B
	B

6 ОСНОВНІ ЕЛЕМЕНТИ і ПРИНЦИПИ ДИНАМІЧНОГО ПРОГРАМУВАННЯ

Розглянуті задачі ЗЗНШ, ЗОВР (ЗОВК) і ЗВРС мають особливості, характерні для всіх багатокрокових процесів прийняття рішень, тому поняття і принципи ДП будемо ілюструвати на прикладах цих задач. При цьому відзначимо, що будь-яка задача ДП може бути зведена до задачі знаходження найкоротшого шляху в мережі. Тому, якщо будемо говорити про мережу і її вершини то, це може відноситись і до будь-якої задачі ДП.

У задачах ДП цільова функція (ЦФ) повинна мати властивість адитивності: значення критерію, досягнуте за весь період планування дорівнює сумі часткових значень того ж критерію, досягнутих на окремих кроках (етапах):

де - це або скалярна величина, або вектор.

Саме адитивність ЦФ задачі дозволяє розбити задачу на етапи. При цьому з кожним з етапів зв'язується тільки одна керована змінна () і кожному етапу відповідає одна складова ЦФ:

ü ЗЗНШ: - довжина -го кроку, - дуга, по якій перейшли з -го слою до -го слою (наприклад дуга , тоді складова ЦФ: = );

ü ЗОВР: - прибуток від виробництва -го продукту в об'ємі ;

ü ЗОВК: - прибуток від модернізації -го підприємства за проектом .

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

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