Властивості розв’язків задачі лінійного програмування

Розглянемо канонічну задачу у векторній формі

;

,

, .

де ; ;...; , .

Запис означає, що є лінійною комбінацією векторів .

Означення 1 План задачі , називається опорним, якщо система векторів-стовпчиків , які відповідають додатним координатам , лінійно незалежна.

Оскільки вектори мають по координат, то лінійно незалежними можуть бути не більше координат. Це означає, що в опорному плані є не більше m строго додатних координат.

Базисні розв’язки системи з невід’ємними координатами є опорними планами.

Приклад 4.1 Перевірити, чи план є опорним, якщо система обмежень така

 

, , .

Додатним координатам плану і відповідають вектори

, .

Перевіримо, чи вони лінійно незалежні. Для цього знайдемо ранг матриці

,

обчислимо визначник .

Отже, вектори і лінійно незалежні, а план - опорний.

Означення 2. Опорний план називається невиродженим, якщо число його додатних координат рівне m, і виродженим, якщо число додатних координат менше m.

У прикладі план невироджений.

Нехай ранг матриці дорівнює .

Означення 3. Базисом опорного плану називається система з лінійно незалежних векторів-стовпчиків матриці , яка містить всі вектори, що відповідають додатним координатам опорного плану.

У прикладі вектори і утворюють базис опорного плану .

Таким чином, базис невиродженого опорного плану визначається однозначно, а у виродженого їх може бути декілька.

Запишемо задачу - у вигляді

;

;

;

і розглянемо основні властивості розв’язків цієї задачі.

Теорема 1. Множина всіх розв’язків системи опукла, якщо вона непорожня.

Доведемо, що якщо , – розв’язки задачі - , то їх лінійна комбінація опукла: ,

, , .

Оскільки , – плани, то , , , . Тоді

.

Отже, задовольняє систему .

Оскільки, , , , , то , тобто виконується .

Опуклу множину планів задачі лінійного програмування позначимо . Можна довести, що буде опуклим многокутником (обмеженим чи необмеженим).

Теорема 2. Якщо цільова функція має максимум на опуклому многограннику допустимих розв’язків , то він досягається у вершині цього многогранника.

Нехай многогранник обмежений і має скінченне число кутових точок . Точку, в якій досягає максимуму, позначимо .

Якщо серед вершин , , є хоч одна, в якій досягає , то теорема доведена.

Нехай не є кутовою точкою. Тоді , .

Якщо – не кутова, то вона є опуклою лінійною комбінацією кутових, тобто

, , .

Тоді

.

Отже, – суперечність. Тому – одна з кутових точок .

Отже, екстремум цільової функції досягається в вершині многогранника розв’язків, але не обов’язково у одній точці.

Теорема 3. Якщо цільова функція має максимум більше, ніж в одній вершині, многогранника , то цей максимум досягається у будь-якій точці, яка є опуклою лінійною комбінацією цих вершин.

Нехай цільова функція досягає максимуму у вершинах многогранника , тобто , . Тоді для довільної прямої лінійна комбінація цих вершин

, ,

Маємо:

Отже, для знаходження досить дослідити всі вершини .

Теорема 4. Вектор є опорним планом задачі - тоді і лише тоді, коли є вершиною многогранника розв’язків .

З теореми випливає, що алгебраїчне поняття опорного плану еквівалентне до геометричного поняття вершини многогранника розв’язків.

Наслідок 1. Кожна вершина многогранника має не більше ніж додатних координат.

За означенням опорного плану, є додатних координат.

Наслідок 2. Кожній вершині многогранника відповідає лінійно-незалежних розв’язків-стовпців , .

Це означення опорного плану.

Висновок. Якщо цільова функція обмежена на , то існує кутова точка (опорний план), в якій досягається . Тому для розв’язування задач лінійного програмування треба дослідити тільки вершини многогранника (опорні плани) задачі лінійного програмування.