Обґрунтування симплекс-методу

Основним методом розв’язування задач лінійного програмування є розроблений у 1949 році американським математиком Д. Данцігом симплекс-метод. Він застосовується для задач у канонічній формі

;

;

;

де ; ; ;

Нагадаємо, що з властивостей розв’язків задачі лінійного програмування випливає: оптимальний план задачі (1)-(3) знаходиться серед опорних планів (вершин многогранника розв’язків), тобто серед таких розв’язків системи (2)-(3), додатним координатам яких відповідають лінійно незалежні стовпці A_j матриці A. Симплексний метод організовує знаходження і перегляд опорних планів у певному порядку. Перехід від одного опорного плану до іншого здійснюється переведенням однієї з небазисних змінних у базисну. При цьому цільова функція не зменшується.

Нехай система (2) є системою у базисній формі. Це означає, що є m базисних змінних (наприклад x₁, x₂, …, x_m), кожна з яких входить лише в одне рівняння з коефіцієнтом 1 і всі числа , . Тобто система (2) має вигляд

; ; .

Тоді загальний розв’язок системи (4) такий:

, ;

а базисний розв’язок буде

, ; ;

або

.

Оскільки , то це опорний план.

Підставимо (5) у цільову функцію (1):

Позначимо , , ;

, ,

Тоді .

Вираз (8) називається зведеним виразом цільової функції, а числа - зведеними коефіцієнтами цільової функції.

Зауваження. З системи випливає, що , . Справді, при , , , тому , , а тоді оцінки базисних змінних дорівнюють нулеві.

Проаналізуємо зв’язок між величиною цільової функції і вільними змінними.

Випадок 1. Нехай усі значення при вільних змінних у функції невід’ємні , .

Тоді всяке збільшення вільних змінних , , …, приводить до зменшення функції (8). Тому найбільше значення функція буде мати при , тобто у допустимому базисному розв’язку (6). Тоді (6) є оптимальним розв’язком.

Таким чином, умовою оптимальності є умова

, .

Випадок 2. Серед оцінок вільних змінних є принаймні одна від’ємна і при цьому серед коефіцієнтів відповідного їй -го стовпчика матриці немає додатних. У цьому випадку функція є необмеженою в області допустимих розв’язків.

Справді, нехай для деякої вільної змінної оцінка і всі , . Розглянемо всі вільні змінні, крім , які є рівними нулю і підставимо у (5) і (8). Одержимо

, ;

.

Оскільки , то при збільшенні функція f зростає. Разом з тим з (10) випливає, що усі змінні , залежні від x_s, залишаються невід’ємними при довільних як завгодно великих x_s (бо ).

Отже, функція f максимуму не має, оптимального плану не існує, хоч є безліч допустимих планів.

Випадок 3. Є вільна змінна x_s з від’ємною оцінкою , у якої принаймні один коефіцієнт є додатним: . Тоді можна знайти новий опорний план, для якого значення цільової функції є більшим, якщо розглядуваний опорний план невироджений.

Справді, як видно з (11), при збільшення приводить до зростання цільової функції . Збільшення припустиме доти, поки праві частини виразу (10) залишаються невід’ємними при всіх . Тобто для , . Максимально можливе значення , при якому забезпечується невід’ємність змінних в (10), визначається з умови

.

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

 

A 1	…	Am	Am+ 1	…	As	…	An	B
	…			…		…
…	…	…	…	…	…	…	…	…
	…			…		…
…	…	…	…	…	…	…	…	…
	…			…		…
…	…	…	…	…	…	…	…	…
	…			…		…
	…			…		…

(14)

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

Покажемо, як змінюється цільова функція при переході до нового опорного плану (14). Для цього підставимо (14) в (8) або в (11):

.

Оскільки , , то цільова функція зростає з до (на величину ).

Формула (15) нагадує формулу прямокутника жорданових виключень. Запишемо (8) у виді

.

Долучимо це рівняння до системи (4) як таке, що розв’язане відносно невідомої базисної змінної . При проведенні жорданового перетворення з провідним елементом одержимо перетворені елементи

, .

Отже, виконавши жорданове перетворення системи (4), розширеної додаванням рядка зведеної цільової функції (16), одержимо новий допустимий базисний рядок (14), для якого значення цільової функції буде більшим.

Щоб вияснити, чи буде новий базисний розв’язок (14) оптимальним, треба проаналізувати оцінки . Якщо маємо випадок 1, то знайдений план є оптимальним, якщо випадок 2, то оптимального плану не існує. Якщо випадок 3, то описаний процес продовжують. Оскільки кількість опорних планів не перевищує , то процес є скінченний.

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

Теоретично можливий випадок, коли послідовність вироджених опорних планів починає повторюватись – зациклюватись. У цьому випадку розроблені спеціальні прийоми. На практиці зациклюваності майже не буває.