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

 

Содержание: 
 
 

Введение.                                                                                                 стр.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 тыс. тонн пшеницы любого класса.