Решение транспортной задачи 3 — страница 3

  • Просмотров 349
  • Скачиваний 5
  • Размер файла 108
    Кб

Ai, i = 1,...,m (3) и n линейных ограничениях пo потреблению: X1,j + ... + Xi,j + ... + Xm,j = Bj, j = 1,...,n, (4) а также при очевидном условии неотрицательности управляемых переменных: , i = 1,...,m и j = 1,...,n. (5) 2.2 Выбор метод составления опорного плана Решение транспортной задачи, после того, когда было установлено, что она открытая либо устранен путем коррекции несбалансированность ее, начинается с составления опорного плана, то есть отыскания начального

базисного решения. Существует большой выбор методов составления опорного плана, рассмотрим некоторые из них. Метод минимального элемента. Алгоритм метода минимального элемента состоит в следующем. Просматривается вся матрица тарифов перевозок, и из нее выбирается позиция с наименьшим значением тарифа C, затем просматриваются значения наличия запасов на складе A и потребности у потребителя B, затем в данную клетку

записывается величина D=MIN(A,B). Из запасов соответствующего склада и потребностей магазина вычитается величина D. Если запас товара на складе исчерпан, то эта строка исключается из дальнейшего рассмотрения. Если потребность магазина в товаре удовлетворена полностью, то этот столбец исключается из дальнейшего рассмотрения. Может быть случай, когда одновременно исключаются и строка и столбец, этот случай называется вырожденным.

В дальнейшем весь процесс повторяется до тех пор, пока не будет исчерпан весь запас товаров на складах и не будет удовлетворена потребность всех магазинов Метод Фогеля. Просматриваются все строки и столбцы матрицы тарифов, вычисляется разность между двумя наименьшими элементами в строке или в столбце. Затем из всех этих разностей выбирается строка или столбец с максимальной разность. В выбранной строке или столбце, как и в

методе минимального элемента, заполняется клетка с наименьшим значением тарифа. Затем обнулявшаяся строка или столбец исключаются из рассмотрения и весь процесс повторяется до полного исчерпания запаса товаров на складах. Метод двойного предпочтения. В начальной своей стадии этот метод похож на метод минимального элемента, но для столбцов. Просматривается первый столбец матрицы тарифов, в нем находится наименьший элемент.

Затем проверяется, минимален ли этот элемент в своей строке. Если элемент минимален в своей строке, то по методу минимального элемента в эту клетку заносится значение D=MIN(A,B), соответствующие запас и потребность уменьшаются на эту величину. Обнулившаяся строка или столбец исключаются из рассмотрения и процесс повторяется, начиная с первого не исключенного столбца. Если найденный минимальный элемент не минимален в своей строке,