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

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

Определения [ править ]

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

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

максимизировать

{\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 строками и только < n m .

Иногда термин базис используется не для самой подматрицы, а для набора индексов ее столбцов. Пусть 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}$ . ^[1]^: 45

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 соответствует вершине этого многогранника. ^[1]^: 53–56

двойной проблемы Основные возможные решения

Как упоминалось выше, каждый базис 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» и «текущую таблицу». Таблица представляет собой представление линейной программы, в которой базовые переменные выражаются через небазисные: ^[1]^: 65

{\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 Преобразование любого оптимального

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

Однако, учитывая любое оптимальное решение ЛП, легко найти оптимальное допустимое решение, которое также является базовым . ^[2]^{: см. также «внешние ссылки» ниже.}

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

Базис 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 . Однако в худшем случае время его выполнения экспоненциально. Нимрод Мегиддо доказал следующие теоремы: ^[2]

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

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

Внешние ссылки [ править ]

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

Ссылки [ править ]

^ Перейти обратно: ^а ^б ^с ^д Гертнер, Бернд; Матушек, Иржи (2006). Понимание и использование линейного программирования . Берлин: Шпрингер. ISBN 3-540-30697-8 . ^: 44–48
^ Перейти обратно: ^а ^б Мегиддо, Нимрод (1 февраля 1991 г.). «О нахождении первично- и дуально-оптимальных базисов» . Журнал ORSA по вычислительной технике . 3 (1): 63–65. CiteSeerX 10.1.1.11.427 . дои : 10.1287/ijoc.3.1.63 . ISSN 0899-1499 .

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

[:0-2] Перейти обратно: ^а ^б Мегиддо, Нимрод (1 февраля 1991 г.). «О нахождении первично- и дуально-оптимальных базисов» . Журнал ORSA по вычислительной технике . 3 (1): 63–65. CiteSeerX 10.1.1.11.427 . дои : 10.1287/ijoc.3.1.63 . ISSN 0899-1499 .

[1]

[2]