Построение исходного опорного плана

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

Для построения начального опорного плана в распределительной таблице исполь-зуют такие правила и методы, как правило «северно-западного угла», правило «мини-мального элемента», метод Фогеля.

Рассмотрим правило «минимального элемента». Суть его состоит в следующем. Просматривая тарифы распределительной таблицы, в первую очередь заполняется клетка с минимальным значением тарифа. При этом в клетку записывается максимально возмож-ное значение поставки. Затем из рассмотрения исключают строку, соответствующую по-ставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения закан-чивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем опорный план, который должен содержать загруженных клеток. В процессе заполнения таблицы могут быть одновременно исклюю-чены строка и столбец. Так бывает, когда полностью исчерпывается запас груза и пол-ностью удовлетворяется спрос (вырожденная задача). В этом случае в свободные клетки надо записать число 0 – «нуль-загрузку», условно считая такую клетку занятой. Однако число 0 записывается в те свободные клетки, которые не образуют циклов с ранее заня-тыми клетками.

После построения начального опорного плана ТЗ возникает вопрос: как опреде-лить, будет ли построенный план оптимальным? Чтобы ответить на этот вопрос, необхо-димо знать признак оптимальности. Для этого разработан метод потенциалов, который опирается на теорему о потенциалах.

Каждому поставщику (ограничению по запасам) поставим в соответствие число , а каждому потребителю (ограничения по спросу) – число . Числа и называются потенциалами соответственно i -го поставщика и j -го потребителя.

Следующую теорему о потенциалах примем без доказательства.

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