Основное возможное решение - Basic feasible solution - Wikipedia

В теории линейное программирование, а базовое возможное решение (BFS) - решение с минимальным набором ненулевых переменных. Геометрически каждая BFS соответствует углу многогранник возможных решений. Если существует оптимальное решение, то существует оптимальная BFS. Следовательно, чтобы найти оптимальное решение, достаточно рассмотреть BFS-ы. Этот факт используется симплексный алгоритм, который, по сути, переходит от одного BFS к другому, пока не будет найден оптимальный.[1]

Определение

Чтобы определить BFS, мы сначала представляем линейную программу в так называемом эквациональная форма:

максимизировать
при условии и

куда:

  • и являются векторами размера п (количество переменных);
  • вектор размера м (количество ограничений);
  • является м-к-п матрица;
  • означает, что все переменные неотрицательны.

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

В качестве предварительного этапа очистки мы проверяем, что:

  • Система имеет хотя бы одно решение (иначе у всей ЛП решения нет и делать больше нечего);
  • Все м строки матрицы линейно независимы, т. е. его ранг равен м (в противном случае мы можем просто удалить лишние строки, не меняя LP).

Обычно м < п, поэтому система есть много решений; каждое такое решение называется возможное решение ЛП.

Позволять B быть подмножеством м индексы из {1, ...,п}. Обозначим через квадрат м-к-м матрица из м столбцы проиндексировано B. Если является неособый, столбцы, проиндексированные B площадь основа из пространство столбца из . В этом случае мы называем B а основа ЛП. С ранга является м, имеет хотя бы одно основание; поскольку имеет п столбцы, он имеет не более базы.

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

Характеристики

1. BFS определяется только ограничениями LP (матрица и вектор ); это не зависит от цели оптимизации.

2. По определению, BFS имеет не более м ненулевые переменные и не менее п-м нулевые переменные. BFS может иметь менее м ненулевые переменные; в этом случае он может иметь множество различных баз, каждая из которых содержит индексы его ненулевых переменных.

3. Возможное решение является основным, если и только если столбцы матрицы линейно независимы, где K - множество индексов ненулевых элементов . [1]:45

4. BFS однозначно определяется базисом B: для каждой основы B из м индексов, существует не более одного BFS с основанием B. Это потому что должен удовлетворять ограничению , а по определению базиса матрица неособо, поэтому ограничение имеет единственное решение. Обратное неверно: каждая BFS может происходить из разных баз.

Если единственное решение удовлетворяет ограничениям неотрицательности, то базис называется возможная основа.

5. Если линейная программа имеет оптимальное решение (т. Е. Допустимое решение, а набор допустимых решений ограничен), то она имеет оптимальную BFS. Это следствие Принцип максимума Бауэра: цель линейной программы - выпуклая; множество допустимых решений выпукло (это пересечение гиперпространств); поэтому цель достигает своего максимума в крайней точке множества возможных решений.

Поскольку количество BFS-s конечно и ограничено , оптимальное решение любой ЛП может быть найдено за конечное время, просто оценив целевую функцию во всех БФС-ы. Это не самый эффективный способ решить ЛП; то симплексный алгоритм исследует BFS-ы более эффективным способом.

Примеры

Рассмотрим линейную программу со следующими ограничениями:

Матрица А является:

Здесь, м= 2 и имеется 10 подмножеств по 2 индексов, однако не все из них являются базисами: набор {3,5} не является базисом, поскольку столбцы 3 и 5 линейно зависимы.

Набор B= {2,4} является базисом, поскольку матрица неособен.

Единственная BFS, соответствующая этому базису, есть .

Геометрическая интерпретация

Удлиненная пятиугольная orthocupolarotunda.png

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

Каждой BFS соответствует вершина этого многогранника. [1]:53–56

Применение в симплексном алгоритме

В симплексный алгоритм сохраняет в каждой точке своего исполнения «текущую основу» B (подмножество м снаружи п переменные), "текущая BFS" и "текущая таблица". Таблица представляет собой представление линейной программы, где основные переменные выражены через неосновные: [1]:65

куда вектор м основные переменные, вектор п неосновные переменные и является целью максимизации. Поскольку неосновные переменные равны 0, текущая BFS равна , а текущая цель максимизации - .

Если все коэффициенты в отрицательны, то является оптимальным решением, поскольку все переменные (включая все неосновные переменные) должны быть не меньше 0, поэтому вторая строка подразумевает .

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

Если этот процесс проделан аккуратно, то можно гарантировать, что увеличивается, пока не достигнет оптимального BFS.

Рекомендации

  1. ^ а б c d Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования. Берлин: Springer. ISBN  3-540-30697-8.:44–48