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

Расширение масштабов современного производства, усложнение уровня проводимых мероприятий, необходимость координации деятельности больших коллективов людей существенно усложнили функции организационного производства. В различных областях целенаправленной человеческой деятельности, в сложных, зачастую противоречивых условиях приходится принимать решения, нередко связанные с людьми и большими материальными затратами. Выбрать наиболее экономичный и целесообразный путь, принять обоснованное, наиболее правильное решение - далеко не простая задача и для своего решения требует привлечения современных и научных методов. Методы исследования операций способствуют выработке рациональных, обоснованных решений по управлению этими процессами. При операционном подходе к поиску наиболее эффективных путей достижения цели осуществляется построение математической модели, содержащей описание этой цели и отражающей условия проведения операции.Необходимо обслужить операций на одной машине. Все операции поступают на выполнение одновременно. Выполнение более одной операции в любой момент времени запрещено. Для операции () заданы следующие параметры: продолжительность выполнения , директивный срок окончания выполнения .Метод полного перебора заключается в определении всевозможных расписаний и выявлением среди них оптимального. Определение всевозможных расписаний реализуется перестановками операций в расписании. В этом нетрудно убедиться: на первом месте в перестановке может стоять любой из операций расписания, после того, как мы на первом месте зафиксировали какой-либо элемент, на втором месте может стоять любой из оставшегося элемента и т.д. То есть, метод полного перебора мы можем рассматривать только у расписаний, состоящих из не более чем 12 элементов, т.к. Метод полного перебора является самым точным из методов нахождения оптимального расписания, однако, как говорилось ранее, имеет недостатки, такие как большая трудоемкость вычислений и заполнение большого объема оперативной памяти компьютера.Метод оптимальной вставки заключается в определении очередности операций расписаний и выявлением среди них оптимального расписания. Этот метод содержит древовидный путь выбора оптимального расписания (см. рис. Метод оптимальной вставки имеет условие неубывания директивных сроков , , т. е. Берем первые две операции и рассмотрим их очередности операций, т. е. и . Условием принятия выбора той или иной очередности операций является значение величины суммарного штрафа, т. е. выбирается та очередность операций, у которой суммарный штраф минимален.Предлагаемый ниже генератор использует идею генерации исходных данных задачи для одной машины.[5] В этой работе генерация исходных данных основана на двух параметрах: TF (tightness factor) и RDD (range of due dates), - имеющих для задачи следующий смысл: , , (*) где , . Из целых чисел интервала случайно по равномерному закону выберем значения . Из целых чисел интервала случайно по равномерному закону выберем значения , вычислим .Чтобы отличать TF, RDD генератора и задачи, параметры генератора обозначим через TFGEN, RDDGEN, а параметры сгенерированной задачи TFPR, RDDPR. Будем считать, что TFPR, RDDPR задачи соответствуют TFGEN, RDDGEN генератора с точностью , если , . Необходимо провести эксперимент по выявлению соответствия параметров TFGEN, RDDGEN генератора, параметрам TFPR, RDDPR сгенерированных задач. · Для каждой пары TFGEN, RDDGEN было сгенерировано задач; С - количество задач, попавших в класс, но сгенерированных при несоответствующих классу параметрах TFGEN, RDDGEN (пришедшие задачи).Интерес к программированию постоянно растет. Бурное развитие вычислительной техники, потребность в эффективных средствах разработки программного обеспечения привели к появлению систем программирования, ориентированных на так называемую «быструю разработку», среди которых можно выделить Borland Delphi и MS Visual Basic. В основе систем быстрой разработки (RAD-систем, Rapid Application Development-среда быстрой разработки приложений) лежит технология визуального проектирования и событийного программирования, суть которой заключается в том, что среда разработки берет на себя большую часть генерации кода программы, оставляя программисту работу по конструированию диалоговых окон и функций обработки событий. Borland Delphi - это среда быстрой разработки, в которой в качестве языка программирования используется Object Pascal. В основе идеологии Delphi лежит технология визуального проектирования и методология объектно-ориентированного событийного программирования.Изучаемые в теории расписаний задачи составления оптимальных расписаний имеют общий характер и возникают при различных видах целенаправленной деятельности: при календарном планировании производства, транспортных перевозок, обучения, информационно вычислительных процессов. Полученные в курсовой работе результаты могут быть использованы для построения алгоритмов решения многоприборных и многостадийных задач выбора очередности выполнения операции, возникающих на прак

Содержание

Введение 3

1. Введение в теорию расписаний 4

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

3. Методы решения задачи 8

3.1 Метод полного перебора 8

3.2 Метод оптимальной вставки 9

4. Генератор исходных данных для задачи 12

4.1 Алгоритм генератора исходных данных для задачи 12

4.2 Численный эксперимент 13

5. Описание работы приложения 15

5.1 Выбор языка программирования 15

5.2 Работа с приложением 16

Заключение 19

Литература 20

Приложения 21

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

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

Как правило, одни и те же цели могут быть достигнуты различным образом, с различными затратами труда и материальных ресурсов. Выбрать наиболее экономичный и целесообразный путь, принять обоснованное, наиболее правильное решение - далеко не простая задача и для своего решения требует привлечения современных и научных методов. [1]

Целью данной курсовой работы является реализация методов решения минимизации средневзвешенного суммарного штрафа на компьютере и разработка программы.

Основные задачи: Изучить методы решения задачи минимизации средневзвешенного суммарного штрафа, генератор исходных данных задачи;

Разработать алгоритмы решения задачи методами полного перебора и оптимальной вставки;

По данным алгоритмам составить программный код на Delphi;

Провести численный эксперимент составленных генератором задач. задача минимизация алгоритм программа

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

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

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

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

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

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

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

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

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

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

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