Решение транспортной задачи различными методами

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Решение транспортной задачи различными методами

Задание

перевозка транспортный тариф

Пусть имеется m поставщиков А₁, А₂, …, А_m однородного груза в количествах соответственно a₁, а₂, …, а_m единиц и n потребителей В₁, В₂, …, В_n этого груза, потребность которых составляет соответственно b₁, b₂,…, b_n единиц.

Известны стоимости перевозок груза от i-того поставщика к j-ому потребителю - с_ij (j=, i=).

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

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

Чтобы лучше представить условия задачи, сведем исходные данные в таблицу.

Строка таблицы соответствует поставщику, а столбец - потребителю. Модель транспортной задачи:

f=

 (*)

i=, j=

(*)-модель, в которой спрос и производство равны, называется закрытой (сбалансированной).

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

Методы построения исходного плана

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

Определение значений х_ij начинается с левой верхней клетки таблицы (это соответствует северо-западному углу на географической карте). Находим значение х₁₁ из соотношения.

х₁₁₌ min{а₁, b₁}

Возможны 3 варианта:

1. Если а₁<b₁, то х₁₁=а₁ следовательно первая строка исключается из дальнейшего рассмотрения, а потребность первого потребителя b₁ уменьшается на величину а₁.

2. Если а₁>b₁, то х₁₁= а₁ = b₁, следовательно первый столбец исключается из дальнейшего рассмотрения, а наличие груза у первого поставщика а₁ уменьшается на величину b₁.

3. Если а₁=b₁, х₁₁= а₁ = b₁, следовательно первая строка и первые столбец исключается из дальнейшего рассмотрения.

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

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

Метод минимального элемента

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

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

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

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

Рассмотрим метод потенциалов для решения транспортной задачи.

Шаг 1 Каждому поставщику А_i (то есть каждой строке) поставим в соответствие некоторое число u_i (i=), называемое потенциалом А_i, а каждому потребителю В_j (то есть каждому столбцу) поставим в соответствие некоторое число v_j (j=), называемое потенциалом В_j.

Для каждой заполненной клетки, то есть для каждой базисной переменной, строится соотношение u_i+ v_j=с_ij.

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

Шаг 2 Для каждой незаполненной клетки, то есть для каждой небазисной переменной, рассчитываются так называемые косвенные тарифы (с_ij) по формуле с_ij =u_i+ v_j

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

Шаг 3 Проверяем полученный план на оптимальность по критерию оптимальности плана транспортной задачи. Если для каждой незаполненной клетки выполняется условие с¹_ij - с_ij?0, то план является оптимальным. В противном случае полученный план не оптимальный, и необходимо переходить к новому базисному плану путем перемещения перевозки в клетку, отвечающий условию max[с¹_ij - с_ij<0]. Если таких клеток более одной, то договоримся перемещать перевозку в первую по порядку. Выбранная клетка помещается в таблице. Перемещенная, стоящая в этой клетке, вводимая в базис.

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

Шаг 5 В каждой клетке цикла, начиная с незаполненной, проставляются поочередно знаки «+» и «-» (обычно они ставятся в правом нижнем углу клетки). В клетках со знаком «-» выбирается минимальная величина. Новый базисный план получается путем сложения выбранной величины с величинами, стоящими в клетках цикла со знаком «+», и вычитания этой величины из величин, стоящих в клетках со знаком «-».

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

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

Осуществляется переход к шагу 1.

Замечание 1

Метод потенциалов обеспечивают монотонное убывание значения целевой функции, и позволяет за конечное число шагов найти её минимум.

Замечание 2

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

Задача. Имеются 2 пункта поставки однородного груза А₁, А₂ и 3 пункта В₁, В₂, В₃ потребления этого груза. На пунктах А₁, А₂ находится груз соответственно в количестве а₁, а₂ т. В пункты В₁, В₂, В₃ требуется доставить соответственно b₁, b₂, b₃ т груза. Расстояние между пунктами поставки и пунктами потребления приведено в таблице. Найти такой план закрепления потребителей за поставщиками однородного груза, чтобы затраты были минимальными.

А, В(10, 8, 7), Д

Пункты поставки	Пункты потребления	Итого груза
	В1	В2	В3
А1	8	6	5	11
А2	4	5	7	14
Итого	10	8	7	25

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

n+m-1=4 - план невырожденный

Модель задачи закрытая

f=8·10+6·1+5·7+7·7=86+35+49=170

II. Метод минимального элемента

f=6·4+5·7+4·10+5·4=24+35+60=11

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

Шаг 1

u₁=0

u₂=-1

v₁=8

v₂=6

v₃=8

f=810+61+57+77=170

Шаг 2

Для каждой незаполненной клетки рассчитаем косвенные тарифы.

с^/₁₃=u₁+v₃=0+8=8

c^/₂₁=u₂+v₁=-1+8=7

Шаг 3

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

с^/₁₃- с₁₃=8-5=3>0

c^/₂₁-с₂₁=7-4=3>0

Критерий целостности нарушен

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

Шаг 4.

Строим цикл. В каждой клетке, начиная с той, в которую начинаем перевозку, ставим знаки «+» и «-».

Шаг 5.

В клетках со знаком «-» выберем наименьшую величину min=1.

Шаг 1. Для заполненных клеток

u₁=0

u₂=2

v₁=8

v₂=5

v₃=3

f=10·8+5·1+8·5+6·7=167

Шаг 2.

Для незаполненных клеток

с^/₁₂=u₁+v₂=0+3=3

c^/₂₁=u₂+v₁=2+8=10

критерий оптимальности нарушен. Заносим эти значения в левый нижний угол незаполненной клетки.

Шаг 3

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

с^/₁₂- с₁₂=3-6=-3<0

c^/₂₁-с₂₁=10-4=6>0

Критерий целостности нарушен. Перемещаемся в клетку 2.1

Шаг 4.

Вводим знаки

Шаг 5

В клетках со знаком «-» выбираем наименьшую величину min=6. Прибавляем число 6 к числам в клетках, где стоит «+», вычитаем из чисел, стоящих в клетках со знаком «-». Получаем новую таблицу.

Шаг 1.

Для каждой заполненной

u₁=0

u₂=-4

v₁=8

v₂=5

v₃=9

f=4*8+7*5+6*4+5*8=131

Шаг 2.

Для незаполненных клеток

с^/₁₂=u₁+v₂=0+9=9

c^/₂₁=u₂+v₃=-4+5=1

критерий оптимальности нарушен. Заносим эти значения в левый нижний угол незаполненной клетки.

Шаг 3

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

с^/₁₂- с₁₂=9-6=3>0

c^/₂₃-с₂₃=1-7=-6<0

Критерий оптимальности нарушен. Перемещаемся в клетку 1.2

Шаг 4.

Строим цикл, вводим знаки

Шаг 5

В клетках со знаком «-» выбираем наименьшую величину min=4. Прибавляем число 6 к числам в клетках, где стоит «+», вычитаем из чисел, стоящих в клетках со знаком «-». Получаем новую таблицу

Шаг 1.

Для каждой заполненной



u₁=0

u₂=-1

v₁=6

v₂=5

v₃=5

f=4·6+7·5+4·10+4·5=119

Шаг 2.

Для незаполненных клеток

с^/₁₁=u₁+v₁=0+5=5

c^/₂₃=u₂+v₃=-1+5=4

Шаг 3

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

с^/₁₁- с₁₁=5-8<0

c^/₂₃-с₂₃=4-7=-3<0

Критерий оптимальности не нарушен. План оптимальный.

Размещено на Allbest.ru

...