ОБСЛУГОВУВАННЯ ПОВІТРЯНОГО РУХУ 1.1 Основні відомості про математичне програмування

ЗАСТОСУВАННЯ МЕТОДІВ ЛІНІЙНОГО І НЕЛІНІЙНОГО ПРОГРАМУВАННЯ ДЛЯ ДОСЛІДЖЕННЯ ПРОЦЕСІВ

Основною складовою запису будь-якої задачі, що розв’язується аналітичними методами, є так звана цільова функція, яка відображає мету розв’язання задачі. Значення цільової функції залежить від змінних, які входять до її складу і називаються керованими змінними. Така назва змінних обумовлена тим, що їх ми можемо, як правило, якимось чином змінювати, змінюючи цим значення цільової функції у потрібному нам напрямку. Наприклад, цільову функцію задачі визначення площі прямокутника можна записати так:

S=х₁∙ х₂,

де S- площа прямокутника; х1 і х2 - розміри сторін прямокутника.

В цій задачі керованими змінними є х1 і х2.

Цільову функцію задачі називають також узагальненим показником якості або ефективності функціонування системи, яка досліджується.

До математичного програмування відносять задачі, в котрих треба визначити такі значення керованих змінних, які відповідають оптимальному, тобто найкращому можливому згідно з прийнятим критерієм, значенню цільової функції з врахуванням певних обмежень на значення керованих змінних. Інакше кажучи, це є задачі оптимізації, в котрих накладаються певні обмеження на значення змінних. Зокрема, загальною метою навігації і управління повітряним рухом (УПР) є забезпечення польоту повітряного судна за траєкторією, яка за протяжністю максимально наближена до програмної (планової), і разом з тим під час польоту по повітряній трасі необхідно забезпечити невихід судна за межі траси з ймовірністю, в середньому, не менше 0,95. В аналітичній формі цю задачу можна записати так:

S_ф(Z) – S_пр. ® min, (1.1)

P (Z£ в) ³ 0,95 (1.2)

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

В наведеній задачі вираз (1.1) є цільовою функцією, а нерівність (1.2) - обмеженням на значення змінної Z.

Підкреслимо, що ця задача записана вище у найбільш загальному вигляді, тому що змінна Z, у свою чергу, є функцією характеристик точності засобів навігації і УПР, інтервалів часу, через які здійснюється корекція шляху (при шляховому способі навігації) або місця повітряного судна (при маршрутному способі навігації). Тому при розв’язуванні задачі на етапі синтезу системи навігації і УПР керованими змінними можуть бути згадані вище характеристики точності і інтервали корекції, а у випадку розв’язування задачі навігації і УПР керованою змінною може бути тільки часовий інтервал корекції, тому що на цьому етапі ми можемо змінювати тільки інтервали корекції і не можемо, здебільшого, якимось чином впливати на характеристики точності засобів навігації і УПР. Отже, склад керованих змінних задачі залежить не тільки від мети, але й від умов її розв’язання.

Слід зауважити, що загальновживаний термін “математичне програмування”, який запозичений з англійської мови, українською мовою не зовсім точно виражає сутність задач, що розглядаються, більш точним було б говорити, що це є задачі математичного планування. Разом з тим ці задачі відносяться до більш широкого класу задач дослідження операцій.

Оскільки в деяких задачах математичного програмування кількість змінних може досягати сотень і навіть тисяч, то їх звичайно означають х1, х2, х3 і т. д.

Таким чином, загальне формулювання задачі математичного програмування можна подати так: потрібно знайти значення керованих змінних х1, х2, ..., хn, які забезпечують оптимальне (максимальне або мінімальне) значення цільової функції,

W(х₁, х₂, ..., х_n),

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

q₁ (х₁, х₂, ..., х_n) £ в₁,

q₂(х₁, х₂, ..., х_n) > в₂,

q_m(х₁, х₂, ..., х_n) = в_m

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

Обмеження задачі математичного програмування за формою можуть бути рівностями, строгими або нестрогими нерівностями.

Функції - обмеження задачі qj (х1, х2, ..., хn), j=1,mназивають також функціями споживання ресурсів, а постійну вj - значенням j-го ресурсу. Як ресурси у конкретних задачах УПР можуть розглядатися кількість повітряних суден, протяжність заданої траєкторії польоту, наявний ресурс льотного часу повітряного судна тощо. Отже, той чи інший ресурс задачі означає певну фізичну величину і тому не може мати від’ємне значення.

Іноді розрізнюють прямі і зворотні задачі математичного програмування. Вище наведені узагальнені формулювання і аналітичний запис зворотної задачі, в котрій необхідно визначити значення керованих змінних, що забезпечують оптимум цільової функції і задовольняють обмеження задачі. У прямій задачі значення змінних відомі, а необхідно обчислити відповідне до них значення цільової функції. Практично, як правило, кожну задачу математичного програмування приходиться розв’язувати спочатку як зворотну, а потім - як пряму. Це обумовлене тим, що в задачах, які відповідають запитам реальної діяльності людей, потрібно визначити не тільки умови одержання найкращого (оптимального) результату діяльності, але й обчислити значення такого результату.

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

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

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

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

2. Задачу нелінійного програмування маємо у випадку, коли цільова функція або хоча б одна функція-обмеження є нелінійною функцією керованих змінних задачі.

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

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

Сутність поняття “статистична оцінка” полягає у наступному. Коли функція залежить від випадкових змінних, то вона, як і ці змінні, може як правило, приймати безліч випадкових значень. При цьому про обчислення (визначення) функції можна говорити тільки стосовно окремих реалізацій випадкового процесу, тобто конкретних значень випадкових змінних. Тому значення цільової функції оцінюють “в середньому”, тобто обчислюють статистичні оцінки параметрів її розподілу як випадкової змінної.

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

6. До евристичного програмування відносять задачі, які алгоритмічними способами не розв’язуються. Такі задачі розв’язуються з використанням спеціальних методик, що називаються евристиками.

Існують також інші різновиди задач математичного програмування і способів їх розв’язання. Оскільки ж задачі управління повітряним рухом відзначаються значною різноманітністю, то для їх розв’язання використовуються способи, що відносяться до більшості різновидів математичного програмування.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Європейський Союз	\|	Основні способи формування цільової функції задачі

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.