Закрытая транспортная задача

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

· Нахождение исходного опорного решения;

· Проверка этого решения на оптимальность;

· Переход от одного опорного решения к другому.

Нахождение опорного решения.

Неотрицательная матрица Х, удовлетворяющая условиям задачи называется планом (или допустимым планом) задачи. Допустимый план называется оптимальным, если он доставляет минимум целевой функции.

Допустимый план имеющий не более m+n-1 отличных от нуля компонентов xij, называется базисным или опорным. Опорный план, имеющий ровно низкий m+n-1 отличных от нуля компонент, называется невырожденным, а если число отличных от нуля компонент меньше, чем m+n-1, то план называют вырожденным. Другими словами, опорным называется такой план, в котором количество не нулевых перевозок равно сумме количеств поставщиков и потребителей минус единица. Оптимальный план перевозок следует искать только среди множества опорных планов.

Условия задачи и её исходное опорное решение будем записывать в распределительную таблицу. Клетки, в которых поместим грузы, называются занятыми, им соответствуют базисные переменные опорного решения. Остальные клетки – незанятые, или пустые, им соответствуют свободные переменные. В верхнем правом углу каждой клетки будем записывать тарифы. Существует несколько способов нахождения опорного решения, которые рассмотрим на примере решения конкретной задачи.

Пример. У поставщиков А1, А2, А3 сосредоточено соответственно 30, 190 и 250 единиц некоторого однородного груза, который необходимо доставить потребителям В1, В2, В3, В4 в количестве 70, 120, 150 и 130 единиц. Стоимость перевозок единицы груза от поставщиков к потребителям задается матрицей:

Обозначив количество груза, поставляемого i-м поставщиком j-му потребителю через xij, запишем задачу в математической форме:

Найти: F(x)=4x11+7x12+2x13+3x14+3x21+1x22+2x23+4x24+5x31+6x32+3x33+7x34 min

при ограничениях:

х_ij ≥ 0.