3.4.2. Модифікації симплексного методу

Симплексний метод є ефективною, досить простою процедурою, проте не позбавленою деяких недоліків. Хоча теоретична основа симплексного методу гарантує збіжність до оптимального розв’язку за скінченну кількість кроків, але труднощі обчислювального характеру, що виникають внаслідок помилок округлення в процесі машинних розрахунків, у цьому методі не враховані. Такі проблеми зустрічаються передусім тоді, коли штучні змінні є частиною початкового базисного розв’язку. Використання як  М у цільовій функції дуже великих чисел може призвести до помилки округлення, що зумовлена операціями над групою чисел, яка містить як дуже великі, так і відносно малі числа.

З метою зменшення впливу помилок округлення був розроблений модифікований симплексний метод. Основні етапи його алгоритму по суті такі ж, як і для симплексного методу. Головна відмінність полягає в тому, що для отримання послідовності симплексних таблиць у модифікованому симплексному методі не застосовується метод виключення змінних Жордана—Гаусса. Допустимо, що розглядається задача лінійного програмування, де базис утворюють останні n+m векторів, які позначимо через Х₂, а відповідні їм коефіцієнти цільової функції — через С₂. Аналогічно перші n змінних позначимо через Х₁, а відповідні коефіцієнти цільової функції — через С₁. Коефіцієнти векторів Х₁ у системі обмежень утворюють матрицю А. Тоді схематично першу та останню симплексні таблиці можна подати у вигляді таблиці 3.3., де В^–1 — матриця, обернена до одиничної, з першої симплексної таблиці. Як видно з наведеної таблиці вся симплексна таблиця сформована шляхом використання початкових даних (матриця А) та обернення поточного базису В^-1. Отже, в обчислювальних процедурах модифікованого симплексного методу головна увага зосереджена на мінімізації помилок округлення при обчисленні матриці В^–1.

Таблиця 3.3.

Крім зменшення помилок округлення, модифікований симплексний метод зменшує тривалість розрахунків. Зокрема, якщо в матриці обмежень А відносна кількість нульових елементів велика, то модифікованим симплексним методом можна скористатись для зменшення кількості операцій множення (порівняно зі звичайним симплексним методом, у якому елементи таблиці, особливо нульові, в процесі послідовних операцій постійно змінюються). Взагалі відомо, що потрібний для реалізації модифікованого симплексного методу обсяг обчислень тим менший, чим менша щільність матриці А (щільність — це відношення кількості ненульових елементів до загальної кількості елементів матриці) та відношення кількості обмежень до кількості змінних.