Экономико-математическая модель транспортной задачи. Методы определения первоначального маршрута поставок: метод минимизации затрат и «северо-западного угла». Метод потенциалов.

Лекция №6. Экономико-математическая модель транспортной задачи. Методы определения первоначального маршрута поставок: метод минимизации затрат и «северо-западного угла». Метод потенциалов. В экономике нередко возникают задачи связанные с транспортной логистикой: перемещение ресурсов и грузов от поставщиков к потребителям. С точки зрения экономической выгоды предприятия решение транспортной задачи сводится к минимизации затрат на перевозку соответствующих товаров. К числу подобных задач относятся: 1. Соответствие пунктов отправления и пунктов назначения; 2. Прикрепление потребителей ресурса к производителям; 3. Взаимная «привязка» грузопотоков прямого и обратного направления; 4. Отдельные задачи оптимальной загрузки промышленного оборудования; 5. Оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и другие [1]. Раздел исследования операций в экономике включает в себя класс, так называемых, транспортных задач, для решения которых существует ряд методов поиска маршрутов перевозок и оптимизации плана транспортировок. Нужно отметить, что транспортные задачи являются подклассом задач линейного программирования. В общем виде постановка транспортной задачи может быть записана так: пусть имеется m поставщиков A1 , A2 ,..., Am , у которых в запасах находится ресурс в объемах a1 , a2 ,..., am , соответственно. Известно, что данный ресурс востребован n-ым количеством потребителей ( B1 , B2, ..., Bn ), чьи потребности определены в объемах b1 , b2 ,..., bn . Кроме того, известна стоимость доставки ресурсов от каждого поставщика к каждому потребителю. Необходимо составить экономико-математическую модель транспортной задачи и определить оптимальный план перевозок. Таким образом, решение транспортной задачи сводится к определению количества груза необходимого для отправки от каждого поставщика каждому потребителю с минимальными затратами на транспортировку. Нужно дополнить, что расходы на перевозку, как правило, представляются в виде матрицы (это обусловлено табличным представлением решения   транспортной задачи, чуть позже это станет очевидным) и обозначаются C  cij . Как и во всякой задаче линейного программирования, необходимо составить целевую функцию, систему ограничений и условие неотрицательности. Если через xij обозначить количество ресурса перевозимого от поставщика Ai к B j , то целевая функция запишется так: m n F   cij xij  min , (6.1) i 1 j 1 а ограничения запишутся следующим образом: m  xij  ai , i  1, m  j 1 n   xij  b j , j  1, n  i 1 (6.2) xij  0, i  1, m, j  1, n. Поясним. Первое равенство (выделенное красным цветом) в системе ограничений демонстрирует тот факт, что все ресурсы из i-х пунктов должны быть отправлены поставщикам, т.е. должны быть осуществлен полный вывоз. В свою очередь, второе равенство (выделенное синим цветом) демонстрирует, что все потребности j-х пунктов (поставщиков) должны быть удовлетворены. Необходимым и достаточным условием разрешимости транспортной задачи является равенство мощностей имеющихся поставщиков и потребителей. Математически это утверждение запишется в виде равенства суммы запасов поставщиков и суммы потребностей потребителей: m n i 1 j 1  ai   b j . (6.3) В том случае, когда равенство (6.3) выполняется, то такая задача называется закрытой. Если же это равенство нарушено, что в реальной экономике происходит часто, то транспортную задачу называют открытой. Нарушение этого равенства происходит по двум причинам. Первая – тот случай, когда запасы ресурсов (мощность) поставщиков больше потребностей потребителей. И, вторая – тогда, когда мощности потребителей превышаю запасы ресурсов поставщиков. Такие задачи необходимо приводить к закрытому виду. В том случае, если потребности в ресурсах со стороны потребителей превышают имеющиеся запасы у поставщиков, то вводится, так называемый, фиктивный поставщик. Потребности фиктивного поставщика составляют ровно то количество ресурсов, которое потребно для полного удовлетворения всех потребителей. В свою очередь, если запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель, потребности которого определяются разнице между запасами поставщиков и потребностями потребителей. Важно отметить, что стоимость перевозки по маршрутам фиктивных поставщиков и потребителей равна нулю. И это вполне естественно, поскольку этих маршрутов фактически (в реальной транспортной сети) не существует. После того, как введены фиктивные пункты, транспортная задача становится закрытой и решается обычными методами. Транспортные задачи также обладают некоторыми особенностями: 1. Распределению подлежат только однородные ресурсы; 2. Условия задачи описываются только уравнениями; 3. Все переменные выражаются в одинаковых единицах измерения; 4. Во всех уравнениях коэффициенты при неизвестных равны единице; 5. Каждая неизвестная встречается только в двух уравнениях системы ограничений. Традиционным представлением транспортной задачи является табличная запись исходных условий. В таблице 6.1 показан обобщённый вариант записи транспортной задачи. Таблица 6.1. Запись транспортной задачи в табличном виде. Потребители B2 b2 B1 b1 B3 b3 … Bn bn Поставщики Мощности A1 a1 c11 c12 c13 … c1n A2 a2 c21 c22 c23 … c2n A3 a3 c31 c32 c33 … c3n … … Am an … cm1 … cm 2 … cm3 … … … … cmn Собственно, все решение будет происходить в рамках этой таблице, где каждая ячейка со стоимостью – это определенный маршрут. Но перед оптимизацией транспортной сети прежде необходимо отыскать первоначальный план перевозок (первоначальный маршрут транспортировки ресурсов от поставщиков к потребителям). В нашей лекции рассмотрим два метода, позволяющих сделать это. Построение начального опорного плана методом минимального элемента (метод минимизации затрат). Метод основан на последовательном поиске того маршрута (той ячейки), стоимость которого является наименьшей из имеющихся. Тогда план перевозок строим таким образом, чтобы перевозки xij выполнялись, по возможности, по маршрутам с минимальной стоимостью. Рассмотрим применение этого метод на конкретном примере. Пусть имеется некоторая маршрутная сеть с известными стоимостями перевозок. Таблица 6.2. Мощности поставщиков и потребителей (стоимость перевозок). Поставщики Потребители Мощности B2 B1 70 5 1 A1 B4 B3 45 70 2 9 7 4 1 5 6 4 8 3 2 3 3 1 60 60 3 A2 55 10 A3 45 40 5 A4 35 35 35 Прежде выполним проверку равенства баланса мощностей. 4 4 i 1 j 1  ai   b j  . 60  55  40  35  70  5  45  70 Мощность поставщиков равны мощности потребителей, а значит, транспортная задача является закрытой. Теперь выполним поиск первоначального маршрута распределения ресурсов. Всего в транспортной сети существует три маршрута (ячейки) с минимальной стоимостью равной 1: маршруты 11, 23 и 44. В том случае, когда есть несколько маршрутов с одинаковой стоимостью перевозки – мы можем выбрать любой из них. Например, маршрут 11. Этот маршрут ведет от первого поставщика ( A1 ) к первому потребителю ( B1 ). Причем, из условий задачи известно, что первому потребителю требуется 70 единиц ресурса, в то время как первый поставщик в запас имеет только 60 единиц ресурса. Тогда, по маршруту 11 перевезем все имеющиеся у первого поставщика запасы первому потребителю. В таблице это запишется так: в ячейке 11 под диагональю (правом нижнем углу, напротив стоимости маршрута) запишем количество перевозимого ресурса, т.е. 60 единиц, и проведем в этой ячейке сплошную диагональ, что будет свидетельствовать о задействованном маршруте. Поскольку запасы первого поставщика исчерпаны, то в строке 1 в оставшихся ячейках (12, 13 и 14) начертим пунктирные диагональные линии, что будет говорить о незадействованных маршрутах. Далее, не прибегая к подробному описанию выполняемых действий, выпишем следующие маршруты, удовлетворяющие используемому методу: маршрут 23 – перевозим 45 ед. ресурса; маршрут 44 – перевозим 35 ед. ресурса; маршрут 21 – перевозим 10 ед. ресурса; маршрут 34 – перевозим 35 ед. ресурса; маршрут 32 – перевозим 5 ед. ресурса. Заметим, что все ресурсы вывезены, а все потребности удовлетворены. После определения первоначального плана транспортировки ресурсов нужно вычислить целевую функцию (6.1). Причем в расчет целевой функции выходят только задействованные маршруты (ячейки со сплошными диагональными линиями). Для транспортной сети из таблицы 6.2 целевая функция составит: F  1 60  3 10  1 45  4  5  3  35  1 35  295 ден.ед. . (6.3) Построение начального опорного плана методом северо-западного угла. Название этот метод получил благодаря способу продвижения по транспортной сети. В отличие от метода минимизации затрат метод северо-западного угла не ориентируется на стоимость перевозки по конкретному маршруту. Первой ячейкой выбирается всегда верхняя левая, после чего весь имеющийся ресурс первого поставщика используется для того, чтобы удовлетворить потребности первого потребителя. В том случае, если ресурс первого поставщика еще не исчерпан, а потребности первого потребителя удовлетворены, то столбик под заполненной клеткой вычеркивается (пунктирной линией) и переходят к удовлетворению следующего потребителя за счет первого поставщика. Этот процесс повторяется до тех пор, пока не будут израсходованы все запасы первого поставщика. После этого переходят к расходованию запасов второго поставщика. Используем метод северо-западного угла для транспортной сети в таблице 6.2. Таблица 6.3. Мощности поставщиков и потребителей (стоимость перевозок). Поставщики Потребители Мощности B2 B1 70 5 1 A1 B4 B3 45 70 2 9 7 4 1 5 60 60 3 A2 55 5 10 6 A3 8 40 3 5 2 A4 4 40 3 3 35 1 35 35 Однако относительная легкость в использовании этого метода компенсируется большим значением целевой функции, которую нужно минимизировать. Для метода северо-западного угла она составит: F  1 60  3 10  4  5  1 40  8  5  3  35  1 35  330 ден.ед. . (6.4) Сравнивая метод минимизации затрат и метод северо-западного угла можно заметить, что, как правило, первый метод позволит обеспечить наименьшие издержки на транспортировку ресурсов и грузов от поставщиков к потребителям. Транспортные задачи могут быть решены, в том числе, и симплекс методом, но применение этого метода для решения таких задач сопряжено с громоздкими записями и формулами. Для проверки полученного первоначального опорного плана транспортировки ресурсов и грузов может быть использован, так называемый, метод потенциалов. Суть этого метода заключается в последовательном улучшении первоначального опорного плана до тех пор, пока он не будет удовлетворять признакам оптимальности. В целом использование метода потенциалов можно свести к следующему алгоритму: 1. Определить первоначальный опорный план одним из методов: минимизации затрат, северо-западным углом; 2. Для каждого поставщика и потребителя назначить потенциалы (ввести их обозначения); 3. Составить систему уравнений для задействованных в транспортировке маршрутов. Для каждого задействованного маршрута уравнение составляется так: cij  ui  v j  0 , где ui - это потенциал i-ого поставщика, а v j - потенциал j-ого потребителя. 4. Приняв один из потенциалов системы равным нулю, необходимо определить численные значения каждого потенциала. 5. Для того, чтобы можно было сделать заключение об оптимальности первоначального плана транспортировки, необходимо вычислить матрицу оценок по следующей формуле: cij  ui  v j . Причем, несмотря на то, что система уравнений составлялась только для задействованных маршрутов, оценки вычисляются для каждой ячейки транспортной сети. 6. Если в оценочной матрице нет отрицательных значений, то план перевозок является оптимальным. 7. Если в оценочной матрице есть отрицательные значения, то план перевозок является неоптимальным. В этом случае необходимо выполнить поиск новых маршрутов транспортировки. В решении транспортной задачи этот этап называется «передачей поставки по циклу» [2]. 8. После «передачи поставки по циклу» вновь вычисляется матрица оценок и проверяется критерий оптимальности. Воспользуемся методом потенциалов для опорного плана из таблицы 6.3, полученного методом северо-западного угла и покажем, что план является неоптимальным и может быть улучшен. Таблица 6.4. Первоначальный опорный план. Потребители Поставщики B2 B1 Мощности 70 v1 1 A1 60 v2 5 B4 B3 v3 45 70 2 9 7 4 1 5 v4 u1 60 3 A2 55 u2 5 10 6 A3 40 35 8 u3 3 5 2 A4 4 40 3 3 35 1 u4 35 Составим систему уравнений для ячеек (маршрутов), задействованных в транспортировки ресурсов. u1  v1  1  0  u2  v1  3  0 u2  v2  4  0  u2  v3  1  0 . u  v  8  0  3 3 u3  v4  3  0  u4  v4  1  0 (6.5) Пусть u1  0 , тогда u 2  2 v1  1 u3  9 v2  2 u 4  7 v3  1 . (6.6) v4  6 Вычислим матрицу оценок.  0 0 10 13    0 0 0 9  I1  .  4 7 0 0     6 6 3 0  (6.7) Матрица I1 содержит отрицательные значения, что говорит о том, что первоначальный план перевозок не является оптимальным. Выполним «передачу по циклу». Для этого определим ту ячейку, которая получила наименьшую оценку. Для существующей транспортной сети наименьшая оценка равна -7, что соответствует маршруту 32. Эта оценка означает, что, если задействовать маршрут 32, то целевая функция может быть уменьшена на величину F  330  7  xij , где xij - это количество ресурсов или грузов, передаваемых по циклу. Фактически, внутри цикла происходит перераспределение грузов. На этом этапе промежуточная задача сводится к поиску этого самого цикла, по которому происходит передача поставки. «Циклом пересчета называется такой цикл в таблице с базисным распределением поставок, при котором одна из его вершин лежит в свободной клетке, остальные – в заполненных. Цикл пересчета называется означенным, если в его вершинах расставлены знаки «+» и «–» так, что в свободной клетке стоит «+», а любые две соседние вершины имеют разные знаки» [2]. Для того, чтобы понять какое количество ресурса передавать по циклу, необходимо среди ячеек со знаком минус выбрать ту, в которой находится наименьшее количество ресурса. После этого, в тех клетках, где есть знак плюс на это количество необходимо увеличить поставляемый ресурс, а в клетках со знаком минус, соответственно, уменьшить. Таблица 6.5. Цикл пересчета. Потребители Поставщики B2 B1 Мощности v1 70 1 A1 60 v2 5 B4 B3 2 v3 45 9 v4 70 7 u1 60 3 A2 55 4 - 4 + 10 6 A3 40 1 + 8 - 5 u2 5 40 3 u3 5 2 A4 35 3 3 35 1 u4 35 Определим величину поставок передаваемых по циклу: min 5;5  5 . Поскольку в обеих ячейках со знаком минус находится одинаковое количество транспортируемого ресурса, то можем выбрать любую из них. Тогда, транспортная сеть после пересчета примет вид: Таблица 6.6. План перевозок после пересчета. Потребители Поставщики B2 B1 Мощности 70 v1 1 A1 60 5 B4 B3 v2 45 v3 70 2 9 7 4 1 5 v4 u1 60 3 A2 55 u2 10 A3 40 6 4 2 3 45 8 3 3 1 u3 5 A4 35 35 u4 35 Важно! Заметьте, что в одной из ячеек (маршрут 22) оставлено значение 0 в качестве перевозимого объема ресурсов. Хотя в такой же ситуации для маршрута 33 ячейка обозначена, как неиспользуемая. Это сделано не случайно. Важно учесть, что далее необходимо составить систему уравнений и заново рассчитать потенциалы поставщиков и потребителей. Если в системе уравнений не будет учтен маршрут 22, то система окажется не разрешимой. Подробный расчет потенциалов поставщиков и потребителей приводить более не будем, поскольку читатель уже ознакомлен с этой процедурой и может её выполнить самостоятельно. Запишем лишь конечную матрицу оценок после выполненного цикла пересчета. 0  I2   3  1 0 10 6   0 0 2 . 0 7 0  1 4 0 (6.8) Как видно в матрице оценок более нет отрицательных значений, что свидетельствует об оптимальности последнего найденного плана перевозок. Осталось выяснить, чему равна целевая функция после перераспределения поставок. Ранее мы говорили, что, если будет задействован маршрут 32, то целевая функции уменьшится на F  330  7  xij . Но тогда нам не было известно количество передаваемого по циклу ресурса. Сейчас же мы знаем этот объем – он равен 5 единицам. Тогда F  330  7  5  295 ден. ед. В следующих лекциях мы попробуем разобраться с тем, что такое системы массового обслуживания и, как можно охарактеризовать их работу. Успехов! Список дополнительных источников литературы и методических пособий 1. Невежин В.П., Кружилов С.И. Сборник задач по курсу «Экономикоматематическое моделирование». – М.: ОАО «Издательский Дом «Городец», 2005. – 320 с. 2. Лукиных, И.Г. Методы оптимальных решений. Учебное пособие: курс лекций для студентов направлений 080100 «Экономика», 100700 «Торговое дело» всех профилей подготовки всех форм обучения/ И.Г.Лукиных. – Киров: ПРИП ФГБОУ ВПО «ВятГУ», 2012. – 63 с.