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

Общая экономическая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления в A ₁, A ₂,…, A_m в n пунктов назначения B₁, B₂, …, B_n.

Груз хранится в пунктах отправления в количествах a₁, a₂,…, a_m.

Пункты назначения подали заявки на груз в количествах b₁, b₂,…b_n.

Кроме того, задается матрица тарифов перевозок C

C=

Или в общем, виде эту матрицу можно записать C=(Cij) (i=1..m, j=1..n).

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

Математическое построение модели.

Обозначим матрицу решений транспортной задачи X=(x_ij) i=1..m, j=1..n, где x_ij – количество груза перевозимого из i–пункта отправления A_i в j – пункт назначения B_j.

Матрица X - матрица поставок (перевозок груза) или план поставок (перевозок).

Аналогично матрица C называется матрицей тарифов перевозок или просто матрицей тарифов.

Система линейных ограничений (СЛО) составляется из выполнения следующих условий:

1. Запасы грузов в каждом пункте отправления ограничены.

i=1..m

2. Заявки всех пунктов назначения должны быть выполнены.

j=1..n

3. Целевая функция по критерию минимальной стоимости общей стоимости перевозок имеет вид:

(min)

4. i=1..m, j=1..n – по экономическому смыслу задачи количество груза не может быть отрицательным.

Пункты 1-4 составляют модель линейного программирования, т.к. СЛО (1),(2)-линейная и целевая функция Z (п.3) тоже линейная функция.

Модель читается:

Среди не отрицательных решений (4) найти такие, которые удовлетворяли бы СЛО (1),(2) и обращали целевую функцию (3) в минимум.

Всякое не отрицательное решение СЛО (1),(2) определяется матрицей значений X=(x_ij) i=1..m j=1..n и называется допустимым решением (опорным) транспортной задачи или допустимым (опорным) планом.

Оптимальный план X^*=(x^*_ij) i=1..m, j=1..n – это тот из опорных планов, при котором целевая функция (3) принимает минимальное значение.

Решить транспортную задачу – значит найти ее оптимальный план (или оптимальное решение).