Шпаргалки по "Основам эконометрики и математического моделирования"

7-8. Транспортная задача и метод потенциалов

Транспортная задача является специальным типом задач  линейного программирования. Экономическая  постановка этой задачи следующая. Имеется m поставщиков и n потребителей некоторой продукции. Заданы тарифы (стоимость) перевозок единицы продукции от поставщиков к потребителям, известны объемы запасов у поставщиков и потребности каждого потребителя в продукции. Требуется составить план поставок продукции от поставщиков к потребителям так, чтобы суммарная стоимость перевозок была минимальной. Математическая постановка этой задачи имеет вид (4.24):

Здесь Xij – объем, cij – тариф поставки продукции от i-го поставщика к j-му потребителю, bj – потребности потребителей в продукции, ai – запасы продукции у поставщиков. Видно, что (4.24) является задачей линейного программирования со специальной матрицей. В задаче (4.24) имеется mn неизвестных Xij и m + n уравнений. Решение транспортной задачи называется оптимальным планом перевозок (поставок) продукции.

Задача (4.24) называется сбалансированной (закрытой), если суммарный

объем потребностей равен суммарному объему предложения продукции, т.е. (4.25):

Если условие (4.25) не выполняется, то задача называется открытой. Для  решения открытую задачу преобразуют  в закрытую. Для этого в задачу вводят либо фиктивного поставщика недостающего объема продукции (если потребности больше предложения), либо фиктивного потребителя лишней продукции (если предложение больше потребностей), тарифы которых полагаются равными нулю. При решении задачи используется свойство, которое состоит в том, что ранг матрицы A задачи (4.24) на единицу меньше числа уравнений r(A) = m + n – 1. С учетом этого число ненулевых переменных Xij > 0 в опорном плане будет не больше (m + n – 1). Если число ненулевых Хij в опорном плане равно (m + n – 1), то план называется невырожденным, иначе – вырожденным. Для решения задачи (4.24) составляется табл. 4.4.

В случае открытой задачи в таблицу вводят либо фиктивного поставщика, либо фиктивного потребителя, с целью получения равенства (4.25), с соответствующим объемом продукции. Поэтому будем считать, что в таблице выполняется соотношение (4.25). Алгоритм решения задачи (4.24) состоит из двух частей: построение начального опорного плана (набора чисел Xij > 0), удовлетворяющих соотношениям (4.24)) и построение оптимального плана. При решении первой задачи осуществляют заполнение табл. 4.4, а при решении второй задачи ее преобразование по определенному алгоритму.

Построение  начального плана перевозок

Есть несколько методов  построения начального опорного плана: метод северо-западного угла, метод минимального элемента и другие. Рассмотрим метод минимального элемента

1. Выбирают клетку  табл. 4.4 с минимальным значением cij, в которую записывают min (ai, bj).

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

3. Повторяют шаг 1 до тех пор,  пока все запасы продукции  не будут исчерпаны.

Метод северо-западного угла отличается от метода минимального элемента тем, что клетки заполняют последовательно  по строкам, начиная с элемента Х11.

Построение  оптимального плана

Для построения оптимального плана перевозок используется метод потенциалов, который является формой симплекс-алгоритма. Здесь могут быть 2 варианта.

Вариант 1. Если опорный план вырожден, то в свободные клетки с минимальными значениями Сij записывают перечеркнутые нули 0, (фиктивные поставки), пока не получат невырожденный план. Число 0 считается очень малой положительной величиной.

Дальше задача решается методом потенциалов.

Вариант 2. Опорный план невырожден, поскольку количество ненулевых Хij равно m + n – 1.

1. Для Xij > 0 составляется система уравнений: ui + vj = cij. (4.26) Неизвестные ui, vj называются индексами (потенциалами).

2. Поскольку в системе (4.26) количество  уравнений на единицу больше числа неизвестных, то одному неизвестному надо присвоить произвольное значение (обычно 0). Система (4.26) решается последовательно подстановкой полученных значений в следующие уравнения. После решения системы (4.26) для свободных клеток таблицы

определяют потенциалы Sij = Сij – (ui + vj). (4.27)

3. Если все Sij ≥ 0, то полученный план оптимальный. Иначе выбирают клетку с минимальным Sij < 0. Начиная с выбранной клетки матрицы перевозок, стоится замкнутый прямоугольный цикл (цепочка) с вершинами в заполненных клетках (в том числе символом 0). Выбранной клетке присваивается знак «+», следующей вершине цикла

по (или против) часовой стрелке – знак «–», далее «+»,«–», и т.д. по циклу. Данная цепочка знаков обязательно заканчивается знаком «–». Цепочка называется вырожденной, если она состоит из одного элемента. Среди клеток цикла, отмеченных знаком «–», выбирается клетка с наименьшим значением переменной Хij, затем из нагрузки клеток, отмеченных знаком «–», вычитают это значение, а клетки, отмеченных знаком «+», прибавляют это значение. Получают новый опорный план, который проверяют на невырожденность и в случае необходимости выполняют переход к невырожденному по варианту 1. После этого осуществляется переход к шагу 1.