2. Система обмежень задана у вигляді рівнянь.

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

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

при обмеженнях виду (1.6).

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

Слід зазначити, що коефіцієнти в системі обмежень (1.6) за змістом задачі не можуть бути негативними. Тому якщо в якомусь із обмежень при формальних перетвореннях отримане значення , то таке обмеження необхідно помножити на -1.

5. Особливості використання симплекс-методу

Перший етап звичайно виконується вручну й на його основі для вирішення на ЕОМ у якості вихідних даних задаються:

1. Загальне число невідомих (основних, додаткових й штучних) і число обмежень.

2. Вектор , складовими якого є коефіцієнти лінійної форми.

3. Вектор , складовими якого є номери базисних змінних.

4. Матриця коефіцієнтів системи обмежень.

5. Вектор значень базисних змінних, тобто з урахуванням запропонованого методу одержання вихідного базисного рішення, це стовпець вільних членів обмежень (1.6).

Для вирішення задачі на ЕОМ розроблено табличний варіант симплекс-методу, так званий метод симплекс-таблиць. Обчислювальною основою для методу є алгоритм повного виключення Гауса.

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

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

• якщо як початковий базис вибирають базис із додаткових змінних, для яких , то оцінки для всіх небазисних змінних

,

а відповідне значення цільової функції

;

• відсутність векторів з негативними оцінками (при вирішенні задачі) є ознакою оптимальності відповідного базисного рішення;

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

• при вирішенні задачі мінімізації в базис уводиться вектор з найбільшою позитивною оцінкою.

6. Обчислювальна ефективність методу

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

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

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

3. Змістовна постановка задачі

1. Визначення оптимальної кількості базових станцій у системі зв’язку з рухомими об’єктами

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

Визначити оптимальне число БС першого й другого типу, при якому приведені витрати на мережу будуть найменшими й будуть виконуватися наступні вимоги:

• загальна споживана потужність всіх БС не більше кВт;

• загальна чисельність обслуговуючого персоналу не повинна перевищувати шт.од.;

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

Вихідні дані для вирішення задачі вибираються з таблиці відповідно до номера варіанта завдання (табл.1.1).

Рішення задачі містить у собі:

1. Математичну постановку задачі та її геометричну інтерпретацію.

2. Аналіз на наявність рішення (єдине, множинне рішення, рішення відсутнє).

3. Виклад алгоритму рішення.

4. Визначення вихідного базового рішення.

2. Мінімізація завад в угрупованні РЕС зв'язку

У п.704 Регламенту радіозв'язку вказується, що смуга 890…960 Мгц виділена РЕС повітряної радіонавігаційної служби, а саме бортовому обладнанню (БО) радіотехнічної системи ближньої навігації і системи посадки (РСБН) літальних апаратів (ЛА). Порівняння частотних діапазонів, які використовуються для БО РСБН і системи посадки ЛА, з частотними діапазонами передавачів БС стандарту GSM показало, що ці діапазони співпадають, а саме, 120 і 121 канали GSM, що працюють в діапазоні 959,0-959,4 Мгц і приймачі ЛА, що працюють на частоті 959,2 Мгц. На даному етапі розвитку ця проблема була розв'язана вирізанням діапазонів. Пропонується інший підхід до вирішення цієї проблеми: зменшення потужності передавачів станцій стандарту GSM таким чином, щоб вони не створювали перешкод РСБН. Це призведе до зменшення енерговитрат і збільшення кількості абонентів.

Ефективним заходом зменшення перешкод у групі РЕС, розташованих у межах обмеженої території (системі РЕС), є спільний вибір потужності в групі передавачів. Збільшення потужності одного з передавачів трохи поліпшує індивідуальні показники радіолінії, що складається з даного передавача та приймача, призначеного для прийому його повідомлень. Однак це веде до росту завад іншим засобам, погіршенню якості передачі інформації у всій системі. З іншого боку, зменшення потужності передавача призводить до зменшення відносшення сигнал/шум, і при подальшому зниженні веде до втрати виконуваних ним функцій, тобто теж до зниження якості передачі інформації у всій системі. Існують деякі значення потужностей, при яких якість передачі інформації в усій системі буде при

Таблиця 1.1.

Вихідні дані	Номер варіанта
	1	2	3	4	5	6	7	8	9	10	11	12	13
– радіус території обслуговування (км)	40	40	40	40	40	40	40	40	40	40	40	35	35
– радіус зони обслуговування БС 1-го типу (км)	5	5	5	5	5	3	3	3	3	3	5	5	5
– радіус зони обслуговування БС 2-го типу (км)	10	10	10	10	10	10	10	10	10	10	10	10	10
– потужність, що споживає БС 1-го типу (Вт)	25	25	25	25	25	25	25	25	25	25	50	50	50
– потужність, що споживає БС 2-го типу (Вт)	100	100	100	100	100	70	70	70	70	70	100	100	100
– питома вартість БС 1-го типу (умов.од.)	40	50	45	55	42	40	50	55	42	45	50	45	45
– питома вартість БС 2-го типу (умов.од.)	100	100	100	110	98	100	100	110	98	100	120	100	120
– кількість співробітників, що обслуговують БС 1-го типу (шт.од.)	0,6	0,58	0,62	0,66	0,7	0,6	0,58	0,66	0,7	0,62	0,6	0,6	0,62
– кількість співробітників, що обслуговують БС 2-го типу (шт.од.)	0,4	0,42	0,38	0,35	0,4	0,4	0,42	0,35	0,4	0,38	0,4	0,4	0,38
– загальна споживана потужність БС (кВт)	2,5	2,4	2,6	2,3	2,5	2,5	2,3	2,6	2,5	2,3	5,0	5,0	5,0
– загальна чисельність обслуговуючого персоналу (шт.од.)	24	22	24	22	20	24	20	24	20	20	26	24	23

Продовження табл.1.1.

Вихідні дані	Номер варіанта
	14	15	16	17	18	19	20	21	22	23	24	25	26
– радіус території обслуговування (км)	35	35	40	40	40	35	35	35	20	20	20	20	35
– радіус зони обслуговування БС 1-го типу (км)	5	5	5	5	5	5	5	5	1,5	1,5	1,5	1,5	5
– радіус зони обслуговування БС 2-го типу (км)	10	10	10	10	10	8	8	8	5	5	5	5	10
– потужність, що споживає БС 1-го типу (Вт)	50	50	50	50	50	50	50	50	10	10	10	10	50
– потужність, що споживає БС 2-го типу (Вт)	100	100	70	70	70	70	70	70	50	50	50	55	70
– питома вартість БС 1-го типу (умов.од.)	42	50	45	40	42	40	42	45	40	40	40	40	45
– питома вартість БС 2-го типу (умов.од.)	98	100	120	100	98	98	104	100	100	100	100	100	110
– кількість співробітників, що обслуговують БС 1-го типу (шт.од.)	0,7	0,6	0,7	0,6	0,7	0,7	0,72	0,64	0,4	0,42	0,38	0,41	0,62
– кількість співробітників, що обслуговують БС 2-го типу (шт.од.)	0,4	0,38	0,4	0,4	0,4	0,4	0,48	0,38	0,2	0,24	0,19	0,2	0,38
– загальна споживана потужність БС (кВт)	5,0	5,0	3,5	3,5	3,5	3,5	3,5	3,5	1,5	1,5	1,5	1,5	5,0
– загальна чисельність обслуговуючого персоналу (шт.од.)	20	22	25	22	23	24	23	24	16	18	16	16	23

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

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

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

(1.8)

Систему рівнянь (1) можна записати в наступному вигляді:

(1.9)

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

мінімізувати:

при виконанні обмежень:

де , , – задані, , , , , ; .

Розглянемо комплекс РЕС, що утворився в районі аеропорту м.Харкова, який складається з трьох БС стандарту GSM, працюючих на частоті 959,2 Мгц, і літака, що здійснює посадку, приймач якого працює на частоті 959,2 Мгц., тобто на частоті передавача БС. У зоні дії кожної БС знаходиться одна мобільна станція (МС), приймачі яких працюють на такій самій частоті, що й передавач РСБН. БС розташовані в зонах, які не перетинаються, і не створюють завад на МС один одної. Позначимо відстані між першою БС і ЛА відповідно R1(км), R2 (км), R3(км.), між РСБН і ЛА – R4 (км), між БС і МС відповідно R5-R7 (км). При цьому обмеження, що накладаються на потужності передавачів, складають: для БС – P1, P2, P3 відповідно, в межах (0...50) Вт, для передавача РСБН – P4 в межах (0…80) Вт. Необхідно, користуючись таблицею 1.2, визначити наступні дані для вирішення ЗЛП.