Классы экономико-математических моделей и методы их прикладного значения в экономике и управлении

     Введем  переменные:

     обозначим количество продукта x_ij , взятого у i-го поставщика и поставленного j-му потребителю и перевозимого из пункта А_i в пункт В_j. Совокупность всех переменных x_ij обозначим .

     Целевая функция показывает затраты на перевозку  и имеет следующий вид (формула 1.7).

     

     (1.7)

      

     т.е. ,

     где f ( ) – целевая функция;

     с_ij – транспортные расходы;

     x_ij – совокупность переменных.

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

           (1.8)

,

     где x_ij – совокупность переменных;

     b_j - объем потребления;

     j – потребители.

             

       

     (1.9) 
 

     где x_ij – совокупность переменных;

     а_i - количество единиц некоторого однородного продукта;

     i – поставщики.               

     Условия (1.8) означают полное удовлетворение спроса во всех пунктах потребления; условия (1.9) определяют полный вывоз продукции от всех поставщиков.

     Таким образом, математическая формулировка транспортной задачи в общей постановке будет следующей:

     на  множестве неотрицательных (допустимых) решений системы ограничений (1.8), (1.9) найти такое решение , при котором значение линейной функции минимально.

     Указанная задача относится к задачам линейного  программирования и линейного целочисленного программирования.

     Необходимым и достаточным условием разрешимости задачи является условие баланса:

        ,     (1.10) 

     где а_i - количество единиц некоторого однородного продукта;

     b_j - объем потребления.

     Транспортная  задача, в которой имеет место, указанное равенство (1.10) называется закрытой и может быть решена, как задача линейного программирования с помощью симплексного метода. Если равенство не выполняется, то задача называется открытой [1]. 

     1.3 Методы  решения  транспортной задачи 

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

     метод потенциалов;

     венгерский  метод.

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

     Название  метода пошло от того, что при решении транспортной задачи этим методом каждому i-му поставщику (i-й строке) устанавливается потенциал u_i, который можно интерпретировать как цену продукта в пункте поставщика, а каждому j-му потребителю (j-му столбцу) устанавливается потенциал v_j, который можно принять условно за цену продукта в пункте потребителя. В простейшем случае цена продукта в пункте потребителя равна его цене в пункте поставщика плюс транспортные расходы на его доставку, т.е.

      ,    (1.11)

     где v_j – потенциал каждому j-му потребителю (j-му столбцу);

     u_i – потенциал каждому j-му потребителю (j-му столбцу);

     с_ij – транспортные расходы.

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

     Этап 1. Составление начального распределения (начального плана перевозок); для реализации этого начального этапа используется ряд методов:

     северо-западного  угла;

     наименьших  стоимостей;

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

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

     Этап 3. Реализация циклов перераспределения (корректировка плана прикрепления потребителей к поставщикам), после чего переходят опять ко второму этапу алгоритма.

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

     Пояснения к реализации данного алгоритма.

     Если  равенство (1.10) не выполняется, то ограничения (1.8 – 1.9) или имеют вид неравенств «меньше или равно», в таком  случае транспортная задача называется открытой. Чтобы использовать для ее решения метод потенциалов, ее преобразуют к закрытой транспортной задаче путем ввода или фиктивного поставщика, если в неравенства превращаются условия (1.8) или фиктивного потребителя, если в неравенства превращаются условия (1.9).

     Для закрытой транспортной задачи ранг системы линейных  уравнений (1.8), (1.9) равен m+n-1; таким образом, из общего числа (m х n) неизвестных базисных неизвестных будет m+n-1.

     Вследствие  этого при любом допустимом базисном распределении в матрице перевозок, представленной в общем виде в таблице 1.1, будет занято       (m+n-1) клеток, которые называются базисными в отличие от остальных свободных клеток; занятые клетки отмечаются диагональной чертой.

     Таблица 1.1 - Общий вид матрицы перевозок

 

     На  основе всего выше сказанного рассмотрим применение метода потенциала.

     Первоначальное  закрепление потребителей за поставщиками - начальное распределение (начальный опорный план) можно получить двумя методами:

     метод северо-западного угла;

     метод наименьших стоимостей.

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

     используя метод северо-западного угла, поступают  следующим образом, при заполнении некоторой клетки, кроме последней, вычеркивается или только строка матрицы перевозок, или только столбец; лишь при заполнении последней клетки вычеркиваются и строка, и столбец. Такой подход будет гарантировать, что базисных клеток будет ровно (m+n-1). Если при заполнении некоторой (не последней) клетки одновременно удовлетворяются мощности и поставщика, и потребителя, то вычеркивается, например, только строка, а в соответствующем столбце заполняется незанятая клетка так называемой «нулевой поставкой», после чего вычеркивается и столбец. Для идентификации клетки обычно в скобках указываются номера ее строки и столбца. В методе северо-западного угла всегда в первую очередь заполняется клетка (из числа невычеркнутых), стоящая в верхнем левом (северо-западном) углу матрицы перевозок.

     Алгоритм  метода северо-западного угла

     Составляется  транспортная задача.

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

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

     Если  а₁<b₁, то x₁₁=a₁, а разницу равную b₁-a₁ размещают в какую-либо из клеток первого столбца таблицы. Выбор строки первого столбца, куда помещают разность b₁-a₁, могут осуществлять по критерию минимальной стоимости, т.е. выбирают клетку первого столбца, в которой с_i1, будет минимальным, в нее помещаем разность b₁-a₁, если .

     Если  а₁>b₁, то x₁₁=b₁, а разницу равную a₁-b₁, размещают в любую клетку начиная со второй, первой строки.

     Если  мощности поставщика исчерпаны, то первую строку таблицы вычеркивают из рассмотрения. Если первый потребитель принял предельно  возможное количество продукции  b₁, то первый столбец таблицы вычеркивают из рассмотрения.

     Далее рассматривают второго поставщика. Распределение его ресурсов начинают с клетки х₂₂. Действия повторяются до тех пор, пока мощности всех поставщиков не будут распределены, а потребности всех потребителей не удовлетворены.

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

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

     Наиболее  оптимальный план дает метод минимального элемента (метод минимальных стоимостей).

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

     Алгоритм  метода минимального элемента

     Составляем  транспортную таблицу.

     Выбираем  клетку таблицы, которой соответствует минимальное значение с_ij

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

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

     Венгерский  метод решения задачи о назначениях