Задать вопрос юристу

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

Метод двойного предпочтения. Вначале анализируются значения с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. Феномен эффективности советского государственного управления в Великой Отечественной войне
  2. Тенденции, роль и противоречия послевоенного государственного управления
  3. 20. Методы математического программирования.
  4. 40.Принятие решения по количеству складов в системе распределения.
  5. 1.4. Методы финансирования инвестиций
  6. Лекция 4. Роль ЦБ в регулировании валютных отношений
  7. Партии в XIX веке как элемент политической культуры США
  8. 34. Возникновение и развитие аэродинамики как науки
  9. Приближенные методы решения транспортной задачи.
  10. 40. Модели теории упругости
  11. Порядок отнесения товарных бирж к перечню товарных бирж, на которые распространяется действие постановления Совета Министров-Правительства Российской Федерации от 11 мая 1993 года N 452 (утв. решением Комиссии по товарным биржам при ГКАП РФ 15 июля 1993 г., протокол N 17) . Товарная биржа как атрибут рыночной экономики
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -