- •1.1. Завдання до лабораторної роботи
- •1.2. Варіанти завдань
- •1.3. Методичні вказівки до виконання лабораторної роботи
- •2.1. Завдання до лабораторної роботи
- •2.2. Варіанти завдань
- •2.3. Методичні вказівки до виконання лабораторної роботи Розв'язання задачі
- •Лабораторна робота № 3. Методи оптимізації транспортних перевезень
- •3.1. Завдання до лабораторної роботи
- •3.2. Варіанти завдань
- •3.3. Методичні вказівки до виконання лабораторної робіти
- •Зведення відкритої т-задачі до закритої т-задачі
- •Пошук оптимального рішення т-задачі у середовищі “excel”
- •Лабораторна робота № 4. Основні способи зведення мережевої задачі до матричної форми
- •4.1. Завдання до лабораторної роботи
- •4.2. Варіанти завдань
- •4.3. Методичні вказівки до виконання лабораторної роботи
- •Зведення мережевої транспортної задачі до матричної форми
- •Лабораторна робота № 5. Розв'язання сітьових транспортних задач. ЗадачІ про найкоротший шлях та максимальний потік на мережі
- •5.1. Завдання до лабораторної роботи
- •3.2. Варіанти завдань
- •3.3. Методичні вказівки до виконання лабораторної роботи
- •6.1. Завдання до лабораторної роботи
- •6.2. Варіанти завдань
- •6.3. Методичні вказівки до виконання лабораторної роботи
6.1. Завдання до лабораторної роботи
1. Розв’язати мережеву транспортну задачу (див. рис. 6.1) за допомогою Excel-таблиці (добавив додатковий транспортний вузол з карти України), одержати оптимальний план перевезень за допомогою “EXCEL -2003”. Проаналізувати результати.
6.2. Варіанти завдань
Додати до структури транспортної мережі (рис. 6.1) транспортний вузол з карти України.
6.3. Методичні вказівки до виконання лабораторної роботи
Транспортна мережа на рис. 6.1 також узята з електронного атласу України у вигляді зваженого графа з 13 вузлами і 19 дугами. Вона задана змішано-орієнтованою мережею, де певні дуги орієнтовані, якщо однозначно визначають напрям перевезень (Київ → Березань), інші, де нема впевненості у напрямку перевезень, – дуги неорієнтовані (Київ ↔ Прилуки). Останні дещо збільшують розмір задачі, бо представляються вже не одною, а парою направлених назустріч друг другу дуг (Київ → Прилуки, Прилуки → Київ).
На транспортній мережі присутні три різновиди вузлів:
пункти-постачальники вантажу (вони зображені у вигляді квадратів);
пункти-споживачі цього вантажу (вони зображені у вигляді овалів);
транзитні пункти (вони зображені у вигляді кіл).
Обсяги поставок (зі знаком + ) і заявок вантажу (зі знаком - ) проставлені поруч із кожним пунктом, а проставлена на кожній дузі дріб являє собою вартість перевезення одиниці вантажу (чисельник дробі) і пропускну здатність цієї дуги (знаменник дробі). Загальний обсяг пропозиції (поставок) перевищує на 130 одиниць сумарний обсяг попиту (споживання), тобто ми маємо відкриту транспортну задачу.
Рис. 6.1. Графічне представлення мережевої транспортної задачі
Необхідно знайти вектор Х = (х1, х2, … х28), де хі – об'єм перевезень і-ою дугою, такий, щоб загальні витрати (цільова функція) , де сі – питомі витрати для і-ої дуги за умови балансу потоків для кожного j-го вузла (j = 1, 2, ... , 13): Fвих(xi) - Fвх(xi) = р(xi), де Fвих(xi), Fвх(xi) – сума потоків вантажу на виході та вході кожного j-го вузла з урахуванням пропускних здатностей дуг.
На рис. 6.2 представлене рішення поставленої транспортної задачі в середовищі додатка Excel, з якого видно, що оптимальний план перевезень складає вектор Х = (0, 0, 0, 80, 150, 0, 50, 0, 100, 5, 40, 0, 0, 60, 80, 75, 0, 85, 0, 15, 195, 130, 0, 0, 0, 40, 0, 0), цільова функція дорівнює 7600. Оскільки модель незбалансована, маємо залишки нерозподіленого запасу у 2-ому (Бобровиця, 30), у 3-ому (Прилуки, 85) та 6-ому (Зеньков, 15) вузлах. Оптимальні перевезення вантажу показані на рис. 6.3.
Рис. 6.2. Розв'язання мережевої транспортної задачі
Рис. 6.3. Оптимальні потоки у мережевої транспортної задачі