Задача на распределение ресурсов.

← →
Сатир (2003-10-31 14:29) [0]

Задача на распределение ресурсов.
Имеется некий ресурс Х. Имеется N потребителей, каждый из которых хочет H ресурса. Как на пропорциональной основе (чтобы досталось всем хоть что-то) распределить этот ресурс?
Если нет приоритетов - то все просто, но как быть, если приоритеты есть?
(Пусть, к примеру, приоритеты задаются от 1 до 20)

← →
Карелин Артем (2003-10-31 14:33) [1]

Ну это. Квантовать время пользования ресурсом и пусть каждый владеет ресурсом определенное количество квантов, пропорционально приоритету.

← →
Mystic (2003-10-31 14:39) [2]

1) Задача оптимизации. Пусть $x_i$~--- количество ресурса, которое нужно дать поребителю $i$. Тогда сформировав некоторую функцию $F(\vec x)$, которая каждому возможномe вектору ставит оценку привлекательности, получаем условия задачи.

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

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

← →
Сатир (2003-10-31 14:40) [3]

> Квантовать время пользования ресурсом и пусть каждый владеет
> ресурсом определенное количество квантов, пропорционально
> приоритету.

распределить ресурс надо мгновенно

← →
Сатир (2003-10-31 14:45) [4]

> 1) Задача оптимизации. Пусть $x_i$~--- количество ресурса,
> которое нужно дать поребителю $i$. Тогда сформировав некоторую
> функцию $F(\vec x)$, которая каждому возможномe вектору
> ставит оценку привлекательности, получаем условия задачи.

а как ты себе представляешь эту ф-цию?

← →
Brahman (2003-10-31 14:47) [5]

Hsum = sum(H[i]*P[i]) P[i]=(0,1) - приоритет
R = X/Hsum
HL[i] = H[i]*R

А лучше, действительно, игровой подход.
См. знаменитого Нэша (кооперативные, бескоалиционные игры)

← →
Думкин (2003-10-31 14:51) [6]

А что тут может значить приоритет? Как его описать?
Если втупую, первое пришедшее, то так:
Есть 21 кг золота, у одного чела приоритет 1, у другого 20. Одному 1 кг, другому 20.

При таком подходе - задача решается, как и при равномерном распределении.

Без уточнения понятия приоритет - ...

← →
Brahman (2003-10-31 14:53) [7]

Приоритет - весовая функция, регламентирующая данному участнику
вероятность получения доли запрошенного ресурса

← →
Думкин (2003-10-31 14:55) [8]

> [7] Brahman © (31.10.03 14:53)
Ну если так, то как и сказано у нас.

← →
Brahman (2003-10-31 14:57) [9]

Ну а если у первого приоритет 1, а захотел 20 кг, а у второго 20, а захотел 1 кг - то, как ?

← →
Сатир (2003-10-31 15:21) [10]

> Hsum = sum(H[i]*P[i]) P[i]=(0,1) - приоритет
> R = X/Hsum
> HL[i] = H[i]*R

это всё фингя
Н = 100
P[0]=1 P[1]=2
P[0] хочет 100
Р[1] хочет 25
по Вашей формуле первому нужно отдать больше ста...

← →
Brahman (2003-10-31 15:31) [11]

Сатир © (31.10.03 15:21) [10]
Читать надо лучше и думать
См.Brahman © (31.10.03 14:47) [5]
Область определения P[i]=(0,1)

Для перехода к диапазону 0..1
Psum = sum(P[i])
P[i] = P[i]/Psum

← →
Сатир (2003-10-31 15:55) [12]

P[0]=1 P[1]=2
H[0]=100 H[1]=25

> Для перехода к диапазону 0..1
> Psum = sum(P[i])
> P[i] = P[i]/Psum

P[0]=1/3
P[1]=2/3
Hsum = sum(H[i]*P[i]) =100*1/3 + 25*2/3 ~=33+17=50

R = X/Hsum = 100/50 = 2

HL[i] = H[i]*R
HL[0] = H[0]*R = 100*2 =200
HL[1] = H[1]*R = 25*2 =50

?

← →
Dona (2003-10-31 16:19) [13]

А критерия полезности (целевой функции) нет, что ли? Как распределили, так и ладно?

Тогда всем по мин., а что останется - первому по приоритету :)

Если приоритет и есть коэфф-т полезности, тогда вроде ЗЛП получается вида
Сумма по i(Pi * Xi ) -> max
при ограничениях для каждого i Xi >= min,
Сумма Xi <= Кол-ву ресурса
Xi - кол-во ресурса, Pi - "вес", "полезность" каждого потребителя, решать можно симплекс-методом.
Если я, конечно, не напутала

← →
Dona (2003-10-31 16:35) [14]

Не совсем постановка понятна.
Если все же нет целевой функции, и оптимизировать нечего, а имееюся просто ранжированные потребители (N) и их потребности (X1..Xn), общее кол-во ресурса (K) и мин. потребность(Mn, Min*N<=K), тогда для начала раздать всем по Mn : Yi := mn (i=1..N), K := K - N*Mn,
затем в цикле по потребителям (считаем, что они упорядочены по убыв. важности), пока есть ресурс (К>0) распределяем ресурс
Yi := Yi + min(Xi - Mn, K)
K := K - min(Xi - Mn, K)
i := i+1

Задача на распределение ресурсов. Найти похожие ветки