Особенности метода неопределенных множителей Лагранжа, градиентного метода и метода перебора и динамического программирования. Конструирование алгоритма решения задачи. Структурная схема алгоритма сценария диалога и описание его программной реализации.
Краткое сожержание материала:

Размещено на

Содержание

• Введение
• 1. Постановка задачи
• 1.1 Качественное описание исследуемой операции
• 1.2 Числовые данные
• 1.2 Концептуальная модель операции
• 1.3 Математическая постановка задачи
• 2. Алгоритмизация решения задачи
• 2.1 Анализ методов решения задачи
• 2.2 Выбор и описание метода
• 2.3 Конструирование алгоритма решения задачи
• 3.4 Проектирование сценария диалога
• 3.5 Описание структур данных
• 3.6 Структурная схема алгоритма сценария диалога и описание его программной реализации
• 3.7 Структурная схема функционального алгоритма решения задачи
• 4. Численные эксперименты
• 4.1 Ручная реализация алгоритма решения задачи
• 3.8 Машинные эксперименты с разработанными данными
• 3.9 Сравнение результатов ручного и машинного расчетов
• Заключение
• Список используемой литературы
• Приложение а - листинг программы

Введение

Одной из задач принятия решений является задача оптимального резервирования элементов сложной системы.

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

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

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

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

Целью курсовой работы является количественное исследование, данной в задании ситуации сложной системы.

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

1. Постановка задачи

1.1 Качественное описание исследуемой операции

На предприятии необходимо выполнить разгрузочно-погрузочные работы на M складах предприятия. Время выполнения работы на каждом складе зависит от количества грузчиков - где n количество грузчиков, занятых на j-м складе при i-м варианте распределения грузчиков. На предприятии имеются грузчики в количестве N человек. Требуется сформировать бригады на каждый склад таким образом, чтобы выполнить все работы за минимальное время.

1.2 Числовые данные

M=5, N =21

Таблица 1. - Время выполнения работы

Количество грузчиков	Склад
	№1	№2	№3	№4	№5
2	10	12	14	8	18
4	6	8	9	5	12
5	5	6	6	3	10
6	3	4	4	2	8
8	2	3	2	1	4

1.2 Концептуальная модель операции

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

алгоритм программная реализация сценарий

В результате проектирования информационной системы выделено множество программных модулей R={R₁,.,R_i,.,R_m}. Эти модули являются информационно-независимыми друг от друга и могут параллельно выполняться на многопроцессорной вычислительной системе, которая содержит D_o процессоров. Для каждого из программных модулей определены варианты их реализации, которые формально задаются переменной d_ij, определяющей количество процессоров, которые могут использоваться для выполнения R_i-го программного модуля в j-м варианте. Необходимо распределить имеющиеся процессоры по программным модулям, чтобы их выполнение было закончено в кратчайшее время, т.е. следует уменьшить отрезок времени, начинающийся с момента начала выполнения работ и заканчивающийся в момент выполнения последнего модуля.

- Количество грузчиков n, занятых на j-м складе при i-м варианте распределения грузчиков соответствует количеству процессоров d_ij, которые могут использоваться для выполнения программного модуля в j-м варианте;

- Процессор D_{i (}по условию задачи N) ставится в соответствие складу М_j;

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

1.3 Математическая постановка задачи

Рассмотрим математическую постановку минимаксной задачи оптимального распределения программных модулей между процессорами. Для этого введем переменные:

В поставленной задаче необходимо произвести разрузочно-погрузочные работы на N-складах, время выполнения всех работ - t_{ij (}N), где N - количество работников.

В ходе решения задача сводится к формированию численности бригад, которые произведут все работы за минимальное количество времени. Решение производится в соответствии с алгоритмом прямой прогонки. Уравнение Беллмана будет выглядеть следующим образом:

Решение уравнения Беллмана даст нам оптимальное распределение численности работников по бригадам и минимальным затратам на выполнение требуемых работ.

2. Алгоритмизация решения задачи

2.1 Анализ методов решения задачи

Данный метод решения задачи решается в m этапов, где m - количество программных модулей. Затем задача решается в соответствии с алгоритмом обратной прогонки.

Идея динамического программирования, основанная на алгоритме обратной прогонки, состоит в том, что в качестве этапа, для которого на первом шаге находится локальное оптимальное управление, рассматривается последний этап принятия решений. Решения, принятые на этом этапе не оказывают влияния на последующий этап, так как этот этап является последним. Однако при таком подходе является неизвестным состояние, в котором будет находиться система перед началом выполнения последнего этапа. Поэтому локальное оптимальное управление необходимо найти для всех возможных состояний, в которых может находиться система, перед выполнением последнего этапа. После этого осуществляется переход к оптимизации управления на предпоследнем этапе. Оптимальное управление на этом этапе находится с учётом того, что уже известно оптимальное управление на последнем этапе. Таким образом, для каждого состояния предпоследнего этапа находится локальное оптимальное управление. Такая процедура повторяется для всех последующих этапов: n-2, n-3, …, i, …, 2, вплоть до первого этапа, то есть, оптимальное решение для первого этапа определяется с учётом ранее найденных оптимальных решений для последующих этапов.

2.2 Выбор и описание метода

Современная трактовка метода динамического программирования позволяет находить оптимальное решение не только для аддитивных критериев, но и для минимаксных.

В данном случае для проектирования информационной системы выделено множество программных...