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

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


 

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

57955. Антарктида 80 KB
  Мета навчальна: закріпити та узагальнити знання і вміння учнів з теми: «Антарктида»; поглибити їх знання за допомогою цікавих фактів про вивчений об’єкт, вдосконалювати вміння та навички роботи з картою, формувати нестандартне мислення...
57956. Антарктида і Антарктика. Загальні відомості. Відкриття та сучасні наукові дослідження 248 KB
  Сформувати поняття «Антарктика»; сприяти формуванню в учнів знань про географічне положення; поглибити і систематизувати знання про відкриття та сучасні дослідження Антарктиди в рамках міжнародного співробітництва; продовжити формування навичок встановлювати закономірності поширення природних умов
57957. Антарктида. Своєрідність географічного положення. Відкриття материка. Льодовиковий покрив 33 KB
  Мета уроку: дати поняття Антарктика и Антарктида льодовий материк планети; вивчити загальні відомості про материк: своєрідність ГП материка його розміри; розглянути відкриття Антарктиди та сучасні наукові дослідження материка...
57958. встралия – самый маленький материк Земли 60.5 KB
  Перед началом соревнования вам ребята надо потренироваться повторить изученный материал о природе Австралии. На протяжении трех уроков вы составляли вопросы об особенностях природы Австралии теперь у вас есть возможность задать их своим одноклассникам и выслушать ответы. Какой остров расположен к северу от Австралии Правила игры: В течение изучения материка ученики составляют вопросы по параграфам. По плану ФГП ученики сравнивают физикогеографическое положение Австралии с ФГП...
57959. ГЕОГРАФІЧНОГО ПОЛОЖЕННЯ. ІСТОРІЯ ВІДКРИТТЯ І ДОСЛІДЖЕННЯ. ГЕОЛОГІЧНА БУДОВА. ФОРМИ РЕЛЬЄФУ ТА КОРИСНІ КОПАЛИНИ АВСТРАЛІЇ 108 KB
  Мета: сформувати в учнів загальне уявлення про своєрідність та особливості природи Австралії; продовжити формування навичок учнів складати характеристику географічного положення материка за планом відшукувати закономірності розташування форм рельєфу та корисних копалин...
57960. Передня Азія в давнину 54.5 KB
  Мета: повторити, закріпити, узагальнити знання учнів з історії Передньої Азії: географічне положення, утворення, розквіт та загибель імперій, культуру та релігійні уявлення. Продовжувати формування навичок узагальнювати, порівнювати, аналізувати історичний матеріал.
57961. Основы объектно-ориентированного программирования. Первое знакомство со средой Visual Studio. Создание консольного приложения с помощью языка Visual Basic. Net 367 KB
  Цель: Сформировать у учащихся представление о среде программирования Visul Studio; Освоить основные приемы создания и запуска на выполнение консольного приложения его редактирования и сохранения; Получить практические навыки работы в среде программирования...
57962. Білорусь 50 KB
  Мета уроку: формування в учнів географічного образу Білорусі знань про її територію населення ресурси І можливості їх використання; визначити актуальні проблеми її соціально-економічного розвитку; розвивати вміння робити відповідні висновки...
57963. Діяльність людини і сучасний стан біосфери 68 KB
  Мета: сформувати поняття про людину як частинку природи її вплив на стан біосфери шляхи подолання екологічних проблем; розвивати вміння висловлювати свої думки аргументувати їх; виховувати любов до природи потребу в дбайливому ставленні до неї...