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

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


 

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

60112. Виховний захід «Миколай святий іде, подарунки всім несе!» 47 KB
  Увага Дітвора У нас чудова новина До казки просимо усіх Де вас чекають жарти й сміх Сьогодні в нас казкове свято Гостей запрошено багато Уучень. Летить сніжок Легесенький кружляє Безшумно осідає він на все...
60114. Виховний захід до річниці визволення Києва та України від німецько-фашистських загарбників 55 KB
  Мета: 1. Показати героїзм визволителів Києва та України. на території України; окупацію України; голокост; битву за Дніпро та визволення Києва від окупантів. Обладнання: проектор на сцені надпис Київ 1941-1943 фотографії Києва часів війни та подій повязаних із визволенням столиці.
60115. НАША ДРУЖНАЯ СЕМЬЯ 58.5 KB
  Время вроде замкнутого круга: Год мелькнул как месяц день как час. Я рада что все вы откликнулись и решили принять участие в конкурсе Мама папа я - дружная семья. Рада приветствовать вас на нашем семейном развлечении Наша дружная семья.
60116. Виховний захід: «Моя Батьківщина – Україна» 59 KB
  Мова кожного народу неповторна і своя це рядки з вірша. Українська мова Давня й молода. Рідна мова як її не знати Як же не любити нам її. Рідна мова в рідній школі Що бринить нам чарівніш Що нам ближче і миліш І дорожче в час недолі Рідна мова...
60117. Позакласний захід з народознавства «Обжинки» 33 KB
  Учні: Ой обжинки господарю обжинки Позбирали колосочки із нивки Ой весело господарю весело Що ми тобі віночок несемо А ще буде веселіш Коли буде цей вінок на голові Коли буде коровай на столі Діти виконують пісню з рухами...
60118. Здоров’я – це скарб. Усний журнал 85 KB
  Мета: вчити здорового способу життя свідома ставитися до свого здоровя; розвивати бажання вести активний спосіб життя берегти зміцнювати здоровя; виховувати хороші звички бажання перетворити набуті знання у внутрішню потребу.
60119. Виховний захід: З усмішкою про наше шкільне життя 47 KB
  Я книжки закинув та й не вчився Телевізор цілий день дивився Ось стою зітхаю нічого не знаю Двійку заробив 1 учень Оце лихо Іване А що ж у тебе вчителька таке спитала 2 учень Таблицю множення скільки буде...
60120. Внеклассная работа. «Выпускной бал в 4 классе» 68 KB
  Цель: подвести итоги обучения за 4 года в начальной школе мотивировать учащихся на дальнейшее успешное обучение. Рады мама с бабушкой папа мой доволен И самой мне нравится в нашей милой школе.