Задача на максимум

[fesoh82663]

Подскажите, пожалуйста, теорию с помощью которой можно искать максимум для функции с ограничениями.
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$

[Dedekind]

fesoh82663 в сообщении #1598540 писал(а):

Подскажите, пожалуйста, теорию с помощью которой можно искать максимум для функции с ограничениями.

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

[fesoh82663]

Dedekind в сообщении #1598544 писал(а):

Теория называется так https://ru.wikipedia.org/wiki/%D0%A6%D0 ... 0%B8%D0%B5

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

[worm2]

fesoh82663 в сообщении #1598550 писал(а):

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

Не обязательно полным. Просто нет эффективных методов, гарантированно работающих для всех случаев. А в статье по ссылке есть же много эвристических методов.

[пианист]

fesoh82663
Если надо просто посчитать, и размер задачи такой как в примере, возьмите python и до-установите ortools.

[fesoh82663]

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

[worm2]

fesoh82663, нет. Иначе мы бы могли перебрать всевозможные значения максимума и двоичным поиском эффективно найти решение и исходной задачи.

[tolstopuz]

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

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

[fesoh82663]

tolstopuz в сообщении #1598575 писал(а):

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

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

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

[Ende]

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

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

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

[Ende]

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

[tolstopuz]

Вообще-то это очень похоже на задачу о максимальном потоке: даны источники ($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$.

[Евгений Машеров]

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

[tolstopuz]

Евгений Машеров в сообщении #1598772 писал(а):

Если бы была ТЗ - то в ней целочисленность получается сама собой, в силу абсолютной унимодулярности. Но именно для приведенного примера - не выполняется.

Почему же? Это матрица инцидентности неориентированного двудольного графа. И задача свелась к задаче о максимальном потоке:

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

[fesoh82663]

Пока вроде решил симплекс методом. А как свести к задаче на макс поток?
Макс поток это когда мы находим максимальное количество жидкости которое может дойти от одной вершины (истока) до другой вершины (стока)?
Мне не очень понятно как тогда выбирать исток и сток.