Транспортная задача.

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

Сформулируем транспортную задачу в общем виде.

У m поставщиков A₁, A₂, …, A_m сосредоточено соответственно a₁, a₂, …, a_m единиц некоторого одного груза, который необходимо доставить n потребителями B₁, B₂, …, B_n в количестве b₁, b₂, …, b_n единиц соответственно. Известна стоимость c_ij перевозки груза от i-того поставщика к j-тому потребителю. Необходимо составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить потребителей и имеющий минимальную стоимость.

Обозначим через x_ij количество единиц груза, запланированного к перевозке от i-того поставщика к j-тому потребителю. Тогда математическая модель транспортной задачи имеет следующий вид.

Найти минимальное значение линейной функции:

{общая сумма затрат должна быть минимальной}

{Объём поставки i-того поставщика должен равняться количеству имеющегося у него груза.}

при ограничениях:

{Размер поставок должен выражаться неотрицательным числом.}

{Объём поставок j-тому потребителю должен быть равен его спросу.}

x_ij≥0

 

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

Рассмотрим как открытую задачу формально преобразовать в закрытую.

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

то в рассмотрение вводится фиктивный (n+1)-й пункт потребления B_n+1 со спросом, равным небалансу, т.е.

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

Если же общий спрос потребителей больше суммарного запаса продукта, то вводится фиктивный (m+1)-й пункт отправления A_m+1 с запасом продукта

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

При решении транспортной задачи все данные помещаются в таблицу.

	B1(b1)	B2(b2)	…	Bn(bn)
A1(a1)			…
A2(a2)			…
…	…	…	...	…
Am(am)			…

Центр клетки небазисных переменных пуст.

Значения базисных переменных

dij

cij

 

Построение начального опорного плана (метод северо – западного угла)

1. min{a₁, b₁}=a₁ (a₁<b₁)

вычёркиваем всю 1-ую строку, кроме 1-ой клетки;

вместо b₁ пишем (b₁-a₁)

 

2. min{a₁, b₁}=b₁ (a₁>b₁)

вычёркиваем весь 1-ый столбец, кроме 1-ой клетки,

вместо a₁ – (a₁-b₁)

 

3. min{a₁, b₁}=a₁=b₁

вычёркиваем либо строку, либо столбец. Если вычёркиваем строку, то во 2-ой строке под 1-ой клеткой пишут 0, а остальной столбец вычёркивают.

Т.о., окажутся заполненными (m+n-1) клетка {расположены произвольно}. Они являются базисными. Для всех остальных клеток соответствующие x_ij=0 (их не пишем в клетках).