Geum.ru


Решение транспортных задач венгерским методом

Дипломная работа - Компьютеры, программирование

Другие дипломы по предмету Компьютеры, программирование



Предварительные потенциалы выбирают так, чтобы их разность для любой пары пунктов Аi и Вj, связанных основной коммуникацией, были равна cij. Если окажется, что разность предварительных потенциалов для всех других коммуникаций не превосходит cij, то данный план перевозок - оптимальное решение задачи. В противном случае указывают способ улучшения опорного плана Т-задачи.

  • Опорный план можно найти следующими методами:
  • метод северо-западного угла;
  • метод минимальной стоимости;
  • метод штрафов.
  • Рассмотрим подробнее каждый из этих методов.
  • 1.2.1 Метод северо-западного угла
  • Строится нулевая матрица размером n*m. Начиная с северо-западного угла в естественном порядке осуществляется заполнение матрицы. Заполнение осуществляется по следующему правилу: для каждого элемента выбирается минимальное число из соответствующих ему значений вектора производства и потребления; это минимальное число вычитается из соответствующих данному элементу значений векторов производства и потребления. Так как при корректировке один из элементов, либо а, либо b, становится равным нулю, то соответствующая строка или столбец исключаются в дальнейшем из рассмотрения. Процесс заполнения продолжается до тех пор, пока все элементы векторов производства и потребления не станут равными нулю. Проверяется вырожденность полученного плана.
  • 1.2.2 Метод минимальной стоимости
  • Производится индексирование матрицы стоимости в порядке возрастания. Согласно индексам, полученным на 1-ом этапе роизводится заполнение элементов опорного плана. При этом элементы и правила коррекций вычисляются также как и метод северо-западного угла.
  • Замечания:
  • при индексации отсутствует правило в присвоении индекса к матрице стоимости;
  • данный метод лучше северо-западного угла.
  • 1.2.3 Метод штрафов
  • Штрафы для строки или столбца представлят положительную разницу между минимальном элементом строки(столбца) и следующим за ним по величине минимальным элементом строки или столбца. Расчитываются штрафы для всех строк и столбцов матрицы. Заполнение опорного плана начинается с минимального элемента строки или столбца с максимальным штрафом. Выбор элементов плана Х и коррекция векторов потребления и постановок осуществляется как рассмотрено выше.
  • Строка или столбец матрицы С, которым соответствует нулевое значение потребности или поставки при дальнейшем вычислении не участвуют в формировании штрафов. Процесс продолжается до тех пор, пока не обнулятся все вектора.
  • Замечание:
  • отсутствует правило выбора альтернативы при равенстве штрафов
  • метод дает решение близкое к оптимуму.

    • Нахождение оптимального плана происходит по следующему алгоритму:

    . Расчитываются потенциалы пунктов производства и потребления, решая последовательность уравнений

    Сij=Ui-Vj;=1;

    . Выполняется пересчет матрицы С по правилу:

    С0=C-(Ui-Vj)

    . Проверка на оптимальность. Если все компоненты матрицы С0 не отрицательны, то мы достигли оптимального решения. В противном случае план можно улучшить.

    . Среди элементов матрицы С0 отыскивается минимальный отрицательный, который обозначается d. Соответствующая ему коммуникация будет вводится в базис. Данную коммуникацию в плане Х обозначают 0+.

    . Для определения коммуникации, выводимой из базиса необходимо построить цепочку. Цепочка строится следующим образом. Начиная со строк матрицы Х вычеркиваются те из них, в которых один не нулевой элемент. Подобную операцию повторяют затем по столбцам, следом по строкам и т.д.

    В результате проведенной процедуры не вычеркнутыми оказываются элементы, которые состовляют цепочку. Цепочка замкнута, содержит четное число элементов и строится, начиная от 0+, безразлично в каком направлении, по ходу ладьи в шахматах.

    При этом элементы, стоящие на нечетных местах помечаются минусом, а на четных - плюсом.

    Среди элементов, отмеченных знаком минус выбирается минимальный элемент Q.=min{Q-}, который прибавляется или вычитается к элементам плана Х, согласно индексации. При этом коммуникация, значение которой равной нулю оказывается выведенной из базиса.

    Появление в результате вычитания более одного нуля черевато потерей опорности плана. Чтобы этого не произошло, все нули, кроме одного помечают символом 0 с эпсилом (все входящие только в цепочку) и соответствующие коммуникации считаются условно существующими.

    . Коррекция значения целевой функции:= L - |d|*Q

    . Подсчитывают матрицу С:

    а) Отмечают в матрице нули, соответствующие базисным элементам плана Х.

    б) Вычеркивается строка, соответствующая введенной коммуникации. Если в процесс вычеркивания строки оказались задетыми существенные или ранее отмеченные нули мытрицы С, то вычеркивают столбцы, на которых они находятся. Если в процесс вычеркивания столбца оказались задетыми ранее отмеченные нули матрицы С, то вычеркивают строки, на которых они находятся.

    в) Процесс вычеркивания продолжается до тех пор, пока есть что вычеркивать. После этого к элементам вычеркнутых строк прибавляют + |d|, а из вычеркнутых столбцов вычитают модуль -|d|. Переходим в пункт 3.

    2 СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ

    В пунктах Аi имеются запасы некоего продукта, который необходимо перевезти потребителям Вj.

    Требуется отыскать такой план перевозок, при котором весь продукт из пунктов Аi будет вывезен, потребности потребителей полностью удовлетворены и суммарные транспортные затраты буду