Базовий допустимий розв'язок

В теорії лінійного програмування, базовий допустимий розв'язок (БДР) це, інтуїтивно, розв'язок з найменшою кількість ненульових змінних. Геометрично, кожен БДР відповідає куту многограника допустимих розв'язків. Якщо існує оптимальний розв'язок, тоді існує оптимальний БДР. Звідси, щоб знайти оптимальний розв'язок, достатньо розглядати лише БДР-и. Цей факт використовує симплекс-метод, який по суті мандрує від якогось БДР до іншого допоки на знайде оптимальний.

Означення

Щоб визначити БДР, ми спершу представимо лінійну програму в так званій екваційній формі:

максимізувати ${\textstyle \mathbf {c^{T}} \cdot \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 (інакше ми видаляємо надлишковий рядок без зміни лінійної програми).

Зазвичай, m < n, тобто система $A\mathbf {x} =\mathbf {b}$ має багато розв'язків; кожен такий розв'язок називається допустимим розв'язком лінійної програми.

Нехай B буде підмножиною m індексів з {1,...,n}. Позначимо через $A_{B}$ квадратну m-на-m підматрицю з m стовпчиків матриці $A$ проіндексовану по B. Якщо $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. За означенням, БДР має не більше ніж m ненульових змінних і щонайменше n-m нульових змінних. БДР може мати менше ніж m ненульових змінних; в такому випадку, він може мати декілька різних базисів, які всі містять індекси його ненульових змінних.

3. Допустимий розв'язок $\mathbf {x}$ це базис тоді і тільки тоді, коли всі стовпчики матриці $A_{K}$ лінійно незалежні, де K це множина індексів ненульових елементів $\mathbf {x}$.

4. БДР унікально визначений базисом B: для кожного базису B з m індексів, існує не більше одного БДР $\mathbf {x_{B}}$ з базисом B. Це через те, що $\mathbf {x_{B}}$ мусить задовольняти обмеженню $A_{B}\mathbf {x_{B}} =b$ і, за означенням базису матриці, матриця $A_{B}$ невироджена, тому це обмеження має єдиний розв'язок. Стверджувати зворотнє не можна: кожен БДР може бути в декількох базисах.

Якщо єдиний розв'язок $A_{B}\mathbf {x_{B}} =b$ задовольняє обмеженню невід'ємності, тоді базис називається допустимий базис.

5. Якщо лінійна програма має оптимальний розв'язок (тобто, має допустимий розв'язок і множина допустимих розв'язків обмжена), тоді вона має оптимальний БДР.

Через те, що число БДР-ів скінченне і обмежене ${\binom {n}{m}}$, оптимальний розв'язок можна знайти за скінченний час просто обчисливши цільову функцію в усіх ${\binom {n}{m}}$ ДБР-ів. Це не найефективніший спосіб розв'язання лінійної програми; симплекс-метод досліджує ДБР-и набагато ефективніше.