2.2. Нахождение начального допустимого плана

Начальный допустимый план представляет собой любой план , удовлетворяющий всем ограничениям исходной задачи. Начальный допустимый план называют такжебазисным или опорным планом.

Желательно, найти базисный план, который обеспечит как можно меньшее значение целевой функции. Для этого пользуются специально разработанными методами:

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

2). Метод минимальной стоимости.

3). Метод Фогеля.

Методы отличаются алгоритмом выбора очередной клетки, в которую помещается объем очередной перевозки.

При заполнении транспортной таблицы значениями объемов перевозок , некоторые клетки могут остаться незаполненными, их называютсвободными. Заполненные клетки, соответствующие ненулевым переменным называют занятыми, а сами переменными — базисными.

Если для сбалансированной задачи число ненулевых переменных в базисном плане равно, план называетсяневырожденным базисным планом.

План с меньшим, чем числом ненулевых компонент называетсявырожденным планом. В этом случае необходимо ввести в базисный план нулевые переменные и считать их базисными.

Исходные данные ТЗ часто задаются в матричном виде:

или

, , .

При решении ТЗ используется транспортная таблица (рис.2.1). Строки таблицы отвечают пунктам производства. В последней клетке каждой строки указан соответствующий объем производства. Например, в первой строке, которая соответствует пункту производства , объем производства равен.

Столбцы соответствуют пунктам потребления. Последняя клетка каждого столбца содержит объем потребления для соответствующего пункта .

Каждая клетка транспортной таблицы содержит информацию о перевозке из -ого пункта в-ый. Здесь— объем перевозок, а— стоимость перевозки единицы товара.

Рис. 2.1. Транспортная таблица

Пример 1. Найти начальный допустимый план транспортной задачи, заданной в матричном виде:

.

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

Построим исходную транспортную таблицу.

Первой заполняем клетку в верхнем левом углу . Присвоим ей значение равное меньшему из объемов спросаи предложения, получим. Уменьшим потребности первого пункта потребления и запасы первого пункта производства на 2. Потребности первого пункта потребления исчерпаны, запретим перевозки в этот пункт, используя символх:

1 2 3 3 2 1 5 5 4 8 2 5 2 7 4



1 2 2 3 3 1 2 — 1 5 5 4 — 8 2 5 х 7 4

Перейдем к следующей клетке и заполним ее аналогично. Уменьшим потребности второго пункта потребления и запасы первого пункта производства на 1. Запасы первого пункта производства при этом будут исчерпаны, запретим перевозки из этого пункта:

1 2 2 3 1 2 — 1 5 5 4 — 8 2 5 х 7 4



1 2 2 1 3 — x 2 — 1 5 5 4 — 8 2 5 х 7 6 4

Перейдем к следующей клетке и заполним ее аналогично :

1 2 2 1 3 x 2 — 1 5 5 4 — 8 2 5 х 6 4



1 2 2 1 3 — x 2 — 1 5 5 — x 4 — 8 2 5 х 6 1 4

Уменьшим потребности второго пункта потребления и запасы второго пункта производства на 5. Запасы второго пункта производства исчерпаны, запретим перевозки из этого пункта.

Перейдем к следующей клетке, . Уменьшим потребности второго пункта потребления и запасы третьего пункта производства на 1. Потребности второго пункта потребления исчерпаны, запретим перевозки в этот пункт:

1 2 2 1 3 — x 2 — 1 5 5 — x 4 — 8 2 5 х 1 4



1 2 2 1 3 — x 2 — 1 5 5 — x 4 — 8 1 2 5 4 х х 4

В последнюю клетку запишем . Уменьшим потребности третьего пункта потребления и запасы третьего пункта производства на 4. Получим допустимый базисный план:

1 2 2 1 3 — x 2 — 1 5 5 — x 4 — 8 1 2 4 х х х х



1 2 2 1 3 — x 2 — 1 5 5 — x 4 — 8 1 2 4 х х х х

Суммы перевозок по строкам и столбцам должны совпадать с исходной задачей. Необходимо выполнить проверку.

Найденный начальный план необходимо также проверить на вырожденность. Вычислим , количество ненулевых переменных в полученном плане тоже равно 5. Полученный базисный план (рис. 2.2) является невырожденным.

1 2	2 1	3 —
2 —	1 5	5 —
4 —	8 1	2 4

Рис. 2.2. Начальный базисный план, метод северо-западного угла

Найдем значение целевой функции для найденного плана:

b). Метод минимальной стоимости.

Алгоритм заполнения клеток такой же, как в методе северо-западного угла, изменяется последовательность заполнения клеток. Первой заполняется клетка с минимальной ценой перевозки. Если таких клеток несколько, выбираем любую из них.

Затем выбираем следующую из незаполненных клеток с минимальной ценой, пока не удовлетворим все потребности. При этом все запасы будут использованы полностью, так как рассматривается сбалансированная задача.

Применим метод минимальной стоимости к рассмотренной выше задаче.

Имеются две клетки с минимальной стоимостью перевозки единицы товара . Заполним сначала клетку.

1 2 3 3 2 1 5 5 4 8 2 5 2 7 4



1 2 2 3 3 1 2 — 1 5 5 4 — 8 2 5 х 7 4

Затем заполним клетку .

1 2 2 3 1 2 — 1 5 5 — х 4 — 8 2 5 х 7 2 4



1 2 2 3 1 2 — 1 5 5 — х 4 — 8 2 5 х 2 4

Следующее по величине значение стоимости равное 2 тоже соответствует двум клеткам . Заполним сначала клетку, а затем:

1 2 2 1 3 х 2 — 1 5 5 — х 4 — 8 2 5 х 2 1 4



1 2 2 1 3 — х 2 — 1 5 5 — х 4 — 8 2 4 1 х 1 х

Осталось заполнить клетку =1 (рис. 2.3). Последовательность заполнения ячеек данным методом: ,,,,.

1 2	2 1	3 —	х
2 —	1 5	5 —	х
4 —	8 1	2 4	х
х	х	х

Рис. 2.3. Начальный базисный план, метод минимальной стоимости

Для данной исходной задачи планы, найденные двумя способами, совпали. Заметим, что обычно метод минимальной стоимости дает лучшее начальное решение.

Самым распространённым способом решения транспортной задачи является получение одного из допустимых планов «методом северо-западного угла», который требует меньшего объема вычислений, с последующим его улучшением «методом потенциалов».