- •Глава 5. Транспортные задачи
- •5.1. Основные модели транспортных задач
- •5.1.1. Простейшая транспортная задача (т-задача)
- •5.1.2. Транспортная задача с ограниченными пропускными способностями (Td- задача)
- •5.1.3. Задачи с неоднородным грузом
- •5.1.4. Многоиндексные задачи
- •5.1.5. Транспортные задачи по критерию времени
- •5.2. Метод потенциалов
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •5.2.2. Переход от одного плана перевозок к другому
- •5.2.3. Признак оптимальности
- •5.2.4. Алгоритм метода потенциалов
- •5.2.5. Двойственная пара транспортных задач
- •5.3. Приведение открытой транспортной задачи к закрытой
- •5.4. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •5.6. Транспортные задачи в сетевой постановке (транспортные сети)
- •5.7. Задания для самостоятельной работы
Правило северо-западного угла
Все исходные данные и переменные сбалансированной Т-задачи удобно представить в виде таблицы (табл. 5.1).
Построение плана начинается с северо-западной клетки таблицы, то есть первым определяется значение переменной X11.
Таблица 5.1
|
b1 |
b2 |
… |
bn |
C11 X11 |
C12 X12 |
… |
C1n X1n | |
C21 X21 |
C22 X22 |
… |
C2n X2n | |
… |
… |
… |
… |
… |
Cm1 Xm1 |
Cm2 Xm2 |
… |
Cmn Xmn |
Так как оно должно быть максимально допустимым, то
При этом обязательно выполнится одно из равенств (5.3), (5.4), что соответствует закрытию строки или столбца: переменные в остальных клетках строки или столбца будут равны нулю. Конкретнее, если X11=а1, то закрывается первая строка и X12=X13=…=X1n=0, а следующей базисной переменной будетX21. Из указанного выше принципаследует X21=min(a2, b1-a1). Если же окажется, чтоX11=b1, то закроется первый столбец и следующей базисной переменной станетX12=min(a1-b1, b2).
Весь процесс построения начального плана можно представить в виде следующего дерева решений.
Общее правило определения значения очередной базисной переменной:
Xij=min(остаток отai, остаток до bj). (5.13)
Из него следует, что на каждом шаге закрывается или строка, или столбец, а на последнем шаге при назначении Xmn закрываются одновременноm-я строка иn-й столбец (так как задача сбалансированная). Таким образом, число базисных переменных равноm+ n-1.Построение начального плана завершено.
Пример 5.1.Исходные данные и построение начального плана показано в табл. 5.2. Значения базисных переменных выделены красным (серым) цветом, а порядок движения по клеткам отражен стрелками. Этому плану соответствуют суммарные затратыL=1295.
Таблица 5.2
Поставщик |
Потребитель |
Запасы груза | |||
B1 |
B2 |
B3 |
B4 | ||
A1 |
6 75 |
7 25 |
3 |
5 |
100 |
A2 |
1 |
2 55 |
5 60 |
6 35 |
150 |
A3 |
3 |
10 |
20 |
1 50 |
50 |
Потребность в грузе |
75 |
80 |
60 |
85 |
300 |
Правило минимального элемента.
В приведенном способе построения плана не участвовали затраты на перевозку. Следует ожидать, что учет затрат позволит получить начальный план, более близкий к оптимальному. Этим и отличается расматриваемое правило.
Первой заполняется клетка с минимальными затратами. Пусть minCij=Ckp. Тогда Xkp=min(ak, bp). Если при этом закрывается строка k, то в столбце p ищем клетку с минимальными затратами и определяем значение соответствующей переменной согласно (5.13).При закрытии столбцаp действуем аналогично в строке k. В общем случае клетка, лежащая в закрытом столбце и/или закрытой строке является закрытой, иначе – открытой. На каждом шаге движение идет либо по столбцу, либо по строке и при этом отыскивается среди открытых клетка с минимальным значениемCij.
Пример 5.2. Построим начальный план по правилу минимального элемента для задачи из примера 1. Результат представлен в табл. 5.3.
Таблица 5.3
Поставщик |
Потребитель |
Запасы груза | |||
B1 |
B2 |
B3 |
B4 | ||
A1 |
6
|
7 5 |
3 60 |
5 35 |
100 |
A2 |
1 75 |
2 75 |
5
|
6
|
150 |
A3 |
3 |
10 |
20 |
1 50 |
50 |
Потребность в грузе |
75 |
80 |
60 |
85 |
300 |
При таком начальном плане L=665, что меньше чем в примере 1. Однако нельзя утверждать, что для любых данных этот способ дает лучший план. Правильнеее говорить, что правило минимального элемента эффективнее в среднем (на множестве задач). В то же время алгоритм реализации этого правила сложнее, чем правила северо-западного угла.
Применяется также вариант, в котором на каждом шаге ищется клетка с минимальными затратами среди всех открытых клеток. Такой способ еще сложнее, но в среднем дает планы, более близкие к оптимальным.