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

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

Означення

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

максимізувати ${𝐜}^{𝐓}\cdot 𝐱$

за умов $A𝐱=𝐛$ і $𝐱\ge 0$

де:

• ${𝐜}^{𝐓}$ і $𝐱$ це вектори розміру n (кількість змінних);
• $𝐛$ вектор розміру m (кількість обмежень);
• $A$ це m-на-n матриця;
• $𝐱\ge 0$ значить, що всі змінні невід'ємні.

Кожну лінійну програму можна перевести в екваційну форму додаючи люзові змінні (допоміжні змінні).

На підготовчому кроці перевіряємо, що:

• Система $A𝐱=𝐛$ має щонайменше один розв'язок (інакше вся лінійна програма не має розв'язку і тут нема, що далі робити);
• Всі m рядків матриці $A$ лінійно незалежні, тобто, її ранг m (інакше ми видаляємо надлишковий рядок без зміни лінійної програми).

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

Нехай B буде підмножиною m індексів з {1,...,n}. Позначимо через $A_B$ квадратну m-на-m підматрицю з m стовпчиків матриці $A$ проіндексовану по B. Якщо $A_B$ невироджена, стовпчики з індексами з B утворюють базис простору стовпців $A$. У такому разі, ми називаємо B базисом лінійної програми. З того, що ранг $A$ це m, існує щонайменше один базис; через те, що $A$ має n стовпчиків, вона має не більше ніж $(\genfrac{}{}{0ex}{}{n}{m})$ базисів.

Маючи базис B, ми кажемо, що допустимий розв'язок $𝐱$ це базовий розв'язок з базисом B якщо всі ненульові змінні мають індекси з B, тобто, для всіх $j\in ̸B:x_j=0$.

Властивості

1. БДР визначається винятково обмеженнями лінійної програми (матрицею $A$ і вектором $𝐛$); він не залежить від цільової функції.

2. За означенням, БДР має не більше ніж m ненульових змінних і щонайменше n-m нульових змінних. БДР може мати менше ніж m ненульових змінних; в такому випадку, він може мати декілька різних базисів, які всі містять індекси його ненульових змінних.

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

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

Якщо єдиний розв'язок $A_B{𝐱}_{𝐁}=b$ задовольняє обмеженню невід'ємності, тоді базис називається допустимий базис.

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

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