Методы решения транспортной задачи

МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА. При использовании этого метода опорный план перевозок начинают строить с левого верхнего угла матрицы перевозок по следующему алгоритму.

Первому потребителю назначается ресурс от первого производителя. При этом возможны следующие варианты:

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

− Запрос первого потребителя удовлетворен полностью. Остаток от ресурса от первого производителя назначают второму потребителю, а при необходимости и третьему потребителю;

− Запрос первого потребителя обеспечен полностью ресурсом от первого производителя и ресурс первого производителя израсходован полностью. Далее переходят к обеспечению запроса второго производителя.

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

МЕТОД МИНИМАЛЬНОГО ЭЛЕМЕНТА. Суть метода состоит в том, что в матрице стоимостей С =(с_ij) выбирается стоимость минимальной перевозки с_ij.Затем назначается максимальный объем ресурса от производителя I к потребителю j для данной перевозки. При этом возможны варианты:

производитель I имеет ресурса больше, чем надо потребителю j. В этом случае удовлетворяется полностью заявка потребителя j, а остаток произведенного ресурса будет распределен после. Т.к. потребность потребителя j удовлетворена полностью, то исключается из рассмотрения столбец матрицы стоимости, принадлежащий j-му потребителю.
производитель I имеет ресурса меньше, чем надо потребителю j. В этом случае весь имеющийся ресурс производителя I назначается потребителю j. Недостающая часть ресурса потребителю j будет назначена потом. Т.к. весь ресурс производителя I исчерпан полностью, то из рассмотрения удаляется строка матрицы стоимостей, принадлежащая производителю i.
Производитель I имеет ресурса столько, сколько надо потребителю j. В этом случае из рассмотрения удаляются и строка и столбец матрицы стоимостей.

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

ДАЛЬШЕ НЕ ПИШИ!!!! :D

РАСПРЕДЕЛИТЕЛЬНЫЙ МЕТОД УЛУЧШЕНИЯ ПЛАНА ПЕРЕВОЗОК. Суть распределительного метода состоит в том, что ресурсы, назначенные потребителям по опорному плану, перераспределяются. Алгоритм перераспределения следующий:

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

Если при решении ТЗ оптимальное решение должно быть максимальным, то алгебраические суммы по всем контурам должны быть отрицательными или равными 0.

Если при решении ТЗ оптимальное решение должно быть минимальным, то алгебраические суммы по всем контурам должны быть положительными или равными 0.

Если план перевозок не оптимален, то перераспределение ресурсов выполняется следующим способом:

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

Пример

Рассмотрим процесс построения оптимального плана на примере опорного плана , полученного методом минимальных элементов. Матрица стоимостей:

Стоимость перевозки	производство




потребление

Опорный план

Получили исходные данные для распределительного метода. Свободные(пустые) элементы опорного плана имеют индексы1,4;2,2;2,3;3,1;3,3;3,4.Для каждого свободного элемента построим свой кратчайший прямоугольный контур.

Для элемента 1,4 построим контур 1,4 2,4 2,1 1,1

Для элемента 2,2 построим контур 2,2 2,1 1,1 1,2

Для элемента 2,3 построим контур 2,3 2,1 1,1 1,3

Для элемента 3,1 построим контур 3,1 1,1 1,2 3,2

Для элемента 3,3 построим контур 3,3 3,2 1,2 1,3

Для элемента 3,4 построим контур 3,4 3,2 1,2 1,1 2,1 2,4

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

Первый контур 7+(-2)+3+(-6)=2

второй контур 6+(-3)+6+(-5)=4

третий контур 4+(-3)+6+(-8)= -1

четвертый контур 9+(-6)+5+(-1)=7

пятый контур 3+(-1)+5+(-8)= -1

шестой контур6+(-1)+5+(-6)+3+(-2)=5

Т.к. нужно минимизировать стоимость перевозок, то все 6 сумм должны быть положительными. 3-я и 5-я суммы- отрицательные, нужно сделать перераспределение ресурсов. Отрицательные суммы принадлежат 3-му и 5-му контурам и одинаковы по модулю, можно выбрать любой из этих контуров, например 3-ий. В этом контуре минимальное по модулю отрицательное значение размещено во 2-ой вершине и равно -6. В опорном плане назначенные перевозки по 3—му контуру таковы. Объемы указаны с сохранением знаков при определении алгебраической суммы. Перераспределим объемы перевозок между вершинами последующему правилу: самый маленький по модулю объем отрицательных перевозок (-6) алгебраически вычтем из всех вершин. Получим (без учета знака)

		-6
-8

Выполним проверку правильности сделанной операции. До перераспределения ресурсов сумма по каждому столбцу третьего контура =10 и 6 , сумма по каждой из строк этого контура =14 и 12. После выполнения преобразования соответствующие сумму получились такими же, преобразование выполнено верно. Полученный план примем за опорный без учета знака « -». Заново для свободных клеток составим кратчайшие прямоугольные контуры и подсчитаем алгебраические суммы по матрице стоимостей. Для элемента 1,3 построим контур 1,3;2,3;2,1;1,1

С1=8+(-4)+3+(-6)=1

Для элемента 1,4 построим контур 1,4;2,4;2,1;1,1

С2=7+(-2)+3+(-6)=2

Для элемента 2,2 построим контур 2,2;2,1;1,1;1,2

С3=6+(-3)+6+(-5)=4

Для элемента 3,1 построим контур 3,1;1,1;1,2;3,2

С4=9+(-6)+5+(-1)=7

Для элемента 3,3 построим контур 3,3;3,2;1,2;1,1;2,1;2,3

С5=9+(-1)+5+(-6)+3+(-4)=0

Для элемента 3,4 построим контур 3,4;2,4;2,1;1,1;1,2;3,2

С6=6+(-2)+3+(-6)+5+(-1)=5

Полученный опорный план оптимален, т.к. все алгебраические суммы не отрицательны. Вычислим стоимость всех перевозок по оптимальному плану С= 8*6+6*5+2*3+6*4+4*2+8*1=124

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

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

Стоимость перевозки	производство




потребление

Суммарная стоимость перевозок опорного плана = 184.

Базисные клетки опорного плана – а11 а12, а22, а23, а33, а34; свободные- а13,а14,а21,а24,а31,а32. Для каждой свободной клетки можно построить замкнутый контур и перераспределить ресурсы между поставщиками и потребителями. Отличие этого метода состоит в том, что определяется потенциал каждой клетки и в зависимости от значения этого потенциала, выполняется перемещение только по одному контуру.

	Потенциалы vj	производство
Потенциалы ui



	потребление

Для вычисления потенциалов в матрицу плана перевозок добавляют строку сверху и столбец слева.

Для определения потенциалов строк и столбцов используют формулу cij=ui+vj, подставляя в нее значения из базисных клеток. Для начала выполнения расчетов надо потенциал одной строки = 0. Затем, используя указанную формулу, выполнить остальные вычисления. Примем за 0 потенциал первой строки. U1=0 Тогда v1=c11-u1=6-0=6. Далее выбираем те базисные клетки, для которых уже имеется один потенциал и определяем следующий потенциал. Можно определить потенциал второго столбца v2=c12-u1=5-0=5


	-5	-1

-3

Матрица стоимостей опорный план оценки свободных клеток



			2

			-2

Для свободных клеток оценки вычисляются по формуле ui+vj-cij<=0. Если оценки всех свободных клеток отрицательны или =0 , то опорный план оптимальный. Если хотя бы одна оценка >0, то относительно этой свободной клетки строят замкнутый контур и выполняют перераспределение ресурсов. Если несколько свободных клеток имеют оценки >0, то замкнутый контур строят для свободной клетки с наибольшим значением оценки. Для нашего примера наибольшая положительная оценка принадлежит а24. Составим для нее замкнутый контур а24 а34 а33 а23 и переместим ресурсы. Заново определим потенциалы и оценки

Опорный план перераспределение ресурсов оценки свободных клеток

			-2
			-10	-6
			-5



		10




-4


		-1	-6

-4	-7		-9

Наибольшая положительная оценка принадлежит а32, поэтому строим замкнутый контур а32 а22 а24 а34 и переместим ресурсы. Заново определим потенциалы и оценки

Опорный план перерасределение ресурсов оценки свободных клеток