1.2 Построение первоначального плана

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

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

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

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

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

3) Метод двойного предпочтения.

В каждом столбце отмечают знаком V клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку VV. В них находится минимальная стоимость как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы и строки. Затем распределяют перевозки по клеткам, отмеченным знаком V. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости. Опорный план, полученный таким образом, наиболее близок к оптимальному плану.

1.3 Метод потенциалов

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

1) Построение системы потенциалов.

Для построения системы потенциалов используем условие

(5)

2) Проверка выполнения условия оптимальности для незанятых клеток.

Просматриваем строки и для каждой незанятой клетки проверяем выполнение условия

(6)

Если для всех незанятых клеток условие (6) выполняется, то план является оптимальным. Если для некоторых клеток , то план является неоптимальным.

3) Выбор клетки, в которую необходимо послать перевозку.

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

4) Построение цикла и определение величины перераспределения груза.

Для определения количества единиц груза подлежащих перераспределению отмечается знаком «+» незанятая клетка, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. Появляется цикл, все вершины которого, за исключением клетки, отмеченной знаком «+», находятся в занятых клетках, причем этот цикл единственный. Отыскивается цикл и, начиная движение от клетки, отмеченной знаком «+», поочередно проставляются знаки «-» и «+». Затем находится , где- перевозки, стоящие в вершинах цикла, отмеченных знаком «-». Величина определяет, сколько единиц груза можно перераспределить по найденному циклу и на эту величину увеличиваются поставки в верши­нах со знаком «+» и уменьшаются поставки в вершинах со зна­ком «-».

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

Для проверки на оптимальность нового опорного плана вновь строится система потенциалов и проверяется выполнение условия оптимальности для каждой незанятой клетки.

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

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

1.4 Открытая модель транспортной задачи

Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е. выполняется условие , называется закрытой моделью; в противном случае – открытой.

Для открытой модели может быть два случая: а) суммарные запасы превышают суммарные потребности ; б) суммарные потребности превышают суммарные запасы .

Открытая модель решается приведением к закрытой модели.

В случае (а) вводится фиктивный потребитель , потребности которого . В случае (б) вводится фиктивный поставщик , запасы которого .

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

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