Решение экономических ЛЗП, сводящихся к транспортной задаче

После того как проделаны т + п — 2 описанных выше шагов, получают задачу с одним пунктом отправления и одним пунктом назначения. При этом останется свободной только одна клетка, а запасы оставшегося пункта отправления будут равны потребностям оставшегося пункта назначения. Заполнив эту клетку, тем самым делают ( п + т — 1 ) - й шаг и получают искомый опорный план. Следует заметить, что на некотором шаге (но не на последнем) может оказаться, что потребности очередного пункта назначения равны запасам очередного пункта отправления. В этом случае также временно исключают из рассмотрения либо столбец, либо строку (что-нибудь одно). Таким образом, либо запасы соответствующего пункта отправления, либо потребности данного пункта назначения считают равными нулю. Этот нуль записывают в очередную заполняемую клетку. Указанные выше условия гарантируют получение п + т — 1 занятых клеток, в которых стоят компоненты опорного плана, что является исходным условием для проверки последнего на оптимальность и нахождения оптимального плана. 

       Метод северо - западного угла.

   При нахождении опорного плана транспортной задачи методом северо-западного угла на каждом шаге рассматривают первый из оставшихся пунктов

      отправления и первый из оставшихся пунктов назначения. Заполнение

клетоктаблицы условий начинается с левой верхней клетки для неизвестного Х₁₁ («северо-западный угол») и заканчивается клеткой для неизвестного х_тп, т. е.

       идет как бы по диагонали таблицы. 

       Метод минимального элемента.

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

       Метод аппроксимации Фогеля.

       При определении оптимального плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывют в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

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

       Определение оптимального плана  транспортной  задачи.

     Для определения оптимального плана транспортной задачи разработано

несколько методов. Однако наиболее часто используются метод потенциалов и метод дифференциальных рент. 

       Метод потенциалов.

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

       Для определения  опорного плана транспортной задачи будем пользоваться одним из методов, рассмотренных в предыдущем параграфе. Эти методы гарантируют получение занятых в исходном плане п+т—1 клеток, причем в некоторых из них могут стоять нули. Полученный план следует проверить на оптимальность.

    Если  для некоторого опорного плана  транспортной задачи

   существуют  такие  числа  что

   

   

                               при                                                  (8)

                               при                                                (9)

для   всех  и ,   то  Х* = ( ) — оптимальный  план 
транспортной задачи.

Числа а_i и b_j; называются потенциалами соответственно пунктов назначения и пунктов потребления.

       Сформулированная  теорема позволяет построить  алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяют потенциалы а_i и b_j . Эти числа находят из системы уравнений

                                                                                                       (10)

       где с_ij — тарифы, стоящие в заполненных клетках таблицы условий транспортной задачи.

       Так как число  заполненных клеток равно п+m—1, то система (10) с

       п + m неизвестными содержит n + m—1 уравнений. Поскольку число неизвестных превышает на единицу число уравнений, одно из неизвестных можно положить равным произвольному числу, например a₁ = 0, и найти последовательно из уравнений (10) значения остальных неизвестных. После того как все потенциалы найдены, для каждой из свободных клеток определяют числа                  .

       Если среди чисел  а_ij нет положительных, то найденный опорный план является оптимальным. Если же для некоторой свободной клетки а_ij > 0, то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых a_ij > О, и среди данных чисел выбирают максимальное. Клетку, которой это число соответствует, следует заполнить.

       Заполняя выбранную  клетку, необходимо изменить объемы поставок, записанных в ряде других занятых клеток и связанных с заполненной так называемым циклом.

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

       Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами. Примеры некоторых циклов показаны на рис.1.

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

1. каждой из клеток, связанных циклом с данной свободной  клеткой, приписывают определенный  знак,  причем  свободной клетке — знак плюс,  а всем  остальным клеткам — поочередно знаки минус и плюс (будем называть эти клетки минусовыми и плюсовыми);
2. в данную свободную клетку переносят меньшее из чисел x_ij , стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая  ранее была свободной,  становится занятой,  а минусовая клетка, в которой стояло минимальное из чисел x_ij считается свободной.

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

       Описанный выше переход  от одного опорного плана транспортной задачи к другому ее опорному плану называется сдвигом по циклу пересчета.

       При сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно остается равным п + m — 1. При этом если в минусовых клетках имеется два (или более) одинаковых числа x_ij , то освобождают лишь одну из таких клеток, а остальные оставляют занятыми (с нулевыми поставками).

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

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

1. Находят   опорный   план.   При   этом   число  заполненных 
   клеток должно быть равным п + m — 1.
2. Находят потенциалы b_j и а_i соответственно пунктов назначения и отправления.
3. Для каждой свободной клетки определяют число а_ij. Если 
   среди  чисел  а_ij  нет  положительных, то  получен оптимальный 
   план транспортной задачи; если же они имеются, то переходят 
   к новому опорному плану.
4. Среди положительных чисел а_ij выбирают максимальное, 
   строят для свободной клетки, которой оно соответствует, цикл 
   пересчета и производят сдвиг по циклу пересчета.
5. Полученный опорный план проверяют на оптимальность, 
   т. е. снова повторят все действия начиная с этапа 2.

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

       3. Алгоритм

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

       При нахождении опорного плана транспортных задач были использованы:

       Метод северо – западного  угла. потребности последнего из оставшихся потребителей удовлетворяют за счет возможности последнего из оставшихся отправителей. Он очень прост, но опорный план не достаточно хорош.

<