Відмінності між версіями «Модифікації симплексного методу»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
Рядок 19: Рядок 19:
 
  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>F{0}(X{0})=0 </math>. Отже, при <math>F{0}(X{0})=0 </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> X_{0} </math> , і процес продовжується за звичайним алгорит¬мом симплексного методу.  На другому етапі задача не містить штучних змінних, отже, значення, що відповідають <math> \pm M </math> , не розглядаються.
−
Крім того, якщо на першому етапі розв’язання задачі <math> F{0}(X{0}) < 0 </math>  , то це означає, що деякі зі штучних змінних додатні, тобто допустимих планів для початкової задачі не існує, її систе-ма обмежень несумісна, задача розв’язків не має. Отже, немає потреби переходити до другого етапу .
+
Крім того, якщо на першому етапі розв’язання задачі <math> F_{0}(X_{0}) < 0 </math>  , то це означає, що деякі зі штучних змінних додатні, тобто допустимих планів для початкової задачі не існує, її систе-ма обмежень несумісна, задача розв’язків не має. Отже, немає потреби переходити до другого етапу .
 
Двохетапний метод застосовують до задач, що вимагають операцій над дуже великими числами, які входять у цільову функцію.
 
Двохетапний метод застосовують до задач, що вимагають операцій над дуже великими числами, які входять у цільову функцію.
  
Рядок 28: Рядок 28:
  
 
'''2. Модифікований симплексний метод.''' Застосування методу виключення змінних Жордана—Гаусса для отримання послідовного ряду симплексних таблиць призводить до накопичення і поширення помилок округлення в такій мірі, що вони спотворюють початкові дані задачі.
 
'''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):
+
З метою зменшення впливу помилок округлення був розроб-лений модифікований симплексний метод. Основні етапи його алгоритму по суті такі ж, як і для симплексного методу. Головна відмінність полягає в тому, що для отримання послідовності симплексних таблиць у модифікованому симплексному методі не застосовується метод виключення змінних Жордана—Гаусса. Допустимо, що розглядається задача лінійного програмування, де базис утворюють останні <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 у системі обмежень утворюють матрицю А. Тоді схематично першу та останню симплексні таблиці можна подати у вигляді (табл.1):
−
                                                   Таблиця
+
                                                   Таблиця1
  
 
[[Файл:Таблица.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> Модифікованим симплексним методом можна скористатись також для зменшення кількості операцій множення.

Версія за 10:42, 4 травня 2012

Модифікації симплексного методу*
1. Двохетапний симплекс-метод. Проблеми зустрічаються тоді, коли штучні змінні є частиною початкового базисного розв’язку. Використання як М у цільовій функції дуже великих чисел може призвести до помилки округлення Розглянемо задачу

Неможливо розібрати вираз (невідома помилка): \mathbf{maxF=c_1x_1+c_2x_2+...+c_nx_n}


Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} b_{1}=a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n} \\ b_{2}=a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n} \\ ................................ \\ b_{m}=a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n} \\ x_{i,j}\ge 0 (j=1,2,...,n+m) \\ \end{array}} \right.
. Процес розв’язування у два етапи.

На першому етапі розв’язується задача виду:

Неможливо розібрати вираз (невідома помилка): \left\{ {\begin{array}{l} b_{1}=a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}+x_{n+1} \\ b_{2}=a_{21}x_{1}+a_{22}x_{2}+...+a_{2n}x_{n}+x_{n+2} \\ ................................ \\ b_{m}=a_{m1}x_{1}+a_{m2}x_{2}+...+a_{mn}x_{n}+x_{n+m} \\ x_{i,j}\ge 0 (j=1,2,...,n+m) \\ \end{array}} \right.

де Неможливо розібрати вираз (невідома помилка): 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

Таблица.PNG де Неможливо розібрати вираз (невідома помилка): B ^ {-1} 

— матриця, обернена до одиничної, з першої симплексної таблиці. Як видно з наведеної табл. 2.11, вся симплексна таблиця сформована шляхом використання початкових даних (матриця А) та обернення поточного базису Неможливо розібрати вираз (невідома помилка):  B ^ {-1} 
. Отже, в обчислювальних процедурах модифікованого симплексного методу головна увага зосереджена на мінімізації помилок округлення при обчисленні матриці Неможливо розібрати вираз (невідома помилка):  B ^ {-1} 
Модифікованим симплексним методом можна скористатись також для зменшення кількості операцій множення.
Отримано з https://wiki.cusu.edu.ua/index.php?title=Модифікації_симплексного_методу&oldid=66736