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). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс опять повторяется для левой верхней клеткиоставшейся матрицы и так до тех пор пока весь запас товаров не будет

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


 

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

66988. ЗАОЧНОЕ ПУТЕШЕСТВИЕ ПО ДНЕПРУ 56 KB
  Днепр - украинское название Дніпро, древнегреческое название Борисфен. Вторая после Волги река восточной Европы. Берет начало на Валдайской возвышенности и протекает по территории России, Беларуси, Украины. Делится натри часті, верхнее течение - от истока до Киева, среднее течение от Киева до Запорожья, и нижчеє течение - от Запорожья до устья.
66989. Образ Добрыни Никитича (былинский сказ). Иллюстрация к былине (портрет богатыря) 28 KB
  Цели: создать у детей целостный литературно-художественный образ былинного героя; показать его в творчестве художников; представить самим и воплотить представленное в рисунке; сформировать понятие о былине виде устного народного творчества; развивать интеллект логическое мышление учащихся...
66990. Морально-етична година 64.5 KB
  Обладнання: на дошці записана тема заняття прихована паперовою смужкою; оформлені висловлювання про добро: Раз добром нагріте серце вік не охолоне.Шевченко Добра людина із доброї скарбниці серця добре виносить а лиха із лихої виносить лихе. Життя таке коротке: поспішайте робити добро.
66991. Ми прийшли у цей світ, щоб творити добро 101.5 KB
  Допомогти учням зрозуміти зміст людського життя визначити своє місце в ньому навчити відрізняти добро від зла; сприяти вихованню в них людяності чесності працьовитості відповідальності любові до людей до рідної землі. На фоні музики читець декламує духовні заповіді Матері Терези Життя це можливість...
66992. «НЕМАЄ ВИЩОЇ СВЯТИНІ НІЖ ЧИСТЕ СЯЙВО ДОБРОТИ» 61.5 KB
  Людяність, милосердя, добро. Такі знайомі нам ці слова. Все частіше ми говоримо про них, а чи кожна людина відкрита для добра? Чомусь сьогдні наше суспільство заражене вірусом егоїзму, зла і жорстокості. Зачерствілі людські серця заросли ряскою байдужості до чужого горя, чужої біди, яких у нашому житті дуже багато.
66994. Про доброту і милосердя 310 KB
  Хто ж винен у ситуації до якої потрапив вовк Чи викликає у вас симпатію герой байки Чому Як можна допомогти вовкові 2. Як це не кайся Яку частину прислівя можна сказати саме вовкові ІІІ. Що можна віднести до милосердя А що ви вважаєте немилосердним ІІІ група Будь привітним.
66995. Доля, що дарує Надію 33.5 KB
  Одного разу Ніна Михайлівна їхала в поїзді і раптом почула по радіо повідомлення що пасажирці цього поїзду терміново потрібна донорська кров. Був випадок коли після забору крові прийшов вагон з мукою і Ніна Михайлівна пішла його розвантажувати. Ніна Михайлівна дістає із шухляди скриньку з паперами.
66996. Урок обучения грамоте 38 KB
  Формировать умение выделять эти звуки в речи. Ой что за звуки мы слышим сейчас Звучат голоса курицы и петуха гусей. Ребята что за интересные звуки сейчас прозвучали в нашем классе Какую песенку пропел петух Какие знакомые нам звуки вы услышали в пении петуха Запишите какими буквами они обозначаются.