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)  Полученные новые значения загрузок записываем в другую таблицу(улучшенное значение). ............