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

Классическая транспортная задача формулируется следующим образом:

Имеется m пунктов отправления (производства) A₁, A₂,...,A_m, в которых расположены запасы некоторого однородного продукта (груза). Объём этого продукта в пункте A_i составляет a_i единиц. Кроме того, имеется n пунктов потребления B₁, B₂,...,B_n. Объём потребления в пункте B _j составляет b_j единиц. Предполагается, что из каждого пункта отправления возможна транспортировка продукта в любой пункт потребления. Известна также стоимость c_ij перевозки единицы продукта из пункта A_i в пункт B_j.

Требуется составить такой план перевозок, при котором все заявки пунктов потребления полностью выполнялись бы пунктами отправления, а общая стоимость перевозок была минимальной.

При такой постановке данную задачу называют транспортной задачей по критерию стоимости.

В общем виде исходные данные представлены в таблице

Таблица 2.

Транспортная задача называется закрытой, если суммарный объем отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения

Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой.

Задача ставится следующим образом. Найти объемы перевозок для каждой пары «поставщик-потребитель» так, чтобы:

1) мощности всех поставщиков были реализованы;

2) спросы всех потребителей удовлетворены;

3) суммарные затраты на перевозку были бы минимальными.

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

Построим экономико-математическую модель следующей задачи.

Пример. Для строительства 3-х участков дорожкой магистрали необходимо завозить песок. Песок может быть поставлен из 4-х карьеров. Перевозка песка из карьеров до участков осуществляется грузовиками одинаковой грузоподъемности. Расстояние в километрах от карьеров до участков, наличие песка в карьерах и потребность песка на участках дороги приведены в следующей таблице.

Таблица 3.

Требуется составить план перевозок, минимизирующий общий пробег грузовиков.

Решение. Обозначим искомый объем перевозок от i-го поставщика j-му потребителю через х_ij. Чтобы мощность каждого поставщика была реализована, необходимо составить уравнения баланса для каждой строки таблицы, т.е.

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

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует предположить, что

Суммарные затраты на перевозку груза составят