36061

Нахождение начального решения для транспортной задачи

Доклад

Информатика, кибернетика и программирование

Для решения транспортной задачи разработано несколько методов каждый из которых отличается от другого методом заполнения матрицы перевозок. Метод минимального элемента Алгоритм метода минимального элемента состоит в следующем. Метод Фогеля Метод состоит в следующем. В выбранной строке или столбце как и в методе минимального элемента заполняется клетка с наименьшим значением тарифа.

Русский

2013-09-20

30.5 KB

5 чел.

2. Нахождение начального решения для транспортной задачи.

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

Существуют два типа транспортной задачи: открытая и закрытая. Транспортная задача называется открытой если сумма запасов товара на складах отличается от суммы потребностей товаров у магазинов. Транспортная задача называется закрытой , если сумма запасов товара на складах равняется сумме потребностей магазинов. Решение существует только для закрытой транспортной задачи, поэтому если транспортная задача открытая , то ее надо привести к закрытому типу. Для этого в случае , если запас товара на складах превышает потребность магазинов, то вводят фиктивного потребителя, который выбирает весь избыток товара. В случае же, если существует дефицит товара, т.е. потребность магазинов больше, чем запас товаров на складах, то вводят фиктивного поставщика, с фиктивным запасом товара на складе. В обоих случаях в матрице тарифов перевозок C данному складу или магазину проставляется нулевая цена перевозки.

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

Алгоритм метода минимального элемента состоит в следующем. Просматривается вся матрица тарифов перевозок, и из нее выбирается позиция с наименьшим значением тарифа C, затем просматриваются значения наличия запасов на складе A и потребности потребителя B, затем в данную клетку записывается величина D=MIN(A,B). Из запасов соответствующего склада и потребностей магазина вычитается величина D . Если запас товара на складе исчерпан, то эта строка исключается из дальнейшего рассмотрения.

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

Метод Фогеля

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

Метод двойного предпочтения

В начальной своей стадии этот метод похож на метод минимального элемента , но для столбцов. Просматривается первый столбец матрицы тарифов, в нем находится наименьший элемент. Затем проверяется , минимален ли этот элемент в своей строке. Если элемент минимален в своей строке, то по методу  минимального элемента в эту клетку заносится значение D=MIN(A,B), соответствующие запас и потребность уменьшаются на эту величину. Обнулившаяся строка или столбец исключаются из рассмотрения и процесс повторяется, начиная с первого неисключенного столбца. Если найденный минимальный элемент не минимален в своей строке, то происходит переход к следующему столбцу и так до тех пор, пока не будет найден такой элемент. По полученной матрице перевозок вычисляется целевая функция Z. Этот метод требует интенсивных операции обмена с памятью , поэтому более громоздок посравнению с остальными и требует больших вычислительных ресурсов. Как и любая задача линейного программирования, необходимо построить первоначальный опорный план для решения задачи. Одним из методов построения исходного опорного плана является так называемый метод «северо-западного» угла.

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

Метод состоит в следующем. Просматривается матрица тарифов перевозок C, начиная с левого верхнего угла (клетки). В эту клетку записывается величина D=MIN(A,B). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс опять повторяется для левой верхней клеткиоставшейся матрицы и так до тех пор пока весь запас товаров не будет

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


 

А также другие работы, которые могут Вас заинтересовать

24113. Социальная реальность и ее характеристики 16.73 KB
  Социальная реальность и ее характеристики. Социальная реальность это реальность в той или иной степени организованная упорядоченная и структурированная. Социальная реальность это реальность динамическая т. Социальная реальность это реальность стратифицированная.
24114. Общество как система. Сферы общественной жизни 17.51 KB
  Общество как система. Собственно философское значение этого термина таково: общество это обособившаяся от природы часть материального мира представляющая собой исторически развивающуюся форму жизнедеятельности людей. В истории социологии и культурологии чаще используется более узкое понятие общества: общество это определённый этап человеческой истории родовое общество общество капитализма или конкретный социальный организм французское общество общество США. Так древнекитайская мысль традиционно смотрела на общество сквозь призму...
24115. Понятие гражданского общества и государства 15.03 KB
  Понятие гражданского общества и государства. Это определение идеального общества реальность которого определяется соотношением идеала и достигнутого состояния общества которое провозгласило построение гражданского общества своей целью. Это фактически бесконечный процесс совершенствования общества власти политики и человека охватывающий все без исключения стороны жизни. Идея гражданского общества термин введен Аристотелем возникла первоначально как философская концепция.
24116. Проблема развития общества. Формационный, цивилизационный подходы, технологический детерминизм в понимании процесса исторического развития 15.08 KB
  Проблема развития общества. Формационный цивилизационный подходы технологический детерминизм в понимании процесса исторического развития. Проблема развития общества Формационный подход был разработан К. В общем же характерно отрицание единства человеческой истории всеобщих исторических закономерностей Недостатками цивилизационного подхода является то что он не позволяет взглянуть на историю как на целостный закономерный процесс; применяя цивилизационный подход трудно изучать закономерности исторического развития.
24117. Культура как объект философского познания, развитие представлений о культуре в истории мысли 15.03 KB
  Культура как объект философского познания развитие представлений о культуре в истории мысли. Культура совокупность проявлений жизни творчества и достижений народа или группы народов. Культура представляет собой средство и способ развития духовного начала в человеке своей целью имея формирование и удовлетворение его духовных запросов; цивилизация же дает людям средства существования она направлена на удовлетворение их практических нужд. Культура являет собой духовные ценности достижения науки философии искусства образования а...
24118. Психоанализ и проблема человека (З.Фрейд, К.Г. Юнг, Э.Фромм) 17.18 KB
  В психике человека Фрейд сначала выделял две относительно автономные но постоянно взаимодействующие между собой структуры бессознательного оно и сознательного Я а затем добавил к ним сверх Я которое внедряется в Я но без специального анализа не осознается им. По мнению Фрейда причиной невроза является особого рода конфликт между оно Я и сверх Я . Согласно теории Фрейда оно набрало свою изна чальную силу но параллельно с этим развивалось и я . Так как инстинкты или оно служат всего лишь внутренним наполнителем то можно...
24119. Русская философия о человеке и обществе 15.01 KB
  Ориентация на гуманитарное знание на литературу и искусство на проблемы человека является безусловной доминантой в русской философии XX века. в виде религиозной философии человека. близкая к художественному творчеству Ориентация на гуманитарное знание на литературу и искусство на проблемы человека основа рус. во весь рост встали проблемы единства человека с космосом космической природы человека и космического масштаба человеческой деятельности.
24120. Русские философы о судьбах России 15.34 KB
  Россия соединяет внутри себя два мира и поэтому в русской душе всегда боролись два начала: восточное и западное. Бердяев называет русскую историю прерывной и выделяет в ней пять периодов дающих пять разных образов России: Россия киевская; Россия времен татарского ига; Россия московская; Россия петровская; Россия советская. Главное нельзя забывать что Россия является самой молодой цивилизацией и ее истинные возможности в новом свободном государстве скоро раскроются поновому с новыми перспективами.
24121. Русский космизм 13.96 KB
  во весь рост встали проблемы единства человека с космосом космической природы человека и космического масштаба человеческой деятельности. Разум и творчество поднимут человека в космос где со временем изменится его физическая природа он приблизится к высшим организмам.