2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Задача на максимум
Сообщение22.06.2023, 12:07 
Подскажите, пожалуйста, теорию с помощью которой можно искать максимум для функции с ограничениями.
1) Все неизвестные больше или равны нулю
2) Все неравенства линейные
3) Все коэффициенты при неизвестных равны $1$
4) Целевая функция состоит из суммы всех неизвестных
5) Все неизвестные целые числа
6) Каждая переменная появляется в ограничениях два раза. Один раз в верхней группе и один раз в нижней группе (см. пример)
7) Левая часть ограничений содержит только операторы сложения. Правая часть ограничений будет всегда неотрицательна.

Пример системы
$x_1+x_2\leqslant 4$
$x_5+x_6\leqslant 7$
$x_3+x_4\leqslant 2$

$x_1\leqslant 4$
$x_2+x_5+x_3\leqslant 3$
$x_6\leqslant 5$
$x_4\leqslant 1$

$x_1,x_2,x_3,x_4,x_5,x_6\geqslant 0$
$x_1+x_2+x_3+x_4+x_5+x_6\to \max$

 
 
 
 Re: Задача на максимум
Сообщение22.06.2023, 12:31 
fesoh82663 в сообщении #1598540 писал(а):
Подскажите, пожалуйста, теорию с помощью которой можно искать максимум для функции с ограничениями.

Теория называется так https://ru.wikipedia.org/wiki/%D0%A6%D0 ... 0%B8%D0%B5
Там (и в английской версии) есть ссылки на литературу.

 
 
 
 Re: Задача на максимум
Сообщение22.06.2023, 13:05 
Dedekind в сообщении #1598544 писал(а):
Теория называется так https://ru.wikipedia.org/wiki/%D0%A6%D0 ... 0%B8%D0%B5


Там сказано что это является NP-трудной задачей. Т.е. решить ее можно только полным перебором?

 
 
 
 Re: Задача на максимум
Сообщение22.06.2023, 13:56 
Аватара пользователя
fesoh82663 в сообщении #1598550 писал(а):
Там сказано что это является NP-трудной задачей. Т.е. решить ее можно только полным перебором?
Не обязательно полным. Просто нет эффективных методов, гарантированно работающих для всех случаев. А в статье по ссылке есть же много эвристических методов.

 
 
 
 Re: Задача на максимум
Сообщение22.06.2023, 14:09 
Аватара пользователя
fesoh82663
Если надо просто посчитать, и размер задачи такой как в примере, возьмите python и до-установите ortools.

 
 
 
 Re: Задача на максимум
Сообщение22.06.2023, 14:36 
А если все условия остаются, но нам уже известен максимум функции, то есть способ найти значения при которых он достигается?

 
 
 
 Re: Задача на максимум
Сообщение22.06.2023, 14:43 
Аватара пользователя
fesoh82663, нет. Иначе мы бы могли перебрать всевозможные значения максимума и двоичным поиском эффективно найти решение и исходной задачи.

 
 
 
 Re: Задача на максимум
Сообщение22.06.2023, 14:44 
Ваши неравенства имеют довольно специальный вид: они состоят из двух групп, и каждая переменная входит с коэффициентом $1$ один раз в верхнюю и один раз в нижнюю группу. Это значит, что матрица неравенств вполне унимодулярна, и можно решать задачу как обычную ЛП, с вещественными переменными, результат получится целочисленным.

Если неравенства всегда будут иметь такой вид, это сильно упрощает дело.

 
 
 
 Re: Задача на максимум
Сообщение22.06.2023, 15:08 
tolstopuz в сообщении #1598575 писал(а):
Ваши неравенства имеют довольно специальный вид: они состоят из двух групп, и каждая переменная входит с коэффициентом $1$ один раз в верхнюю и один раз в нижнюю группу. Это значит, что матрица неравенств вполне унимодулярна, и можно решать задачу как обычную ЛП, с вещественными переменными, результат получится целочисленным.

Если неравенства всегда будут иметь такой вид, это сильно упрощает дело.


Да, каждая переменная будет с коэффициентом $1$. Один раз в верхней и один раз в нижней группе. Правая часть ограничений будет всегда неотрицательна. Еще будет известен максимум функции и нужно найти любой вариант решения, при котором этот максимум достигается. Либо сказать, что это невозможно.

 
 
 
 Posted automatically
Сообщение22.06.2023, 15:30 
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы)

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 
 
 
 Posted automatically
Сообщение22.06.2023, 17:04 
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Причина переноса: не указана.

 
 
 
 Re: Задача на максимум
Сообщение23.06.2023, 09:40 
Вообще-то это очень похоже на задачу о максимальном потоке: даны источники ($4, 7, 2$), стоки ($4, 3, 5, 1$), между каждой парой источника и стока пропускная способность либо бесконечная, либо нулевая. То есть решать это можно любым алгоритмом для задачи о максимальном потоке, на бумажке вполне хватит Форда-Фалкерсона.

При заданном условии получается примерно так:

- жадным алгоритмом назначаем $x_1=4$, $x_5=3$, $x_6=4$, $x_4=1$;
- находим увеличивающий путь $x_3\to x_5\to x_6$;
- протаскиваем по нему недостающую единицу: $x_3=1$, $x_5=2$, $x_6=5$.

 
 
 
 Re: Задача на максимум
Сообщение23.06.2023, 10:12 
Аватара пользователя
Общая постановка содержит два принципиальных условия. Линейность (2) и целочисленность (5). Первое очень приятно, второе - совсем не приятно. То есть это задача целочисленного линейного программирования, она действительно NP, но совершенно не обязателен перебор. Методы её решения появились ещё в 1950е, и в основном либо метод ветвей и границ, либо метод отсечений. Как правило, они позволяют решить за приемлемое время, хотя и существенно большее, чем для линейной без требования целочисленности.
Но мне отчего-то видится сходство с транспортной задачей. Но в ней ограничения единообразны, если переменные записать в виде прямоугольной матрицы, то одна группа ограничений - суммы по строкам, вторая - по столбцам. Если бы была ТЗ - то в ней целочисленность получается сама собой, в силу абсолютной унимодулярности. Но именно для приведенного примера - не выполняется.

 
 
 
 Re: Задача на максимум
Сообщение23.06.2023, 11:01 
Евгений Машеров в сообщении #1598772 писал(а):
Если бы была ТЗ - то в ней целочисленность получается сама собой, в силу абсолютной унимодулярности. Но именно для приведенного примера - не выполняется.
Почему же? Это матрица инцидентности неориентированного двудольного графа. И задача свелась к задаче о максимальном потоке:

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

 
 
 
 Re: Задача на максимум
Сообщение23.06.2023, 11:48 
Пока вроде решил симплекс методом. А как свести к задаче на макс поток?
Макс поток это когда мы находим максимальное количество жидкости которое может дойти от одной вершины (истока) до другой вершины (стока)?
Мне не очень понятно как тогда выбирать исток и сток.

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group