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

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

Определения

Предварительные сведения: эквациональная форма с линейно независимыми строками.

Для приведенных ниже определений мы сначала представим линейную программу в так называемой эквациональной форме :

максимизировать ${\textstyle \mathbf {c^{T}} \mathbf {x} }$

при условии $A\mathbf {x} =\mathbf {b}$ и $\mathbf {x} \geq 0$

где:

• $\mathbf {c^{T}}$ и $\mathbf {x}$ – векторы размера n (количество переменных);
• $\mathbf {b}$ — вектор размера m (количество ограничений);
• $A$ представляет собой m матрицу размером × n ;
• $\mathbf {x} \geq 0$ означает, что все переменные неотрицательны.

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

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

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

Возможное решение

ЛП Допустимым решением является любой вектор $\mathbf {x} \geq 0$ такой, что $A\mathbf {x} =\mathbf {b}$. Мы предполагаем, что существует хотя бы одно допустимое решение. Если m = n , то существует только одно допустимое решение. Обычно m < n , поэтому система $A\mathbf {x} =\mathbf {b}$ имеет множество решений; каждое такое решение называется допустимым решением ЛП.

Основа

Базисом неособая ЛП является подматрица A со всеми m строками и только m < n столбцами.

Иногда термин базис используется не для самой подматрицы, а для набора индексов ее столбцов. Пусть B — подмножество m индексов из {1,..., n }. Обозначим через $A_{B}$ квадратная m матрица размером на m, состоящая из m столбцов $A$ индексируется Б. ​Если $A_{B}$ несингулярен , , столбцы, B являются базисом пространства столбцов индексированные $A$. В этом случае мы называем B базисом ЛП.

Начиная с ранга $A$ есть m , оно имеет хотя бы один базис; с $A$ имеет n столбцов, имеет не более ${\binom {n}{m}}$ базы.

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

Учитывая базис B , мы говорим, что допустимое решение $\mathbf {x}$ является базовым допустимым решением с базисом B, если все его ненулевые переменные проиндексированы B , то есть для всех $j\not \in B:~~x_{j}=0$.

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

1. БФС определяется только ограничениями ЛП (матрица $A$ и вектор $\mathbf {b}$); это не зависит от цели оптимизации.

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

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

4. Каждый базис определяет уникальную БФС: для каждого базиса B из m индексов существует не более одной БФС. $\mathbf {x_{B}}$ с Б. базисом Это потому, что $\mathbf {x_{B}}$ должно удовлетворять ограничению $A_{B}\mathbf {x_{B}} =b$, и по определению базиса матрица $A_{B}$ не является сингулярным, поэтому ограничение имеет единственное решение:

$\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$

Обратное неверно: каждый BFS может происходить из множества разных баз. Если единственное решение $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ удовлетворяет ограничениям неотрицательности $\mathbf {x_{B}} \geq 0$, то B называется допустимым базисом .

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

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

Примеры

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

${\begin{aligned}x_{1}+5x_{2}+3x_{3}+4x_{4}+6x_{5}&=14\\x_{2}+3x_{3}+5x_{4}+6x_{5}&=7\\\forall i\in \{1,\ldots ,5\}:x_{i}&\geq 0\end{aligned}}$

Матрица А :

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

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

Множество B ={2,4} является базисом, поскольку матрица $A_{B}={\begin{pmatrix}5&4\\1&5\end{pmatrix}}$ не является особенным.

Единственная БФС, соответствующая этому базису, равна $x_{B}=(0~~2~~0~~1~~0)$.

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

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

Основные возможные решения двойной задачи

Как упоминалось выше, каждый базис B определяет единственное базовое допустимое решение. $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ . Аналогичным образом каждый базис определяет решение двойственной линейной программы :

минимизировать ${\textstyle \mathbf {b^{T}} \mathbf {y} }$

при условии $A^{T}\mathbf {y} \geq \mathbf {c}$.

Решение $\mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c$.

Поиск оптимального BFS

Существует несколько методов поиска оптимального BFS.

Использование симплексного алгоритма

На практике самый простой способ найти оптимальную BFS — использовать симплексный алгоритм . В каждой точке своего выполнения он сохраняет «текущий базис» B (подмножество m из n переменных), «текущую BFS» и «текущую таблицу». Таблица представляет собой представление линейной программы, в которой базовые переменные выражаются через небазисные: $${\begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T}x_{N}\end{aligned}}$$где $x_{B}$ — вектор m основных переменных, $x_{N}$ - вектор n неосновных переменных, а $z$ является целью максимизации. Поскольку неосновные переменные равны 0, текущий BFS равен $p$, и текущая цель максимизации $z_{0}$.

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

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

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

Преобразование любого оптимального решения в оптимальную BFS

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

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

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

Базис B ЛП называется дуально оптимальным, если решение $\mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c$ является оптимальным решением двойной линейной программы, т. е. минимизирует ${\textstyle \mathbf {b^{T}} \mathbf {y} }$. В общем, первично-оптимальный базис не обязательно является дуально-оптимальным, а дуально-оптимальный базис не обязательно является первично-оптимальным (фактически, решение первично-оптимального базиса может быть даже неосуществимо для двойственного, и наоборот ).

Если оба $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ является оптимальным BFS исходной ЛП, а $\mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c$ является оптимальной БФС двойственной ЛП, то базис B называется PD-оптимальным . Каждая ЛП с оптимальным решением имеет PD-оптимальный базис, и он находится с помощью алгоритма Simplex . Однако в худшем случае время его выполнения экспоненциально. Нимрод Мегиддо доказал следующие теоремы:

• Существует строго полиномиальный алгоритм по времени, который вводит оптимальное решение для первичной ЛП и оптимальное решение для двойственной ЛП и возвращает оптимальный базис.
• Если существует алгоритм со строго полиномиальным временем , который вводит оптимальное решение только для первичной ЛП (или только для двойственной ЛП) и возвращает оптимальный базис, то существует алгоритм со сильно полиномиальным временем для решения любой линейной программы (последний представляет собой знаменитая открытая задача).

Алгоритмы Мегиддо могут быть выполнены с использованием таблицы, как и симплексный алгоритм.

Внешние ссылки

• Как перейти от оптимального допустимого решения к оптимальному базовому допустимому решению . Пол Робин, Stack Exchange для исследования операций.