Приближенные методы решения транспортной задачи.

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

Составление начального плана начинается с клеток, помеченных двумя звездочками. При этом необходимо следить за тем, чтобы при составлении плана общее число базисных клеток удовлетворяло условию: L=n+m-1. Составление плана перевозок методом двойного предпочтения требует минимальных вычислений, однако в общем случае он гарантирует получение только приближенно-оптимального плана. Метод не содержит условий для проверки плана на оптимальность и поиска путей его улучшения. Проверка плана на оптимальность может быть произведена с помощью метода потенциалов.

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

Из полученных разностей, записанных в первом вспомогательном столбце и первой строке, выбирается наибольшая.

Далее вновь определяются разности среди оставшихся строк и столбцов и заносятся в следующие вспомогательные строки и столбцы. Указанные вычисления продолжаются до составления окончательного плана. Метод не позволяет обнаруживать оптимальность полученного плана. Поиск оптимального плана также может быть произведен одним из точных методов.

Метод минимального элемента позволяет построить начальный план транспортной задачи и является вариантом способа северо-западного угла, учитывающим специфику матрицы { cij } Элементы матрицы нумеруют, начиная с минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу { xij }.

Пусть элементом с минимальным порядковым номером оказался элемент xij= min {ai,вj}. Возможны три случая:

а) если min {ai,вj} = ai =Хij то оставшуюся часть i-й строки заполняем нулями;

б) если min {ai,вj} = вi =Хij то оставшуюся часть j–го столбца заполняем нулями;

в) если Хij= aij= вijijijijвax==, то оставшуюся часть строки и столбца заполняем нулями. Далее этот процесс повторяют с незаполненной частью матрицы.

Метод ветвей и границ – один из методов решения различных задач комбинаторного типа. Для решения задачи о коммивояжере может применяться алгоритм Литтла.

Алгоритм простейшей реализации метода ветвей и границ следующий:

1) принимается один из пунктов за начальный пункт ветвления, например, один из пунктов, принадлежащих переходу с наибольшей стоимостью (длиной). Стоимость (длина) ветвления у начального пункта принимается равной нулю;

2) из пункта с минимальной стоимостью ветвления (минимальной текущей оценкой границы ветвления) производятся ветвления (включение переходов), не приводящие к преждевременному зацикливанию (в ветви отсутствуют пункты с одинаковыми номерами кроме последнего n-го шага ветвления по каждой ветви) и рассчитываются стоимости ветвления у вновь включенных в ветви пунктов; каждая ветвь на n-м шаге замыкается на начальный пункт. Стоимость ветвления у вновь включенных пунктов рассчитывается по формуле Zji=Zj,i -1 + ci, где Zji и Zj,i-1– соответственно оценка стоимости j-й ветви на шаге i и i-1;ci – стоимость перехода, включаемого в ветвь на i-м шаге;

3) находится минимальное значение из всех рассчитанных стоимостей дерева ветвления. Если какая-то ветвь имеет число переходов (звеньев) n и минимальное значение стоимости ветвления, то оптимальное решение получено, а иначе необходимо продолжать ветвление (переход на п. 2).

Одна из ветвей с минимальным значением стоимости ветвления у конечного пункта и включающая все n пунктов, дает оптимальное решение.

<< | >>
Источник: Ответы по математическим моделям в транспортных системах. 2016
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме Приближенные методы решения транспортной задачи.:

  1. 39 Транспортная задача в матричной постановке и ее свойства. Математическая модель транспортной задачи. Теорема о существовании решения транспортной задачи.
  2. Решение транспортной задачи методом потенциалов.
  3. 5. Решение системы нелинейных уравнений методом Ньютона (алгоритм, выбор начального приближения, сходимость метода).
  4. 21. Метод последовательных приближений решений ИУ Фредгольма.
  5. Алгоритм решения сбалансированной транспортной задачи
  6. 4. Решение транспортной задачи с помощью ЭВМ:
  7. Транспортная задача: задачи с фиксированными перевозками, с ограничениями на пропускную способность, с фиксированными доплатами, транспортная таблица.
  8. 40. Приклади розв’язування транспортних задач методом потенціалів
  9. Численные методы решения начальной задачи (задачи Коши)
  10. 55. Методы прогонки и пристрелки решения разностных схем при решении краевых задач для обыкновенных д.у.
  11. 45. Классификация численных методов решения задачи Коши. Методы Эйлера, трапеций и К-Э.
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -