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

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


 

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

68399. Измерение технологических параметров 396 KB
  Первичный преобразователь датчик сенсор наиболее многочисленная группа преобразователей предназначенных для измерения состояния окружающей среды и диагностики. Для оценки количественного значения температуры используют температурные шкалы имеющие начало отсчета ноль...
68400. Типы интенсификации теплопередачи 97.5 KB
  Снижение термического сопротивления всегда ведет к увеличению, однако этот путь не всегда возможен т.к. толщина стенки и материал из которого она изготовлена часто диктуется соображениями стойкости. Однако не следует забывать о этом способе интенсификации при эксплуатации...
68402. Элементарные измерительные преобразователи 153 KB
  Однако элементарные преобразователи и измерительные приборы обычно не обеспечивают требуемых метрологических характеристик преобразования: малой погрешности стабильности линейности чувствительности а также достаточной мощности выходного сигнала.
68403. Промежуточные (вторичные, нормирующие) преобразователи 145.5 KB
  Метод уравновешивающего преобразования характеризуется тем что в приборах используется две цепи преобразования: прямая и обратная роли которых резко отличаются. Цепь прямого преобразования служит для обнаружения степени неравновесия.
68404. Автоматические регуляторы 562 KB
  Регулирующее воздействие формируется в зависимости от заданного значения величины регулируемого параметра Регулирующее воздействие формируется в результате автоматического поиска т. Недостаток: сложность принципиальной электрической схемы регулирования что предъявляет повышенные требования...
68405. Исполнительные механизмы и регулирующие органы 561.5 KB
  Исполнительный механизм преобразует выходной сигнал регулятора в перемещение регулирующего органа. ИМ должен сохранять равенство между перемещением выходного элемента и рабочим ходом штока затвора регулирующего органа.
68406. Конвективный теплообмен в однофазной среде 67.5 KB
  Конвективным теплообменом называется процесс передачи теплоты при движении жидкости или газа. Под конвекцией понимают процесс переноса теплоты при перемещении макрочастиц в жидкости или газе в пространстве из области одной температуры в область с другой температурой.