Анализ и краткое описание возможных методов решения - Исследование методов описания, анализа и моделирования технологических процессов в производстве ЭВМ

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

Считаем, что множество проектных решений задано графом:

С пронумерованными вершинами от 1 до n. Где E={e1,e2,..eN} - множество графа, которому поставлено в соответствие множество узловых реализаций, т. е. частных, промежуточных технических решений;

V={v1,v2,...,vM} - множество возможных переходов (связей) между узловыми реализациями.

При этом каждой дуге графа (еI, eJ) приписано значение интегрированного критерия качества, т. е. длина дуги а(eI, eJ)

Процесс проектирования технических решений является ориентированным процессом от его начала к завершению. Эта особенность отражена в порядковой функции MMD в виде множества дуг графа без контуров. Свойство упорядоченности процесса проектирования позволяет более рациональную процедуру поиска оптимального технического решения на основе MMD с меньшими затратами.

Модифицированный метод последовательных приближений предполагает :

    1. разбиение сетевой модели ТП на уровни (слои); 2. решение системы линейных уравнений обычным методом последовательных приближений с учетом модели:

Г-1 eI - множество вершин графа G, предшествующих вершине eI.

При решении задачи графическим способом на заданном графе определяются вершины, которые не имеют предков и которые образуют первый слой. Затем удаляются вершины первого слоя с инцидентными дугами и ребрами и определяются вершины, которые не имеют предков и которые образуют второй слой. Операция п.2 повторяется многократно до полного расслоения графа.

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

Модифицированный метод решения задачи сводится к решению системы:

Где k - номер приближения;

R - число слоев сети;

N - номер конечной вершины сети.

NG - множество вершин, расположенных в g-том слое. Очевидно, что для нахождения оптимального решения достаточно (r-2) итерации.

Похожие статьи




Анализ и краткое описание возможных методов решения - Исследование методов описания, анализа и моделирования технологических процессов в производстве ЭВМ

Предыдущая | Следующая