Відмінності між версіями «Двоїстий симплексний метод»
(Створена сторінка: \min \,\,F=CX) |
|||
| (не показано 40 проміжних версій цього учасника) | |||
| Рядок 1: | Рядок 1: | ||
| − | \min \,\,F=CX | + | Двоїстий симплексний метод |
| + | |||
| + | Як відомо кожній [http://wiki.kspu.kr.ua/index.php/Розв’язування_задачі_лінійного_програмування_симплексним_методом._Геометрична_інтерпретація_симплексного_методу задачі лінійного програмування] можна пос-тавити у відповідність двоїсту задачу. Теоремами двоїстості встановлено зв’язок між розв’язками прямої та двоїстої задач. Для знаходження розв’язку однієї зі спряжених задач можна пе-рейти до двоїстої і, використовуючи її оптимальний план, визна-чити оптимальний план початкової. | ||
| + | |||
| + | Перехід до [http://wiki.kspu.kr.ua/index.php/Економічна_інтерпретація_прямої_та_двоїстої_задач_ЛП._Правила_побудови_двоїстих_задач двоїстої задачі] не обов’язковий. Легко помітити, що звичайна симплексна таблиця в стовпчиках містить початкову задачу, а в рядках — двоїсту. Оцінками плану прямої задачі є рядок <math>\Delta_{j} =F_{j} -c_{j}</math> <math>(j=\overline {1,n})</math> а оцінками плану двоїстої — стовпчик «План» з компонентами вектора вільних членів системи обмежень В. Отже, розв’язуючи пряму задачу, симплексний метод дає змогу одночасно знаходити і розв’язок двоїстої задачі. Однак двоїсту задачу можна також розв’язати за таблицею, в якій записана пряма, а відшукавши оптимальний план двоїстої задачі, разом з тим отримати розв’язок початкової задачі. Такий спосіб розв’язання задачі лінійного програмування має назву двоїстого симплексного методу. Прямий та двоїстий симплексні методи пов’язані між собою. | ||
| + | Нехай необхідно розв’язати [http://wiki.kspu.kr.ua/index.php/Розв’язування_задачі_лінійного_програмування_симплексним_методом._Геометрична_інтерпретація_симплексного_методу задачу лінійного програмування], подану в канонічному виді: | ||
| + | |||
| + | <math>min \,\,F=CX</math> (1) | ||
| + | |||
| + | <math>AX=B</math> (2) | ||
| + | |||
| + | <math>X\ge 0</math> (3) | ||
| + | |||
| + | Тоді двоїстою до неї буде така задача: | ||
| + | |||
| + | <math>max \,\,Z=BY</math> (4) | ||
| + | |||
| + | <math>YA\le C</math> (5) | ||
| + | |||
| + | За алгоритмом двоїстого симплексного методу як перший опорний план вибирається деякий допустимий розв’язок двоїстої задачі (іноді в літературі його називають «псевдопланом») і зберігається його допустимість для двоїстої задачі упродовж всіх кроків. | ||
| + | |||
| + | Допустимо, що початковий базис складається з m векторів <math>D=(A_{1} ,A_{2} ,...A_{l} ,...,A_{m} )</math> , причому хоча б одна з компонент вектора <math>X=D^{-1}B=(x_{1} ,x_{2} ,...,x_{l} ,...,x_{n} )</math> від’ємна. Нехай <math>x_{l} <0</math>, однак справджується критерій оптимальності плану, тобто всі оцінки векторів <math>\Delta_{j} =F_{j} -c_{j} \ge 0</math> <math>(j=\overline {1,n})</math> | ||
| + | |||
| + | Отже, вектор, що відповідає компоненті <math>x_{l} <0</math>, потрібно виключити з базису початкової задачі, а вектор двоїстої задачі, що відповідає від’ємній оцінці, включити до базису двоїстої. | ||
| + | |||
| + | У прямому симплекс-методі спочатку виявляють змінну, яку слід ввести у базис, а в двоїстому симплекс-методі навпаки — спочатку визначають змінну, яку виключають з базису, а потім змінну, яку вводять у базис. | ||
| + | |||
| + | У літературі [19, 22, 28, 31] зустрічаються різні варіанти двоїстого симплексного методу, які не мають принципових відмінностей. Розглянемо такий алгоритм двоїстого симплексного методу: | ||
| + | |||
| + | 1. Необхідно звести всі обмеження задачі до виду «<math>.\le </math>», ввести додаткові невід’ємні змінні, визначити початковий базис та пер-ший опорний план <math>X=(b_{1} ,b_{2} ,...,b_{m} )</math> | ||
| + | |||
| + | 2. Якщо всі оцінки векторів <math>\Delta_{j} =F_{j} -c_{j} \le 0</math> і компоненти вектора-стовпчика «План» <math>(b_{1} ,b_{2} ,...,b_{m} )\ge 0</math> для всіх <math>i=\overline{1,m}</math> то задача розв’язана. Інакше необхідно вибрати найбільшу за модулем компоненту <math>b_{l} <0</math> і відповідну змінну <math>x_{l} </math> виключити з базису. | ||
| + | |||
| + | 3. Виконавши крок методу повних виключень Жордана—Гаусса, переходять до наступної симплексної таблиці (Переходять до пункту 2). | ||
| + | Зазначимо, що для задачі знаходження максимального зна-чення цільової функції за наведеним алгоритмом необхідно пе-рейти до цільової функції <math>{F}'=-F</math>, або дещо змінити сам алгоритм. | ||
| + | Детальне доведення всіх кроків алгоритму двоїстого симплек-с¬ного методу розглянуто в [10]. | ||
Поточна версія на 10:48, 5 травня 2012
Двоїстий симплексний метод
Як відомо кожній задачі лінійного програмування можна пос-тавити у відповідність двоїсту задачу. Теоремами двоїстості встановлено зв’язок між розв’язками прямої та двоїстої задач. Для знаходження розв’язку однієї зі спряжених задач можна пе-рейти до двоїстої і, використовуючи її оптимальний план, визна-чити оптимальний план початкової.
Перехід до двоїстої задачі не обов’язковий. Легко помітити, що звичайна симплексна таблиця в стовпчиках містить початкову задачу, а в рядках — двоїсту. Оцінками плану прямої задачі є рядок Неможливо розібрати вираз (невідома помилка): \Delta_{j} =F_{j} -c_{j}
Неможливо розібрати вираз (невідома помилка): (j=\overline {1,n})
а оцінками плану двоїстої — стовпчик «План» з компонентами вектора вільних членів системи обмежень В. Отже, розв’язуючи пряму задачу, симплексний метод дає змогу одночасно знаходити і розв’язок двоїстої задачі. Однак двоїсту задачу можна також розв’язати за таблицею, в якій записана пряма, а відшукавши оптимальний план двоїстої задачі, разом з тим отримати розв’язок початкової задачі. Такий спосіб розв’язання задачі лінійного програмування має назву двоїстого симплексного методу. Прямий та двоїстий симплексні методи пов’язані між собою.
Нехай необхідно розв’язати задачу лінійного програмування, подану в канонічному виді:
Неможливо розібрати вираз (невідома помилка): min \,\,F=CX
(1)
Неможливо розібрати вираз (невідома помилка): AX=B
(2)
Неможливо розібрати вираз (невідома помилка): X\ge 0
(3)
Тоді двоїстою до неї буде така задача:
Неможливо розібрати вираз (невідома помилка): max \,\,Z=BY
(4)
Неможливо розібрати вираз (невідома помилка): YA\le C
(5)
За алгоритмом двоїстого симплексного методу як перший опорний план вибирається деякий допустимий розв’язок двоїстої задачі (іноді в літературі його називають «псевдопланом») і зберігається його допустимість для двоїстої задачі упродовж всіх кроків.
Допустимо, що початковий базис складається з m векторів Неможливо розібрати вираз (невідома помилка): D=(A_{1} ,A_{2} ,...A_{l} ,...,A_{m} )
, причому хоча б одна з компонент вектора Неможливо розібрати вираз (невідома помилка): X=D^{-1}B=(x_{1} ,x_{2} ,...,x_{l} ,...,x_{n} )
від’ємна. Нехай Неможливо розібрати вираз (невідома помилка): x_{l} <0
, однак справджується критерій оптимальності плану, тобто всі оцінки векторів Неможливо розібрати вираз (невідома помилка): \Delta_{j} =F_{j} -c_{j} \ge 0
Неможливо розібрати вираз (невідома помилка): (j=\overline {1,n})
Отже, вектор, що відповідає компоненті Неможливо розібрати вираз (невідома помилка): x_{l} <0 , потрібно виключити з базису початкової задачі, а вектор двоїстої задачі, що відповідає від’ємній оцінці, включити до базису двоїстої.
У прямому симплекс-методі спочатку виявляють змінну, яку слід ввести у базис, а в двоїстому симплекс-методі навпаки — спочатку визначають змінну, яку виключають з базису, а потім змінну, яку вводять у базис.
У літературі [19, 22, 28, 31] зустрічаються різні варіанти двоїстого симплексного методу, які не мають принципових відмінностей. Розглянемо такий алгоритм двоїстого симплексного методу:
1. Необхідно звести всі обмеження задачі до виду «Неможливо розібрати вираз (невідома помилка): .\le », ввести додаткові невід’ємні змінні, визначити початковий базис та пер-ший опорний план Неможливо розібрати вираз (невідома помилка): X=(b_{1} ,b_{2} ,...,b_{m} )
2. Якщо всі оцінки векторів Неможливо розібрати вираз (невідома помилка): \Delta_{j} =F_{j} -c_{j} \le 0
і компоненти вектора-стовпчика «План» Неможливо розібрати вираз (невідома помилка): (b_{1} ,b_{2} ,...,b_{m} )\ge 0
для всіх Неможливо розібрати вираз (невідома помилка): i=\overline{1,m}
то задача розв’язана. Інакше необхідно вибрати найбільшу за модулем компоненту Неможливо розібрати вираз (невідома помилка): b_{l} <0
і відповідну змінну Неможливо розібрати вираз (невідома помилка): x_{l}
виключити з базису.
3. Виконавши крок методу повних виключень Жордана—Гаусса, переходять до наступної симплексної таблиці (Переходять до пункту 2). Зазначимо, що для задачі знаходження максимального зна-чення цільової функції за наведеним алгоритмом необхідно пе-рейти до цільової функції Неможливо розібрати вираз (невідома помилка): {F}'=-F , або дещо змінити сам алгоритм. Детальне доведення всіх кроків алгоритму двоїстого симплек-с¬ного методу розглянуто в [10].
