Методы построения плана перевозок

Рассмотрим два метода построения первоначального плана перевозок в распределительной таблице.

Метод "северо-западного угла".

1) Будем распределять груз, начиная с верхней левой клетки, условно называемой северо-западной: в клетку (1.1) заносят число, минимальное из чисел и , т.е. .

2) Если , то и потребности пункта полностью удовлетворены. После этого заполняется клетка (1.2) числом .

3) Если же , то и запас груза в полностью исчерпан. После этого заполняется клетка (2.1) числом .

4) Процесс продолжается до тех пор, пока не исчерпаются все ресурсы и полностью не будет удовлетворен спрос . Последней заполняется клетка .

Незаполненным клеткам таблицы соответствуют значения переменных (свободные переменные), а заполненным - значения переменных (базисные переменные).

Число заполненных кленок в опорном плане перевозок должно быть ровно . Если в процессе заполнения таблицы одновременно исчерпывается запас груза и полностью удовлетворен спрос (одновременно исключается строка и столбец), то в какую-либо свободную клетку надо условно считать занятой. Для этого в нее нужно вписать число 0, но чтобы эта клетка не образовала цикла с ранее занятыми клетками.

Метод "минимального элемента".

1) Сбалансировать задачу (убедиться, что ТЗ закрытая).

2) Определить свободную клетку с наименьшей стоимостью перевозки. Если таких клеток несколько, то выбрать клетку с наибольшей потенциальной грузоперевозкой. Если и таких клеток несколько, то выбирается любая из этих клеток.

3) В выбранную клетк

4) у поставить максимально возможную грузоперевозку для потребителя от поставщика.

5) Из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения груза заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен.

6) В результате получаем опорный план, который должен содержать заполненных клеток.

Задача 1. Приведем в качестве примера два плана перевозок транспортной задачи: первый построен по методу "северо-западного угла" (табл.2), второй - методом "минимального элемента" (табл.3).

Таблица 2 - План перевозок по методу «северо-западного угла»

Запасы груза	Потребности в грузе

Клетки заполнялись в последовательности: (1.1), (1,2), (2,2), (2,3), (3,3), (3,4). План перевозок имеет вид .

Стоимость перевозок по плану "северо-западного угла" равна

ден. ед.

Таблица 3 - План перевозок по методу "минимального элемента".

Запасы груза	Потребности в грузе

Клетки заполнялись в последовательности: (1,3), (3,2), (3,3), (2,1), (3,4), (2,4). Стоимость перевозок по плану "минимального элемента" равна

ден. ед.

Так как 1530 < 3220, то план перевозок, построенный по методу "минимального элемента", лучше, чем план, построенный по методу "северо-западного угла".

Дата добавления: 2014-01-07