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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Означення

[ред. | ред. код]

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

максимізувати
за умов і

де:

  • і це вектори розміру n (кількість змінних);
  • вектор розміру m (кількість обмежень);
  • це m-на-n матриця;
  • значить, що всі змінні невід'ємні.

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

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

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

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

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

Маючи базис B, ми кажемо, що допустимий розв'язок це базовий розв'язок з базисом B якщо всі ненульові змінні мають індекси з B, тобто, для всіх .

Властивості

[ред. | ред. код]

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

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

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

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

Якщо єдиний розв'язок задовольняє обмеженню невід'ємності, тоді базис називається допустимий базис.

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

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

Примітки

[ред. | ред. код]