Транспортная задача. Транспортная задача является частным случаем ЗЛП или частным случаем задачи оптимизации сетей, применяется при решении плановых задач выбора маршрутов

Транспортная задача является частным случаем ЗЛП или частным случаем задачи оптимизации сетей, применяется при решении плановых задач выбора маршрутов перевозок. В общем виде формулируется следующим образом. Пусть рассмотрено m различных поставщиков (пунктов отправления) P_i_,располагающих некоторой однородной продукций соответственно в количествах a_i , и рассматривается отправление этой продукции в n пунктов потребления Q_j, j= , потребности которых равны b_j cоответственно. Известны тарифы перевозок этой продукции из пункта P_i в пункт Q_j (затраты на перевозку единицы груза) C_ij. Требуется составить такой план перевозок, чтобы общая стоимость затрат была минимальной.

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

X_ij – количество едениц груза из i в j пункт.

ƒ= →min

x_ij≥0.

Учитывая, что эта задача является частным случаем ЗЛП, рассматриваются специальные способы решения этих задач.

Транспортная таблица задачи имеет вид:

Q_j P_i	Q₁	Q₂	…	Q_n	Запасы
P₁	X₁₁c₁₁	X₁₂c₁₂	…	X_1nc_1n	a₁
P₂	X₂₁c₂₁	X₂₂c₂₂	…	X_2nc_2n	a₂
…	…	…	…	…	…
P_m	X_m₁ c_m₁	X_m2 c_m2	…	X_mnc_mn	a_m
Потребность	b₁	b₂	…	b_n

Транспортная задача имеет решение, если ∑a_i=∑b_j (закрытая модель).

Если ∑a_i < ∑b_j, то вводят фиктивный пункт производства, и не все пункты в оптимальном решении будут удовлетворены в потребности.

Если ∑a_i>∑b_j_,то не все запасы будут вывезены из пунктов производства, в решении вводят фиктивный пункт потребления. Заметим, что объем продукции в фиктивном пункте равен разности │∑a_i -∑b_j│.

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

1. Все вершины ломаной находятся в клетках транспортной таблицы.

2. Ребра расположены по строкам или столбцам, но не диагоналям.

3. К каждой вершине подходят 2 ребра: одно - по строке, другое - по столбцу транспортной таблицы.

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

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

Определение. Потенциалом опорного решения α транспортной задачи называют числа U_i , V_j j= , такие что U_i+V_j=C_ij – тариф заполненной клетки.

Теорема ( Достаточное условие оптимальности опорного решения). Если для всех незаполненных клеток (i,j) U_i+V_j=C_ij, где U_i и V_j - потенциалы опорного решения α, тогда это опорное решение является оптимальным.

Методы построения опорных решений:

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

2. Метод минимального элемента. Среди всех клеток выбираем клетку с наименьшим тарифом C_ks и начинаем заполнение с этой клетки либо удовлетворяя потребность, либо исчерпывая запасы (если таких клеток несколько, то заполняем все эти клетки). Затем переходим к заполнению клеток с большими по величине тарифами, пока полностью не исчерпаем запасы или не удовлетворим потребности.

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

Замечание: Если заполненных клеток оказалось меньше чем m+n-1, то к полученному набору дописывают в некоторых клетках «0», так чтобы общее количество заполненных клеток стало m+n-1.

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

1. Построить опорное решение транспортной задачи тремя описанными выше методами. Для каждого опорного решения найти значение целевой функции и остановится на том, для которого это значение минимально.

2. Найти потенциалы заполненных клеток.

3. Для незаполненных клеток проверить условие оптимальности. Если условие оптимальности выполняется, то полученное решение оптимально.

4. В противном случае выбирают клетку (k,s), для которой U_k+V_s>C_ks и строим цикл транспортной таблицы, приписывая клетке знак «+» и чередуя знаки во всех остальных клетках цикла.

5. Проводим пересчет таблицы по следующему правилу. Необходимо выбрать число r=min x_ij из клеток цикла, помеченных знаком «-». В клетках цикла, помеченных знаком «+», это число прибавляем. В клетках цикла, помеченных знаком «-», это число отнимаем. Остальные клетки цикла не изменяем, и ту клетку, в которой было найдено r, не заполняем.

6. Возвращаемся к пункту 2.

Пример. Решить транспортную задачу