Базовый возможное решение

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

• 1 Определение
• 2 Свойства
• 3 Примеры
• 4 Геометрическая интерпретация
• 5 Применение в симплексном алгоритме
• 6 Ссылки

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

увеличить $c\; T\; \cdot \; x\; \{\backslash \; textstyle\; \backslash \; mathbf\; \{c\; ^\; \{T\}\}\; \backslash \; cdot\; \backslash \; mathbf\; \{x\}\}$

с учетом $A\; x\; =\; b\; \{\backslash \; displaystyle\; A\; \backslash \; mathbf\; \{x\}\; =\; \backslash \; mathbf\; \{b\}\}$и $x\; \ge \; 0\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \backslash \; geq\; 0\}$

где:

• $c\; T\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{c\; ^\; \{T\}\}\}$и $x\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\}$- векторы размера n (количество переменных);
• $b\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{b\}\}$- вектор размера m (количество ограничений);
• $A\; \{\backslash \; displaystyle\; A\}$- матрица размера m на n;
• $x\; \ge \; 0\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\; \backslash \; geq\; 0\}$означает, что все переменные неотрицательны.

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

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

• Система $A\; x\; =\; b\; \{\backslash \; displaystyle\; A\; \backslash \; mathbf\; \{x\}\; =\; \backslash \; mathbf\; \{b\}\}$имеет по крайней мере одно решение (в противном случае весь LP не имеет решения и больше нечего делать);
• Все m строки матрицы $A\; \{\backslash \; displaystyle\; A\}$линейно независимы, т. е. ее ранг равен m (в противном случае мы можем просто удалить лишние строки, не меняя LP).

Обычно m A x = b {\ displaystyle A \ mathbf {x} = \ mathbf {b}}имеет множество решений; каждое такое решение называется допустимым решением ЛП.

Пусть B - подмножество m индексов из {1,..., n}. Обозначим через $AB\; \{\backslash \; displaystyle\; A\_\; \{B\}\}$квадратную матрицу m на m, составленную из m столбцов $A\; \{\backslash \; displaystyle\; A\}$проиндексированных на B. Если $AB\; \{\backslash \; displaystyle\; A\_\; \{B\}\}$равно неособое число, столбцы, проиндексированные B, являются базисом пространство столбца из $A\; \{\backslash \; displaystyle\; A\}$. В этом случае мы называем B базой ЛП. Поскольку ранг $A\; \{\backslash \; displaystyle\; A\}$равен m, он имеет по крайней мере одно основание; поскольку $A\; \{\backslash \; displaystyle\; A\}$имеет n столбцов, он имеет не более $(нм)\; \{\backslash \; displaystyle\; \{\backslash \; binom\; \{n\}\; \{m\}\}\}$базы.

Для базиса B мы говорим, что допустимое решение $x\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\}$является базовым допустимым решением с базисом B если все его ненулевые переменные проиндексированы B, т. е. для всех $j\; \notin \; B:\; xj\; =\; 0\; \{\backslash \; displaystyle\; j\; \backslash \; not\; \backslash \; in\; B:\; ~~\; x\_\; \{j\}\; =\; 0\}$.

1. BFS определяется только ограничениями LP (матрица $A\; \{\backslash \; displaystyle\; A\}$и вектор $b\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{b\}\}$); это не зависит от цели оптимизации.

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

3. Возможное решение $x\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\}$является базовым, если и только если столбцы матрицы $AK\; \{\backslash \; displaystyle\; A\_\; \{K\}\}$линейно независимы, где K - это набор индексов ненулевых элементов $x\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\}\}$.

4. BFS однозначно определяется базисом B: для каждого базиса B из m индексов существует не более одного BFS $x\; B\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\_\; \{B\}\}\}$с базой B. Это потому, что $x\; B\; \{\backslash \; displaystyle\; \backslash \; mathbf\; \{x\_\; \{B\}\}\}$должен удовлетворять ограничению $AB\; x\; B\; =\; b\; \{\backslash \; displaystyle\; A\_\; \{B\}\; \backslash \; mathbf\; \{x\_\; \{B\}\}\; =\; b\}$, и по определению основы матрица $AB\; \{\backslash \; displaystyle\; A\_\; \{B\}\}$неособая, поэтому ограничение имеет уникальный решение. Обратное неверно: каждая BFS может происходить из разных баз.

Если уникальное решение $AB\; x\; B\; =\; b\; \{\backslash \; displaystyle\; A\_\; \{B\}\; \backslash \; mathbf\; \{x\_\; \{B\}\}\; =\; b\}$удовлетворяет ограничениям неотрицательности, тогда базис называется допустимым базисом .

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

Поскольку количество BFS-ов конечно и ограничено $(нм)\; \{\backslash \; displaystyle\; \{\backslash \; binom\; \{n\}\; \{m\}\}\}$, оптимальное решение для любого LP можно найти за конечное время, просто оценив целевую функцию во всех $(нм)\; \{\backslash \; displaystyle\; \{\backslash \; binom\; \{n\}\; \{m\}\}\}$BFS-s. Это не самый эффективный способ решить ЛП; симплексный алгоритм исследует BFS-файлы гораздо более эффективно.

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

$x\; 1\; +\; 5\; x\; 2\; +\; 3\; x\; 3\; +\; 4\; x\; 4\; +\; 6\; x\; 5\; =\; 14\; x\; 2\; +\; 3\; x\; 3\; +\; 5\; x\; 4\; +\; 6\; x\; 5\; =\; 7\; \forall \; i\; \in \; \{1,\dots ,\; 5\}:\; xi\; \ge \; 0\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; x\_\; \{1\}\; +\; 5x\_\; \{2\}\; +\; 3x\_\; \{3\}\; +\; 4x\_\; \{4\}\; +\; 6x\_\; \{5\}\; =\; 14\; \backslash \backslash \; x\_\; \{2\}\; +\; 3x\_\; \{3\}\; +\; 5x\_\; \{4\}\; +\; 6x\_\; \{5\}\; =\; 7\; \backslash \backslash \backslash \; для\; всех\; i\; \backslash \; in\; \backslash \; \{1,\; \backslash \; ldots,\; 5\; \backslash \}:\; x\_\; \{i\}\; \backslash \; geq\; 0\; \backslash \; end\; \{align\}\}\}$

Матрица A:

$A\; =\; (1\; 5\; 3\; 4\; 6\; 0\; 1\; 3\; 5\; 6)\; b\; =\; (14\; 7)\; \{\; \backslash \; displaystyle\; A\; =\; \{\backslash \; begin\; \{pmatrix\}\; 1\; 5\; 3\; 4\; 6\; \backslash \backslash \; 0\; 1\; 3\; 5\; 6\; \backslash \; end\; \{pmatrix\}\}\; ~~~~~\; \backslash \; mathbf\; \{b\}\; =\; (14\; ~~\; 7)\}$

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

Множество B = {2,4} является базисом, поскольку матрица $AB\; =\; (5\; 4\; 1\; 5)\; \{\backslash \; displaystyle\; A\_\; \{B\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 5\; 4\; \backslash \backslash \; 1\; 5\; \backslash \; end\; \{pmatrix\}\}\}$неособое число.

Уникальный BFS, соответствующий этому основанию, равен $x\; B\; =\; (0\; 2\; 0\; 1\; 0)\; \{\backslash \; displaystyle\; x\_\; \{B\}\; =\; (0\; ~~\; 2\; ~~\; 0\; ~~\; 1\; ~~\; 0)\; \}$.

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

. Каждой BFS соответствует вершина этого многогранника.

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

$x\; B\; =\; p\; +\; Q\; x\; N\; z\; =\; z\; 0\; +\; r\; T\; x\; N\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{выравнивается\}\; x\_\; \{B\}\; =\; p\; +\; Qx\_\; \{N\}\; \backslash \backslash \; z\; =\; z\_\; \{0\}\; +\; r\; ^\; \{T\}\; x\_\; \{N\}\; \backslash \; end\; \{выравнивается\}\}\}$где $x\; B\; \{\; \backslash \; displaystyle\; x\_\; \{B\}\}$- вектор из m базовых переменных, $x\; N\; \{\backslash \; displaystyle\; x\_\; \{N\}\}$- вектор из n неосновных переменных, и $z\; \{\backslash \; displaystyle\; z\}$- цель максимизации. Поскольку неосновные переменные равны 0, текущая BFS - это $p\; \{\backslash \; displaystyle\; p\}$, а текущая цель максимизации - $z\; 0\; \{\backslash \; displaystyle\; z\_\; \{0\}\}$.

Если все коэффициенты в $r\; \{\backslash \; displaystyle\; r\}$отрицательны, то $z\; 0\; \{\backslash \; displaystyle\; z\_\; \{0\}\}$является оптимальным решением, поскольку все переменные (включая все неосновные переменные) должно быть не менее 0, поэтому вторая строка подразумевает $z\; \le \; z\; 0\; \{\backslash \; displaystyle\; z\; \backslash \; leq\; z\_\; \{0\}\}$.

Если некоторые коэффициенты в $r\; \{\backslash \; displaystyle\; r\}$положительны, тогда можно будет увеличить цель максимизации. Например, если $x\; 5\; \{\backslash \; displaystyle\; x\_\; \{5\}\}$не является базовым, а его коэффициент в $r\; \{\backslash \; displaystyle\; r\}$положительный, тогда увеличение его выше 0 может увеличить $z\; \{\backslash \; displaystyle\; z\}$. Если это возможно сделать без нарушения других ограничений, то увеличенная переменная становится базовой (она «входит в базовую»), в то время как другая небазовая переменная уменьшается до 0 для сохранения ограничений равенства и, таким образом, становится не базовой (она «выходит с базы»).

Если этот процесс проделан осторожно, то можно гарантировать, что $z\; \{\backslash \; displaystyle\; z\}$увеличивается до тех пор, пока не будет достигнута оптимальная BFS.