Постановка транспортных задач

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

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

Постав-щики	Мощ-ность постав- щика	Потребители и их спрос
		1	2	…	j	…
		N1	N2		Nj		N
1	M1	a11 x11	a12 x12	...	a1j x1j	…	a1 x1
2	M2	a21 x21	a22 x22	…	a2j x2j	…	a2 x2
…	…	…	...	…	…	…	…
i	Mi	ai1 xi1	ai2 xi2	…	aij xij	…	ai xi
…	…	…	…	…	…	…	…
k	Mk	ak1 xk1	ak2 xk2	…	akj xkj	…	ak xk

Здесь показатели a_ij означают затраты на перевозку единицы груза i-го поставщика, где i=1,2,...,k, а j=1,2,…, . N – мощность поставщика в планируемы период, M_i – спрос j-го потребителя на этот период. x_ij – поставка (кол-во) груза, которое планируется в перевозке от i-го поставщика к j-ому потребителю. Математически задача сводится к нахождению минимума целевой функции, выражающей суммарные затраты на перевозку всего груза, т.е. функции F

F= a₁₁ x₁₁ + a₁₂ x₁₂ + … + a_1j x_1j + … + a₁ x₁ + …+ a_ij x_ij + … + a_k x_k min

При ограничениях

x₁₁ + x₁₂ + … + x₁ = M₁

x₂₁ + x₂₂ + … + x₂ = M₂

…………………………

x_i1+ x_i2 + … + x_i = M_i

………………………..

x_k1 + x_k2 + … + x_k = M_k

x₁₁ + x₁₂ + … + x_k1 = N₁

x₂₁ + x₂₂ + … + x_k2 = N₂

…………………………

x_1j + x_2j + … + x_kj = N_j

………………………..

x₁ + x₂ + … + x_k = N (1)

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

Особенности экономико-математической модели транспортной задачи

1. Система ограничений сразу имеет вид уравнений, поэтому отпадает необходимость вводить добавочные переменные.

x₁₁ + x₁₂ + … + x₁ = M₁

x₂₁ + x₂₂ + … + x₂ = M₂

…………………………

x_i1+ x_i2 + … + x_i = M_i

………………………..

x_k1 + x_k2 + … + x_k = M_k

x₁₁ + x₁₂ + … + x_k1 = N₁

x₂₁ + x₂₂ + … + x_k2 = N₂

…………………………

x_1j + x_2j + … + x_kj = N_j

………………………..

x₁ + x₂ + … + x_k = N (1)

2. Матрица коэффициентов при переменных в системе ограничений (1) состоит только из 1 и 0.

3. Система ограничений (1) включает k уравнений, связывающих поставки i-го поставщика с мощностью M_i и i=1,2,...,k, и уравнений, связывающих поставки j-ому потребителю со спросом N и j=1,2,…, этого потребителя. Заметим, что число k равно числу строк исходной таблицы, а число равно числу столбцов. Число переменных x_ij, входящих в целевую функцию и в систему ограничений (1), равно произведению k и , т.е. числу клеток таблицы.

Таким образом система ограничений (1) – есть система из k + уравнений с k* переменными. Специфичность ЭММ ТЗ привела к появлению особого метода её решения – распределительного метода, а в дальнейшем к различным модификациям этого метода. Все теоретические предпосылки, которые лежат в основе симплексного метода, сохраняются.

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

Особенности ЭММ:

1. каждая переменная входит в систему ограничений дважды, поэтому число основных (или базисных) элементов будет равно k + –1 (‘nj условие базисности решения);

2. в любой ТЗ значение z(x) min;

3. решение ТЗ оформляется на каждом шаге в виде таблиц, в которых должны быть заполнены k + –1 клеток, в ходе решения происходит переход от одной таблицы к другой, от 1-го поставщика к другому, пока не будет найдено оптимальное распределение поставок.

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

Заполнение таблицы ТЗ начинается с левого верхнего угла, состоящее из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов потребителя, заполняется только одна клетка, и соответственно исключается из рассмотрения один поставщик или потребитель. При этом нулевые перевозки принято заносить в таблицу только в том случае, когда они попадают в клетку (ij), подлежащую заполнению. Остальные клетки с нулевыми перевозками остаются пустыми. Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно k + –1 и вектора условий, соответствующие этим клеткам, линейно независимы.

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

Метод минимальной стоимости позволяет построить опорное решение, которое достаточно близко к оптимальному, т.к. исп-ют матрицу стоимости ТЗ: C = (C_ij) , где i=1,2,…,m; а j=1,2,…,n. Как и метод северо-западного угла он состоит из ряда однотипных шагов, на каждом их которых заполняется только 1 клетка таблицы, соответствующая минимальной стоимости (min(C_ij)) и исключается из рассмотрения только 1 строка (поставщик) или 1 столбец (потребитель). Очередную клетку, соответствующую (min(C_ij)), заполняют по тем же правилам, что и в методе северо-западного угла.

Поставщик исключается из рассмотрения, если его запасы закончились. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо 1 поставщик, либо 1 потребитель. При этом если поставщик еще не исключен, но его запасы равны 0, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заносится базисный 0, и лишь затем поставщик исключается из рассмотрения. Аналогично поступаем и с потребителем.

Для проверки линейной независимости векторов условий соответствующих координатов допустимого решения исп-ют циклы. Циклом наз-ся такая последовательность клеток таблицы ТЗ (i₁,j₁), (i₂,j₂), …, (i_k,j ), в которой две и только две соседние клетки расположены в одной строке или столбце, причем 1-е и последние также находятся в одной строке или одном столбце. Циклом ТЗ называется несколько клеток, соединенных замкнутой ломанной линией так, чтобы 2 соседние вершины ломанной были расположены либо в 1 строке, либо в 1 столбце. Ломанная может иметь точки самопересечения, но не в клетках цикла.

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

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

План называется ациклическим, если его базисные клетки не содержат циклов. Планы, полученные с помощью методов северо-западного угла и минимальной стоимости – ациклические. Имеет место теорема: для любой свободной клетки можно построить цикл и при этом единственный.

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

Для проверки возможности образования цикла исп-ся метод вычеркивания, который состоит в следующем: если в строке или столбце таблицы 1 занятая клетка, то она не может входить в какой-либо цикл, т.к. цикл имеет 2 клетки в каждой строке или столбце, следовательно, можно вычеркнуть все строки таблицы, содержащие по 1 занятой клетки, а затем аналогично столбцы. Далее вернуться к строкам и продолжить вычеркивание строк и столбцов.

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