Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 42

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 36 37 38 39 40 41 < 42 > 43 44 45 46 47 48 .. 84 >> Следующая


F(x !,X2,...,Xn) = 4EiMxi) —>• max, (4.1.1)
Гл. 4• Применение метода динамического программирования 121

y^Xi = A, Л целое, (4.1.2)

г=1

Xi > 0 целые, Xi Є di, і = 1,2,...,п. (4.1.3)

Ясно, что при фиксированных функциях /? (хі) результат определяет-

ся лишь значением параметра А.

Пусть п

Gn(A) =TnaxYfi(Xi)- (4-1.4)

1=1

Для вычисления Gn (А) выполним следующие шаги:

Flj2 (-4) = max [/і (х) + /2 (А- х)\,

xEdi

F1,2,3 (-4) = max [Fij2 (х) + f3 (А- ж)],

x?d2

F1,2,3,...,І (-4) = max [Flj2,...,а-и (х) + fi(A- ж)] ,

xEdi — i

Gn(A) = max [Flt2^,, tn_u(x) + fn(A - x)] .

XEdri — і

В этих соотношениях Fl,2,3,...,г (x) — максимальное значение этой функции для заданного значения ресурса ж, вложенного в проекты

1,2,...,?.

Полученные соотношения перепишем в следующем виде. Пусть Gk {%) — суммарный доход на шаге к при использовании ресурса х. Тогда получаем

G1 (х) = /і (ж),

G1 (Л) = h (А),

G2 (A) = max [G1 (х) + /2 (А- ж)],

xEd і

G3 (^4) = max [G2 (х) + /3 (А- ж)], (4.1.5)

x?d2

Gk+1 (-4) = max [Gfc (х) + fk+1 (-4 - ж)],

xEdk

Gn (-4) = шах [Gn_i (х) H- /п (А х)\.

XEdn-1

Соотношения вида (4.1.5), к = 0,1,..., (гг — 1), называются уравнениями Беллмана. Эти рекуррентные соотношения позволяют вычислить Gk(A) для любого значения А и всех к = I, 2,..., (п — 1), т.е. найти глобальный экстремум в задаче оптимизации (4.1.1)-(4.1.3). Задача (4.1.1)-(4.1.3) рассматривалась на дискретном множестве точек.

Если Xi Є di = [a,i,bi\, то, задав шаг hi = а\ перейдем к задали*

нию каждой из функций fi (х) на дискретном множестве точек. При
122

Разд. II. Комбинаторные методы решения задач

достаточно малом шаге hi соотношения типа (4.1.5) позволяют найти глобальный экстремум задачи.

4.1.3. Принцип оптимальности. Соотношения (4.1.5) являются формальным описанием некоторого утверждения, получившего название принципа оптимальности Беллмана. Сформулируем этот принцип применительно к рассмотренной задаче.

Пусть вектор Xk(Y) = (Xi(Y)j ж2(Y)j ..., Xk(Y)) максимизирует функцию Gk (Y) в следующей задаче:

Gk (Y) = max J2 fi (xi)

X1 +х2 + ... + Xk=Y, (4Л-б)

Xi Є di, і = 1,2,..., &, 0 < Y < А.

Тогда значение переменной Xk+i (Y), определяемое из уравнения Gk+i(Y) = max[Gfc(ж) + fk+i(Y -х)\, Y - х > О,

xEdk

является таковым, что вектор

Xk+1(Y) = (X1(Y), X2(Y), ...,xk(Y), xk+1(Y)) является решением задачи

Gk+1 (Y) = max J2 fi (хі),

v»1 v (4-1-7)

E Xi = у,

і= I

Xi Є di, і = I, 2,..., (к H-1), 0<У < А.

Переход от соотношений (4.1.6) к соотношениям (4.1.7) позволяет найти Xk+i (Ir) для любого Y при уже известных значениях Xi(Y)jX2(Y)j ...jXk(Y).

4.2. Задача о ранце

4.2.1. Принцип оптимальности Беллмана. Рассмотрим задачу в следующем виде:

/ (X1, X2,..., хп) = YcJxJ тах’

J=I

Tl

Yl ajXj ^ ^5

J = I

хз Є {0;1}, J = 1,2,... ,гг, ^4'2'1)

Cj > Oj 0 < aj < Rj j = 1, 2,..., п.

Предполагается, что все параметры Rj Cj и aj принимают целочисленные значения.
Гл. 4• Применение метода динамического программирования 123

Пусть о < у < R — целочисленная переменная. Рассмотрим оптимальное решение задачи (4.2.1) в зависимости от переменной у:

п

9п (у) = E сзхз ->¦ тах>

J = I

А / (4.2.2)

zZ ajxj — Уі

J=і

^J Є {0; 1I, J = I, 2,..., n, 0 < у < R.

Пусть для каждого значения у уже определены значения переменных xi(y),x2(y),... ,Xk-i (у), т.е. решена следующая задача:

к-1 Як-і (у) = E сзхз тах>

*-i' (4.2.3)

L азхз < У, j=i

^J Є {0; 1I, j = 1,2,...,(?- I), 0 <y<R.

Тогда значение переменной Xk (у) определяется из условия

Qk (у) = max (CkXk + gk-1 (у ~ акХк)), (4.2.4)

Хк Є{0;1}

при этом у — CtkXk > 0, А: = 1,2,..., п.

Отметим, что:

9о(у) — 0 Для всех 0 < у < R, дк{0) = 0 для всех 1 < к < п.

Рекуррентное соотношение (4.2.4) называется уравнением Веллмана для задачи о ранце. Это уравнение позволяет свести задачу максимизации функции f (х 1,^2,..., жп) от п булевых переменных к п-

шаговой процедуре, на шаге с номером к которой максимизируется

функция ОДНОЙ переменной Хк, 1 < к < п.

Рекуррентные соотношения вида (4.2.4) систематически применяются для решения оптимизационных задач с сепарабельной (аддитивной) целевой функцией. Эти соотношения являются формальным описанием некоторого утверждения, получившего название принципа оптимальности Веллмана.

Принцип оптимальности Беллмана. Пусть вектор Xk-i(y) = (xi(y), Х2(у),Xk-i(y)) максимизирует целевую функцию в задаче (4.2.3). Тогда значение Xk (у) переменной ж*., определяемое из уравнения (4.2.4), таково, что вектор Xk(у) = (х\ (у), Х2(у),... ,Xk(y)) максимизирует целевую функцию в задаче

к

9к (У) = E сзхз тах>

J=I

к

E азхз < у> ж^е{0;1}, j = 1,2, ...,к, 0 < у < R.
124

Разд. II. Комбинаторные методы решения задач

Из соотношения (4.2.4) следует, что gn (R) = /(х°),

X0 — оптимальное решение исходной задачи. Отметим, что соотношение (4.2.4) позволяет получить оптимальное решение для любого целочисленного значения у, 0 < у < R. Если х° (у) — оптимальное решение исходной задачи для значения у, то / (X0 (у)) = дп (у).
Предыдущая << 1 .. 36 37 38 39 40 41 < 42 > 43 44 45 46 47 48 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100