1.Формулировка задачи и исходные данные
Имеется 5поставщиков (отправителей) груза и 10получателей (потребителей) груза, сизвестным количеством груза у каждого из поставщиков и потребности в нёмкаждого получателя (Таблица 1.1 и 1.2). Определены также расстояния между ними(Таблица 1.3).
Необходимо получитьоптимальный вариант закрепления получателей за поставщиками таким образом,чтобы минимизировать грузооборот перевозок (то есть получение кратчайшихрасстояний доставки груза).
Таблица 1.1 –Объём отправления грузовНаличие груза у грузоотправителя, т Товарный склад №1 Товарный склад №2 КЖБИ №1 КЖБИ №2 ООО «Стройка» A1 A2 A3 A4 A5 960 870 720 890 380
Таблица 1.2 –Объём потребления грузов, тГрузополучатель Условное обозначение Потребность в грузе, т. Объект №1 B1 530 Объект №2 B2 230 Объект №3 B3 190 Объект №4 B4 300 Объект №5 B5 100 Объект №6 B6 200 Объект №7 B7 140 Объект №8 B8 60 Объект №9 B9 150 Объект №10 B10 1920
Таблица 1.3 –Расстояния между отправителями и потребителями, кмГрузополучатель Грузоотправитель A1 A2 A3 A4 A5 B1 6 6 7 8 3 B2 18 21 20 20 5 B3 2 15 14 15 4 B4 10 8 8 10 6 B5 6 9 8 8 8 B6 5 8 7 7 10 B7 6 6 7 8 15 B8 2 5 4 4 19 B9 17 3 5 6 6 B10 14 9 10 17 12
2. Решениетранспортной задачи распределительным методом
Методикарасчёта
1) Распределяемгруз по каждому столбцов клетке с наименьшим расстоянием. После распределениятакие клетки называются загруженными (Таблица 2.1).
2) Дляпроверки оптимальности полученного распределения определяем специальныеиндексы(потенциалы), которые проставляем в клетки вспомогательной строки истолбца. Индексы определяют по следующему правилу: вначале в клетке столбцастроки В1 проставляем нуль, а остальные индексы рассчитываем исходя из того,что их сумма должна быть равна
расстояниюкаждой загруженной клетки. Затем определяем потенциалы остальных столбцов истрок, исходя из того, что u+v=c, при этом определяем потенциалы только строк истолбцов, содержащих загруженные клетки. В случае, если количество загруженныхклеток окажется меньше числа m+n-1 (где m-число строк, n-число столбцов), тонеобходимо искусственно загрузить недостающее количество клеток, для этого вних проставляют нуль загрузки и после этого с такой клеткой оперируют как сзагруженной. Целесообразно нуль ставить в такую клетку, для которой один изиндексов уже определён, а также по возможности в клетку с наименьшимрасстоянием.
3) Послеэтого находим такие незагруженные клетки, в которых сумма индексов большерасстояния, указанного в соответствующих клетках – такие клетки называютсяпотенциальными. Цифру разности между суммой индексов и расстоянием называютпотенциалом. Потенциал записываем в соответствующую незагруженную клетку вкруглых скобках.
4) Находимклетку с наибольшим потенциалом (это условие является необязательным). Длявыбранной потенциальной клетки «строим» контур – замкнутую линию, состоящую изпрямых горизонтальных и вертикальных линий, все вершины этой линии должнынаходиться в загруженных клетках, а также в выбранной потенциальной. Контурстроим по правилу – от выбранной потенциальной клетки веду прямуюгоризонтальную или вертикальную линию до такой загруженной клетки, которой подпрямым углом соответствует ещё одна загруженная клетка, и так до тех пор, покалиния не замкнётся в исходной потенциальной клетке.
5) Послеэтого всем вершинам контура попеременно присваиваем знаки «-» и «+», начиная свыбранной потенциальной.
6) Иззагрузок, обозначенных знаком «+», выбираем наименьшую.
7) Даннуювеличину отнимаем от загрузок со знаком «+» и прибавляем к загрузкам со знаком «-».
Таблица 2.1 –Первоначальное распределение объёма перевозок между отправителями ипотребителями
Пот-ре-
би-тель Ин-дексы Поставщик
Пот-реб-ность
в грузе A1 A2 A3 A4 A5
u
v B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 Наличие груза 960 870 720 890 380 3820 /> /> /> /> /> /> /> /> /> /> /> /> />
8) Полученныеновые значения загрузок записываем в другую таблицу(улучшенное значение). Послеэтого снова рассчитываем
специальные индексы, строим контур и так до тех пор, пока небудет потенциальных клеток.
Таблица 2.2 –Второе распределение объёма перевозок между отправителями и потребителями
Пот-ре-
би-тель Ин-дексы Поставщик
Пот-реб-ность
в грузе A1 A2 A3 A4 A5
u
v B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 Наличие груза 960 870 720 890 380 3820 /> /> /> /> /> /> /> /> /> /> /> /> />
Таблица 2.3 –Третье распределение объёма перевозок между отправителями и потребителями
Пот-ре-
би-тель Ин-дексы Поставщик
Пот-реб-ность
в грузе A1 A2 A3 A4 A5
u
v B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 Наличие груза 960 870 720 890 380 3820 /> /> /> /> /> /> /> /> /> /> /> /> />
Таблица 2.4 –Четвёртое распределение объёма перевозок между отправителями и потребителями
Пот-ре-
би-тель Ин-дексы Поставщик
Пот-реб-ность
в грузе A1 A2 A3 A4 A5
u
v B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 Наличие груза 960 870 720 890 380 3820 /> /> /> /> /> /> /> /> /> /> /> /> />
Таблица 2.5 –Пятое распределение объёма перевозок между отправителями и потребителями
Пот-ре-
би-тель Ин-дексы Поставщик
Пот-реб-ность
в грузе A1 A2 A3 A4 A5
u
v B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 Наличие груза 960 870 720 890 380 3820 /> /> /> /> /> /> /> /> /> /> /> /> />
Таблица 2.6 –Шестое распределение объёма перевозок между отправителями и потребителями
Пот-ре-
би-тель Ин-дексы Поставщик
Пот-реб-ность
в грузе A1 A2 A3 A4 A5
u
v B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 Наличие груза 960 870 720 890 380 3820 /> /> /> /> /> /> /> /> /> /> /> /> />
Таблица 2.7 –Седьмое и окончательное распределение объёма перевозок между отправителями ипотребителями
Пот-ре-
би-тель Ин-дексы Поставщик
Пот-реб-ность
в грузе A1 A2 A3 A4 A5
u
v B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 Наличие груза 960 870 720 890 380 3820 /> /> /> /> /> /> /> /> /> /> /> /> />
9) Послеполучения окончательного распределения объёма перевозок между отправителями ипотребителями груза определяем грузооборот по следующей зависимости:
n
Р=∑Qili, т-км
i=1
где Qi– объём i-ой перевозки груза, т; li – расстояние i-ой перевозкигруза, км;
Р=380*8+150*3+230*5+190*2+300*10+60*8+40*6+200*5+140*6+
60*2+150*6+330*14+870*9+720*10=31250т-км
3. Решениетранспортной задачи с использованием MS Excel
Вначалеподготавливаем необходимые таблицы на рабочем листе MS Excel.
Таблица 3.1 –Изменяемые в процессе решения ячейки Поставщик A1 A2 A3 A4 A5 Потребитель B1 5 1 1 1 1 1 B2 5 1 1 1 1 1 B3 5 1 1 1 1 1 B4 5 1 1 1 1 1 B5 5 1 1 1 1 1 B6 5 1 1 1 1 1 B7 5 1 1 1 1 1 B8 5 1 1 1 1 1 B9 5 1 1 1 1 1 B10 5 1 1 1 1 1 Факт 10 10 10 10 10
Таблица 3.2 –Исходные данные для решения транспортной задачиЗапросы Поставщик A1 A2 A3 A4 A5 Потребитель 590 1040 1260 560 380 B1 530 6 6 7 8 3 B2 230 18 21 20 20 5 B3 190 2 15 14 15 4 B4 300 10 8 8 10 6 B5 100 6 9 8 8 8 B6 200 5 8 7 7 10 B7 140 6 6 7 8 15 B8 60 2 5 4 4 19 B9 150 17 3 5 6 6 B10 1920 14 9 10 17 12 Всего 457 86 90 90 103 88
Послеиспользования процедуры Поиск решения получаем следующие результаты:
Таблица 3.3 –Результаты поиска решенияОптимизация транспортных потоков Поставщик A1 A2 A3 A4 A5 Потребитель B1 530 200 180 150 B2 230 230 B3 190 190 B4 300 300 B5 100 100 B6 200 200 B7 140 140 B8 60 60 B9 150 150 B10 1920 330 870 720 Факт 960 870 720 890 380 Запросы Поставщик A1 A2 A3 A4 A5 Потребитель 590 1040 1260 560 380 B1 530 6 6 7 8 3 B2 230 18 21 20 20 5 B3 190 2 15 14 15 4 B4 300 10 8 8 10 6 B5 100 6 9 8 8 8 B6 200 5 8 7 7 10 B7 140 6 6 7 8 15 B8 60 2 5 4 4 19 B9 150 17 3 5 6 6 B10 1920 14 9 10 17 12 Всего 31250 7640 7830 7200 6980 1600
Вывод: витоге результаты первого и второго способов решений полностью совпадают,получен оптимальный вариант грузооборота перевозок.