В.23 Построение кратчайших путей.

Алгоритм Дейкстры поиска кратчайшего пути

1. Начальной вершине присваиваем метку Оставшимся вершинам присваиваем метку начальную вершину окрашиваем.

2. Для каждой неокрашенной вершинысвязанной с последней вершиной y, дугой пересчитываем ее метку по формуле

В.24 Достоинства метода ДП:

1)Сравнительная простота и однотипность расчетов, что является удобным для алгоритмизации и программирования задач при их решении на ЭВМ;

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

3)Отсутствие специальных ограничений на природу, характер и свойства функций. Они, например, могут не являться линейными, выпуклыми, непрерывными, дифференцируемыми, и могут быть заданы как таблично, так и в виде формул (аналитич).

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

В общем виде задачи оптимального распределения ресурсов могут быть описаны следующим образом. Имеется некоторое количество ресурсов (материальные, трудовые, финансовые), которые необходимо распределить между различными объектами их использования, чтобы получить максимальную суммарную эффективность от выбранного способа распределения.Показателем эффективности может служить, например, прибыль, себестоимость, суммарные затраты и т.д.

Переход к вопросу 21!

В25. Метод главного критерия.

Заключается в том, что критерий качества связывается с одним из показателей, выбранным в роли основного (главного). На остальные показатели накладываются ограничения. В этом случае по главному показателю реализуется критерий оптимальности, по остальным - пригодности. Например, если имеется вектор полезного эффекта в виде

W<k>= <W1,W2,...,Wk>,

где W i(i=1,2...k) - компоненты вектора, например, для оборудования: производительность, экологичность, надежность, себестоимость и т.д., то метод главной компоненты заключается в произвольном выборе одного из компонентов в качестве главного, по которому производится оптимизация и выбирается решение. При этом остальные компоненты переводятся в разряд ограничений.

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

В26. Метод последовательных уступок.

В задачах многокритериальной оптимизации при переходе от одного варианта к другому, как правило, улучшаются значения одних критериев, но ухудшаются значения других. Компромисс разрешается введением тех или иных дополнительных ограничений или субъективных предположений. Здесь нельзя говорить об объективном единственном решении задачи; выбор наилучшего решения в значительной степени субъективен. Так как область допустимых решений очередной задачи представляет собой множество оптимальных решений предшествующих задач, то она быстро сужается до одной точки, лишая свободы выбора при максимизации последующих критериев. Следует помнить, что решение задачи оптимизации существенно зависит от результатов ранжирования критериев качества. В известной мере избавиться от этого недостатка позволяет применение метода последовательных уступок, процедура которого включает:

- расположение частных критериев в порядке их относительной важности;

- максимизацию первого, наиболее важного критерия;

- назначение величины допустимого снижения (уступки) значения этого критерия;

- максимизацию второго по важности частного критерия при условии, что значение первого критерия не должно отличаться от максимального более, чем на величину уступки;

- назначение величины уступки по второму критерию;

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

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

Приведенный метод широко и эффективно используется при решении задач управления в технических системах разной направленности.