Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 36

Случай идентичных потребителей: j_i(x)=j(x). Докажите, что а) если j(x) выпукла по x, то весь ресурс можно отдать одному потребителю, б) если вогнута, то его надо делить поровну между всеми потребителями.

№31. Задача о рюкзаке.

Пусть есть рюкзак объема V ³ 0 и n камней с объемами v_i и ценами c_i. С каждым камнем свяжем переменную x_i, принимающую значение 1 (если камень берется) или 0 (в противном случае). Требуется найти подмножество камней с максимальной суммарной стоимостью S_i c_i×x_i, влезающее в рюкзак (т.е. S_i v_i×x_i,  £ V).

ПустьF_k(y) - максимальная стоимость камней с номерами от k до n, влезающих в рюкзак объема y.       Т.к. любая часть оптимального решения оптимальна, то

F_n(y) = c_n (если v_n £ y)или 0 (в противном случае)         ЕслиV и v_i – целые, то метод

F_k(y) = max { F_k+1(y), c_k + F_k+1(y-v_k) если y³v_k}          динамического программирования:

x_k(y) = min { x_k £ y | c_k×x_k + F_k+1(y-v_k×x_k) = F_k(y) }.     меняя k от n-1 до 1, найдемF₁(V), Трудоемкость - O(n×V).                            x₁(y₁=V), x_k+1(y_k+1= y_k -v_k×x_k(y_k)).

Пример:

5x₁+6x₂ + 8x₃+10x₄® max

x₁+2x₂ + 3x₃+  4x₄£ 5

F₂(4) =max{ F₃(4),6+ F₃(4-2=2)}

= max{10,6+0} = 10,    x₂(4)=0.

F₁(5) =max{ F₂(5),10+ F₂(5-1)}

= max{14,5+10} = 15,  x₁(5)=1.

x₁ =x₁(5)=1,      x₂ =x₂(5-v₁×x₁ =4)=0,    x₃ =x₃(4-v₂×x₂ =4)=0,    x₄=x₄(4-v₃×x₃ =4)=1.