Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 22
Текст из файла (страница 22)
Графическая интерпретация транспортной задачи. Таблица 2.28. Входная информация в транспортной задаче У = 1 У = 2 / = 3 " У = я 1=1 а~ аз аз 1=2 1=3 а ь ь- ь, " ь„ Рассмотрим следующий пример, в котором заданы два источника снабжения и три пункта потребления и, кроме того, предполагается, что если стоимость производства единицы продукции не постоянна для каждого источника снабжения, то ве.
Входная информация в транспортной задаче обычно представляется двумерным массивом, содержащим стоимости перевозок продукта по всевозможным маршрутам, а также производительности пунктов снабжения и спросы пунктов потребления. Пример такого массива для задачи, описанной на рис. 2.38„ приведен в табл. 2.23. 127 Детерминированнь~е иотони в сетя» личина сп может включать в себя стоимость производства еди- ницы продукции 1-м источником: 1 2 3 ас 1 3 4 7 20 2 б 3 2 10 Ь, Ю 12 В Если в силу причин сризического или экономического характера некоторый маршрут не может быть использован, то стоимость транспортировки единицы продукта по данному маршруту принимается равной оо. 2.10.1.МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА Пусть хп — количество продукта, транспортируемого из с-го источника в у-й сток.
Целевая функция в данной модели соответствует общим транспортным затратам. Накладываемые ограничения нужны для того, чтобы вся произведенная продукция использовалась и спрос каждого пункта потребления удовлетворялся. Задача формулируется следующим образом: минимизировать Е='~' ~~~~~ о,ух,у при условии, что хм — — аи с = 1,..., лу, / Х хм= Ьс, у = 1,..., пс ху>~0, 1=1,...,лу, 1=1,...,п. Для этой задачи выполнены некоторые необходимые и достаточные условия существования целочисленного оптимального решения для задач ЛП с целочисленными параметрами. Для существования решения в сформулированной задаче мы требуем, чтобы предложение и спрос удовлетворяли соотношению Хпс=ХЬу, которое означает, что по крайней мере одно ограничение является избыточным.
Если в качестве целевой функции выбрать — е"„то можно дать эквивалентную формулировку данной задачи: максимизировать ~' ~~~~ ( †ос )х, Глава 2 $28 при условии, что хм=а,, Х ! ~~~, хи= б' хм>~ Ов 1э" э лдэ 1=1,...,л. 1= 1,..., пд, минимизировать (~ а,Яд+ '~' ЬдКд) Е ! при условии, что Р,+Кд+сдд ~~ 0 для всех д и всех 1. В данной задаче дд; — это двойственная переменная, соответствующая д-му ограничению на предложение, а Кд — двойственная переменная, соответствующая 1-му ограничению на спрос.
Обе переменные могут принимать как положительные, так и отрицательные значения, поскольку они соответствуют ограничениям типа равенства в прямой задаче. Для рассмотренного выше примера прямая и двойственная задачи линейного программирования формулируются следующим образом. Прямая задача. Максимизировать ( — Зхм — 4х,д — 7хдв — 6хдд — Зх„— 2х 1 ари условии, что х„+х„+хда 20, + +х =10 + хлд *= 10, +хдд = 12, +~Ъ=8, х„+ хдз хдв хм) )О. Двойственная задача.
Минимизировать (20Яд+10Яд+ 10К, + 12К,+ 8Кв1 Ниже будет дано описание симплексного алгоритма для транспортной задачи. Для этого сформулируем двойственную задачу по отношению к предыдущей задаче линейного программирования: 129 Детерминированные потоки е сете« при условии, что я, +к, +з>о, й, +К, +4>0, Р +Ко+7 )~ 0 Р,+К, +6>0, л, +к, +з>о, И, +К,+2 > О.
Рг и К~ могут принимать как положительные, так и отрицательные значения. Допустимое решение транспортной задачи может быть записано в виде следующего двумерного массива, состоящего из т строк н и столбцов. Значение элемента хп этого массива равно количеству продукта, транспортируемого из 1-го источника в гчй сток: «ы «те «ы ''' «те х„х„х„х,„ х , хее х, х „ Допустимое решение, соответствующие ему транспортные затраты и величины предложения и спроса могут быть записаны в виде одного массива, как это показано на рис. 2.39. Для рассматриваемого числового примера допустимое решение может быть записано в следующем виде: от го гз 1о 12 з Общие транспортные затраты в данном случае равны 10 3+ +10 4+2 3+8 2=92.
Глаза 2 ат 02 ьл ь, ьт ь, Рис. 2.39. Матрица условий транспортной задачи. 2Я0,2. СИМПЛЕКСНЫИ АЛГОРИТМ ДЛЯ ТРАНСПОРТНОИ ЗАДАЧИ Перед тем как перейти к описанию алгоритма, введем несколько важных понятий. Базисным допустимым решением транспортной задачи с лт источниками и п стоками называется допустимое решение, содержащее не более па+и — 1 положительных переменных. Как отмечалось в равд. 2.10.1, в транспортной задаче, решаемой методом линейного программирования, не более т+и — 1 независимых ограничений.
Совокупность лтп переменных базисного решения может быть разбита на две группы, в одну из которых входят па+и — 1 переменных, а во вторую лтп — (си+и — 1) переменных. Базисное допустимое решение можно найти, полагая значения переменных второй группы равными нулю и определяя затем значения переменных первой группы как решение системы уравнений, соответствующих независимым ограничениям задачи. Переменные первой группы называются базисными, а переменные второй группы— внебазисныии. Маршрут будем называть базисным, если он соответствует базисным переменным (т. е. поток по нему не равен нулю), и внебазисным, если он соответствует внебазисным переменным. Говорят, что базисное решение является вырожденным, если по крайней мере одна из его базисных переменных равна нулю.
)з) Детерминированные логани е сетях Редукция строк и столбцов матрицы стоимостей: в каждой строке (и столбце) найти минимальный элемент и вычесть вго из всех элементов этой строки (столбца) Шатт Найти назначение, единичным элвмвнтам которого соотввтотвуют пулевые элементы редуцированной матрицы стоимостей Шага Олтималь. нов реве- нив Найдвнолн назначение? Нвт модифицировать редуцированную матрицу стоимостей: а. Вычеркнуть вов пулевые элементы, используя лри этом минимальное число ввртикальных и горизонтальных линий.
б. Из всех нввычвркнутых элементов вычесть минимальь ный нввычвркнутый элемент и прибавить вго к каж. дому элементу, расположенному на пересечении двух линий. Шага Ряс, 2.40. Блок-схема сямплскспого алгорнтма для транспортной задачи, проверяется, не окажется ли полезной замена одного из текущих базисных маршрутов другим (внебазисным), еще не использованным маршрутом. Если в результате такой проверки устанавливается, что замена некоторого маршрута приводит к улучшению решения, то все потоки должны быть выбраны таким образом, чтобы базисное решение оставалось допустимым.
9' Симплексный алгоритм для транспортной задачи начинает работу при некотором невырожденном базисном допустимом решении. Затем, выполняя проверку, аналогичную проверке условия оптимальности для задачи линейного программирования, 1ЗЯ Глаза г Алгоритм состоит из' четырех шагов. Назначение каждого шага и его связь с другими шагами показаны на блок-схеме, изображенной на рис. 2.40. В дальнейшем для простоты изложения множество базисных маршрутов будем называть базисом. Обозначим через т' вектор двойственных переменных, т. е.
у=[11ь Лз. -.. Я ь, Кь Км .-, К4, и пусть Ац — вектор коэффициентов, с которыми переменные хц входят в ограничения в прямой задаче. Как было установлено при рассмотрении. примера нз разд. 2.10.1, вектор Ац может быть записан в виде 0 ~ — ья позиция О Ац = « — Оп + й.я позиция О У словие оптимальности для прямой задачи может быть записано в виде неравенства з'Ац+сц)0. Поскольку ТАц= =%+Кь то данное условие можно переписать в виде Л;+К~+ +сц)0, что совпадает с условием допустимости для двойственной задача, Это означает, что 7 не является допустимым решением двойственной задачи, а решение прямой задачи не является оптимальным, если для некоторого внебазисного маршрута, соединяющего 1-й источник с )ьм стоком, величина К+ +К~+сц(0, Кроме того, наименьшая отрицательная величина Й~+Кт+сц соответствует маршруту с наибольшей возможностью улучшить решение. Перейдем к описанию алгоритма.
Шаг 1. Выбор начального допустимого решения. Существует несколько методов построения начального допустимого решения. Наиболее распространенными из них являются, вероятно, метод «северо-западного угла» и приближенный метод Фогеля (ПМФ). Остановимся иа кратком описании этих методов. Метод «северо-западного угла». Определяем для маршрута, соединяющего первый источник с первым стоком, максимально допустимый поток.
Пусть хп — число единиц этого потока. Если а~ =Ьь то удаляем источник 1 и сток 1 и выбираем маршрут, 1ЗЗ Детермииироваиные потоки е сетях соответствующий переменной хзз. В противном случае поступаем следующим образом. Если предложение источника реализовано полностью, то удаляем источник и выбираем маршрут, соответствующий переменной хш. Если же удовлетворяется спрос стока, то удаляем сток и выбираем маршрут, соответствующий переменной хш. Определяем для выбранного маршрута максимально допустимый поток н удаляем либо источник, если его предложение реализовано полностью, либо сток, если его спрос удовлетворяется. Если одновременно выполняются условия на предложение и спрос, то удаляется н источник, и сток.
Продолжаем выполнять аналогичную процедуру. Пусть хн— последняя из выбранных базисных переменных. Тогда на следующем шаге выбирается переменная хп1+ь если предложение 1-го источника реализовано не полностью, переменная х;+!,1, если спрос 1чго стока удовлетворен не полностью, и хг+1,1+!— в противном случае. Таблица 2.24.
Начальное решенне, найденное с помощью метода «северо-западного угла» з 4 5 6 а! 150 Ззо 250 Ь| 100 150 250 250 Зоо 200 В качестве примера рассмотрим транспортную задачу, описанную в табл. 2.24, и найдем для нее начальное решение с помощью метода «северо-западного угла». Через М здесь обозначено произвольное достаточно большое число. а. Задание 1-й строки 1 2 3 4 5 б !! ! Предложение источника 1 потреблено полностью Спрос стока 1 удовлетворен 134 Глава 2 б. Задание 2-й строки 1 2 3 4 5 б Предложение источника 2 потреблено полностью Спрос стока 2 удовлетворен в.
Задание 3-й строки 1 2 3 4 5 б Предложениеисточника Э потреблено полностью Спрос стока 3 удовлетворен г. Задание 4-й строки 1 2 3 4 5 б Предложение источника 4 потреблено полностью Спрос стока 4 удовлетворен д. Начальное базисное допустимое решение, полученное с помощью метода «северо-западного угла» 1 2 3 4 5 б а~ 150 200 300 350 250 У = 40 950 Ь| 100 150 250 250 300 200 Приближенный метод Фогеля. Данный эвристический метод является более совершенным по сравнению с методом «северозападного угла», поскольку при выборе маршрута с помощью ПМФ используется информация о транспортных затратах. Для каждого источника (и каждого стока) вычисляется минимальный штраф за отказ воспользоваться наиболее экономным маршрутом, исходящим из этого источника (заходящим в этот 1Зо Детериинироеаннь~е яотохи е сетях 1 2 3 4 5 б аг 1 2.
з 4 150 200 зоо 350 250 о = 39300 Ье 100 150 250 250 300 200 Общие транспортные затраты для схемы перевозки, полученной с помощью метода «северо-западного угла», составляют 40950, а для схемы, полученной с помощью ПМФ, они составляют 39 300. Зто говорит о превосходстве ПМФ над методом «северо-западного угла». сток). Затем среди вычисленных значений минимального штрафа определяется наибольшее и выбирается соответствующий этому значению источник или сток, Наиболее экономному маршруту, исходящему из выбранного источника (или заходящему в выбранный сток), назначается максимально допустимый поток.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
