Транспортная задача линейного программирования

Постановка транспортной задачи Однородный груз, имеющийся в m пунктах отправления (производства) А 1, А 2,..., А m соответственно в количествах а 1, а 2,..., а m единиц, требуется доставить в каждый из n пунктов назначения (потребления) В 1, В 2,..., В n соответственно в количествах b 1, b 2,..., b n единиц. Стоимость перевозки (тариф) единицы продукции из А i в В j известна для всех маршрутов A i B j и c ij (i=1..m; j=1..n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится и запросы всех пунктов потребления удовлетворяются (закрытая модель), т. е. а суммарные транспортные расходы минимальны.

Математическая модель транспортной задачи Будем называть любой план перевозок допустимым, если он удовлетворяет системам ограничений и требованием неотрицательности. Допустимый план, будем называть опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0. План будет называться оптимальным, если он, среди всех допустимых планов, приводит к максимальной суммарной стоимости перевозок.

Методы решения транспортных задач Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще. Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза Xij>=0, а в маленькие клетки - соответствующие тарифы Cij.

Методы решения транспортных задач Затем решение задачи разбивается на два этапа: 1. Определение опорного плана 2. Нахождение оптимального решения, путем последовательных операций Найдем в начале допустимое (опорное) решение транспортной задачи. Это решение можно находить, используя метод "северо-западного угла" или метод "минимального элемента". Метод северо-западного угла (диагональный). Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, что найденные компоненты плана Хij удовлетворяют горизонтальным и вертикальным уравнениям. Метод наименьшего элемента. Сущность способа в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу.

Метод северо-западного угла Начнем заполнение с клетки, расположенной вверху слева, то есть с "северо-западного угла". Вместо x 11 впишем число x 11 =min(a 1, b 1 ). Возможны два варианта. 1. min(a 1, b 1 )=a 1, то есть a 1

Метод северо-западного угла Наша таблица примет вид: a1a1 00…00 a2a2 a3a3 … amam b 1 -a 1 b2b2 b3b3 …bnbn

Метод северо-западного угла 2. min(a 1, b 1 )=b 1, то есть b 1

Метод северо-западного угла Наша таблица примет вид: b1b1 00…0a 1 -b 1 a2a2 a3a3 … amam 0b2b2 b3b3 …bnbn

Метод северо-западного угла У нас всего в таблице m строк и n столбцов. Каждый раз исчезает, как минимум, либо строка, либо столбец (могут исчезнуть сразу и строка, и столбец, если запасы какого-то подмножества складов полностью удовлетворят потребности какого-то подмножества пунктов потребления). Однако при последней перевозке исчезает сразу и последняя строка, и последний столбец. Поэтому получающийся план перевозок содержит не более m+n-1 компонент. Мы не будем доказывать, что план, полученный методом северо-западного угла, является опорным. Заметим лишь, что если получающийся план содержит ровно m+n-1 компоненту, то он называется невырожденным. Если число положительных компонент плана перевозок меньше, то он называется вырожденным.

Метод северо-западного угла Рассмотрим задачу. Фирма должна отправить некоторое количество кроватей с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 кроватей. Стоимость перевозки одной кровати со склада в магазин приведены в таблице.

Решение Построим опорный план для рассмотренной выше задачи. В начале построим его с помощью метода "северно-западного угла" Исходная транспортная таблица:

Метод минимального (максимального) элемента Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел a i и b j. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

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

Задание Найти опорный план для задачи Поставщики Потребители Запасы груза В1В1 В2В2 В3В3 В4В4 А1А X=X= А2А А3А Потребность в грузе