3. Сутність застосування симплекс-методу для рішення військово-спеціальних задач.

Основу симплекс-методу складає представлення множини допустимих рішень деяким багатогранником (симплексом) у n - мірному просторі й спрямуванні руху до крайньої по відношенню до градієнта точки симплекса для виявлення оптимального рішення. Координати вершин симплекса називаються опорними рішеннями.

Алгоритм рішення задачі лінійного програмування за симплекс-методом являє собою послідовність ітераційних процедур перебору варіантів значень базисних змінних та їх заміни вільними і навпаки. На кожному кроці ітерації здійснюється перевірка отриманого варіанта рішення задачі на допустимість та оптимальність і визначається подальший напрямок дій для отримання кінцевого результату. Процес продовжується до отримання мінімального значення цільової функції.

Для наочності та більш глибокого засвоєння алгоритм подається на прикладі рішення конкретної задачі.

Приклад. На позиційний район, що займають війська та об’єкти тилу, противник може здійснювати наліт засобами повітряного нападу (ЗПН) на двох висотах. Відомо, що в атаках з малих висот беруть участь максимум 100 літаків, із середніх та великих висот – 150 літаків. У розпорядженні протидіючої сторони є два типи зенітно-ракетних комплексів (3РК) – висотні та маловисотні, для яких відповідні імовірності ураження цілей p_ij наведені в таблиці 3.

Таблиця 3

Тип	Імовірність ураження ЗПН на висотах
ЗРК	малих	середніх та великих
Маловисотні	0,8	0,25
Висотні	0,25	0,8

Макс. число ЗПН на висотах

100

150

Потрібно визначити розподіл 3РК так, щоб, з одного боку, математичне очікування числа знищених ЗПН було не менше того числа літаків, яке може брати участь у нальоті на даній висоті, і з іншого – розхід ракет при цьому був мінімальним.

Позначимо кількість стрільб i-м ЗРК по j-й групі літаків (залежно від висоти) через X_ij .

Цільова функція та система умов-обмежень відповідно мають вигляд:

L = Х₁₁ + Х₁₂ + Х₂₁ + Х₂₂  min ,

0

(3.1)

,8 X₁₁+ 0,25X₂₁  100;

0,25X₁₂ + 0,8X₂₂  150,

Перш за все здійснюється приведення задачі до виду основної задачі лінійного програмування. З цією метою в систему умов-обмежень необхідно ввести вільні змінні (у нашому випадку дві – X₅, X₆) для перетворення її із системи нерівностей у систему рівнянь та, за необхідністю (при умові максимізації цільової функції) здійснюється підстановка L₁ = -L. Для симплекс-методу цільова функція й система умов-обмежень об’єднуються в одну загальну систему рівнянь. Після виконання вказаних операцій отримаємо нову систему рівнянь:

L = Х₁₁ + Х₁₂ + Х₂₁ + Х₂₂  min;

0,8 X₁₁+ 0,25X₂₁ + X₅ = 100; (3.2)

0,25X₁₂ + 0,8X₂₂ + X₆ = 150.

На попередньому етапі симплекс-методу будується перше пробне рішення за допомогою тільки вільних змінних та цільової функції L. Це рішення є першим опорним рішенням або стандартною формою:

L - Х₁₁ - Х₁₂ - Х₂₁ - Х₂₂ = 0;

0,8 X₁₁+ 0,25X₂₁ + X₅ = 100; (3.3)

0,25X₁₂ + 0,8X₂₂ + X₆ = 150.

Змінні L, X₅, X₆ – є базисними змінними, X₁₁ , X₁₂ , X₂₁ , X₂₂ – небазисними (вільними). Вільні змінні й цільова функція дорівнюють 0, а базисні змінні - відповідним вільним членам рівнянь.

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

На першому кроці алгоритму у відповідності до стандартної форми складається симплекс-таблиця, яка містить рядки базисних змінних і цільової функції, визначені через вільні члени і вільні змінні. Для (3) симплекс-таблиця має вигляд:

Таблиця 4

Базисні	Вільні	Вільні змінні
змінні	члени	Х11	Х12	Х21	Х22
L	0	-1	-1	-1	-1
Х5	100	-0,8	0	-0,25	0
Х 6	150	0	-0,25	0	-0,8

Як видно з табл. 4, симплекс-таблиця – це те ж саме базисне рішення, тільки у табличній формі. Вона відповідає одній з вершин симплекса. Кожна вершина симплекса визначається деяким способом розбиття вихідних змінних на базисні й вільні. При обході всіх вершин симплекса здійснюється послідовний обмін однієї базисної змінної на вільну та перевірка отриманого базисного рішення на допустимість і оптимальність. Якщо отримане базисне

рішення недопустиме або допустиме, але неоптимальне, здійснюється пошук пари для обміну і подальший перерахунок симплекс-таблиці у відповідності до алгоритму методу (рис. 3).

Розглянемо детальніше усі блоки алгоритму симплекс-методу.

Перевірка допустимості рішення: перевіряється стовпець вільних членів; рішення допустиме, якщо у стовпці, виключаючи рядок L, не знаходиться ні одного від’ємного елемента.

Провівши перевірку на допустимість рішення таблиці 4, можна зробити висновок, що отримане для нашого прикладу рішення за стандартною формою є допустимим.

Перевірка оптимальності: рішення оптимальне, якщо воно допустиме і в рядку L всі елементи, окрім 1-го стовпця, невід’ємні.

У таблиці 4 усі елементи вільних змінних у рядку L мають від’ємні значення. Отже, таблиця 2 представляє допустиме неоптимальне рішення і в подальшому виконання алгоритму рішення задачі буде здійснюватися по правій гілці блок-схеми (рис 3).

З А К Л Ю Ч Е Н Н Я

Слід відмітити, що алгебраїчний та геометричний методи рішення задач лінійного програмування широкого практичного використання не отримали через надто велику кількість обчислень у першого (особливо при значній кількості змінних) та обмеженість у застосуванні другого (тільки для двох змінних).

Серед методів лінійного програмування найбільш широке застосування знайшли симплекс-метод та транспортна задача. На відміну від попередніх вони дозволяють вирішувати широкий клас задач, володіють високим ступенем сходимості алгоритмів (результат отримується за обмежену кількість кроків ітерації) та чутливості на екстремум цільової функції. До того ж алгоритми за вказаними методами просто реалізуються для рішення задач з використанням обчислювальної техніки.

Основні терміни та визначення:

1. Математичне програмування - розділ теорії дослідження операцій, який займається вивченням задач відшукання екстремуму функцій на деякій множині та розробкою методів рішення цих задач.

2. Лінійне програмування – розділ математичного програмування, що вивчає задачу відшукання максимуму (мінімуму) лінійної функції при лінійних обмеженнях у вигляді рівнянь або нерівностей.

3. Нелінійне програмування – розділ математичного програмування, у якому вивчаються методи рішення і характер екстремуму в задачах оптимізації з нелінійною цільовою функцією або множиною, що визначається нелінійними обмеженнями.

4. Опукле програмування – розділ математичного програмування, що вивчає задачі мінімізації, в яких функція, що мінімізується, опукла і обмеження задаються також опуклими функціями.

5. Цілочисельне програмування – розділ математичного програмування, що вивчає задачі, в яких на значення усіх або частини змінних накладена вимога цілочисельності.

6. Квадратичне програмування – розділ математичного програмування, що розглядає спеціальний клас задач, у яких функція, що мінімізується, квадратична, а обмеження лінійні.

7. Стохастичне програмування – розділ математичного програмування, який вивчає моделі вибору оптимальних рішень в ситуаціях, що характеризуються випадковими величинами.

8. Кусочно-лінійне програмування – розділ математичного програмування, який вивчає задачу відшукання мінімуму (максимуму) опуклої (ввігнутої – у випадку максимуму) кусочно-лінійної функції на опуклій багатогранній множині.

9. Динамічне програмування – розділ математичного програмування, який вивчає багатокрокові процеси пошуку рішень.

10. Градієнт функції f(x) = f(x₁, …, x_n) в точці x E ⁿ – вектор, координати якого в середовищі E ⁿ дорівнюють окремим похідним цієї функції в точці x (grad f(x), f(x), f ^'(x)).

Старший викладач кафедри

В.К. Петров