Відмінності між версіями «Модифікації симплексного методу»
Tenatin (обговорення • внесок) |
Tenatin (обговорення • внесок) |
||
(не показано одну проміжну версію цього учасника) | |||
Рядок 33: | Рядок 33: | ||
[[Файл:Таблица.PNG]] | [[Файл:Таблица.PNG]] | ||
де <math> B ^ {-1} </math> — матриця, обернена до одиничної, з першої симплексної таблиці. Як видно з наведеної табл. 2.11, вся симплексна таблиця сформована шляхом використання початкових даних (матриця А) та обернення поточного базису <math> B ^ {-1} </math> . Отже, в обчислювальних процедурах модифікованого симплексного методу головна увага зосереджена на мінімізації помилок округлення при обчисленні матриці <math> B ^ {-1} </math> Модифікованим симплексним методом можна скористатись також для зменшення кількості операцій множення. | де <math> B ^ {-1} </math> — матриця, обернена до одиничної, з першої симплексної таблиці. Як видно з наведеної табл. 2.11, вся симплексна таблиця сформована шляхом використання початкових даних (матриця А) та обернення поточного базису <math> B ^ {-1} </math> . Отже, в обчислювальних процедурах модифікованого симплексного методу головна увага зосереджена на мінімізації помилок округлення при обчисленні матриці <math> B ^ {-1} </math> Модифікованим симплексним методом можна скористатись також для зменшення кількості операцій множення. | ||
+ | |||
+ | '''Приклад''' | ||
+ | Посилання http://www.semestr.ru/ks839.html <br> </br> | ||
+ | [[Файл:Пример1.png]] | ||
+ | [[Файл:Пример2.png]] | ||
+ | [[Файл:Пример3.png]] |
Поточна версія на 23:03, 4 травня 2012
Модифікації симплексного методу*
1. Двохетапний симплекс-метод. Проблеми зустрічаються тоді, коли штучні змінні є частиною початкового базисного розв’язку. Використання як М у цільовій функції дуже великих чисел може призвести до помилки округлення
Розглянемо задачу
На першому етапі розв’язується задача виду:
де Неможливо розібрати вираз (невідома помилка): x_{j}(J=n+1,...,n+m)
– штучні змінні. Перший етап характеризується використанням лише великих чисел як коефіцієнтів цільової функції. Очевидно значення цільової функції для оптимального плану буде Неможливо розібрати вираз (невідома помилка): F_{0}(X_{0})=0
. Отже, при Неможливо розібрати вираз (невідома помилка): F_{0}(X_{0})=0
початкова задача має допустимий базисний розв’язок, причому такий, що не містить штучних змінних.
На другому етапі розв’язування задачі як початковий опорний план береться Неможливо розібрати вираз (невідома помилка): X_{0}
, і процес продовжується за звичайним алгорит¬мом симплексного методу. На другому етапі задача не містить штучних змінних, отже, значення, що відповідають Неможливо розібрати вираз (невідома помилка): \pm M , не розглядаються.
Крім того, якщо на першому етапі розв’язання задачі Неможливо розібрати вираз (невідома помилка): F_{0}(X_{0}) < 0
, то це означає, що деякі зі штучних змінних додатні, тобто допустимих планів для початкової задачі не існує, її систе-ма обмежень несумісна, задача розв’язків не має. Отже, немає потреби переходити до другого етапу .
Двохетапний метод застосовують до задач, що вимагають операцій над дуже великими числами, які входять у цільову функцію.
2. Модифікований симплексний метод. Застосування методу виключення змінних Жордана—Гаусса для отримання послідовного ряду симплексних таблиць призводить до накопичення і поширення помилок округлення в такій мірі, що вони спотворюють початкові дані задачі.
З метою зменшення впливу помилок округлення був розроб-лений модифікований симплексний метод. Основні етапи його алгоритму по суті такі ж, як і для симплексного методу. Головна відмінність полягає в тому, що для отримання послідовності симплексних таблиць у модифікованому симплексному методі не застосовується метод виключення змінних Жордана—Гаусса. Допустимо, що розглядається задача лінійного програмування, де базис утворюють останні Неможливо розібрати вираз (невідома помилка): n+m
векторів, які позначимо через Неможливо розібрати вираз (невідома помилка): X_{2} а відповідні їм коефіцієнти цільової функції — через Неможливо розібрати вираз (невідома помилка): C_{2} Аналогічно перші n змінних позначимо через Неможливо розібрати вираз (невідома помилка): X_{1} , а відповідні коефіцієнти цільової функції — через Неможливо розібрати вираз (невідома помилка): C_{1}
. . Коефіцієнти векторів Неможливо розібрати вираз (невідома помилка): X{1} . Х1 у системі обмежень утворюють матрицю А. Тоді схематично першу та останню симплексні таблиці можна подати у вигляді (табл.1):
Таблиця1
де Неможливо розібрати вираз (невідома помилка): B ^ {-1}
— матриця, обернена до одиничної, з першої симплексної таблиці. Як видно з наведеної табл. 2.11, вся симплексна таблиця сформована шляхом використання початкових даних (матриця А) та обернення поточного базису Неможливо розібрати вираз (невідома помилка): B ^ {-1} . Отже, в обчислювальних процедурах модифікованого симплексного методу головна увага зосереджена на мінімізації помилок округлення при обчисленні матриці Неможливо розібрати вираз (невідома помилка): B ^ {-1} Модифікованим симплексним методом можна скористатись також для зменшення кількості операцій множення. Приклад
Посилання http://www.semestr.ru/ks839.html
</br>