Транспортная задача по критерию времени
Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы условий, соответствующие этим клеткам, линейно независимы.
Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому, опорное решение, построенное по данному методу, может быть далеким от оптимального.
ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЮ ВРЕМЕНИ
Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется 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. Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.
3. ПРАКТИЧЕСКАЯ ЧАСТЬ
Составляем начальное опорное решение Х1 по методу северо-западного угла. Максимальной целевой функции T(X1)=max {10,8,5,12,4}=12 достигается в клетке (3,4). Перечеркиваем клетку (4,1), в которой время доставки груза t41=15 больше, чем T(X1)=12.
Таблица 2
Bj Ai |
20 |
30 |
40 |
60 |
20 |
10 20 |
6 |
3 |
2 |
30 |
5 |
- 8 30 |
7 |
+ 4 |
50 |
2 |
+ 4 |
5 40 |
- 12 10 |
50 |
15 |
5 |
9 |
4 50 |