Транспортная задача по критерию времени
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
?аспределяются объемы перевозок(осуществляется сдвиг по циклу). Перевозка загружается в выбранную свободную клетку и освобождается одна из занятых клеток, получается новое опорное решение.
Если таблица транспортной задачи содержит опорное решение, то для любой свободной клетки таблицы существует единственный цикл, содержащий эту клетку и часть клеток, занятых опорным решением.
Для удобства вычислений вершины циклов нумеруют и отмечают нечетные знаком +, а четные знаком - . Такой цикл называется означенным.
Сдвигом по циклу на величину называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком +, и уменьшение объемов перевозок на ту же величину во всех не четных клетках, отмеченных знаком - .
.2.3 МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА
Согласно данному методу запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут иiерпаны полностью, после чего используется запасы следующего по номеру поставщика.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. При этом нулевые перевозки принято заносить в таблицу только в том случае, когда они попадают в клетку (i,j), подлежащую заполнению, т.е. в таблицу заносятся только базисные нули , остальные клетки с нулевыми перевозками остаются пустыми.
Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы условий, соответствующие этим клеткам, линейно независимы.
Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому, опорное решение, построенное по данному методу, может быть далеким от оптимального.
2.2.4ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЮ ВРЕМЕНИ
Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется m поставщиков с запасами однородного груза в количестве a1,a2, тАж,am и n потребителей, которым этот груз доставляется от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок груза, при котором запасы всех грузов являются минимальным.
Составим математическую модель этой задачи. Обозначим xij - объем перевозимого груза от i-го поставщика j-му потребителю. Система ограничений задачи не отличается от системы ограничений обычной транспортной задачи. Пусть Х=(Хij), i=1,2 тАж,m; j=1,2,тАж, n - некоторое опорное решение задачи. Запишем целевую функцию задачи. Обозначим через Т(Х) наибольшее значение элементов матрицы Т=(tij), i=1,2,тАж, m; j=1,2,тАж, n, соответствующих клеткам таблицы, занятым опорным решением: Т(Х)= max{tij}. Таким образом, за время Т(Х) план перевозок будет выполнен полностью.
Задача решается в следующем порядке. Находится начальное опорное решение Х1. Определяется значение целевой функции Т(Х1)=max{tij}=tl1k1. Все свободные клетки, которым соответствует значение tij>T(X1), исключается из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как увеличивается значение целевой функции. Чтобы уменьшить ее значение, необходимо освободить клетку (l1, k1), в которой tij достигает максимума. Для этого строят так называемые РАЗГРУЗОЧНЫЕ циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l1, k1), расставляются поочередно знаки - и + и осуществляется сдвиг на величину Q=min {xij}. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение Х2 , на котором значение целевой функции меньше, чем на Х1.
Далее снова пытаются разгрузить клетку, соответствующую Т(Х2)=max{tij}=tl2k2. Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не иiезнет.
3.ПРАКТИЧЕСКАЯ ЧАСТЬ
Составляем начальное опорное решение Х1 по методу северо-западного угла. Максимальной целевой функции T(X1)=max {10,8,5,12,4}=12 достигается в клетке (3,4). Перечеркиваем клетку (4,1), в которой время доставки груза t41=15 больше, чем T(X1)=12.
Таблица 2
Bj Ai 203040602010 206 3 2 305 - 8 307 + 4 502 + 4 5 40- 12 105015 5 9 4 50
Для улучшение решения разгрузки освободим клетку (3,4) с помощью цикла (3,4), (2,4), (2,2), (3,2). Означим цикл, найдем Q=min{10,30}=10. Осуществив сдвиг по циклу, получим второе опорное решение:
Т(Х2)=max{10,8,4,5,4}=10,
Достигается в клетке (1,1). Перечеркиваем клетку (3,4), т.к. время t34=12 больше, чем Т(Х2)=10
транспортная разгрузка сбалансированность
Bj Ai 2030406020- 10 20+ 6 3 2 30+ 5 - 8 207 4 10 502 4 105 4012 5015 5 9 4 50
Разгружаем клетку (1,1) с помощью цикла (1,1), (1,2), (2,2), (2,1). Означим цикл, найдем:
Q=min{20,20}=20.
Осуществив сдвиг по циклу, получим третье опорное решение Х3. Максимум целевой функции на этом опорном решении:
Т(Х3)=max {6,5,4,4,5,4}=6 и достигается в клетке (1,2). Перечеркиваем клетки (1,1) (2,2) (2,3) и (4,3) в них время больше, чем Т(Х3)=6
Bj Ai 203040602010 - 6 20+ 3 2 305 208 7 4 10502 + 4 10- 5 4012 5015 5 9 4 50
Разгрузим клетку (1,2) с помощью цикла (1,2), (1,3), (3,3), (3,2). Означим цикл, найдем:
Q=min {20,20}=20
Осуществляем сдвиг по циклу, получим 4 опорное решение Т(Х4).
Т(Х4)=max {5,4,4,5,4}=5 и достигается в клетках (2,1) и (3,3). Перечеркиваем клетки (1,2) и (4,2)