Навигация
3.2 Симплекс-метод
Симплекс-метод — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.
Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану.
Розглянемо опис методу:
Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:
(3.2.1)
(3.2.2)
де X = (x1, …, xn) — вектор змінних, C = (c1, …., cn), B = (b1, …, bm)T, Aj = (a1j, …, amj)T, j = 1, …, n — задані вектори, T — знак транспонування, та 
відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору X. Базис цього плану — 
Тоді
(3.2.3)
(3.2.4)
де 
значення лінійної форми на даному плані. Так як вектор-стовпці матриці A лінійно незалежні, будь який із векторів умов Aj розкладається по ним єдиним чином:
(3.2.5)
(3.2.6)
(3.2.7)
де xij - коефіцієнт розкладання. Система умов
(3.2.8)
zk ≥ 0, xj = 0, j = m + 1, …, n, j ≠ k (3.2.9)
при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної xk при русі по цьому проміню дорівнює θ, тоді значення базисних змінних дорівнюють xi(θ). В цих позначеннях рівняння (5) можна представити в вигляді:
(3.2.10)
помноживши рівняння (3) на θ при j = k та віднявши від рівняння (1), отримаємо:
(3.2.11)
Із рівнянь (10-11) отримаємо:
(3.2.12)
Оскільки xi(θ) при θ = 0 визначають план задачі, то найбільше θ, яке не порушує обмеження xi (θ) ≥ 0, визначається із умови:
(3.2.13)
де I = {i | xik > 0}
В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J та θ > 0. Значення лінійної форми при θ = θ0 визначається із рівнянь (9), (4), (2)
(3.2.14)
де Δk = zk — ck. Очевидно, Δj = 0 для j = 1, …, m.
Нехай 
— початковий базис із m одиничних векторів. Всі дані задачі записуються у вигляді симплекс-таблиці (першої ітерації обчислювального процесу). Симплекс-алгоритм розв'язання задачі лінійного програмування складається із наступних операцій:
1. Знайти Δk = minjΔj. Якщо Δk = 0, тоді план, який розглядається оптимізовано; якщо Δk < 0, вектор Ak вводиться в базис;
2. Знайти θ0 та l для якого 
, із формули (10). Якщо I = Λ — порожня множина, лінійна форма необмежена зверху; якщо I ≠ Λ вектор Al виводиться із базису;
3. По знайденим l, k обчислити нові значення елементів таблиці по формулам
Перетворення (12) замінює вектор коефіцієнтів Xk = (x1k, …, xmk) на одиничний вектор Xk з xlk = 1. В силу монотонного збільшення x0 повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму. Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу,
(3.2.15)
при обмеженнях
(3.2.16)
(3.2.17)
(3.2.18)
яка містить одиничний базис, який складається із векторів An+1, …, An+m. Цим векторам відповідають штучні змінні із значеннями 
, i = 1, …, m. Якщо в оптимальному розв'язку цієї задачі
, вихідна задача не має розв'язку. Якщо ж 
та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які по формулам (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення z0 може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин bi на bi + εi, де εi достатньо малі, при вдалому виборі εi не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.
Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця A-1, обернена до базисної матриці.
Похожие работы
... розвиток як математична теорія лінійного і нелінійного програмування, так і додаток її методів до дослідження різних економічних проблем. У 1949 р. американським математиком Дж. Данцигом (GB Dantzig) був опублікований симплекс-метод - основний метод рішення задач лінійного програмування. Термін «лінійне програмування» вперше з'явився в 1951 р. в роботах Дж. Данцига і Т. Купманса. При всьому ...
... і екстремуми, полягає в послідовному виборі числових значень , після реалізації, якого дана система зважується відносно х. 3. ВИКОРИСТАННЯ МЕТОДУ ЯКОБІ ДЛЯ РІШЕННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ Дано задачу лінійного програмування, у якій потрібно максимізувати z=2xi+3xa при обмеженнях х1+х2+х3=5 х1-х2+х4=3 х1,х2,х3,х4>0 Розглянемо обмеження xj>0 устанавлюючи не заперечність перемі ...
... зумовлюється метою, якої хочуть досягти даною геометричною інтерпретацією та особливостями структури самої задачі, в тому числі й формою її представлення. Для геометричної інтерпретації візьмемо основну задачу лінійного програмування у другій стандартній формі. Для наочності розглянемо найпростіший випадок, коли в системі обмежень (26) і цільовій функції (25) є лише дві змінних, Розглянемо розв' ...
... , а при більшому числі змінних - взагалі неможливим. Незважаючи на це, розгляд графічного методу дасть змогу зробити висновки, що послужать основою для розробки загального методу розв’язання задач лінійного програмування[2]. Перший крок при використанні графічного методу полягає в поданні області допустимих розв’язків, у якій водночас задовольняються всі обмеження моделі. Нехай шукана область ( ...
0 комментариев