Решение задач на тему: Постановка задачи о переналадке станков как задачи динамического программирования

Введение

Опис. часть

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

Опис. часть

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

Опис. часть

Алгоритм метода ветвей и границ

Опис. часть

Схема алгоритма

Граф. часть

Решение поставленной задачи

Расчет. часть

Составление программы

Расч. на ЭВМ

Отладка программы

Расч. на ЭВМ

Инструкция пользователю

Опис. часть

Граф-кая часть А1

Граф. часть

Оформл. Тит.л. и л. содержания

Графич. часть

Выводы

Опис. часть

Оформление курсового проекта

Срок сдачи проекта на проверку __9.11-15.11________

День защиты проекта_____16.11-24.11_____________

Руководитель______________________________

Содержание

Введение

1 Постановка задачи о переналадке станков как задачи линейного программирования

2 Методы решения задачи. Метод ветвей и границ

3 Алгоритм метода ветвей и границ. Схема алгоритма

4 Решение поставленной задачи

4.1 Условие задачи

4.2 Решение задачи вручную

5 Выводы

Литература

Приложение А Текст программы

Схема алгоритма

Описание программы

Инструкция пользоватедлю

Приложение Б Входная информация

Выходная информация

Приложение В Графическая часть (1А1)

ВВЕДЕНИЕ

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

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

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

Оглавление

- Введение

- Постановка задачи о переналадке станков как задачи динамического программирования

- Методы решения задачи. Метод ветвей и границ

- Алгоритм метода ветвей и границ. Схема алгоритма

- Решение поставленной задачи

- Условие задачи

- Решение задачи вручную

- 5 Выводы

- Литература

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

- Расчетная часть

- Задача

- Определить оптимальную последовательность запуска деталей в производство, если задана матрица затрат на переналадку оборудования

Заключение

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

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

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

Также прилагается программана решающая задачу о коммивояжере методом ветвей и границ. Для разработки данной программы была использованя среда разработки Delphi версии 6.0.

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

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

Список литературы

1 Балашевич В.А., Алгоритмизация математических методов планирования и управления. - Минск: Вышэйшая школа,1979.-286с

2 Дегтярев Ю.И., Исследование операций.- Москва: Высшая школа,1986.-270с.

3 Ляшенко И.Н. Линейное и нелинейное программирование - Киев: Вища школа,1975.-370с.

ПРИЛОЖЕНИЕ А

(обязательное)

Текст программы

Схема программы

Описание программы

Инструкция пользователю

ПРИЛОЖЕНИЕ Б

(обязательное)

Входная информация

ПРИЛОЖЕНИЕ В

(обязательное)

Выходная информация