Изменения

[[файл:ТЗППэ.JPG|thumb|300|Математическая модель эквивалентной ТЗПП]]

[[файл:ТЗПП1.JPG|thumb|300|Математическая модель классической ТЗПП]]

== Постановка задачи ТЗПП ==

Пусть имеется '''m''' поставщиков '''(A1,A2,…,Am)''', '''n''' потребителей '''(B1,B2,…,Bn)''' и '''k''' промежуточных пунктов '''(C1,C2,…,Ck)''', однородного продукта. Пусть заданы объёмы поставок '''a_i''' продукта поставщиком '''Ai''', объёмы потребностей '''b_j''' в продукте у потребителя '''Bj''', объёмы дополнительных потребностей '''c_t''' в продукте в промежуточном пункте (на складе) '''Ct''', причём если '''c_t<0''', то дополнительные потребности являются избытком. Пусть известны транспортные расходы '''d_ti''' на перевозку единицы продукта от поставщика '''Ai''' на склад '''Ct''', и транспортные расходы '''q_tj''' на перевозку единицы продукта со склада '''Ct''' к потребителю '''Bj''' и необходимо определить план перевозок с минимальной суммой транспортных расходов, тогда [[Трёхиндексная транспортная задача|транспортная задача]] с промежуточными пунктами формулируется следующим образом:

'''y_tj''' — объём перевозок продукта со склада '''Ct''' к потребителю '''Bj'''.

== Условия разрешимости ==

Для разрешимости задачи необходимо выполнение условий баланса:

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

== Постановка эквивалентной задачи ==

Введём новые обозначения:

[[файл:ТЗППэ.JPG]].

== Условия разрешимости эквивалентной задачи ==

Для разрешимости эквивалентной задачи необходимо выполнение условий баланса:

то есть необходимо, чтобы объём поставок продукта на склады и объём отрицательных поставок со складов (потребностей в продукте) равнялся объёму дополнительных потребностей в продукте на складах. В этом случае транспортная задача с промежуточными пунктами называется закрытой.

== Постановка классической задачи ==

В экономической транспортной системе имеются '''n''' конечных пунктов ('''np''' поставщиков продукции и '''n-np''' потребителей продукции) и '''m''' промежуточных пунктов (складов). Продукция перевозится от поставщиков на склады, будем обозначать эти перевозки положительными переменными '''x_ij≥0, (i=1,m,j=1,np)'''. А со складов часть продукции перевозится потребителям - их обозначим отрицательными переменными '''x_ij≤0, (i=1,m,j=np+1,n)'''. Объёмы поставок поставщиков обозначим положительными числами '''b_j>0, (j=1,np),''' объёмы потребностей потребителей обозначим отрицательными числами '''b_j<0, (j=np+1,n)'''. Если склад имеет дополнительные (внутренние) потребности продукции, то обозначим их положительными числами '''a_i>0, (i=1,mp)'''. Если склад имеет излишки продукции или нулевые остатки, то обозначим их числами '''a_i≤0, (i=mp+1,m)'''. Транспортные тарифы на перевозку единицы продукции от поставщика на склад выразим положительными числами '''c_ij>0, (i=1,m,j=1,np),''' транспортные тарифы на перевозку со склада к потребителю выразим отрицательными числами '''c_ij<0, (i=1,m,j=np+1,n)'''.

[[файл:ТЗПП1.JPG]].

[[файл:ТТ.JPG]].

== Условия разрешимости классической задачи ==

Для разрешимости классической задачи необходимо выполнение условий баланса:

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

== Метод решения ТЗПП ==

Необходимо найти начальное опорное решение, например, методом северо-западного угла.

Затем транспортная задача с промежуточными пунктами решается обобщённым методом потенциалов для решения транспортной задачи модифицированным с учётом отрицательных перевозок.

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

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

'''3.'''Наконец, удовлетворяем потребности потребителей '''(b_j<0)''', т.е. назначаем соответствующие отрицательные перевозки по формулам: '''x_ij=max(a_i,b_j), a_ij=a_i-x_ij, b_j=b_j-x_ij'''.

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

'''2.'''Определяем значение целевой функции '''L=ΣΣc_ijx_ij''' и базис опорного решения '''Bo={(i,j)|z_ij=1}'''.

'''4.'''Проверяем решение на оптимальность. Если '''Δo=0''', то решение '''Xmxn''' - оптимальное и конец работы.

'''6.'''Определяем новое значение целевой функции '''L=L-ΔoΔx''' и новый базис '''Bo=Bo\(i_x,j_x)U(i_o,j_o)'''.

Переходим к пункту 3.

== Пример ТЗПП ==

[[файл:СЗУ10.JPG]]

=== Нахождение допустимого решения ===

[[файл:СЗУ11.JPG]]

[[файл:СЗУ13.JPG]]

[[файл:СЗУ04.JPG]]

=== Решение методом потенциалов ===

[[файл:МП01.JPG]]

[[файл:МП03.JPG]]

[[файл:МП04.JPG]]

== Другие задачи: ==

== Ссылки ==

* Кривопалов В. Ю., Метод северо-западного угла для нахождения допустимого решения транспортной задачи с промежуточными пунктами. Сборник конференции ПИТ-2014, СГАУ, стр.369-372. http://www.ssau.ru/files/events/2014/pit_14_1_6.pdf

* Кривопалов В. Ю., Обобщённый метод потенциалов для решения транспортной задачи с промежуточными пунктами. Сборник Х конференции «Наука. Творчество» 2014, Самара-Москва, Т.1,стр.23-29.

* [[Участник:Logic-samara]]

[[Категория:Линейное программирование]][[Категория:Транспортная задача]][[Категория:Логистика]]