Текущий вес рюкзака определяется выражением

(5)

Текущий вес рюкзака в силу (2) удовлетворяет неравенству

£ B. (6)

Очевидно ограничения (4) – (6) эквивалентны ограничению (2), поэтому вместо модели (1) – (3) можно рассматривать модель (1), (3) – (6). Здесь ограничение (6) выводит эту модель за рамки модели (4) – (7) из предыдущей лекции. Для сведения задачи к общему виду задач динамич. программирования, запишем (6) с учетом (5):

.

Отсюда следует: ,

или окончательно с учетом (3):

(7)

В результате исходная модель (1) – (3) свелась к эквивалентной модели вида

(8)

(9)

(10)

(11)

Задача (8)-(11) является частным случаем общей задачи динамического программирования, в которой . Здесь ограничение (9) является рекуррентным и отражает процесс загрузки рюкзака, а неравенство (10) задает область возможных значений .

Рассмотрим решение задачи (8)-(11) методом динамического программирования:

1 шаг. Вычисляется величина

(12).

В результате решения серии задач максимизации получаем точки максимума и значения .

S-тый шаг (). Вычисляются величины

(13)

В результате решения серии задач максимизации, получаем и . При s=1 решается только одна задача на максимум, т.к. значение - задано.

Для определения безусловных точек максимума, т.е. решения исходной задачи, проводим обратное движение алгоритма:

.

Отсюда:

.

Далее: . И так далее . Причем есть максимальное значение целевой функции.

Наличие условия целочисленности переменных x_j и упрощает решение задачи. В этом случае . Здесь [] указывает на то, что берется целая часть числа. Если не целые, то .

Пример:

Постановка задачи:

Имеется свободный капитал в размере 4 млн. у.е. Этот капитал может быть распределен между 4-мя предприятиями, причем распределение осуществляется только целыми частями (0, 1, 2, 3 или 4 млн. у.е.). Прибыль, получаемая каждым предприятием при инвестировании в него определенной суммы, указана в таблице.

Предпр. ^Капитал	0 млн. у.е.	1 млн. у.е.	2 млн. у.е.	3 млн. у.е.	4 млн. у.е.
1-е предпр.
2-е предпр.
3-е предпр.
4-е предпр.

Требуется распределить инвестиции между предприятиями из условия максимальной общей прибыли.

Построение ММ.

Обозначим: х_j - количество капиталовложений, выделенных j -тому предприятию (). Тогда прибыль, записанная в таблице, можно обозначить как F_j(x_j) (). Например, F₁(0)=0; F₁(1)=10; F₁(2)=17 и т.д..... F₂(0)=0; F₂(1)=11; F₄(4)=35.

Тогда математическая модель примет вид:

х_j≥ 0 – целые, ()

Данная модель является частным случаем задачи о загрузке рюкзака, где N=4, В=4, а_j =1 (). Введя новую переменную y_j - израсходованные средства до выделения капиталовложений j -тому предприятию, приведем исходную модель к виду ЗДП:

; ()

y₁= 0;

; ()

Решение задачи проведем в соответствии с алгоритмом динамического программирования:

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