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

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

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

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

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

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

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

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

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

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

3. Производитель I имеет ресурса столько, сколько надо потребителю j. В этом случае из рассмотрения удаляются и строка и столбец матрицы стоимостей.

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

Дальше не пиши!!!! :d

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

1. выбирается свободный (незаполненный ) элемент опорного плана.

2. от выбранного свободного элемента строится кратчайший прямоугольный замкнутый контур. Остальные вершины замкнутого контура( кроме первой) проходят через заполненные элементы опорного плана перевозок. Поворот осуществляется только на 90 градусов и только в заполненных элементах.

3. Каждой вершине контура присваивается коэффициент, равный соответствующему значению элемента из матрицы стоимости.

4. Каждому коэффициенту в вершинах контура строго поочередно присваивается знак + или -, начиная с пустой клетки.

5. Выполняется алгебраическое суммирование коэффициентов по всему контуру.

6. Пункты с1 по 5 выполняются для каждого нулевого (пустого) элемента опорного плана.

7. Проверяются результаты суммирования по всем контурам на оптимальность.

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

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

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

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

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

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

• Проверяется сохранение баланса перевозок по строкам и столбцам

• Заново рассчитываются алгебраические суммы(по стоимости) для всех контуров.

• Проверяется условие оптимальности.

Пример

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

Стоимость перевозки				производство
6	5	8	7	14
3	6	4	2	12
9	1	3	6	8
10	14	6	4
потребление

Опорный план

2	6	6		14
8			4	12
	8			8
10	14	6	4

Получили исходные данные для распределительного метода. Свободные(пустые) элементы опорного плана имеют индексы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) алгебраически вычтем из всех вершин. Получим (без учета знака)

2	6	-6		14
-8			4	12
	8			8
10	14	6	4

8	6			14
2		6	4	12
	8			8
10	14	6	4

Выполним проверку правильности сделанной операции. До перераспределения ресурсов сумма по каждому столбцу третьего контура =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