logo
vstyp_mpdo

507. Знаходження оптимального розв'язку задачі лінійного програмування. Алгоритм симплексного методу.

Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:

,

де X = (x1, …, xn) — вектор змінних, C = (c1, …., cn), B = (b1, …, bm)T, Aj = (a1j, …, amj)T, j = 1, …, n — задані вектори, T — знак транспонування, та

відмінні від нуля компоненти опорного плану, для полегшення пояснення розташовані на перших m місцях вектору X. Базис цього плану — . Тоді

, (1)

, (2)

де значення лінійної форми на даному плані. Так як вектор-стовпці матриці A лінійно незалежні, будь який із векторів умов Aj розкладається по них єдиним чином:

, (3)

, (4)

де xij коефіцієнт розкладання. Система умов

, (5)

zk ≥ 0, xj = 0, j = m + 1, …, n, j ≠ k (6) при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної xk при русі по цьому променю дорівнює θ, тоді значення базисних змінних дорівнюють xi(θ). В цих позначеннях рівняння (5) можна представити у вигляді

. (7)

помноживши рівняння (3) на θ при j = k та віднявши від рівняння (1), отримаємо

.(8)

Із рівнянь (7-8) отримаємо

. (9)

Оскільки xi(θ) при θ = 0 визначають план задачі, то найбільше θ, яке не порушує обмеження xi (θ) ≥ 0, визначається із умови

. (10)

де I = {i | xik > 0}.

В силу невиродженості задачі мінімум досягається не більш ніж для одного i = J та θ > 0. Значення лінійної форми при θ = θ0 визначається із рівнянь (9), (4), (2)

,

де Δ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)

,

де та перейти до виконання операції (1) з новими значеннями всіх xij = x'ij.