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

Question

Мне нужен алгоритм, который автоматически делает задачу линейного программирования выполнимой.Конкретно, алгоритм таков, что его вход представляет собой задачу линейного программирования, которая потенциально не имеет возможных решений, а его выход представляет собой аналогичное программирование (с параметрами, измененными с минимумом), которое обязательно имеет возможные решения.Я новичок в алгоритмах и спрашиваю, есть ли какие-либо исследования / работы для таких проблем?Любые предложения и комментарии приветствуются.Спасибо, Ричард

Answer 1

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

Answer 2

Добавьте набор «искусственных переменных», по одной на уравнение, с единичным весом в этом уравнении и нулевым весом везде.Затем вы можете выбрать этот набор в качестве первой основы и добавить «исключить искусственные переменные» в качестве начальной цели.Если вы можете устранить все искусственные переменные, вы можете отказаться от них, и у вас будет реальная основа для вашей первоначальной проблемы;если вы не можете исключить искусственные переменные, не существует выполнимого решения.

исходная проблема (в канонической форме - любая проблема с LP может быть преобразована в эту!)возможное решение (при условии, что все b_j>=0; если нет, просто умножьте строку на -1):

minimize sum(y), given:  y + [A]x = b, x_i>=0, y_j>=0
  with initial, feasible solution: x_i=0, y_j=b_j

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

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