18. Транспортная задача

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

Известна стоимость перевозки одной единицы груза от поставщика потребителю. Составить план перевозок, позволяющий с min затратами перевезти все грузы и полностью удовлетворить потребителей.

- количество единиц груза запланированных к перевозке от i поставщика к j потребителю, т.к. от поставщика i к потребителю j, запланировано перевезти единиц груза, то стоимость перевозки составит .

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

Стоимость всего плана выразится двойной суммой:

Систему ограничений задачи получаем из следующих условий:

1. все грузы д/б перевезены, т.е.

2. все потребности д/б удовлетворены, т.е.

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

В рассмотренной задаче предполагается, что суммарные запасы = суммарным потребностям, т.е. выполняется условие:

Транспортная задача в которой называется закрытой моделью, в противном случае открытой. Для открытой модели м/б 2 случая:

1. суммарные запасы превышают суммарные потребности:

2. суммарные потребности превышают суммарные запасы: