Динамическое программирование (ДП). Задача о поиске самого короткого (самого быстрого) маршрута

Метод потенциалов. Основные этапы: 1) Предварительный шаг. В предварительном шаге составляем опорный план любым из известных методов (см. выше). 2) Вычисление потенциалов. Вычисление потенциалов производится на основе соотношения для заполненных клеток , если первоначальный опорный план является вырожденным, то есть число заполненных клеток меньше чем , то необходимо проставить столько значений нулей, сколько их не хватает до . Эти нули проставляют таким образом, чтобы они не составляли цикл с остальными заполненными клетками. Цикл- это последовательность клеток в которых две соседние клетки лежат в одном столбце или одной строке. В опорном плане нельзя составить цикл из заполненных клеток, а для каждой свободной клетки можно составить цикл и при этом только один. Поскольку число переменных и равно , а число заполненных клеток равно , то одной из переменной мы задаемся, например: , а остальные переменные вычисляем на основе выше приведенного соотношения . 3) Проверка плана на потенциальность. Проверка плана на потенциальность производится по следующим соотношениям для незаполненных клеток. Если для всех незаполненных клеток условие выполняется, то план является потенциальным. Следовательно, оптимальное решение найдено. Иначе переходим к повторяющемуся шагу. В повторяющемуся шагу производится : а) исправление первоначального плана перевозок; б) исправление потенциалов; в) проверка плана на потенциальность. Для исправления первоначального плана выбирается клетка с наибольшим невыполнением условия на потенциальность, то есть . С этой клеткой составляем цикл и обходим его по часовой стрелке. В исходной клетке ставим “+” в следующей “-“ и т.д. Рассматриваем клетки со знаком “-“ выбираем из них минимальную поставку и исправляем план таким образом, что для клеток со знаком “+” , а для клеток со знаком “-“ . При исправлении потенциалов необходимо исправить один из потенциалов в исходной клетке. Причем исправляется тот из потенциалов, который приведет к наименьшему исправлению остальных потенциалов. В общем случае можно пересчитать все потенциалы заново. После этого выполняется условие потенциальности.

Динамическое программирование (ДП)

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

1) выбор кратчайшего пути;

2) распределение ресурсов между однопрофильными предприятиями с целью максимизации прибыли;

3) разработка сетевого плана графика;

4) завоз материалов и выполнение строительства объекта с целью минимизации срока строительства и т.д..

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

Динамическое программирование (ДП). Задача о складе

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

34.Требуется распределить A единиц ресурсов между всеми предприятиями так, чтобы выпуск продукции был максимальным. Обозначим через Xk количество ресурсов, которое нужно выделить K - му предприятию, тогда математическая модель задачи запишется так:
φ1(X1)+φ2(X2)+…+φn(Xn)→max
при ограничениях
X1+X2+…+Xn=A
X1≥0, X2≥0,…,Xn≥0.
Если φ1, … φn – заданы таблично, то задача решается методами динамического программирования.
Рассмотрим оптимальное распределение ресурсов с помощью метода динамического программирования.
При решении задачи о распределении ресурсов введем функцию Беллмана fk(X) – максимальное количество продукции, которое могут выпустить K предприятий, при этом αk(X) – количество ресурса, получаемое K - ым предприятием при оптимальном распределении ресурса между первыми предприятиями.
Предположим, что fk(X) известно, тогда вычислим fk+1 (X).
Пусть К+1 – ое предприятие получает t единиц (0 ≤ t ≤ X) ресурса, тогда оно выпускает φk+1 (t) единиц продукции. На долю же первых K предприятий останется X – t единиц ресурса.
В силу принципа оптимальности: чтобы получить больше продукции, необходимо распределить оптимально оставшиеся (X – t) единиц ресурса между K предприятиями. Тогда общий выпуск продукции будет равен
φk+1(t)+fk(X – t).
Но, чтобы этот общий выпуск продукции был максимальным, необходимо t подобрать так, чтобы эта сумма достигала наибольшего значения, т.е. fk+1 (X). Функциональное уравнение Беллмана:

Зная f1(X), находим f2(X), затем f3(X) и т.д

Динамическое программирование (ДП). Задача о поиске самого короткого (самого быстрого) маршрута

Дата добавления: 2018-02-15; просмотров: 502; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!