6. Транспортные задачи

Одной из разновидностей ЗЛП являются так называемые транспортные задачи, которые подразделяются на транспортные задачи по критерию стоимости (стоимость перевозок min) и по критерию времени (время перевозок min). Но в целом в зависимости от конкретной задачи по этой схеме могут оптимизироваться закрепление за станками операций по обработке деталей; назначения или выбор; размещение с учетом транспортных и производственных затрат и т.д.

Пусть в m пунктах отправления (склады, поставщики) А_1, A₂, ...,A_m сосредоточено определенное количество единиц некоторого однородного продукта a_i (i = ), который должен быть доставлен в n пунктов B₁, B₂, ..., B_n потребителям. Расходы на перевозку единицы продукта из пункта А_i в пункт B_j равны с_ij и приведены в матрице транспортных расходов С = [с_ij]. Требуется составить такой план перевозок, чтобы общая величина транспортных издержек была минимальной.

B₁

A₁

c₁₁

c₁₂

c_1n

c₂₁

c₂₂

c_2n

A₂

c₃₁

c₃₂

c_3n

c_mn

c_m1

c_m2

A₃

A_m

B_n

B₂

Рис. 6.1. Геометрическое представление транспортной задачи

Если обозначить количество продукта, перевозимого из пункта А_i в пункт B_j через x_ij, то задача может быть записана в общем виде как:

(6.1)

(6.2)

(6.3)

где x_ji – количество единиц продукта, отправленного от i-го поставщика к j-му потребителю;

с_ij – стоимость перевозки единицы продукта i-го поставщика до j-го потребителя;

A_i – запасы продукта i-го поставщика;

В_j – запрос продукта j-го потребителя.

Условии (6.3) означают полное удовлетворение спроса во всех пунктах потребления, а (6.2) – полный вывоз продукции от всех поставщиков.

Необходимым и достаточным условием разрешимости задачи (6.1)-(6.3) является условие баланса:

a_i =b_j.

(6.4)

Транспортная задача, в которой выполняется условие (6.4), называется закрытой и может быть решена не только симплекс-методом, но и более простым – методом потенциалов.

В соответствии с этим методом каждой i-й строке (i-му поставщику) устанавливается потенциал U_i (цена продукта в пункте поставщика), а каждому j-му столбцу (j-му потребителю) – потенциал V_j (цена продукта в пункте потребителя). В простейшем случае должно выполняться:

V_j = U_i + C_ij,

(6.5)

т.е. цена продукта в j-м пункте потребителя должна равняться цене продукта в пункте поставщика плюс транспортные доходы на его доставку.

Алгоритм метода потенциалов для закрытой транспортной задачи состоит из 3-ех этапов.

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

2. Строится система потенциалов на основе равенств (6.5) и начальный план проверяется на оптимальность. В случае его неоптимальности переходят к 3-ему этапу.

3. Реализуются циклы перераспределения (корректировка плана прикрепления потребителей к поставщикам) и переходят опять ко 2-му этапу. И так повторяется до тех пор, пока план перевозок не окажется оптимальным в соответствии с (6.1).

Если равенства (6.4) не выполняется, то транспортная задача называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче путем ввода фиктивного потребителя, если (6.2) – неравенства, или фиктивного поставщика, если (6.3) представляют собой неравенства.

В соответствии с условиями задачи составляется таблица поставок (матрица перевозок)

Таблица 6.1

Схема матрицы перевозок

Мощности поставщиков	Мощности потребителей
	b1		b2		…	bn
a1	c11	x11	c12	x12	…	c1n	x1n
a2	c21	x21	c22	x22	…	c2n	x2n
…	…		…		…	…
am	cm1	xm1	cm2	xm2	…	cmn	xmn

Общее число неизвестных в системе уравнений (6.2), (6.3) будет определяться как mn , из которых (m + n – 1) – базисные неизвестные (занятые клетки таблицы – отмечаются диагональной чертой).

Рассмотрим применение метода потенциалов на примере.

Пример 6.1. В трех пунктах отправления A_i (i = 1, 2, 3) находятся соответственно а₁ = 60, а₂ = 100 и а₃ = 120 тонн горючего. Необходимо доставить это горючее в четыре пункта потребления В_j (j = 1, 2, 3, 4), требующих b₁ = 30, b₂ =100, b₃=40, b₄ = 110 тонн горючего соответственно. Стоимость x_ij перевозки тонны горючего из пункта i в пункт j указаны в таблице (таблица 6.2). Составить оптимальный план перевозок горючего так, чтобы общая сумма транспортных расходов была наименьшей.

Таблица 6.2