Пример. С четырех складов (СК1, СК2, СК3, СК4) доставляется товар в три магазина (МГ1, МГ2, МГ3)

С четырех складов (СК1, СК2, СК3, СК4) доставляется товар в три магазина (МГ1, МГ2, МГ3). На складе СК1 имеется 40 тонн товара, на складе СК2 – 50 тонн, на складе СК3 – 60 тонн, на складе СК4 – 30 тонн. Магазину МГ1 требуется 60 тонн товара, магазину МГ2 – 80 тонн, магазину МГ3 – 40 тонн. Затраты (в ден. ед.), связанные с перевозкой одной тонны товара с каждого склада в каждый магазин, приведены в табл. 1.

Таблица 1 – Данные по затратам на перевозку, ден. ед.

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

Решение:

Данную задачу можно представить как задачу линейного программирования. Для построения математической модели этой задачи введем переменные Xij, i = 1,..., 4, j = 1,..., 3, обозначающие количество товара, перевозимого с i -го склада в j -й магазин.

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

X 11 + X 12 + X 13 = 40

X 21 + X 22 + X 23 = 50

X 31 + X 32 + X 33 = 60

X 41 + X 42 + X 43 = 30.

Каждый магазин должен получить ровно столько товара, сколько ему

требуется. Ограничения, выражающие это условие, следующие:

X 11 + X 21 + X 31 + X 41 = 60

X 12 + X 22 + X 32 + X 42 = 80

X 13 + X 23 + X 33 + X 43 = 40.

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

Xij ≥ 0, i = 1,..., 4, j = 1,..., 3.

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

E = 4 X 11 + 3 X 12 + 5 X 13 + 6 X 21 + 2 X 22 + 1 X 23 + 10 X 31 +4 X 32 +7 X 33 + 8 X 41 + 6 X 42 + 3 X 43 → min.

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

величины перевозок (значения переменных Xij), а также вспомогательные величины, используемые для решения задачи. Расчетная таблица для данного примера показана в табл. 2.

Таблица 2 – Расчетная таблица для решения транспортной задачи

Решение транспортной задачи включает два этапа:

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

• поиск оптимального решения, т.е. плана перевозок с минимальными

затратами.