3.1 Постановка транспортної задачі
Транспортна
задача ‑ це задача відшукання таких
шляхів перевезення продукту від пунктів виробництва до пунктів споживання, при
яких загальна вартість перевезень виявляється мінімальною.
Математичний апарат транспортної задачі можна застосувати
й до завдань електроенергетики. Тут під продуктом мається на увазі електрична потужність, передана від
джерел живлення до споживачів ЛЕП. Джерелами
живлення є електричні станції або підстанції, споживачами ‑ промислові, міські, сільськогосподарські
споживачі електроенергії. Оптимізації підлягають витрати на схему
електричної мережі, що складається з ліній електропередачі, що зв'язують вузли
джерел живлення з вузлами споживачів.
Нехай у проектованій системі електропостачання є i = 1, 2,…n вузлів джерел живлення й j = 1, 2, ... m вузлів споживачів.
Потужність кожного із джерел становить Aі,
а потужність кожного зі споживачів – Bj
одиниць потужності (о.п.). Відомо взаємне розташування вузлів джерел і
споживачів. Вартість передачі одиниці потужності від джерела і до споживача j (питома вартість) становить сij
у.о./о.п.
Загальна кількість можливих до будівництва ліній
електропередачі, що зв'язують джерела зі споживачами, становить nхm. Потужності, які передаються цими
лініями, є шуканими змінними xіj,
отже, кількість шуканих змінних становить nхm.
Витрати на електричну мережу дорівнюють сумі добутків питомих вартостей на
величини переданих потужностей від джерел і
до споживачів j. Тому підлягаюча
мінімізації цільова функція має такий вигляд:
(3.1)
З позицій теоретичної електротехніки електрична мережа є
електричним колом і для цієї мережі можна застосовувати всі закони, відомі з
курсу електротехніки, зокрема, перший
закон Кірхгофа. Для кожного і-го
джерела живлення сума потужностей, що течуть лініями до j = 1,2, ... m вузлів споживачів, дорівнює потужності Aі цього джерела.
(3.2)
Для кожного j-го споживача сума потужностей, що
приходять лініями від всіх і=1,2,...n
джерел, дорівнює потужності Bj
цього споживача.
(3.2а)
Співвідношення (3.2) і (3.2а), що представляють собою
баланси потужності в кожному з вузлів, є обмеженнями при рішенні транспортної
задачі. Загальна кількість обмежень дорівнює кількості вузлів джерел і
споживачів n+m. З теоретичної
електротехніки відомо, що для будь-якої електричної мережі кількість незалежних
рівнянь, складених за першим законом Кірхгофа, на одиницю менше кількості
вузлів і становить (n+m-1). Отже,
кількість незалежних обмежень становить (n+m-1).
Кількість базисних (не рівних нулю) змінних дорівнюють кількості незалежних
обмежень і становить (n+m-1). Інші змінні
є вільними (рівними нулю). Кількість вільних змінних становить (nm-(n+m-1)). Кожна базисна змінна xіj відповідає присутності в
схемі лінії між вузлами і та j, оскільки потужність, що протікає між
вузлами і та j, не дорівнює нулю. Кожна вільна змінна xіj відповідає відсутності в схемі лінії між вузлами і та j,
оскільки потужність, що протікає між вузлами і та j, дорівнює нулю. У
розглянутій постановці транспортної задачі всі шукані потужності хіj, передані від джерел до
споживачів, є невід’ємними. Отже, граничні умови мають вигляд:
(3.3)
Вирази (3.1), (3.2), (3.2а) і (3.3) являють собою
математичну модель транспортної задачі. Видно, що вирази цільової функції (3.1)
та обмежень (3.2) і (3.2а) є лінійними. Отже, транспортна задача може бути розв’язана симплексним
методом. Однак безпосереднє застосування цього методу до розв’язку транспортної
задачі є недоцільним. У силу своєї універсальності симплекс-метод має досить
складну обчислювальну процедуру й без врахування специфічних особливостей
транспортної задачі її розв’язок виявляється занадто громіздким.
Особливості транспортної задачі наступні:
1. всі обмеження мають форму рівностей;
2. всі коефіцієнти при змінних у системі обмежень дорівнюють плюс одиниці;
3. кожна змінна двічі входить у систему обмежень; один раз у баланси вузлів
джерел (3.2), другий раз у баланси вузлів споживачів (3.2а).
З урахуванням цих особливостей для розв’язку транспортної
задачі розроблені спеціальні методи розв’язку, більш прості, ніж
симплекс-метод.