Максимизируйте полезность, учитывая произвольное количество товаров и условие, что необходимо купить ровно Х количество товаров

Как можно максимизировать полезность, учитывая некоторые бюджетные ограничения, произвольное количество разных товаров (с разной полезностью и ценами) и добавленное условие, что должно быть куплено ровно Х количество товаров?

Я думаю, это должно быть сделано алгоритмически, но я понятия не имею, как.

utility Деннис
источник

Похоже, очень типичная проблема максимизации ограничений. В общем, вы можете использовать метод Лагранжа и получить условия Куна-Такера. Однако, если вы хотите получить более конкретный ответ, вам нужно отредактировать свой вопрос, чтобы сделать его более конкретным: расскажите, как выглядит функция полезности, каковы ограничения и т. Д.

герр К.

@HerrK. Я думаю, что это похоже на дискретную проблему оптимизации, но, откровенно говоря, недостаточно подробностей.

Жискар

Под «Х количеством товаров» вы подразумеваете «Х количество разных товаров»?

Алекос Пападопулос

@AlecosPapadopoulos Нет, будет произвольное количество товаров на выбор, но нужно купить X единиц товара. Допустим, есть 2 товара, и нам абсолютно необходимо купить 3 товара с некоторыми бюджетными ограничениями. В этом примере мы могли бы максимизировать утилиту, покупая 1 единицу товара A и 2 единицы товара B, учитывая наше бюджетное ограничение. Но как определить, какая комбинация максимизирует нашу полезность, учитывая произвольное количество товаров и X количество предметов?

Деннис

@denesp Какие детали вам понадобятся?

Деннис

Ответы:

Задача максимизации полезности:

\begin{array}{rcl} max_{x_{1}, x_{2}, \dots, x_{n}} & u (x_{1}, x_{2}, \dots, x_{n}) \\ s.t. & \sum_{i = 1}^{n} p_{i} x_{i} \leq M \\ \sum_{i = 1}^{n} x_{i} = X \\ x_{i} \in Z_{+} \forall i \in {1, 2, \dots, n} \end{array}

$\begin{eqnarray*} \max_{x_1, x_2, \ldots, x_n} && u(x_1, x_2, \ldots, x_n) \\ \text{s.t.} && \sum_{i=1}^n p_ix_i \leq M \\ && \sum_{i=1}^n x_i = X \\ && x_i\in\mathbb{Z}_+ \ \ \forall i\in\{1,2,\ldots, n\} \end{eqnarray*}$

Если мы проигнорируем ограничение бюджета, уравнение имеет решения. Перечислите их, отсортируйте их от высокого к низкому по полезности, а затем определите самый высокий в отсортированном списке, который также удовлетворяет бюджетному ограничению. $\sum\limits_{i=1}^n x_i = X$ ${X+n-1\choose n-1}$

Если строго возрастает, дифференцируемые и квазивогнута на , то можно решить проблему максимизации полезности обычным способом, игнорируя ограничение Затем просмотрите интегральные решения которые окружают решение задачи максимизации полезности, и выберите лучшее из них, чтобы получить окончательное решение. $u$ $\mathbb{R}_+^n$ $\sum_{i=1}^n x_i = X$ $\sum_{i=1}^n x_i = X$

Amit
источник

Ваша проблема

max U (z_{1}, . . ., z_{n})

$\max U(z_1,...,z_n)$

s . t . \sum p_{i} z_{i} \leq I

$s.t. \sum p_iz_i \leq I$

а также

s . t . \sum z_{i} = X, z_{i} \in N

$s.t. \sum z_i = X, \;\;\; z_i\in N$

Таким образом, у вас есть дополнительное линейное ограничение, но также , как отмечено в комментарии, ограничение делает эту проблему оптимизации, когда переменные решения являются дискретными (в частности, целыми числами), что означает, что, формально говоря, вы не получите иметь производные. $z_i\in N$

На практике многие проблемы дискретной оптимизации подвергаются «притворству», что мы можем вычислить производные (таким образом, сформировать лагранжиан с двумя ограничениями, получить условия Каруша-Куна-Такера и т. Д.), Получить вектор максимизатора таким образом, а затем проверьте, что происходит, когда мы округляем вверх или вниз его элементы, чтобы они стали целыми числами.

Вам также необходимо проверить, что бюджетное ограничение не нарушается этими округлениями, и разрешить только те комбинации, которые этого не делают. Здесь важно ограничение бюджета как неравенства, потому что допустимый вектор максимизатора , скорее всего, не полностью исчерпает бюджет. $z_i$

Смотрите здесь для некоторых вводных битов по целочисленному программированию.

Алекос Пападопулос
источник

Денис - в его нынешнем виде на ваш вопрос не всегда можно ответить. По крайней мере, не так, как я думаю, вас это интересует. В частности, ограничение выбора потребителя каким-либо ограниченным, произвольным набором вариантов, наделение этого агента некоторым количеством богатства и последующее требование того, чтобы потребитель приобрел определенное количество товаров, не всегда осуществимо всякий раз, когда эти товары подвергаются дискретизации.

Предположим, что у некоторого агента есть богатство и он сталкивается с выбором товаров в наборе { }, где мы предполагаем, что мы можем перечислять цены st . Если мы предположим, что , то мы не сможем выполнить какое-либо требование о том, что этот агент должен приобрести какое-то минимальное количество товаров, независимо от того, определяем ли мы минимальное количество типов или количество товаров. Это просто самый простой пример, который я могу подумать, чтобы проиллюстрировать точку зрения. Вы могли бы также подумать о необходимости выполнения некоторых минимальных требований для товаров. Кроме того, мы могли бы иметь этого агента сталкиваюсь с $i$ $w$
$G \equiv$ $g_1,...,g_n$ $p_{g1}<p_{g2}<...<p_{gn}$ $w<p_{g1}$ $n$ $i$ $w-p(n-1)$

Единственный «максимальный» агент, которого могу достичь - это поскольку этот агент не может участвовать на этом рынке. $i$ $U(w)$

123
источник