Математическая постановка транспортной задачи

Транспортная задача является задачей линейного программирования; для её решения применяется не симплекс-метод, а более простые методы.

Транспортная задача формулируется следующим образом. Имеется m пунктов производства (отправления) A_i некоторого однородного продукта в количестве a_i (i = 1,2, …, m) единиц соответственно. Груз необходимо доставить n потребителям B_j в количестве b_j (j= 1,2, …, n) единиц. Известны транспортные издержки c_ij на перевозку единицы груза от i -го поставщика к j -му потребителю. В различных задачах в роли транспортных издержек могут выступать расстояние, время и т.д.

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

Исходные данные транспортной задачи удобно представлять в виде таблицы:

Таблица 4.1 – Структура транспортной таблицы

B A	B1 b1	B2 b2	…	Bn bn
A1 a1	c11 x11	c12 x12	…	c1n x1n
A2 a2	c21 x21	c22 x22	…	c2n x2n
…	…	…	…	…
Am am	cm1 xm1	cm2 xm2	…	cmn xmn

Здесь – количество единиц груза, запланированных к перевозке от

i -го поставщика к j -му потребителю.

Целевая функция имеет смысл суммарных транспортных издержек

(4.1)

Ограничения получаем из требований, чтобы все грузы были вывезены и спрос каждого потребителя удовлетворен.

1. Весь продукт из каждого пункта производства должен быть полностью вывезен:

. (4.2)

2. Спрос каждого потребителя должен быть удовлетворен

. (4.3)

3. Объемы перевозок должны быть неотрицательными

. (4.4)

Уравнения (4.2), (4.3) получаются соответственно из строк и столбцов транспортной таблицы 4.1.

Математическая модель (4.1)-(4.4) построена в предположении, что суммарный объем производства продукта равен суммарной потребности в нем:

. (4.5)

Такая модель называется замкнутой.

Транспортная задача содержит m·n неизвестных . Клетки таблицы 4.1, в которых находятся отличные от нуля перевозки , называют занятыми, остальные – незанятыми.

Дата добавления: 2014-11-18