4) Математична постановка транспортної задачі оптимізації. Що таке збалансовані та незбалансовані задачі?

Класична транспортна задача полягає у пошуку оптимального плану перевезень однорідного вантажу з (m) пунктів відправлення A1, A2, …, Am, у яких знаходиться відповідно a1, a2,…,am одиниць вантажу, у (n) пунктів призначення B1, B2, …, Bn, у кожний з яких потрібно завезти відповідно b1, b2, …, bn. Вартість перевезення одиниць вантажу з пункту (Ai) відправлення у пункт (Вj) при- значення відома і складає (Сij). Потрібно скласти такий план перевезень, при якому загальна вартість перевезень була б мінімальною, були б задоволені потреби споживачів. Будемо вважати, що задача збалансована (закрита),

тобто Незбалансована задача (відкрита) зводиться до збалансованої шляхом введення фіктивних постачальників або фіктивних споживачів у залежності від дефіциту потреб чи запасів. Вартість перевезень (відстань) від фіктивних постачальників або до фіктивних споживачів вважають рівною нулю. Математична постановка транспортної задачі Позначимо: xij – кількість одиниць вантажу, яку потрібно перевез- ти з пункту відправлення (Ai) до пункту призначення (Вj), щоб план перевезень був оптимальним. Враховуючи вартість перевезень одиниці вантажу (Сij), загальна вартість перевезення вантажу з пункту (Ai) до пункту (Вj) складає: Сij ∙ xij . Загальна вартість перевезень всього вантажу складає:

Система обмежень складається, виходячи з передумови, що загаль- на сума запасів, вивезених з (m) пунктів, дорівнює загальній сумі по- треб у “j”-му пункті:

загальна кількість вантажу, вивезеного з “і”-го пункту, дорівнює наявності вантажу у “і”-му пункті:

за умов, що кількість одиниць вантажу, вивезених з пункту (Ai) до пун- кту (Вj), невід’ємна:

задача збалансована

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

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

де: m – кількість пунктів відправлення; n – кількість пунктів спожи- вання, бо за умов виконання збалансованості транспортної задачі кількість лінійно незалежних рівнянь-обмежень на одне менше загальної кілько- сті рівнянь. Таким чином, кількість базисних невідомих у транспорт- ній задачі дорівнює завжди m + n – 1, а кількість вільних невідомих: m ∙ n – (m + n – 1). Отже, транспортна задача є задачею лінійного програмування у канонічній формі з деякими особливостями:  Коефіцієнти при невідомих у всіх рівняннях-обмеженнях дорі- внюють одиниці.  Кожна невідома змінна зустрічається лише у двох функціона- льних рівняннях-обмеженнях; тому матриця коефіцієнтів при невідомих змінних (xij) побудована з одиниць та нулів; кожен стовпець матриці нараховує дві одиниці, а інші елементи – нулі.  Система рівнянь-обмежень транспортної задачі симетрична відносно усіх змінних (xij). Послідовність розв’язання транспортної задачі відповідає послідо- вності розв’язання звичайної задачі лінійного програмування: 1. Визначається опорний план (припустиме базисне рішення) транспортної задачі. 2. З’ясовується оптимальність опорного плану. 3. Здійснюється перехід від одного опорного плану до іншого, або завершується задача оптимізації.