Методические указания по курсовой работе для студентов специальности 22. 02 Автоматизированные системы (стр. 9 из 13)

Тема 3. Транспортная задача по критерию времени

Покажем на конкретном примере решение транспортной задачи по критерию времени.

Пример. Определить оптимальный план перевозок из условия доставки груза в кратчайший срок при следующих данных. Имеется три пункта производства однородного продукта, в каждом из которых производится количество этого продукта:

Имеется пять пунктов потребления проводимого однородного продукта с объемом потребления в каждом из них: Задана матрица затрат времени на перевозку однородного продукта

где

время, затрачиваемое на перевозку из го пункта отправления в й пункт потребления.

Подчеркнем два момента:

а)перевозки считаются законченными, если закончилась самая длительная перевозка;

б)время

не зависит от количества перевозимого продукта из го пункта отправления в й пункт потребления.

Решение. Прежде всего заметим, что если определить план перевозок из условия минимизации функции

то по этому плану в общем случае продукт потребителю не будет доставлен в кратчайший срок.

Решение задачи начинаем, как обычно, с начального опорного, построенного, например, с помощью метода "северо-западного угла".

Дальнейшие расчеты можно вести одним из двух методов: 1)минимизировать функцию

но при дополнительных условиях, вводимых последовательно в процессе решения; 2)производить последовательные преобразования решения путем построения так называемых "разгрузочных циклов".

Первый способ. 1-ый шаг. Имеем начальный опорный план

Подчеркиваем в матрице

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

2-ой шаг. Все элементы матрицы, которым соответствуют

блокируем, то есть заменяем реальные значения на произвольно большое число В рассматриваемом примере блокированию подлежит элемент, у которого 3, 5, куда и заносим вместо число и тем самым имеем матрицу

2-ой шаг. Для измененной на 2-ом шаге матрицы

ищем оптимальное решение, минимизирующее функцию

Это можно сделать, в частности, применяя метод потенциалов. В рассматриваемом примере на предварительном этапе начального опорного плана

строим матрицу . Представим схему, которая соответствует плану .

Отсюда

Выделяем в этой матрице отрицательный элемент

и в матрице строим замкнутый маршрут, затем производим перемещение и получаем план

Преобразуем матрицу

затем улучшаем план до тех пор пока имеется возможность. В рассматриваемом примере получим

Возвращаемся к 1-ому шагу, продолжая расчеты в той же последовательности

1-й шаг. В решении

элемент , т.е. мы освободились от самой длительной перевозки начального плана . В плане среди находим В рассматриваемом примере Поэтому на 2-ом шаге записываем новую матрицу в которой элементы и заменены числом

2-ой шаг. Исходя из этой матрицы, применением метода потенциалов находим

И так как в этом плане элементы

и соответствуют блокированным элементам матрицы то найденное на предыдущем этапе решение является оптимальным решением, исходя из критерия времени. Этому плану соответствует

Второй способ. 1-ый шаг. Имеем начальный опорный план

Определяем наибольший элемент

из всех соответствующих плана и все элементы соответствующие подчеркиваем. В данном примере а элементы для отсутствуют.