рассчитать максимальную прибыль

[Spook]

Допустим, я могу получать доход в диапазоне $1\leqslant ...\leqslant{A}$ c каждого из $k$ тарифов, а всего имеется $N$ фиксированных источников дохода. Как можно рассчитать максимально возможную прибыль?

[Лиля]

оптимизация? -однако не совсем ясно условие...

[Spook]

Вот, напрмер, есть 9 источников с доходами равными соответственно: 9 1 5 5 5 5 4 8 80. А я могу получать деньги только по 4 тарифам. В таком случае, мне лучше организовать все так:

1 тариф: источник с доходом 4
2 тариф: источники с доходом 5
3 тариф: источники с доходом 8 и 9 (доход будет по 8)
4 тариф: источник с доходом 80

То есть получилось так, что в данной ситуации выгоднее вообще не рассматривать источник с доходом 1.

[ИСН]

Пахнет полным перебором.

[Лиля]

если имеется ввиду то что во 2м посту сказано то просто бери $k$ тарифов с самым большим доходом в порядке убывания случае со 2м постом это будет $80, 9, 8, 5$ странное задание или я не правильно его поняла...

[Spook]

ИСН, скорее всего. Я вот пока ничего не придумал кроме перебора
Лиля, тут нужно выбрать 4 тарифа, например, двое могут платить 8 и 9 соответственно, но я буду брать с обоих по 8. То есть тарифов может быть меньше, чем источников дохода.

[Лиля]

решайте перебором

[Spook]

Лиля писал(а):

имеете ввиду разбить на 4 множества так что прибыль была б максимальной?

В общем-то - да. Но дело в том, что иногда нужно именно выделить эти четыре множества (в каждом одинаковый доход), то есть отказаться от некоторых клиентов как бы, а с некоторых брать меньше, чем они могут платить.

[Лукомор]

Spook писал(а):

Допустим, я могу получать доход в диапазоне $1\leqslant ...\leqslant{A}$ c каждого из $k$ тарифов, а всего имеется $N$ фиксированных источников дохода. Как можно рассчитать максимально возможную прибыль?

1. Считаем прибыль для $k=1$ для каждого источника $N$.
2. Выкидываем лишние источники, начиная с наименьшего получившегося значения прибыли.
3. Оставшиеся $k$ чисел и будут требуемыми величинами тарифов.
.
Для вашего числового примера:
$1\cdot 9=9$
$4\cdot 8=32$
$5\cdot 7=35$
$8\cdot 3=24$
$9\cdot 2=18$
$80\cdot 1=80$
Соответственно, выбрасываем $1$ и $9$...

[Spook]

Лукомор, хм.. интересно. Я еще потестирую Ваш метод. Еще тут можно попробовать использовать динамическое программирование.

[Spook]

Лукомор, Ваш метод оказался неверным . Например, для 10 человек способных платить соответственно :
49 393 405 627 744 818 822 823 927 949 и количества тарифных планов равного 5, наиболее выгодны следующие тарифы:
393 627 744 818 927. По-Вашему же получается, что лучшая система тарифов такая: 393 627 744 818 822.
Видимо, так и придется использовать метод динамического программирования.

[gris]

Схема динамического программирования здесь проста, если принять два разумных правила, что каждый тариф равняется величине дохода какого-нибудь источника и что каждый источник облагается максимальным допустимым для него тарифом. Тогда источники с одинаковам доходом будут облагаться одинаковым тарифом. Если, конечно, нет других ограничений.
Количество ветвлений будет большим. Для некоторых N и k будет пожалуй почище полного перебора. Это для простейшей схемы, когда мы предполагаем, что $k-1$ тариф уже установлен и подбираем наивыгоднейший последний. Ну и двигаемся назад.

[Spook]

Вот сейчас и думаю, как учесть расчет для (k-1) тарифов. Я посчитал, какая максимальная прибыль будет для одного тарифа для i первых (упорядоченных по неубыванию) плательщиков. Теперь хочу перейти во второй столбец таблицы (то есть уже будет два тарифа).

[mserg]

Пусть $ v $ – вектор длины $n$ посильных тарифов, где $ v_{j} \le v_{j+1}$, $ c $ – вектор их частот. Например, для исходной задачи $ v= <1,4,5,8,9,80> $, $ c = <1,1,4,1,1,1> $, $n=6$. Обозначим через $y_i$ – псевдобулевы переменные, принимающие значение 1 только если имеет место порог тарифа, соответствующее значению $v_i$; через $x_i_j$ – обозначим псевдобулевы переменные, принимающие значение 1 только в том случае, если $j$-ый плательщик получит тариф $v_i$.

1. Очевидно, что $x_i_j=0$ если тариф не по карману ($j<i$)

2. Для одного плательщика используется не более одного тарифа:
$\sum\limits_{i=1}^j} x_i_j \le 1$ (для $1 \le j \le n$)

3. Количество тарифов не более 4-х:
$\sum\limits_{i=1}^n y_i \le 4 $

4. Плательщик может использовать только выбранные тарифы:
$ x_i_j \le y_i$ (для $1 \le i \le j \le n$)

5. Требуется максимизировать выручку:
$\sum\limits_{i=1}^n \sum\limits_{j=i}^n v_i \ldot c_j \ldot x_i_j $

Это классическая задача псевдобулева программирования. Может быть решена методом неявного перебора или целочисленным линейным программированием.

[Лукомор]

Spook писал(а):

Лукомор, Ваш метод оказался неверным . Например, для 10 человек способных платить соответственно :
49 393 405 627 744 818 822 823 927 949 и количества тарифных планов равного 5, наиболее выгодны следующие тарифы:
393 627 744 818 927. По-Вашему же получается, что лучшая система тарифов такая: 393 627 744 818 822.
Видимо, так и придется использовать метод динамического программирования.

Согласен, поторопился я!
Но для экспресс-анализа "на - коленке" мой метод не так уж плох....