Модифікації симплекс 424h72e 85;ого методу*

Симплекс 424h72e 85;ий метод є ефективною, досить простою процедурою, проте не позбавленою деяких недоліків. Цей факт пояснює численні спроби модифікування симплекс 424h72e 85;ого методу, які можна зустріти в літературі, наприклад [31].

Хоча теоретична основа симплекс 424h72e 85;ого методу гарантує збіжність до оптимального розв’язку за скінченну кількість кроків, але труднощі обчислювального характеру, що виникають внаслідок помилок округлення в процесі машинних розрахунків, у цьому методі не враховані. Такі проблеми зустрічаються передусім тоді, коли штучні змінні є частиною початкового базисного розв’язку. Використання як

де – штучні змінні.

Очевидно значення цільової функції для оптимального плану буде . Отже, при початкова задача має допустимий базисний розв’язок, причому такий, що не містить штучних змінних. На другому етапі розв’язування задачі як початковий опорний план береться Х₀, і процес продовжується за звичайним алгорит­мом симплекс 424h72e 85;ого методу. Завдяки поділу розв’язування задачі на два етапи на кожному з них у процесі обчислень використовуються майже однакові за значеннями числа. Перший етап характеризується використанням лише великих чисел як коефіцієнтів цільової функції, проте на другому етапі задача не містить штучних змінних, отже, значення, що відповідають

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

Двохетапний метод застосовують до задач, що вимагають операцій над дуже великими числами, які входять у цільову функцію. Однак навіть за умови, що така ситуація не склалася, тобто задача не містить штучних змінних, проблеми обчислювального характеру залишаються. Застосування методу виключення змінних Жордана—Гаусса для отримання послідовного ряду симплекс 424h72e 85;их таблиць призводить до накопичення і поширення помилок округлення в такій мірі, що вони спотворюють початкові дані задачі. Розглянемо приклад, в якому помилки округлення пов’язані з визначенням умов допустимості розв’язку. Допустимо, що точне значення деякої базисної змінної , вибрано деякий напрямний вектор і в цьому векторі єдина невід’ємна компонента, що відповідає і-ій (нульовій) базисній змінній, також дорівнює нулю. Тоді вектор вводити до базису не можна. Однак, унаслідок помилки округ к­тора , а значення коефіцієнта, що відповідає і-ій базисній змінній та j-му вектору в симплекс 424h72e 85;ій таблиці — . Тоді вектор буде вибрано для введення до базису.

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

де В^–1 — матриця, обернена до одиничної, з першої симплекс 424h72e 85;ої таблиці. Як видно з наведеної табл. 2.11, вся симплекс 424h72e 85;а таблиця сформована шляхом використання початкових даних (матриця А) та обернення поточного базису В^-1. Отже, в обчислювальних процедурах модифікованого симплекс 424h72e 85;ого методу головна увага зосереджена на мінімізації помилок округлення при обчисленні матриці В^–1.

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