Поставщики товара – оптовые
коммерческие предприятия
имеют
запасы товаров соответственно в количестве:
ед.,
и розничные торговые предприятия
-
подали заявки на закупку товаров в объемах соответственно:
Тарифы перевозок единицы груза с
каждого из пунктов поставки в соответствующие пункты потребления
заданы в виде матрицы:
Найти такой план перевозки груза от
поставщиков к потребителям, чтобы совокупные затраты на
перевозку были минимальными.
Решение:
Так как запасы товаров у поставщиков
не
равны общей потребности потребителей
,
мы имеем дело с открытой транспортной задачей.
Введем фиктивного потребителя
с
потребностью а
тарифы положим равными наибольшему из всех тарифов. В целевой
функции этот потребитель не учитывается.
Потребности
290
380
350
80
З
а
п
а
с
ы
410
12
15
5
15
190
8
13
7
15
300
7
15
5
15
200
4
7
10
15
Распределим грузы в первую очередь в те
клетки, в которых находится минимальный тариф перевозок
,
т. е. сначала в клетки с тарифами 4, 5, 7 и т. д., с учетом
потребностей и запасов.
290
380
350
80
410
12
15
5
350
15
60
190
8
13
190
7
15
300
7
90
15
190
5
15
20
200
4
200
7
10
15
Контроль: число занятых клеток
должно быть равно:
Исходное опорное решение:
Стоимость перевозок при этом
составит:
Проверим найденное решение на
оптимальность. Для этого вводим потенциалы
и
занятых
клеток. Добавляем к таблице строку
и
столбец .
290
380
350
80
410
12
15
5
350
15
60
0
190
8
13
190
7
15
-2
300
7
90
15
190
5
15
20
0
200
4
200
7
10
15
-3
7
15
5
15
Одному из потенциалов придаем
произвольное значение, например,
Остальные
потенциалы находим из условия
.
Например,
и
т.д.
Далее находим оценки свободных
клеток:
Среди оценок имеются положительные, поэтому найденное опорное решение не является оптимальным. Чтобы перейти к другому опорному решению, для клетки с
строим
цикл (цепь, многоугольник), все вершины которого, кроме одной,
находятся в занятых клетках; углы прямые, число вершин четное.
Около свободной клетки цикла ставим знак (+), затем поочередно
проставляем знаки (-) и (+). У вершин со знаком (-) выбираем
минимальный груз, прибавляем его к грузам, стоящим у вершин со
знаком (+), и отнимаем этот минимальный груз от грузов у вершин
со знаком (-). В результате перераспределения грузов получим
новое опорное решение. Это решение проверяем на оптимальность и
т. д. до тех пор, пока не получим оптимальное решение. Строим
цикл для клетки 4,
2.
Новое решение:
Стоимость перевозок уменьшилась и
стала равна 7550.
Проверяем на оптимальность.
290
380
350
80
410
12
15
5
350
15
60
0
190
8
13
190
7
15
3
300
7
280
15
5
15
20
0
200
4
10
7
190
10
15
-3
7
10
5
15
остальные
оценки свободных клеток неположительные.
Строим цикл для клетки
2,
1.
Новое решение:
Стоимость перевозок 7530.
Проверяем на оптимальность.
290
380
350
80
410
12
15
5
350
15
60
0
190
8
10
13
180
7
15
1
300
7
280
15
5
15
20
0
200
4
7
200
10
15
-5
7
12
5
15
Строим цикл для клетки
2,
4.
Новое решение:
Стоимость перевозок 7520.
Проверяем на оптимальность.
290
380
350
80
410
12
15
5
350
15
60
0
190
8
13
180
7
15
10
0
300
7
290
15
5
15
10
0
200
4
7
200
10
15
-6
7
13
5
15
Среди оценок нет положительных.
Оптимальное решение найдено:
Минимальная стоимость перевозок
7520.
Однако среди оценок имеется нулевая
значит,
задача имеет альтернативное решение.
Произведем перераспределение грузов
относительно клетки 3,
2.
Еще одно решение:
Минимальная стоимость перевозок при
этом не меняется.
строим
цикл (цепь, многоугольник), все вершины которого, кроме одной,
находятся в занятых клетках; углы прямые, число вершин четное.
Около свободной клетки цикла ставим знак (+), затем поочередно
проставляем знаки (-) и (+). У вершин со знаком (-) выбираем
минимальный груз, прибавляем его к грузам, стоящим у вершин со
знаком (+), и отнимаем этот минимальный груз от грузов у вершин
со знаком (-). В результате перераспределения грузов получим
новое опорное решение. Это решение проверяем на оптимальность и
т. д. до тех пор, пока не получим оптимальное решение. Строим
цикл для клетки 
