Постановка задачи и ее математическая модель

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

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

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

Транспортные издержки здесь являются условным понятием. В различных задачах в роли их нередко могут выступать тариф, расстояние, время и т.п.

Обозначим через количество единиц груза, запланированных к перевозке от -го поставщика к -му потребителю; тогда условие задачи можно записать в виде таблицы 1.

Распределительная таблица транспортной задачи

Таблица 1.

поставщики	потребители	запасы
		…
			…
			…
… … …	… … …	… … …	… … …	… … …	… … …
			…
потребности			…

Матрица называется матрицей тарифов (издержек) или транспор­тных расходов.

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

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

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

а) все грузы должны быть вывезены, т.е. ;

б) все потребности должны быть удовлетворены, т.е. ;

в) переменные должны удовлетворять условиям неотрицательности.

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

Найти наименьшее значение функции

при ограничениях

.

В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е.:

.

Такая модель называется закрытой.

Теорема. Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.

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

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

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

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

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

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

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

Шаги повторяются до тех пор, пока не будут удовлетворены потребно­сти всех потребителей и пока не будут вывезены все запасы.

Пример 1. Рассмотрим транспортную задачу, условие которой записано в таблице 2.

Таблица 2.

поставщики	потребители	запасы
	0,2	0,7	0,8
	0,3		0,7
	1,1	1,6
	0,7
потребности

Очевидно, что транспортная зада­ча является закрытой, так как .

Требуется построить опорный план этой задачи методом северо-за­падного угла.

Решение. Не учитывая стоимости перевозки груза, начинаем удовлетво­рение потребностей первого потреби­теля за счет запаса поставщика .

Дня этого сравниваем объемы и , меньший из объемов, т.е. 110 ед., записываем в левый нижний угол клетки (табл. 3).

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

У поставщика осталось 255 ед. груза, сравниваем этот остаток с потребностями . Его потребности 260 ед. груза удовлетворим за счет постав­щика и частично (еще 5 ед.) за счет поставщика и т.д.

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

Таблица 3.

поставщики	потребители	запасы
потребности

При составлении опорного плана методом северо-западного угла сто­имость перевозки единицы груза не учитывалась, поэтому построенный план далек от оптимального.

Транспортные расходы по этому плану составляют

.

Метод минимального элемента. В методе северо-западного угла при построении опорного плана не учитываются величины затрат , поэтому в дальнейших расчетах потребуется много итераций для достижения оптималь­ного плана. Число итераций можно сократить, если исходный план строить методом минимального элемента. Суть метода состоит в том, что на каждом шаге осуществляется максимально возможное размещение груза в клетку с минимальным тарифом . Заполнение таблицы начинается с клетки, которой соответствует наименьший элемент матрицы тарифов. В эту клетку помеща­ют меньшее из чисел или . Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетво­рен. Может оказаться, что следует исключить строку и столбец одновременно, если полностью израсходованы запасы поставщика и полностью удовлетворен спрос потребителя. Далее из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом, и процесс распределения запасов продолжают до тех пор, пока все они не будут распределены, а спрос удовлетворен.

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

Пример 2. Составить опорный план предыдущей задачи методом минимального элемента.

Таблица 4.

поставщики	потребители	запасы
потребности

Транспортные расходы по этому плану составляют

.

Теорема. Все перевозки любого опорного плана транспортной задачи являются линейными комбинациями объемов производства и потребления с коэффициентами .

Метод потенциалов. Применение симплекс-метода приводит к громоздким таблицам с неизвестными. Самым распространенным является метод потенциалов.

Теорема. Если план транспортной задачи является оптимальным, то ему соответствует система из чисел и , удовлетворяющих условиям

для ;

для .

Числа и называются потенциалами соответственно поставщиков и потребителей.