Оптимизация грузопотоков

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

1. Задана транспортная сеть района, состоящая их 9-ти пунктов и дорог, соединяющая эти пункты.

     В соответствии со схемой транспортной сети района перевозок, используя метод потенциалов составляем таблицу кратчайших расстояний района перевозок груза (табл. 3).

     Таблица 3

     Матрица условий

 
     

2. Приступаем  к нахождению индексов, используя  правила

     Vj=Ui;  Vj=Ui+Lij

     Принимаем индекс U₁=V₁=0

     По  правилу находим V₃=U₃=6, V₆=U₆=7; V₇=U₇=4; V₈=U₈=4; V₉=U₉=4;

     V₂=min (по столбцу)=9, V₂=U₂=9;

     V₄= min (по столбцу)=9, V₄=U₄=9;

     V₅= min (по столбцу)=12, V₄=U₄=12;

     Проверяем заполненные клетки таблицы на оптимальность  по критерию: lij ≥ Vj-Ui. Критерий соблюдается, поэтому решение оптимально, кратчайшие расстояния от АТП до других пунктов задано числами V₂-V₉.

     Затем аналогично выполняем определение  кратчайших расстояний между грузопунктами.

     2.3. Определив кратчайшие расстояния между грузопунктами транспортной сети района, заносим полученные данные в таблицу кратчайших расстояний (таблица 4).

     Таблица 4

     Кратчайшие расстояния между грузопунктами

 
 
 
     

3. ОПТИМИЗАЦИЯ ГРУЗОПОТОКОВ

     В этом разделе определяются оптимальные  размеры и направления грузопотоков по каждому виду груза, а также  составляется сводный план грузопотоков.

1. Оптимальные размеры и направления грузопотоков по перевозке краски эмалевой белой.
1. На основании исходных данных формируется матрица (табл. 5): составляем матрицу условий способом минимального элемента по строке – вначале планируем перевозки грузов с первого склада, записывая их в клетки с ближайшим расстоянием к потребителю, пытаясь, таким образом, полностью удовлетворить их потребности.

     Таблица 5

     Матрица условий

     3.1.2. Затем проверяем заполненность матрицы, т.е. число заполненных клеток по критерию m+n-1. В данном случае количество занятых клеток удовлетворяет условию, что позволяет проводить дальнейшие расчеты.

     3.1.3. Производим расчет индексов U и V для занятых клеток. Для этого используются следующие правила:

     - вспомогательный индекс U₁ всегда равен нулю;

     - для каждой занятой клетки  матрицы сумма, соответствующей  ей индексов U и V, равна расстоянию в данной клетке, т.е. удовлетворяет условию U_i + V_j = l_ij. Это дает возможность при известном одном индексе определить значение другого.

     3.1.4. Сравниваем во всех незанятых клетках расстояния l_ij с суммой соответствующих ей индексов по критерию U_i + V_j ≤ l_ij, т.е. расстояния должны быть больше или равны сумме индексов. Сравнение показывает, что у незанятой клетки А₃В₁ расстояние меньше суммы индексов, 2+6>3, следовательно, составленный допустимый исходный план не является оптимальным и подлежит улучшению. Выявленная клетка является резервом улучшения плана, такие клетки называют потенциальными, почему и данный метод называют «методом потенциалов».

     Метод потенциалов является модификацией симплекс-метода решения задачи линейного  программирования применительно к  транспортной задаче. Он позволяет, отправляясь  от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема  отдельной итерации такова. По допустимому  решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. 

     3.1.5. Улучшаем неоптимальный план перемещением загрузок в потенциальные клетки матрицы. Для этого составляем цепочку возможных перемещений загрузок в матрице и определяем величины перемещения загрузки и самого перемещения (табл. 6). Для потенциальной клетки (в нашем случае А₃В₁), строим замкнутую цепочку из горизонтальных и вертикальных линий так, чтобы одна ее вершина лежала в потенциальной клетке, а все остальные вершины располагались бы в занятых клетках.

     Таблица 6

     Построение цепочки перемещений

 
 
 

     Составив  цепочку, помечаем знаком «+» ее нечетные вершины и знаком «-» четные вершины. Наименьшая из четных загрузок определяет величину перемещаемой загрузки. Переместив эту загрузку из клетки со знаком «-» в клетку со знаком «+», получаем улучшенный вариант плана перевозки (табл. 7) .

Таблица 7

     Улучшенный  вариант плана  перевозки

     3.1.6. Производим расчет индексов U и V для занятых клеток, используя правила, указанные в пункте 3.1.3.,  а затем сравниваем во всех незанятых клетках расстояния l_ij с суммой соответствующих ей индексов по критерию U_i + V_j ≤ l_ij (смотри пункт 3.1.4.).