ИССО-для ГОСов / транспортная задача

1. Транспортная задача. Методы построения опорного плана. Метод оптимального распределения поставок.

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

Имеется m пунктов отправления A1, A2, . . . , Am, в которых сосредоточены запасы однородных грузов в количестве соответственно a1, a2, . . . , am единиц. Имеетсяn пунктов назначения В1, В2, . . . , Вn, подавших заявки соответственно на b1, b2, . . . , bn единиц груза. Если сумма всех заявок равна сумме всех запасов

,

то задача называется задачей закрытого типа. Известны стоимости Сij перевозки единицы груза от каждого пункта отправления Ai до каждого пункта назначения Bj. Все числа cij образующие прямоугольную матрицу, заданы:

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

Обозначим xij - количество единиц груза, отправляемого из пункта Ai в пункт назначения Bj . Неотрицательные переменные xij можно записать в виде матрицы

Эти неотрицательные переменные должны удовлетворять следующим условиям:

1) Суммарное количество груза, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте.

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

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

3) Суммарная стоимость всех перевозок должна быть минимальной:

В силу особой структуры ТЗ все операции по нахождению оптимального плана сводятся к манипуляциям непосредственно с таблицей. Транспортная таблица состоит из m строк и n столбцов. В верхнем левом углу каждой клетки будем указывать стоимость Cij перевозки единицы груза из Аi в Вj , а в правом нижнем углу помещаем перевозку xij.

Заказы Запасы		B1		B2		…	Bn
		b1		b2		…	bn
A1	a1	c11		c12		…	c1n
			x11		x12			x1n
A2	a2	c21		c22		…	c2n
			x21		x22			x2n
…	…	…		…		…	…
Am	am	cm1		cm2		…	cmn
			xm1		xm2			xmn

Алгоритм решения транспортной задачи делится на два этапа:

Первый этап: Построение опорного плана методом северо-западного угла или методом наименьшей стоимости.

Второй этап: Нахождение оптимального распределения поставок методом потенциалов.

Рассматрим алгоритм записи исходного опорного решения методом северо-западного угла:

1. В таблицу всегда заносятся неотрицательные числа.

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

3. Так как при записи базисной переменной исключается или строка, или столбец, и лишь при записи последней базисной переменной исключаются одновременно и строка, и столбец, то всего в таблицу вносятся (m+n-1) базисных переменных. После записи опорного плана всегда проверяем соответствует ли количество заполненных клеток величине(m+n-1).

Алгоритм метода потенциалов заключается в следующем.

1. Строим первоначальный опорный план, содержащий (m+n-1) занятых клеток (первый этап ).

2. Для полученого плана определяем систему потенциалов ai (i= 1,2,…m) и bj (j= 1,2,…n), исходя из условия с ij= ai+bj (это условие действительно для всех занятых клеток). Поскольку для построения системы потенциалов используем только занятые клетки, то число неизвестных(ai

и bj), равное (m+n), на единицу превышает число уравнений, равное (m+n-1). Поэтому для однозначного определения всех потенциалов одному из них придают произвольное значение(как правило, тому, для которого в соответствующей ему строке или столбце находится наибольшее количество занятых клеток). Обычно в качестве такого произвольного значения выбирается нуль. Затем из условия сij= ai+bj последовательно находят значения остальных потенциалов.

3. Исследуем систему потенциалов на оптимальность. План оптимален, если для всех незанятых клеток выполняется условие сij>= ai +bj, или сij-(ai+bj) >= 0. То есть, разность между оценкой незанятой клетки и суммой потенциалов строки и столбца, на пересечении которых находится эта клетка, является неотрицательной величиной. Обозначим эту разность через lij

. Проверим выполнение условия lij >=0 для каждой свободной клетки. Если это условие выполняется, то построенный опорный план оптимален.

В противном случае переходим к новому плану.

4. Для этого вычислим lij для всех незанятых клеток и среди отрицательных величин находим наибольшую по абсолютному значению, что соответствует клетке с максимальным нарушением оптимальности. Такая клетка называется “плохой”.

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

6. В углах поворота цикла проставляем знаки плюс и минус чередуя их, начиная с“плохой” клетки, в которую записываем “+”.

7. Выбираем наименьшую поставку среди клеток, помеченных знаком “-”.

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