ТРАНСПОРТНАЯ ЗАДАЧА

Как организовать перевозку грузов из одних пунктов в другие, чтобы общая стоимость перевозок была минимальной?

ЭКОНОМИЧЕСКАЯ ПОСТАНОВКА И МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ

Пусть имеем m пунктов производства, пронумерованных по i, т.е. . В каждом пункте производства (A_i) сосредоточен однородный товар (a_i). Пусть этот товар необходимо перевезти в n пунктов потребления, которые пронумерованы по j, т.е. . Потребность каждого пункта в потреблении (B_j), соответственно, будет b_j. Обозначим через x_ij – количество товара, перевезенного из пункта производства (A_i) в j -й пункт потребления (B_j); c_ij – стоимость перевозки единицы продукции из i -го пункта производства (a_ij) в j -й пункт потребления (B_j).

Допустим, что выполняется баланс: общее количество единиц товара, сосредоточенных в пунктах производства, совпадает с общим количеством единиц товара, которые требуются в пунктах потребления. Запишем задачу в виде таблицы:

 

пункты потребления	B1	B2	B3	...	Bn	запасы
пункты производства
А1	x11	x12	x13	...	x1n	a1
c11	c12	c13	...	c1n
А2	x21	x22	x23	...	x2n	a2
c21	c22	c23	...	c2n
...	...	...	...	...	...	...
...	...	...	...	...
Аm	xm1	xm2	xm3	...	xmn	am
cm1	cm2	cm3	...	cmn
потребность	b1	b2	b3	...	bn

 

Сформулируем задачу таким образом, чтобы:

1. Весь товар из пунктов производства был вывезен.
2. Потребности каждого пункта потребления были удовлетворены.
3. Общая стоимость всех перевозок из пунктов производства в пункты потребления была бы минимальной.

Из таблицы видно, что количество товара, перевезенного из первого, второго,... m -го пунктов производства, соответственно, удовлетворяют условиям:

Количество товара, который ввозится в первый, второй, третий,... n -й пункт потребления удовлетворяет, соответственно, условиям:

Общая стоимость всех перевозок выражается формулой:

Таким образом, математическая модель этой задачи имеет вид:

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

при условиях

 

Пример 4. Для удовлетворения потребностей трех районов города хлебом работает два хлебозавода. Первый район ежедневно потребляет 26 тонн хлеба, второй 14 тонн, а третий – 10 тонн хлеба. Хлебозавод № 1 ежедневно выпекает 30 тонн хлеба, а хлебозавод № 2 – 20 тонн. Стоимость доставки каждому району одной тонны хлеба из каждого хлебозавода приведено в таблице:

Таблица 4.1

хлебозавод	районы	запасы
I	3	4	6	30
II	3	5	2	20
потребность	26	14	10

Необходимо составить наиэкономнейший план перевозки хлеба.

Решение. Обозначим через x – количество тонн хлеба, перевезенного из хлебозавода № 1 в первый район, y – количество тонн хлеба, перевезенного из этого же завода в другой район. Тогда в третий район из хлебозавода № 1 будет перевезено 30-x-y тонн. Поскольку первый район ежедневно потребляет 26 тонн хлеба, то со второго хлебозавода необходимо доставить 26-x тонн. Аналогично из хлебозавода № 2 необходимо доставить в другой район 14-y тонн, а в третий район x+y-20 тонн хлеба. Таким образом, ежедневный план перевозки хлеба можно представить в виде таблицы:

Таблица 4.2

хлебозавод	районы
I	x	y	30-x-y
II	26-x	14-y	x+y-20

 

Стоимость всех перевозок z равняется сумме попарных произведений чисел из таблице 4.1 на соответствующие числа таблицы 4.2: z=3x+4y+6(30-x-y)+3(26-x)+5(14-y)+2(x+y-20) или

z=288-4x-5y.

Поскольку количество хлеба, который перевозят в данный район города, не может быть отрицательным, то все числа второй таблицы должны быть положительными:

Стоимость z можно рассматривать как функцию точки М, координаты которой удовлетворяют системе неравенств. Построим в системе координат систему этих неравенств. Множество всех этих точек есть замкнутый многоугольник ABCDE. Функцию z называют целевой функцией.

Изобразим на плоскости Oxy множество (x, y), координаты которых удовлетворяют системе неравенств:

1) неравенству удовлетворяют координаты точек, которые расположены справа от прямой x=0.

2) неравенству удовлетворяют координаты точек, которые расположены выше прямой y=0.

3) неравенству удовлетворяют координаты точек, которые расположены ниже прямой 30-x-y=0.

4) неравенству удовлетворяют координаты точек, которые расположены слева от прямой x=26.

5) неравенству удовлетворяют координаты точек, которые расположены ниже прямой y=14.

6) неравенству удовлетворяют координаты точек, которые расположены выше прямой x+y-20=0.

Таким образом, всем неравенствам удовлетворяют точки, которые расположены в замкнутом многоугольнике ABCDE. Целевая функция достигает максимального и минимального значений в вершинах многоугольника ABCDE, потому что в середине его частные производные не равны нулю, а на сторонах его она монотонна. Находим координаты вершин из системы уравнений:

 

 

 

Из рисунка видно, что D(26; 0), E(20; 0). Определим значение z в каждой вершине:

Из полученных значений видно, что наименьшее значение z равно 154 и достигается в вершине В, т.е. при x=16, y=14. Следовательно, наиболее экономным планом перевозок хлеба является план, который задан следующей таблицей:

 

хлебозавод	районы
I
II

Следует обратить внимание, что наибольшее значение z равно 208 и отвечает точке E(20; 0). Соответствующий план перевозок является самым дорогим. По сравнению с ним наиболее экономный план дает экономию 54 грн. ежедневно. Это пример наиболее простой транспортной задачи.