Транспортна задача за критерієм мінімізації максимального часу перевезення

НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ

Факультет транспорту, менеджменту та логістики

Кафедра організації авіаційних перевезень

Лабораторна робота №9

з дисципліни «Дослідження операцій на транспорті»

На тему: «Транспортна задача за критерієм мінімізації максимального часу перевезення»

Виконала: студентка групи ОП-201Б Клименко Юлія

Київ 2022

Умова задачі:

Дано:

m – кількість пунктів виробництва деякого однорідного вантажу,

n – кількість пунктів споживання.

Q i – об’єм виробництва в і – му пункті,

V j – об’єм споживання в j – му пункті,

(c ij ) – матриця затрат часу на перевезення одиниці вантажу із і- го пункту виробництва в j- й пункт споживання.

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

[pic 1]

Розв’язання:

1. На листі редактора Microsoft Excel створюємо дві таблиці: розрахункову таблицю, враховуючи фіктивний пункт призначення, та матрицю часу.

[pic 2]

Мал. 9.1. Розрахункова таблиця та матриця часу

1. Будуємо початковий план перевезень методом подвійної переваги

[pic 3]

Мал. 9.2. Початковий план перевезень

1. У отриманому плані перевезень серед зайнятих клітин найбільше значення tij має клітина А3В3, отже, tmax = t33 = 9, відповідно Т1 = 9. Усі клітини для яких tij ≥ 9, забороняємо для перевезень і викреслюємо.

[pic 4]

Мал. 9.3. Клітини з найбільшим значенням часу та заборонені до перевезень

1. Проводимо перенесення перевезень з клітини А3В3 у вільну клітину при цьому враховуючи балансові умови. Для цього будуємо цикл перерахунку за результатом якого отримуємо новий план перевезень.

[pic 5]

Мал. 9.4. Цикл перерахунку

[pic 6]

Мал. 9.5. Результати перерахунку

1. У новому плані перевезень tmax = t32 = 7, відповідно Т2 = 7. Після виконання перевірки можливості перенесення кореспонденції з клітини А3В2 у іншу вільну клітину, враховуючи балансові умови та умову заборони перенесень в клітини зі значеннями tij ≥ 7, доходимо висновку, що отриманий план перевезень є оптимальним і забезпечує мінімально можливий час виконання перевезень.

[pic 7]

Мал. 9.6. отриманий оптимальний план перевезень

Висновок: Вирішуючи транспортну задачу за критерієм мінімізації максимального часу перевезення використовуючи цикл перерахунку було оптимізовано початковий план перевезень. Було мінімізовано час виконання перевезень враховуючи балансові умови.