злами.
Через х позначимо оптимальний план вирішення транспортної задачі. Необхідною умовою вирішення транспортної задачі є виконання умови балансу:
т.е. кількість вантажу у всіх грузопоставщіков повинна дорівнювати кількості вантажу, необхідного споживачам.
Відстань між постачальниками і споживачами повинно бути невід'ємним:
Таким чином, загальний обсяг транспортної задачі повинен бути мінімальним:
Обсяг поставок, виконуваний постачальниками i, повинен бути рівний кількості вантажу, наявного у нього:
а кількість вантажу, необхідного споживачам, має дорівнювати
Необхідно так само врахувати, що
Дані рівняння є лінійними.
При вирішенні транспортної задачі використовується матрична форма запису. Модель транспортної задачі дана в табл. 1.1.
Таблиці 1.1.- Модель транспортної задачі
ГрузополучательГрузоотправітельbА1А2А3 ... АmБ1 ... Б2 ... Б3 ... ..................... Бn ...
Загальний холостий пробіг виражається наступним рівнянням:
Ix=c11 x11 + c21 x21 + c31 x31 + ... + cn1 xn1 + c12 x12 + c22 x22 + ... + cn2 xn2 + c13 x13 + c23 x23 + ... + cn3 xn3 + ... + c1m x1m + c2m x2m + ... + cnm xnm=cmin. (1.7)
Транспортна задача вирішується до певного оптимального плану.
Критерій - мінімізація транспортної роботи. Попереднім етапом є складання матриці вихідних умов.
У клітинах матриці вказуємо відстань перевезення і обсяг вантажів у тоннах по відправникам та одержувачам, потім будуємо у вигляді матриці можливий план перевезень.
Розподіл вантажу зробимо методом мінімального елемента.
. 2 Рішення транспортної задачі методом лінійного програмування
Для складання транспортної задачі з вихідних даних вибираються вантажі, що перевозяться одним типом рухомого складу. Перелік цих вантажів представлений в таблиці 1.2.
Таблиця 1.2.- Вантажі, що перевозяться одним типом рухомого складу.
ГрузопотокіРод грузаОб'ем перевезень, тКласс грузаіз пунктав пунктА1Б2щебень10001 (навалом) А2Б5песок7501 (навалом) А4Б2песок15001 (навалом) А3Б4грунт7501 (навалом) А4Б5щебень12501 (навалом) А5Б3кокс7501 (навалом)
Заповнимо матрицю транспортної задачі і з допомогою методу мінімального елемента визначимо первинний план перевезень вантажів (табл. 1.3).
Таблиця 1.3.- Початковий опорний план перевезень вантажів.
ГрузополучательГрузоотправітельОб'ём завезення bА1А2А3А4А5Б218750 6101000 14750 122500Б3312420750 913750Б4161410750 712750Б51000 57750 6250 18202000Об'ем вивезення a100075075027507506000
Далі отриманий план перевезень перевіряється на оптимальність. У таблицю транспортної задачі вводяться допоміжні рядок і стовпець, в які заносяться спеціальні показники, звані потенціалами. Результати відобразимо в таблиці 1.4.
Таблиця 1.4.- Уточнений план перевезень вантажів.
ГрузополучaтельГрузоотправітельОб'ём завезення bUjА1А2А3А4А5Б218750 6 - 101000 14 +750 12250014Б3 31 24 20 750 9 137509Б4 16 14 10 750 7 127507Б51000 +5 7 + - 3750 6250 18 - 20200018Об'ем вивезення a100075075027507506000Vi - 13- 8- 12 0- 2 Сумарний холостий пробіг автомобілів для даного плану перевезень склав 53500 км, однак він не є оптимальним, оскільки є одна негативна оцінка. Для поліпшення плану перевезень побудуємо замкнутий контур для клітини (5,2). Він містить клітини (5,2), (2,2), (2,4), (5,4). Клітини (5,2) і (2,4) помічаємо знаком + raquo ;, а клітини (2,2) і (5,4) - знаком - Так як для клітин (2,2), (5,4) мінімальний обсяг перевезень дорівнює 250 тонн, то віднімати і додавати необхідно 250 одиниць. У результаті клітина (5,2) стає завантаженої, а клітина (5,4) порожній. Отримуємо матрицю з новим планом перевезень (табл. 1.5).
Таблиця 1.5.- Матриця з планом перевезень вантажів
ГрузополучaтельГрузоотправітельОб'ём завезення bUjА1А2А3А4А5Б2 18 500 6 10 1250 14 750 12250014Б3 31 24 20 750 9 137509Б4 16 14 10 750 7 127507Б51000 5250 7750 18 червня 20200015Об'ем вивезення a100075075027507506000Vi - 10- 8- 9 0- 2
Сумарний холостий пробіг автомобілів для даного плану перевезень склав:
Ix=500? 6 + 1250? 14 + 750? 12 + 750? 9 + 750? 7 + 750? 6 +
+ 250? 7 + +1000? 5=52750 км.
