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

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (производства) в n пунктов назначения (потребления) . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе в j-м пункте назначения, а через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения.

Составим математическую модель задачи. Найти наименьшее значение линейной функции

(12.1)

при условиях

(12.2)

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

Таблица 12.1

Пункты отправления	Пункты назначения	Запасы
			…
				…
				…
…	…	…	…	…	…	…
				…
Потребности				…

УСЛОВИЕ РАЗРЕШИМОСТИ ТРАНСПОРТНОЙ ЗАДАЧИ

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

(12.3)

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

В случае вводится фиктивный (n + 1)-й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю: аналогично, при вводится фиктивный (m + 1)-й пункт отправления с запасом груза и тарифы полагаются равными нулю: .

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

Число переменных в транспортной задаче с m пунктами отправления и n пунктами назначения равно mn, а число уравнений в системе (12.2) ‑ m + n. Так как мы предполагаем выполнение условия (12.3), то число линейно независимых уравнений равно m + n – 1. Следовательно, опорный план может иметь не более m + n – 1 отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонент равно в точности m + n – 1, то план называется невырожденным, а если меньше – то вырожденным.

ПОСТРОЕНИЕ ПЕРВОНАЧАЛЬНОГО ОПОРНОГО ПЛАНА

Для определения опорного плана существует несколько методов: метод северо-западного угла (диагональный метод), метод наименьшей стоимости (минимального элемента), метод двойного предпочтения и метод аппроксимации Фогеля.

Кратко рассмотрим каждый из них:

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

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

Дата добавления: 2015-04-29