Найти для сети, изображенной на рис. 13, кратчайший путь объезда всех пунктов, если: с1,2 = с2,1 = а; с1,3 = с3,1 = b; с1,4 = с4,1 = c; с2,3 = с3,2 = d; с2,6 = с6,2 = e; с2,7 = с7,2 = f; с3,4 = с4,3 = g; с3,5 = с5,3 = h; с4,5 = с5,4 = i; с4,8 = с8,4 = j; с5,6 = с6,5 = k; с5,8 = с8,5 = l; с6,7 = с7,6 = m; с6,8 = с8,6 = n; с7,8 = с8,7 = o.
Рис. 13. Граф транспортной сети.
Задача решается с помощью надстройки OpenSolver вExcel. Для этого формируются следующие таблицы 16, 17, 18.
Таблица 16. Коэффициент целевой функции Сij (расстояние перевозки)
| Пункты отправления и назначения | ||||||||
В эту таблицу заносятся расстояния между пунктами. В тех направлениях, в которых по условию задачи транспортировка физически невозможна, проставляются очень большие расстояния перевозки, чтобы исключить эти маршруты из искомого решения.
Таблица 17. Искомые переменные Х ij
| Переменные Хij | xi1 | xi2 | xi3 | xi4 | xi5 | xi6 | xi7 | xi8 | Сумма |
| x1j | |||||||||
| x2j | |||||||||
| x3j | |||||||||
| x4j | |||||||||
| x5j | |||||||||
| x6j | |||||||||
| x7j | |||||||||
| x8j | |||||||||
| Сумма | |||||||||
| Переменные ui |
Переменные Хij и Ui являются изменяемыми параметрами и будут найдены программой в процессе поиска решения.
|
|
В таблице 18 представлена система ограничений, используемая для построения модели. Данная система ограничений рассчитывается для каждого пункта отправки, начиная со второго, так как первый пункт отправки по условию задачи является исходным пунктом отправления транспортного средства.
Таблица 18. Система ограничений ui-uj+n*xij
| u2-uj+8*x2j | |||||||
| u3-uj+8*x3j | |||||||
| u4-uj+8*x4j | |||||||
| u5-uj+8*x5j | |||||||
| u6-uj+8*x6j | |||||||
| u7-uj+8*x7j | |||||||
| u8-uj+8*x8j |
Ограничениями данной модели будут:
1. Коэффициенты Хij являются бинарными значениями. Если коэффициент равен 1 – то в этом направлении совершается перевозка, если 0 – то перевозка отсутствует.
2. Сумма коэффициентов Хij по столбцу и по строке должна быть равна 1, так как из одного пункта возможна лишь одна отправка.
3. Выражения ui-uj+n*xij больше или равны 7, а переменные Uij больше 0.
Целевой функцией является расстояние перевозки, которое записывается как сумма произведений расстояния перевозки на переменные Xij. Эта функция должна стремиться к минимуму.
После решения задачи с помощью OpenSolver необходимо нарисовать спроектированную оптимальную схему движения транспортного средства, определяемую по последовательности переменных Ui.
|
|
Данные для выполнения задания по вариантам приведены в таблице 23.
ДАННЫЕ ДЛЯ ВЫПОЛНЕНИЯ ПРАКТИЧЕСКИХ ЗАДАНИЙ
Задание 3.
Таблица 19. Данные для расчета длительности производственного цикла при последовательном, параллельном и параллельно-последовательном способах движения партий деталей в обработке.
| Вариант | Число изделий | Число операций | Время операций |
| 3, 4, 1, 4, 4, 3, 5, 5 | |||
| 3, 5, 6, 5, 3 | |||
| 5, 2, 3, 3, 6 | |||
| 5, 3, 4, 5, 3, 1 | |||
| 2, 2, 1, 1, 3, 4, 5 | |||
| 5, 3, 2, 2, 5, 1, 1 | |||
| 1, 6, 2, 2, 2, 5 | |||
| 5, 3, 6, 2, 1, 5, 5, 2 | |||
| 2, 3, 5, 4, 1 | |||
| 5, 2, 3, 3, 4, 6, 3 | |||
| 3, 3, 5, 2, 2 | |||
| 5, 4, 1, 2, 5, 2, 5, 6 | |||
| 5, 2, 3, 3, 6, 6 | |||
| 3, 4, 5, 3, 4 | |||
| 3, 3, 2, 4, 5, 1, 4 | |||
| 3, 4, 1, 4, 6, 5, 3 | |||
| 3, 2, 3, 1, 2, 6, 5, 1 | |||
| 5, 1, 6, 3, 1, 5 | |||
| 2, 3, 2, 4, 7, 8, 5 | |||
| 4, 5, 8, 9, 6 | |||
| 5, 3, 2, 2, 4, 1 | |||
| 5, 6, 4, 3, 3, 2, 4 | |||
| 2, 3, 4, 2, 2, 1, 3, 4 | |||
| 3, 4, 5, 2, 2, 3, 1, 3 | |||
| 5, 4, 3, 5, 2, 1 | |||
| 3, 3, 2, 5, 2, 1, 1, 3 |
Задание 4.
Таблица 20. Данные для расчета длительности производственного цикла по правилу Джонсона.
| Вариант | Номер операции | Название детали | |||||||||||
| А | Б | В | Г | Д | Е | Ж | З | И | К | Л | М | ||
| Вариант | Номер операции | Название детали | |||||||||||
| А | Б | В | Г | Д | Е | Ж | З | И | К | Л | М | ||
| Вариант | Номер операции | Название детали | |||||||||||
| А | Б | В | Г | Д | Е | Ж | З | И | К | Л | М | ||
|
|
Задание 5.
Таблица 21. Данные для расчета параметров системы управления запасами.
| Вариант | Система управления запасами с фиксированным размером заказа | Система управления запасами с фиксированным интервалом времени между заказами | ||||||||
| S, шт. | A, руб. | W, руб. | Тпос, дн. | Тз.пос, дн | S, шт. | A, руб. | W, руб. | Тпос, дн. | Тз.пос, дн | |
| .8 | ||||||||||
Задание 7.
Таблица 22. Исходные данные по вариантам для выполнения транспортной задачи.
| Вариант | Максимальная вместимость склада, тонн | Потребность магазинов в товаре, тонн | Затраты на транспортировку 1 тонны товара со склада в магазин, тыс. руб. | ||||||||||
| Номер склада и магазина | 1 2 3 4 5 | Склад № 1 | Склад № 2 | Склад № 3 | Склад № 4 | Склад № 5 | |||||||
| 5 3 5 6 4 | 4 7 6 9 8 5 2 | 2 4 8 8 5 3 7 | 7 3 4 1 2 5 5 | 8 3 4 2 3 5 2 | 2 3 5 4 9 6 2 | ||||||||
| 6 3 4 8 7 | 6 8 3 7 4 3 2 | 8 9 7 3 5 5 8 | 1 4 1 5 2 2 3 | 2 9 3 7 5 2 1 | 9 8 4 5 6 6 1 | ||||||||
| 7 2 6 5 2 | 2 9 3 7 5 2 1 | 5 3 7 1 4 4 3 | 6 4 8 7 3 2 1 | 1 1 4 3 6 4 2 | 7 3 1 2 7 7 4 | ||||||||
| 6 2 2 3 7 | 4 4 5 9 7 8 3 | 3 2 5 7 2 2 1 | 9 6 3 4 5 5 7 | 1 2 9 2 7 4 5 | 8 2 8 2 5 3 3 | ||||||||
| 5 8 7 4 2 | 9 6 3 4 5 5 7 | 1 1 4 3 4 4 2 | 8 7 3 9 4 4 3 | 4 5 1 3 8 7 3 | 6 8 7 7 2 4 2 | ||||||||
| 4 8 4 3 7 | 3 2 5 7 2 2 1 | 5 3 7 1 4 4 3 | 4 4 5 6 3 2 1 | 6 4 2 5 8 7 3 | 3 2 5 7 2 2 1 | ||||||||
| 6 8 3 7 9 | 3 5 2 9 6 6 4 | 6 8 7 7 2 4 2 | 2 7 9 8 3 2 3 | 6 6 4 3 8 2 1 | 8 7 3 9 4 4 3 | ||||||||
| 7 8 3 5 4 | 6 2 5 1 3 4 5 | 3 2 5 7 2 2 1 | 6 4 2 5 8 7 3 | 5 3 3 2 1 6 9 | 7 4 4 5 3 2 2 | ||||||||
| 2 5 3 7 9 | 1 2 9 2 7 4 5 | 3 2 5 7 2 2 1 | 6 8 7 7 2 4 2 | 4 4 5 6 3 2 1 | 6 6 4 3 8 2 1 | ||||||||
| 9 5 5 8 7 | 8 8 7 3 5 5 8 | 6 6 4 3 8 2 1 | 7 4 4 5 3 2 2 | 5 8 9 3 1 2 4 | 3 2 5 7 2 2 1 | ||||||||
| 9 7 3 2 6 | 5 3 7 1 4 4 3 | 5 3 7 1 4 4 3 | 3 2 5 7 2 2 1 | 1 1 4 3 4 4 2 | 2 3 7 4 3 2 5 | ||||||||
| 6 5 3 4 8 | 9 8 4 5 6 6 1 | 3 2 5 7 2 2 1 | 4 4 5 6 3 2 1 | 2 7 9 8 3 2 3 | 5 3 3 2 1 6 9 | ||||||||
| 2 2 6 8 4 | 6 8 7 7 2 4 2 | 1 1 4 3 4 4 2 | 5 3 3 2 1 6 9 | 7 4 4 5 3 2 2 | 3 2 5 7 2 2 1 | ||||||||
| 3 3 8 7 5 | 8 2 8 2 5 3 3 | 6 6 4 3 8 2 1 | 8 7 3 9 4 4 3 | 6 8 7 7 2 4 2 | 1 1 4 3 4 4 2 | ||||||||
| 6 3 4 5 2 | 1 1 4 3 4 4 2 | 6 4 2 5 8 7 3 | 2 7 9 8 3 2 3 | 5 8 9 3 1 2 4 | 3 2 5 7 2 2 1 | ||||||||
| 8 8 5 7 4 | 7 3 1 2 4 7 4 | 5 3 3 2 1 6 9 | 6 8 7 7 2 4 2 | 2 3 7 4 3 2 5 | 7 4 4 5 3 2 2 | ||||||||
| 8 4 3 7 9 | 8 7 3 9 4 4 3 | 2 7 9 8 3 2 3 | 5 3 3 2 1 6 9 | 1 1 4 3 4 4 2 | 6 4 2 5 8 7 3 | ||||||||
| 3 6 7 5 2 | 6 8 4 7 5 5 2 | 1 1 4 3 4 4 2 | 6 6 4 3 8 2 1 | 4 4 5 6 3 2 1 | 5 3 3 2 1 6 9 | ||||||||
| 7 6 4 8 5 | 8 3 5 4 1 1 3 | 6 8 7 7 2 4 2 | 4 4 5 6 3 2 1 | 5 3 3 2 1 6 9 | 2 7 9 8 3 2 3 | ||||||||
| 5 9 4 6 8 | 1 9 7 1 2 2 8 | 8 7 3 9 4 4 3 | 6 4 2 5 8 7 3 | 3 2 5 7 2 2 1 | 7 4 4 5 3 2 2 |
| Вариант | Максимальная вместимость склада, тонн | Потребность магазинов в товаре, тонн | Затраты на транспортировку 1 тонны товара со склада в магазин, тыс. руб. | ||||||||||
| Номер склада и магазина | 1 2 3 4 5 | Склад № 1 | Склад № 2 | Склад № 3 | Склад № 4 | Склад № 5 | |||||||
| 6 4 2 3 7 | 6 4 2 5 8 7 3 | 1 9 7 1 2 2 8 | 1 1 4 3 4 4 2 | 8 2 8 2 5 3 3 | 6 8 4 7 5 5 2 | ||||||||
| 5 7 3 9 4 | 5 3 3 2 1 6 9 | 7 3 1 2 4 7 4 | 8 2 8 2 5 3 3 | 6 8 4 7 5 5 2 | 1 1 4 3 4 4 2 | ||||||||
| 2 5 5 4 7 | 5 8 9 3 1 2 4 | 8 2 8 2 5 3 3 | 1 9 7 1 2 2 8 | 6 2 5 1 3 4 5 | 7 3 1 2 4 7 4 | ||||||||
| 8 4 3 5 2 | 2 3 7 4 3 2 5 | 6 8 4 7 5 5 2 | 1 1 4 3 4 4 2 | 5 8 9 3 1 2 4 | 6 2 5 1 3 4 5 | ||||||||
| 4 4 7 8 3 | 2 7 9 8 3 2 3 | 8 2 8 2 5 3 3 | 4 3 5 7 2 8 2 | 6 8 4 7 5 5 2 | 7 3 1 2 4 7 4 | ||||||||
| 5 5 9 4 2 | 4 4 5 6 3 2 1 | 7 3 1 2 4 7 4 | 6 8 4 7 5 5 2 | 2 2 7 8 3 5 1 | 9 8 4 5 6 6 1 | ||||||||
| 3 3 7 8 4 | 6 6 4 3 8 2 1 | 5 8 9 3 1 2 4 | 4 6 3 2 7 6 3 | 1 9 7 1 2 2 8 | 8 2 8 2 5 3 3 | ||||||||
| 6 6 4 3 2 | 7 4 4 5 3 2 2 | 1 9 7 1 2 2 8 | 6 8 4 7 5 5 2 | 9 8 4 5 6 6 1 | 1 1 4 3 4 4 2 |
Продолжение таблицы 21.
Задание 8.
Таблица 23. Исходные данные по вариантам для решения задачи коммивояжера.
| Вариант | Расстояние между пунктами, км | ||||||||||||||
| a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | |