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

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


 

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

58158. Государство и право Российской Федерации (90–е годы – по настоящее время) 55.5 KB
  Развитие права Российской Федерации. Если в условиях тоталитарных режимов на первое место ставилось государство то в Конституции РФ на первое место ставится личность и ее политические и экономические права.
58159. Создание web-страниц. Работа с фоном страницы. Формат изображения 68.5 KB
  И осторожно BR Там где вожможно BR Тёмного облака BR Край отогнуть BR font font color= 008000 P lign=right Стёртые лица BR Забытые профили BR И многоточий упрямая нить. BR font DDRESS Ирина Леонардова DDRESS body html Теперь поговорим...
58160. Соседи восточных славян 33.5 KB
  Эти народы жили в трудных природно-климатических условиях. Поэтому вместе с земледелием они занимались скотоводством, собирательством, охотой, были знакомы с железом. Жили они в полуземлянках.
58161. СОСТАВ, СТРУКТУРА И ФУНКЦИИ НАЛОГОВЫХ ОРГАНОВ 117 KB
  В ходе реформирования органов исполнительной власти определена новая структура федеральных органов исполнительной власти в соответствии с которой в составе Министерства финансов РФ выделена Федеральная налоговая служба...
58162. Основные положения теории химического строения органических соединений А.М.Бутлерова 1.62 MB
  Химическое строение вещества как порядок соединения атомов в молекулах. Взаимное влияние атомов и атомных групп в молекуле. При этом строго соблюдается четырехвалентность атомов углерода и одновалентность водородных атомов. Свойства веществ зависят не только от качественного и количественного состава но и от порядка соединения атомов в молекуле явление изомерии.
58163. Уровни организации живой природы 81 KB
  Ученые выделяют несколько уровней организации живой природы: молекулярный клеточный организменный популяционно-видовой экосистемный и биосферный. На молекулярном уровне изучаются молекулы которые находятся в клетке их строение и функции.
58164. Утверждение Новой Культуры 83 KB
  Появляется интерес к античной культуре происходит как бы её возрождение так и появился термин. Термин Возрождение встречается уже у итальянских гуманистов например у Джорджо Вазари. В настоящее время термин Возрождение превратился в метафору культурного расцвета: например Каролингское Возрождение IX века. Возрождение возникло в Италии где первые его признаки были заметны ещё в XIII и XIV веках в деятельности семейства Пизано Джотто Орканья и др.
58165. Збройні сили Київської Русі 138.5 KB
  Княжа дружина була зорганізована на зразок варязьких дружин. Хоча скандинавці втратили значення в Україні і мусили уступити з війська, але їх військову організацію, що визначалася дуже високими прикметами, князі зберегли та тільки її перетворили, відповідно до розвитку і потреб держави.
58166. Формы государства 51.5 KB
  Формы государства, как совокупность его внешних признаков представляет организацию государственной власти в стране, включая 3 взаимосвязанных элемента...