Курсовая работа: Аналіз методів рішення задачі лінійного програмування симплекс методом

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

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

(3.2.10)

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

(3.2.11)

Із рівнянь (10-11) отримаємо:

(3.2.12)

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

(3.2.13)

де I = {i | x_ik > 0}

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

(3.2.14)

де Δ_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 виводиться із базису;

3. По знайденим l, k обчислити нові значення елементів таблиці по формулам

Перетворення (12) замінює вектор коефіцієнтів X_k = (x_1k , …, x_mk ) на одиничний вектор X_k з x_lk = 1. В силу монотонного збільшення x0 повернення до вже пройденого плану неможливе, а із скінченності кількості опорних планів випливає скінченність алгоритму. Початковий опорний план з одиничним базисом можна отримати, розв'язавши описаним алгоритмом допоміжну задачу,

(3.2.15)

при обмеженнях

(3.2.16)

(3.2.17)

(3.2.18)

яка містить одиничний базис, який складається із векторів A_n+1 , …, A_n+m . Цим векторам відповідають штучні змінні із значеннями , i = 1, …, m. Якщо в оптимальному розв'язку цієї задачі, вихідна задача не має розв'язку. Якщо ж та задача невироджена, оптимальний базис складається лише тільки із векторів вихідної задачі, які по формулам (12) перетворені в одиничну матрицю. Якщо задача має невироджені плани, значення z₀ може не збільшуватись на ряді ітерацій. Це відбувається через те, що значення відповідних дорівнює нулю та визначається неоднозначно. В таких випадках монотонність методу порушується і може трапитись зациклювання, тобто, повернення до вже пройденого базису. Невелика зміна вектора обмежень задачі, яка полягає в заміні величин b_i на b_i + ε_i , де ε_i достатньо малі, при вдалому виборі ε_i не змінюють множину векторів оптимального опорного плану вихідної задачі і робить її невиродженою.

Описаний вище алгоритм називається першим (або прямим) алгоритмом симплекс-методу. Також відомий другий алгоритм (алгоритм із оберненою матрицею). В ньому перетворюється лише матриця A-1, обернена до базисної матриці.

3.3 Двоїстий симплекс-метод

Двоїстий симплекс-метод розроблений згодом після прямого симплекс-методу, і який є, по суті, симплекс-методом розв'язання двоїстої задачі лінійного програмування, але сформульованої в термінах вихідної задачі.

Симплекс метод приміняється для рішення задач с невідємними вільними членами в_і і вільні у виборі знаку приведеними коефіцієнтами цільової функції с _j ^’ . Іноді буває легше знайти базис, який задовільняє ознаку оптимальності (усі с _j ^’ ≥0), але не задовільняє критерії допуску (не всі в_і ≥0). Варіант симплекс метода, який приміняється для рішення таких задач, називається двоїстим симплекс методом. За його допомоги рішаються задачі лінійного програмування виду:

(4.3.1)