Відмінності між версіями «Модифікації симплексного методу»
Tenatin (обговорення • внесок) |
Tenatin (обговорення • внесок) |
||
| Рядок 10: | Рядок 10: | ||
x_{i,j}\ge 0 (j=1,2,...,n+m) \\ | x_{i,j}\ge 0 (j=1,2,...,n+m) \\ | ||
\end{array}} \right.</math></center> | \end{array}} \right.</math></center> | ||
| − | де <math> x {j}(J=n+1,...,n+m)</math> | + | де <math> x {j}(J=n+1,...,n+m)</math> – штучні змінні. Перший етап характеризується використанням лише великих чисел як коефіцієнтів цільової функції. Очевидно значення цільової функції для оптимального плану буде <math>F{0}(X{0})=0 </math>. Отже, при <math>F{0}(X{0})=0 </math> початкова задача має допустимий базисний розв’язок, причому такий, що не містить штучних змінних. |
| + | На другому етапі розв’язування задачі як початковий опорний план береться <math> X{0} </math> , і процес продовжується за звичайним алгорит¬мом симплексного методу. На другому етапі задача не містить штучних змінних, отже, значення, що відповідають <math> \pm M </math> , не розглядаються. | ||
| + | Крім того, якщо на першому етапі розв’язання задачі <math> F{0}(X{0}) < 0 </math> , то це означає, що деякі зі штучних змінних додатні, тобто допустимих планів для початкової задачі не існує, її систе-ма обмежень несумісна, задача розв’язків не має. Отже, немає потреби переходити до другого етапу . | ||
| + | Двохетапний метод застосовують до задач, що вимагають операцій над дуже великими числами, які входять у цільову функцію. | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | 2. Модифікований симплексний метод. Застосування методу виключення змінних Жордана—Гаусса для отримання послідовного ряду симплексних таблиць призводить до накопичення і поширення помилок округлення в такій мірі, що вони спотворюють початкові дані задачі. | ||
| + | З метою зменшення впливу помилок округлення був розроб-лений модифікований симплексний метод. Основні етапи його алгоритму по суті такі ж, як і для симплексного методу. Головна відмінність полягає в тому, що для отримання послідовності симплексних таблиць у модифікованому симплексному методі не застосовується метод виключення змінних Жордана—Гаусса. Допустимо, що розглядається задача лінійного програмування, де базис утворюють останні <math> n+m </math> векторів, які позначимо через <math> X{2} </math> а відповідні їм коефіцієнти цільової функції — через <math> C{2} </math> Аналогічно перші n змінних позначимо через <math> X{1} </math> , а відповідні коефіцієнти цільової функції — через <math> C{1} </math>. . Коефіцієнти векторів <math> X{1} </math>. Х1 у системі обмежень утворюють матрицю А. Тоді схематично першу та останню симплексні таблиці можна подати у вигляді (табл. 2.11): | ||
| + | Таблиця 2.11 | ||
| + | |||
| + | [[Файл:Таблица.PNG]] | ||
| + | де <math> B^(-1) </math> | ||
Версія за 09:37, 4 травня 2012
Модифікації симплексного методу* 1. Двохетапний симплекс-метод. Проблеми зустрічаються тоді, коли штучні змінні є частиною початкового базисного розв’язку. Використання як М у цільовій функції дуже великих чисел може призвести до помилки округлення Розглянемо задачу (2.60)—(2.61). Процес розв’язування у два етапи. На першому етапі розв’язується задача виду:
де Неможливо розібрати вираз (невідома помилка): 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 у системі обмежень утворюють матрицю А. Тоді схематично першу та останню симплексні таблиці можна подати у вигляді (табл. 2.11):
Таблиця 2.11
де Неможливо розібрати вираз (невідома помилка): B^(-1)
