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

Главная

Программирование, компьютеры и кибернетика
Ручная реализация алгоритма решения задачи

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


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

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

алгоритм программная реализация сценарий
В результате проектирования информационной системы выделено множество программных модулей R={R 1 ,.,R i ,.,R m }. Эти модули являются информационно-независимыми друг от друга и могут параллельно выполняться на многопроцессорной вычислительной системе, которая содержит D o процессоров. Для каждого из программных модулей определены варианты их реализации, которые формально задаются переменной d ij , определяющей количество процессоров, которые могут использоваться для выполнения R i -го программного модуля в j-м варианте. Необходимо распределить имеющиеся процессоры по программным модулям, чтобы их выполнение было закончено в кратчайшее время, т.е. следует уменьшить отрезок времени, начинающийся с момента начала выполнения работ и заканчивающийся в момент выполнения последнего модуля.
- Количество грузчиков n, занятых на j-м складе при i-м варианте распределения грузчиков соответствует количеству процессоров d ij , которые могут использоваться для выполнения программного модуля в j-м варианте;
- Процессор D i ( по условию задачи N) ставится в соответствие складу М j ;
Наличие этих соответствий и позволяет свести на концептуальном уровне решаемую задачу к минимаксной задаче оптимального распределения программных модулей между процессорами и применить для её решения алгоритмы, разработанные для данной задачи.
Остальные таблицы формируются по такому же алгоритму, но с учетом вычисленных данных.
Этап 2. Текущее количество процессоров D распределяется между двумя программными модулями R 1 и R 2 . Тогда i=2 и уравнение Беллмана имеет следующий вид:
T 2 (D) = max (t (d 2,j ), T 1 (D-d 2,j )).
Результаты выполнения второго шага представлены в таблице:
Результаты выполнения второго шага
D 2, N ( 1 ) = d 2,1 + D 1, N ( 1 )
D 2 , i N ( 1 ) = d 2 , i + D 1, N ( 1 )
При составлении таблицы используются следующие правила и выполняются определенные процедуры:
количество строк равно количеству различных значений управлений U 2 . В каждой строке указывается соответствующее значение: d 2,1, ., d 2, j , ., d 2, N ( 1 );
количество столбцов соответствует количеству состояний на предыдущем i=1 шаге, т.е. в заголовке столбцов указываются значения
D 1,1 , D 1,2 ,., D 1, j ,.,D 1, N ( 1 );
каждая клетка таблицы разбивается на 2 части. В нижней части записывается сумма значений, указанных в заголовках соответствующих столбцов и строк. Эта сумма определяет состояние для второго этапа - количество процессоров, распределяемых на этапе. Недопустимые значения вычеркиваются, и для них не определяются значения верхней части клетки;
производится заполнение верхней части каждой клетки, в которой указывается максимальное из следующих двух значений: первое значение - время выполнения второго модуля при реализации управления U 2 ; второе значение - время выполнения первого модуля на оставшихся процессорах;
составляется окончательная таблица для второго этапа принятия решения. Эта таблица содержит три столбца: в первом столбце указываются уникальные значения состояний для второго этапа (табл). В промежуточной таблице имеются повторяющиеся значения состояний. таком случае необходимо для состояния D 2,1 найти клетки, имеющие такие же значения состояний, и среди них выбрать клетку с минимальным значением T 2 * (D 2,1 ), т.е. T 2 (D 2,1 ) = min{ T 2 * (D 2,1 ) }. Оптимальное значение управления U 2 для состояния D 2,1 указывается во втором столбце окончательной таблицы, а в третьем столбце записывается условное оптимальное время выполнения первых двух программных модулей R 1 и R 2 при наличии D 2,1 процессоров - T 2 (D 2,1 ). Аналогичные действия выполняются для всех остальных состояний D 2, s , s=, и критерия.
Окончательная таблица для второго этапа
Условное оптимальное время T 2 ( D 2 , i )
Этап 3 . Совершаем распределение между R 1 -м, R 2 -м, R 3 -м программными модулями текущего количества процессоров D. Функциональное уравнение Беллмана для i=3 имеет следующий вид:
T 3 (D) = max (t (d 3,j ), T 2 (D-d 3,j )).
Формируются элементы 3-го этапа, при их формировании используем следующее соотношение:
T 2 * (D 3, ( i-1 ) z ( 2 ) +j ) = max (t (d 3 , i ), T 2 (D 3, ( i-1 ) z ( 2 ) +j - d 2 , i )).
Значения T 2 (D 3, ( i -1 ) z ( 2 ) + j - d 2 , i ) выбираются из третьего столбца окончательной таблицы для второго этапа. Аналогично шагу 2 конструируется окончательная таблица для третьего этапа, содержащая в первом столбце перечень уникальных состояний для третьего этапа, во втором столбце оптимальные управления для каждого состояния и в третьем столбце значения условного оптимального времени выполнения трех программных модулей: R 1, R 2, R 3 . Выполнение алгоритма прямой прогонки прекращается при i=m. После этого в окончательной таблице m-го этапа для состояния, соответствующего предельному количеству процессоров D 0 , находится оптимальное время T m (D m , N ( m ), z ( m )) выполнения всех программных модулей R 1 ., R m , а также оптимальное количество процессоров, выделенных для реализации R m -го модуля. На основании этого значения вычисляется оптимальное количество процессоров, которое назначено для реализации оставшихся модулей: R 1, R 2 ,. R m -1 . Это число процессоров является входом в окончательную таблицу (m-1) - го этапа, что позволяет установить оптимальное количество процессоров для R m -1 -го модуля. Процесс последовательного обратного просмотра окончательных таблиц позволяет определить оптимальное число процессоров для R m -го, R m -1 -го, R m -2 -го,., R 1 -го программных модулей.
Состояние предыдущего второго этапа
Задает количество вариантов распределения грузчиков
Сохраняет введенные изменения таблицы времени выполнения работ
Демонстрирует пошаговое решение задачи
В таблице 2 представлены структуры и классы, используемые в программе
Int [] sost2, sost3,sost4, sost5, sost6
Временные массивы для хранения уникальных состояний
Int [,] temp21 temp22, temp31, temp32, temp41, temp42, temp51, temp52, temp61, temp62
Временные матрицы для определенных шагов 1,2,3,4,5,6
Int [,] tab2, tab3, tab4, tab5,, tab6;
niz (ref int [,] temp1, int [,] a, int [,] tab)
Функция заполнения матрицы, соответствующая значениям нижней части
verh (int [,] temp1, ref int [,] temp2, int [,] a, int [] difMas, int step)
Функция заполнения матрицы, соответствующая значениям верхней части
Функция нахождения максимального элемента из двух
Функция нахождения минимального элемента из двух
countDifEl (int [,] mas, int [,] mas2, int [] U, int [,] tab, ref int [] difMas1, ref int [] difMas2, ref int [] difMas3, ref int [] sost)
Функция нахождения различных значений (количеств работников) в нижней части клетки и минимальных в верхней
search (int [,] mas, int [,] mas2, int a, int b, ref int f)
Функция поиска состояния (количества работников) для обратного просмотра
minTime (int step, int [,] tab, ref int [] answer, ref int t)
Функция нахождения минимального времени выполнения работ
Заполнение таблицы, выбор параметров
Автоматическое заполнение всех данных
Заполнение матрицы времени выполнения работ
Формирование окончательной таблицы для первого этапа
Нахождение промежуточной таблицы i этапа
Формирование окончательной таблицы i этапа
Проверка достигли ли мы последнего этапа, если i=m, то идем к следующему этапу, иначе возвращаемся на 4 этап.
Решение задачи в соответствии с алгоритмом обратной прогонки.
Рисунок 2.8 - Структурная схема алгоритма решения задачи
Из 12 выделенных - 11 уникальных значений. На следующем шаге 11 столбцов.
Сумма в нижней части не больше 21, 15 - уникальных значений. На следующем шаге 15 столбцов.
На следующем шаге 11 уникальных столбцов
Время выполнения всех разгрузочно-погруззочных работ составит Т=8. Для этого потребуется:
- на 5 склад отправить 6 грузчиков,
- на 3 склад отправить 5 грузчиков,
- на 1 склад отправить 21- (6+2+5+4) =4 грузчика.
1. Черноморов Г.А. Теория принятия решений: Учебное пособие / Юж. - Рос. гос. техн. ун-т. Новочеркасск: Ред. журн. "Изв. вузов. Электромеханика" 2002, 276 с.
2. Черноморов Г.А. Методические указания к выполнению курсовой работы по дисциплине "Системный анализ и исследование операций”/ Новочерк. гос. техн. ун-т. Новочеркасск: НГТУ, 1998. С.76.
Концептуальная модель операции. Математическая постановка задачи. Описание метода ветвей и границ, прямого перебора. Проектирование сценария диалога. Описание структур данных. Ручная реализация решения задачи с помощью алгоритма Литла и перебора. курсовая работа [202,6 K], добавлен 14.12.2013
Транспортная задача как одна из самых распространенных специальных задач линейного программирования: понятие, основное назначение. Формальное описание метода минимального элемента. Характеристика этапов разработки алгоритма решения поставленной задачи. курсовая работа [713,3 K], добавлен 19.10.2012
Определение наиболее выгодного соотношения сортов сырой нефти, используемой для производства бензина. Математическая постановка задачи. Выбор метода решения задачи. Описание алгоритма решения задачи (симплекс-метода) и вычислительного эксперимента. курсовая работа [1,1 M], добавлен 08.12.2010
Рентабельность как относительный показатель экономической эффективности. Виды рентабельности и их назначение. Графическое описание метода решения поставленной задачи. Конструирование алгоритма. Характеристика программной реализации. Листинг программы. курсовая работа [45,3 K], добавлен 02.10.2013
Общие задачи линейного программирования. Описание алгоритма симплекс-метода, записанного в канонической форме с односторонними ограничениями. Алгоритм построения начального опорного плана для решения задачи. Расширенный алгоритм искусственного базиса. курсовая работа [142,9 K], добавлен 24.10.2012
Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo. курсовая работа [586,3 K], добавлен 04.04.2015
Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения. курсовая работа [2,0 M], добавлен 12.02.2013
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Ручная реализация алгоритма решения задачи курсовая работа. Программирование, компьютеры и кибернетика.
Сочинение по теме Лужин и Свидригайлов
Дипломная работа по теме Семантический исследование сложных слов в арабском и английском языках
Реферат: Хронический пиелонефрит (история болезни)
Курсовая работа: Расчет себестоимости и цены программного продукта по моделированию объект
Дипломная Работа На Тему Формирование Научных Понятий На Основе Витагенного Обучения На Уроках Информатики
Реферат На Тему Сейсмические Средства Охранной Сигнализации
Реферат: Авария на Чернобыльской АЭС
Реферат: Особливості фіскальної політики в Україні
Культура Ораторской Речи Реферат
Курсовая работа по теме Роль устного счета в процессе формирования устных вычислительных навыков младших школьников
Курсовая Работа Маркетинг Проекта
Применение операционного исчисления при решении дифференциальных уравнений
Курсовая Работа На Тему Исследование Систем Управления Качеством
Контрольная работа: Электрические машины и трансформаторы
Курсовая работа по теме Ведение налогового учета по налогу на доходы физических лиц
Эссе Логика Вопросов И Ответов
Контрольная Работа На Тему Проявление Рда В Дошкольном Возрасте
Реферат по теме Сельскохозяйственные кооперативы в Российской Федерации
Курсовая работа: Тактика допиту свідка
Дипломная Работа На Тему Современное Состояние И Перспективы Развития Кредитного Страхования В Российской Федерации
Состав и содержание бухгалтерской (финансовой) отчетности - Бухгалтерский учет и аудит презентация
Характеристика ООО "ГРИЛЬЯТО-Мастер" - Менеджмент и трудовые отношения отчет по практике
Учение И. Канта о государстве и праве. Связь права и этики - Государство и право контрольная работа