задача оптимизации

[mthmtcn]

Задачу можно сформулировать так:
есть матрица двумерных точек размера $K\times3$, причем каждая строка имеет вид:
i строка: $(X_{i1},Y_{i1})$ $(X_{i2},Y_{i2})$ $(X_{i3},Y_{i3})$
Задача состоит в том, чтобы выбрать в каждой строке такую точку (обязательно одну и только одну), чтобы
сумма всех игреков в полученной последовательности точек была наибольшей, а при этом сумма всех иксов полученной последовательности была не более чем некоторое наперед заданное X.
Мне кажется, что эта задача не очень подходит под симплекс-метод, хотя может я и ошибаюсь. Подскажите, пожалуйста, какие могут быть подходы к решению.

[Lia]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

Запишите формулы в соответствии с требованиями Правил форума, т.е. в $\TeX$.
Краткие инструкции можно найти здесь: topic8355.html и topic183.html.
Кроме этого, в теме Видео-пособия для начинающих форумчан можно посмотреть видео-ролик "Как записывать формулы".

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

[Lia]

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

[ИСН]

Это случайно не какая-нибудь "задача о рюкзаке"?

[mthmtcn]

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

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

Без игреков это задача о назначении. Для которой есть хорошие алгоритмы. Но они дают целочисленное решение без особых мер для этого потому, что матрица коэффициентов абсолютно унимодулярна. Добавление ограничения по игрекам это свойство нарушает, и обычный симплекс-метод даст, скорее всего, нецелочисленное решение. Так что задача ЦЛП общего вида. Можно попытаться построить нечто метода ветвей и границ. Скажем, так:
0. Рекорд устанавливаем -М (где М - большое число)
1. Решаем задачу о назначении, максимизируя сумму по Y. Если хуже рекорда - выходим.
2. Проверяем сумму по X. Если условие выполняется - запоминаем рекорд по Y. Далее здесь не ветвим.
3. Если не выполняется - находим самый большой $X_{i,j}$ в полученном решении, ветвимся, переходя в каждой ветке к ш. 1. Одна ветвь - запрет этого X (установлением соответствующего $Y_{i,j}$ "глубоко отрицательным"), вторая - обязательное включение i,j в решение (вычёркивая соответствующие строки и столбцы, но запоминая вклад $X_{i,j}$ и $Y_{i,j}$.

[mthmtcn]

Насколько я понимаю, в задаче о назначении мне всегда нужно выбрать все виды работ: то есть грубо говоря, если отмечать построчно в матрице $K\times3$ те ее элементы, которые входят в решение, то в полученной матрице не будет столбца, в котором не выделено ни одного элемента. Тут же эта ситуация допускается. Более того, мне заведомо известно, что $X_{i1}>X_{i2}>X_{i3}$, $Y_{i1}>Y_{i2}>Y_{i3}$

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

Исправил описку.

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

А все строки надо использовать? Или в некоторых "Не более одной"?

[mthmtcn]

Обязательно использовать все строки