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а).

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