Транспортная задача в сетевой постановке

Содержание: 
 
 

Введение.                                                                                                 стр.3 

1.   Постановка задачи.                                                                        стр.4

1.1 Алгоритм метода потенциалов.                                                      стр.6 

1.2 Усложненные задачи транспортного типа.                                     стр.7 

1.3 Метод Фогеля.                                                                                   стр.15 

2.   Транспортная задача в сетевой постановке.                             стр.16

2.1 Доставка груза в кратчайший срок.                                                 стр. 17 

2.2 Пример решения транспортной задачи.                                          стр.18 

Заключение.                                                                                            стр.23 

Список  литературы.                                                                             стр.25 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение: 

        Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся «на глазок» (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием. Слово «программирование» здесь и в аналогичных терминах («линейное программирование, динамическое программирование» и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово «планирование». С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу.

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

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

    Цель  заданной работы - освоить математическую постановку транспортной задачи линейного программирования. 

1.Постановка задачи. 

        Классическая транспортная задача  ЛП формулируется следующим образом.  

            Имеется  m  пунктов производства (поставщиков) и n  пунктов  

потребления (потребителей) однородного продукта. Заданы величины:  

  - объем  производства (запас) i-го поставщика,  i=1, m  ;  

  - объем  потребления   (спрос) j-го потребителя, i=1, n ;  

   - стоимость перевозки (транспортные  затраты) единицы продукта от i-го поставщика к j-му потребителю.  

            Требуется составить такой план  перевозок, при котором спрос  

всех  потребителей был бы выполнен и при  этом общая стоимость всех  

перевозок была бы минимальна.  

            Математическая модель транспортной задачи имеет вид

Транспортная  задача, в которой суммарные запасы

и суммарные  потребности  

совпадают, называется закрытой моделью;  в  противном случае - открытой. Открытая модель решается приведением к закрытой.  

            В случае, когда суммарные запасы  превышают суммарные  

потребности, т.е.

вводится  фиктивный n+1 потребитель, потребности  которого  

В случае, когда суммарные потребности  превышают суммарные  

запасы,  т.е.  

, вводится  фиктивный m+1 поставщик, запасы  которого  

Стоимость перевозки единицы груза как  до фиктивного потребителя, так и  стоимость перевозки единицы  груза от фиктивного поставщика  

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

            Прежде чем решать транспортную  задачу, необходимо проверить, к  какой модели она принадлежит,  и если необходимо, то привести  ее к  

закрытой  модели.

1.1.Алгоритм метода потенциалов. 

    Алгоритм  метода потенциалов для транспортной задачи. Критерий положен в основу одного из методов решений транспортной задачи, получившего название метода потенциалов. Впервые он был предложен в 1949г. Л. В. Канторовичем и М. К. Гавуриным. Позже на базе общих идей линейного программирования аналогичный метод был предложен Дж. Данцигом. 

    Точно так же как транспортная задача является частным случаем задачи ЛП, так  и метод потенциалов, вообще говоря, может трактоваться как разновидность  симплексных процедур. Он представляет собой итеративный процесс, на каждом шаге которого рассматривается некоторый текущий базисный план, проверяется его оптимальность, и при необходимости определяется переход к «лучшему» базисному плану. 

    Алгоритм  начинается с выбора некоторого допустимого базисного плана. Если данный план не вырожденный, то он содержит m + n -1 ненулевых базисных клеток, и по нему можно так определить потенциалы ui и vj, чтобы для каждой базисной клетки (т. е. для той, в которой хi,j > 0) выполнялось условие 

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

1.2  Усложненные задачи транспортного типа. 

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

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

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

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

    3. Ряд транспортных маршрутов, по  которым необходимо доставить  грузы, имеют ограничения по  пропускной способности. Если, например, по маршруту AiBj  можно провести  не более q единиц груза, то Bj  -й столбец матрицы разбивается на два столбца -   и . В первом столбце спрос принимается равным разности между действительным спросом   и ограничением q: , во втором – равным ограничению q, т.е. . Затраты cij  в обоих столбцах одинаковы и равны данным, но в первом столбце , в клетке, соответствующей ограничению i, вместо истинного тарифа cij   ставится искусственно завышенный тариф M (клетка блокируется). Затем задача решается обычным способом. 

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

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

    6. Необходимо максимизировать целевую  функцию задачи транспортного  типа. В этой ситуации при составлении  опорного плана в первую очередь  стараются заполнить клетки с  наиболее высокими значениями  показателя cij . Выбор клетки, подлежащей заполнению при переходе от одного допустимого плана к другому, должен производиться не по минимальной отрицательной разнице , а по максимальной положительной разнице . Оптимальным будет план, которому в последней таблице сопутствуют свободные клетки с неположительными элементами: все разности . 

    7. необходимо в одно время распределить  груз различного рода по потребителям. Задачи данного типа называются  многопродуктовыми транспортными  задачами. В этих задачах поставщики m родов грузов разбиваются на m условных поставщиков, а потребители n родов грузов разбиваются на n условных потребителей. С учетом этой разбивки составляют полную транспортную таблицу. При этом заметим, что некоторые маршруты AiBj  должны быть блокированы (закрыты), поскольку в данной постановке задачи грузы разного рода не могут заменять друг друга. Этим маршрутам AiBj    должна соответствовать очень высокая стоимость перевозки. Многопродуктовую задачу не всегда обязательно описывать одной моделью. Например, если поставки грузов различного рода независимы, тот задачу можно представить в виде комплекса транспортных задач по каждому роду груза. Однако, если между грузами Различного рода существует связь (например, одни из грузов можно заменить другими), то в общем случае исходную модель (задачу) не удается разбить на комплекс простых транспортных задач. 

    Рассмотрим  примеры задач транспортного  типа. 

    Пример 1. Одно фермерское хозяйство (A1) имеет  продовольственное зерно двух видов: 3 тыс. тонн – III класса и 4 тыс. тонн - IV класса. Второе фермерское хозяйство (A2) также имеет зерно двух видов: 5 тыс. тонн – III класса и 2 тыс. тонн - IV класса. Зерно должно быть вывезено на два элеватора: на первый элеватор (B1) необходимо поставить 2 тыс. тонн пшеницы III класса, 3 тыс. тонн пшеницы IV класса и остальные 2 тыс. тонн пшеницы любого класса. 

    Аналогично  второй элеватор (B2) должен получить 8,25 тыс. тонн, из них пшеницы - 1 тыс. тонн III класса и 1,5 тыс. тонн IV класса.  

    Стоимость перевозки в д.е. 1 тонны зерна  составляет: из пункта A1  в пункты B1   и B2  - 1 и 1,5 соответственно; из пункта A2  в пункты B1  и B2  - 2 и 1 д.е. соответственно. 

    Составить оптимальный план перевозок. 

    Решение 

    Каждого поставщика условно разбиваем на две части согласно двум видам  зерна ( и ;   и ), аналогично потребителей разбиваем на три части (пшеница III класса, IV класса и любой класс): ,  и , а также , и . Потребности превышают запасы, поэтому вводим фиктивного поставщика A3. Часть клеток в таблице запираем большими числами М; например, в клетке (1; 2) стоит большое число. Это значит, что поставщик   не может удовлетворить потребителя   пшеницей IV класса за счет имеющейся пшеницы III класса. 

    С учетом сделанных замечаний составим первую таблицу (табл. 3.6). 

    Таблица 3.6 

    Исходные  данные. 
 

    Перевозки от фиктивного поставщика не производятся, поэтому . Величина М намного больше cij . Применяя метод потенциалов, в  итоге получим таблицу с оптимальным  решением (табл. 3.7). 
 
 
 
 
 

    Таблица 3.7 

    Оптимальное решение. 

    Анализ  решения. Первый поставщик поставит на первый элеватор (B1) пшеницу III класса ( x12 = 2); пшеницу IV класса (x22 = 3), а также пшеницу любого класса (III или IV) (x13 = 1 ; x23 = 1). 

    Второй  поставщик (A2) поставит на второй элеватор (B2) пшеницу III класса (x31 = 1), пшеницу IV класса (x45 = 1,5) и частично любую пшеницу (x36 = 4; x46 = 0,5). Потребность элеватора в любой пшенице не удовлетворена на 1,25 тыс. тонн (x56 = 1,25). Минимальные затраты на перевозку составили: Zmin = 14 д.е. 

    Пример 2. Модель производства с запасами. 

    Фирма переводит свой головной завод на производство определенного вида изделий, которые будут выпускаться в  течение четыре месяцев. Величины спроса в течение этих четырех месяцев  составляют 100, 200, 180 и 300 изделий соответственно. В каждый месяц спрос можно удовлетворить за счет: 

    -       запасов изделий, произведенных  в прошлом месяце, сохраняющихся  для реализации в будущем; 

    -       производства изделий в течение  текущего месяца; 

    -       избытка производства изделий  в более поздние месяцы в  счет невыполненных заказов.  

    Затраты на одно изделие в каждом месяце составляют 4 д.е. Изделие, произведенное  для более поздней реализации, влечет за собой дополнительные издержки на хранение в 0,5 д.е. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыполненных заказов, облагается штрафом в размере 2 д.е. в месяц. 

    Объем производства изделий меняется от месяца к месяцу в зависимости от выпуска  других изделий. В рассматриваемые  четыре месяца предполагается выпуск 50, 180, 280 и 270 изделий соответственно. 

    Требуется составить план, имеющий минимальную  стоимость производства и хранения изделий. 

    Решение 

    Задачу  можно сформулировать как транспортную. Эквивалентность между элементами производственной и транспортной систем устанавливается следующим образом:

    Транспортная  система 

    Производственная  система 

    1. Исходный пункт i 

    1. Период производства i 

    2. Пункт назначения j 

    2. Период потребления j 

    3. Предложение в пункте i 

    3. Объем производства за период i 

    4. Спрос в пункте j 

    4. Реализация за период j 

    5. Стоимость перевозки из i в j 

    5. Стоимость производства и хранения  за период i и j 
 

      Перед нами структура транспортной  модели. Для рассматриваемой задачи  стоимость "перевозки" изделий  из периода i в период j выражается  как: 

    Из  определения cij   следует, что затраты в период i при реализации продукции в тот же период i (i = j) оцениваются только стоимостью производства. Если в период i производится продукция, которая будет потребляться позже (i < j), то имеют место дополнительные издержки, связанные с хранением. Аналогично производство в i –й период в счет невыполненных заказов (i > j) влечет за собой дополнительные расходы в виде штрафа. Например,  

    c11  = 4 д.е. 

    c24  = 4 + (0,5 + 0,5) = 5 д.е. 

    c41  = 4 + (2 + 2 + 2) = 10 д.е. 

    Исходная  транспортная таблица выглядит следующим образом (табл. 3.8). 

    Таблица 3.8 

    Оптимальное решение. 

    Пример 3. Имеются три сорта бумаги в  количестве 10, 8 и 5 т, которую можно  использовать на издание четырех  книг тиражом 8000, 6000, 15000 и 10000 экземпляров. Расход бумаги на одну книгу составляет: 0,6; 0,8; 0,4; 0,5 кг, а себестоимость тиража книги при использовании i-го сорта бумаги задается следующей матрицей (д.е.): 

    Определить  оптимальное распределение бумажных резервов. 
 
 
 

Решение 

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

    Потребности в бумаге легко определить, зная тираж и расход на одну книгу: 

    8000 * 0,6 = 4,8 т 

    15000 * 0,4 = 6 т 

    8000 * 0,6 = 4,8 т 

    10000 * 0,5 = 5 т 

    Общие запасы бумаги составляют 23т, а общие  потребности – 20,5 т, поэтому необходимо в таблицу ввести фиктивный тираж B5   с нулевыми затратами. В  связи с тем, что мы составляем модель относительно бумаги, а матрица cij   характеризует себестоимость печатания книги, необходимо исходную матрицу преобразовать относительно единицы бумаги (каждый столбец матрицы cij   разделим на количество бумаги, приходящейся на одну книгу). 

    Согласно  изложенному составим первую таблицу (табл. 3.9). 

    Таблица 3.9 

    Исходные  данные. 

    Используя метод потенциалов, получим оптимальное  решение (табл. 3.10). 
 

    Таблица 3.10 

    Оптимальное решение. 

      Анализ решения. Бумаги 1-го сорта  в количестве 4,8 т затрачено на  издание второй книги; 2,8 т –  на издание четвертой книги; 2,4 т – не использовано. Бумаги 2-го  сорта затрачено: на первую  книгу – 4,8 т; на издание  третьей книги 1 т; на издание  четвертой книги – 2,2 т; бумага 3-го сорта использована на издание третьей книги в количестве 5 т. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     1.3.Метод Фогеля.

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

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

2.Транспортная задача в сетевой постановке. 

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

      Ограничения задачи:  

      Естественное ограничение -- условие  неотрицательности  

      Задача линейного программирования (1)-(3) называется транспортной задачей  в сетевой постановке. Обозначим через  матрицу инцидентности графа. Тогда в матричной форме задача записывается так:  

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

    2.1  Доставка груза в кратчайший срок. 

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

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

    Любым способом строим один из опорных планов.

    Определяем  наибольший элемент /' из всех ty, соответствующих занятым клеткам, и все клетки с элементами t_tj > t' (это могут быть лишь свободные клетки) вычеркиваются.

    Начиная с клетки с наибольшим временем доставки /', строим разгрузочный цикл так, чтобы клетки с нечетными номерами (считая первой разгружаемую клетку с элементом /') были занятыми. Одна из вершин разгрузочного цикла будет свободной. В общем случае построение разгрузочного цикла неоднозначно.

    Сделав  в свободную вершину цикла  поставку р, проводим компенсации по вершинам цикла, определяем величину р (так же, как в методе потенциалов), строим новый план.

    Переходим ко второму пункту алгоритма, естественно, не учитывая ранее вычеркнутые клетки.

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

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