Моделювання і методика рішення задач лінійного програмування

2. Моделювання і методика рішення задач лінійного програмування

2.1 Різновиди форм моделі задач лінійного програмування

2.1.1 Загальна форма моделі

Загальна форма моделі задачі лінійного програмування характеризується наступним:

Знайти сукупність значень n змінних  що задовольняють системі обмежень:

і умові невід’ємності:

,

для яких лінійна функція (цільова функція)  досягає екстремуму (максимуму або мінімуму) [9].

2.1.2 Стандартна форма моделі

Знайти сукупність значень n змінних  що задовольняють системі обмежень:

і умові невід’ємності:

,

для яких лінійна функція (цільова функція)  досягає максимуму.

Якщо ввести у розгляд матрицю:

і вектори:

, , ,

то стандартна форма моделі матиме вид:

Задачу ЛП в стандартній формі зручно вирішувати графічним методом, якщо число змінних дорівнює двом () [1].

2.1.3 Канонічна форма моделі

Знайти сукупність значень n змінних  що задовольняють системі рівнянь:

()

і умові невід’ємності:

(),

для яких цільова функція  досягає максимуму.

Компактна форма моделі має вид:

,

,

. [9].

2.2 Симплекс-метод

Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану [6].

Опишемо метод.

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

,

де X = (x₁, …, x_n) — вектор змінних,

C = (c₁, …., c_n), B = (b₁, …, b_m)^T,

A_j = (a_1j, …, a_mj)^T, j = 1, …, n — задані вектори,

T — знак транспонування, та

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

, (1)

, (2)

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

, (3)

, (4)

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

, (5)

z_k ≥ 0, x_j = 0, j = m + 1, …, n, j ≠ k (6)

при заданому k визначає в просторі змінних задачі промінь, який виходить із точки, яка відповідає опорному плану, що розглядається. Нехай значення змінної x_k при русі по цьому променю дорівнює θ, тоді значення базисних змінних дорівнюють x_i(θ). В цих позначеннях рівняння (5) можна представити в виді

. (7)

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

. (8)

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

. (9)

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

. (10)

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

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

,

де Δ_k = z_k — c_k. Очевидно, Δ_j = 0 для j = 1, …, m.

Нехай  — початковий базис із m одиничних векторів. Всі дані задачі записуються у вигляді симплекс-таблиці (першої ітерації обчислювального процесу). Симплекс-алгоритм розв'язання задачі лінійного програмування складається із наступних операцій:

1.  знайти Δ_k = min_jΔ_j. Якщо Δ_k = 0, тоді план, який розглядається оптимізовано; якщо Δ_k < 0, вектор A_k вводиться в базис;

2.  знайти θ₀ та l, для якого , із формули (10). Якщо I = Λ — порожня множина, лінійна форма необмежена зверху; якщо I ≠ Λ вектор A_l виводиться із базису;