16. Построение исходного опорного плана (первый пункт алгоритма)
Построение опорных планов, а также их преобразование будем производить непосредственно в распределительной таблице. Если в плане перевозок переменная 
равна некоторому числу 
, то число записываем в соответствующую клетку 
и считаем ее занятой или базисной, если же 
, то клетку оставляем свободной.
Существует несколько методов построения исходного опорного плана. Рассмотрим Методы северо-западного угла и Минимального элемента на примере 8.
Пример 8
В трех хранилищах 
и 
имеется соответственно 70, 90 и 50 т топлива. Требуется спланировать перевозку топлива четырем потребителям 
и 
, спрос которых равен соответственно 50, 70, 40 и 40 т так, чтобы затраты на транспортировку были минимальными. Стоимость перевозки 1 т (в усл. ден. ед.) указана в таблице 15.
Таблица 15
|
Хранилища |
Потребители |
Запас топлива, т | |||
|
В1 |
В2 |
В3 |
В4 | ||
|
А1 |
5 |
4 |
3 |
6 |
70 |
|
А2 |
4 |
3 |
5 |
1 |
90 |
|
А3 |
2 |
4 |
1 |
5 |
50 |
|
Потребность в топливе, т |
50 |
70 |
40 |
40 |
200\210 |
Поскольку запасы топлива в хранилищах превышают спрос потребителей, введем фиктивного потребителя 
, спрос которого равен
Все тарифы фиктивного потребителя равны нулю, т. е. 
. После введения фиктивного потребителя 
открытая модель задачи преобразовалась в закрытую, а распределительная таблица примет вид (см. таблицу 16).
Таблица 16
|
Хранилища |
Потребители |
Запас топлива, т | ||||
|
В1 |
В2 |
В3 |
В4 |
В5 | ||
|
А1 |
5 |
4 |
3 |
6 |
0 |
70 |
|
А2 |
4 |
3 |
5 |
1 |
0 |
90 |
|
А3 |
2 |
4 |
1 |
5 |
0 |
50 |
|
Потребность в топливе, т |
50 |
70 |
40 |
40 |
10 |
210 |
Найдем начальный опорный план методом «северо-западного угла». Сущность его состоит в следующем: пользуясь распределительной таблицей закрытой модели, будем распределять груз, начиная с максимально возможной загрузки левой верхней, условно называемой северо-западной клетки, т. е. клетки (
). В эту клетку занесем меньшее из чисел 
, т. е. 
. Таким образом, потребности в топливе потребителя 
удовлетворены, и первый столбец из рассмотрения исключается (вычеркивается), а в хранилище 
осталось 
т топлива. Теперь левой верхней клеткой оставшейся части таблицы является клетка (
) и 
. Так как в первом хранилище топлива больше нет, то первая строка из рассмотрения исключается (вычеркивается), а потребителю 
недостает 
т топлива. Теперь заполним клетку (
) и 
. Столбец 
вычеркиваем, а в хранилище 
осталось 
Т топлива. Теперь заполним клетку (
) и 
. Строку 
и столбец 
вычеркиваем. Теперь заполним клетку (
) и 
. Столбец вычеркиваем, а в хранилище осталось 
т топлива. Незаполненной осталась одна клетка (
) и 
. Итак в распределительной таблице записан исходный опорный план (см. таблицу 17).
Таблица 17
|
Храни Лища |
Потребители |
Запас топлива, т | ||||
|
В1 |
В2 |
В3 |
В4 |
В5 | ||
|
А1 |
|
|
|
|
|
70 |
|
А2 |
|
|
|
|
|
90 |
|
А3 |
|
|
|
|
|
50 |
|
Потребность в топливе, т |
50 |
70 |
40 |
40 |
10 |
210 |
Или
.
Транспортные издержки для этого плана:
(усл. ден. ед.)
Найдем начальный опорный план методом Минимального элемента. Будем распределять груз, начиная с загрузки клетки с минимальным значением тарифа. При этом в клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен.
Итак, просматривая распределительную таблицу, замечаем, что наименьшие затраты на перевозку топлива соответствуют маршруту из хранилища 
потребителю , поэтому заполним любую клетку столбца , например клетку (
) и 
. Таким образом, потребности в топливе потребителя удовлетворены и пятый столбец из рассмотрения исключается (вычеркивается), а в хранилище 
осталось 
т топлива. Просматриваем оставшиеся клетки таблицы. Наименьшие тарифы имеют клетки (
) и (
): 
. Заполняем любую из этих клеток, например клетку () и 
. Столбец 
вычеркиваем, а в хранилище при этом останется 
т топлива. Просматриваем оставшиеся клетки таблицы. Наименьший тариф имеет клетка (). Загрузим ее: 
и вычеркиваем столбец 
, а в хранилище 
осталось т топлива. Просматриваем оставшиеся клетки таблицы. Наименьший тариф имеет клетка (
): 
. В клетку () помещаем 
и вычеркиваем строку , а потребителю недостает 
т топлива. Далее по величине тарифа следует загружать клетку (), так как 
. В клетку (
) помещаем 
и вычеркиваем строку , а потребителю недостает т топлива. Далее по величине тарифа следует загружать клетку (
), так как 
. В клетку (
) помещаем 
и вычеркиваем столбец , а в хранилище осталось 
т топлива. Заполняем оставшуюся клетку (
): 
. Итак, в распределительной таблице записан исходный опорный план (см. таблицу 18).
Таблица 18
|
Хранилища |
Потребители |
Запас топлива, т | ||||
|
В1 |
В2 |
В3 |
В4 |
В5 | ||
|
А1 |
|
|
|
|
|
70 |
|
А2 |
|
|
|
|
|
90 |
|
А3 |
|
|
|
|
|
50 |
|
Потребность в топливе, т |
50 |
70 |
40 |
40 |
10 |
210 |
Или
.
Транспортные издержки для этого плана:
(усл. ден. ед.)
Если в найденном исходном опорном плане число занятых клеток меньше, чем M + N – 1, то найденный опорный план вырожден. Для преодоления вырожденности плана следует добавить «0» в пустую клетку таким образом, чтобы эта клетка не образовывала цикла с занятыми клетками, и считать ее занятой.
Так, в последнем примере начальный опорный план, найденный методом северо-западного угла, является вырожденным (6 занятых клеток, что меньше, чем 
). Для преодоления вырожденности этого плана добавим 0, например, в клетку (
). Тогда число занятых клеток будет равно 7, и план становится невырожденным. Клетка () не образует цикла с остальными занятыми клетками.
| < Предыдущая | Следующая > |
|---|
