2. Теоретичні основи симплекс-метода.

Теорема 1.

Якщо для деякого вектора P_j, який не входить у базис, виконується умова

Δ_j<0, (j=1,2,3…..n) (для задачі на максимум)

або

Δ_j>0, (j=1,2,3…..n) (для задачі на мінімум),

то можна отримати новий опорний план, для якого значення цільової функції f(x) буде більше (якщо f(x)→max),або менше ( якщо f(x)→min) вихідного; при цьому можуть бути два випадки:

а) якщо координати вектора P_j, який необхідно ввести у базис, недодатні, то задача ЛП не має розв’язку;

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

Теорема 2.

Якщо для всіх векторів P_j, виконується умова

Δ_j≥0, (j=1,2,3…..n) (для задачі на максимум)

або

Δ_j≤0, (j=1,2,3…..n) (для задачі на мінімум),

то опорний план Х^*=((х₁)^*, (х₂)^*, ......... (х_n)^*) є оптимальним.

Якщо після побудови симплекс-таблиці виявилось, що виконуються умови Т.1 (пункт а)), або Т.2 розв’язання задачі припиняється. Якщо виконуються умови Т.1 (пункт б)), то потрібно перейти до нового оптимального опорного плану, побудувавши наступну симплексну таблицю. Для переходу до нового опорного плану треба один вектор вивести з базису і на його місце ввести новий вектор, який не належить базису. У базис вводять вектор, якому відповідає найбільша за абсолютною величиною від’ємна оцінка Δ_j. Нехай існує така оцінка в k- му стовпці, тобто max| Δ_j | = Δ_k.

Δ_j≤0

Тоді вектор Р_к вводимо у новий базис. Для знаходження вектора Р_r, який необхідно вивести, обчислюють співвідношення

Q= min(b_i/a_ik) ( i=1,2…..m) ,

мінімальне значення якого досягається при i=r. Елемент a_rk називається розв’язувальним .

Рядок Р_r і стовпець Р_к на перетині яких знаходиться розв’язувальний елемент a_rk, називають розв’язувальним. Для перерахунку елементів нової (наступної) симплекс – таблиці користуються методом Жордана – Гауса.

3. Поняття виродженності задач лп.

У випадку не виродженої задачі ЛП симплекс-метод за скінченну кількість кроків дає можливість одержати оптимальний план, або встановити, що задача не має розв’язків. Це випливає з того, що кожному оптимальному плану відповідає свій базис, причому кількість базисів не перевищує , де n – кількість змінних задачі, m – ранг матриці А.

При використанні симплекс-методу вважалося, що всі вільні члени >0, ( ) додатні як у вихідній системі обмежень, так і в системах обмежень, які одержуємо після чергових ітерацій. Якщо в деяких рівняннях вільні члени дорівнюють нулю, то у відповідному цій системі опорному плані базисні змінні приймають нульові значення. Опрний план, у якому хочаб одна з базисних змінних дорівнює нулю, називається виродженим. Задача ЛП, яка має хоча б один вироджений опорний план, називається виродженою задачею ЛП.

Вироджений опорний план може бути або початковим або виникнути у процесі розв’язання задачі.

Приклад 1.

За початковий базис можна вибрати Р₁, Р₄, Р₅ або Р₂, Р₄, Р₅, тоді початковий опорний план Х=(0,0,0,1,1) є виродженим, так як базисна змінна х₁=0 або х₂=0. Для обох початкових планів z=0, тобто у випадку виродженності значення цільової функції може повторюватись навідь при зміні базису.

Поточний базисний розв’язок може стати виродженим, якщо виникає невизначеність у виборі ключового рядка, тобто одержуємо однакове мінімальне значення симплексного відношення

для декількох значень k, де s – номер вектора, який вводять до базису. У цьому випадку також при зміні складу базисних змінних значення цільової функції буде залишатись незмінним.

Оскільки число наборів векторів скінченне, то після деякого числа ітерацій дійдемо до одного з висновків:

1. розв’язок оптимальний;

2. задача не розв’язувана;

3. отриманий базисний розв’язок був на попередніх ітераціях. Це значить, що процес обчислення зациклився, тобто після ряду ітерацій ми повертаємося до раніше використаного базису.