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

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

B1

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

c2n

c32

c31

Bn

A3

c3n

cmn

Am

cm2

cm1

B2

c22

c21

A1

c1n

c12

c11

A2

Рис. 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) является условие баланса:

(6.4)

a_i = b_j.

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

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

(6.5)

V _j = U _i + C _ij,

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

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

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

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

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

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

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

Таблица 6.1