Реферат Решение задачи о расписании обработки деталей СГРК.КП.П-41.21.ПЗ
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Министерство образования и науки Республики Казахстан
Семипалатинский геологоразведочный колледж
Курсовой проект
Тема: Решение задачи о расписании обработки деталей
СГРК.КП.П-41.21.ПЗ
Руководитель: Н.Ю. Толпегина
«________»____________2008г
Нормоконтролер: З.Н. Берекболова
«________»________________________2008г
Разработала студентка: А
.Н. Подвязная
группа П-41
г. Семей
2008г.
Введение…………………………………………………..
Общая часть…………………………………………….
1. Содержательная постановка задачи…………
2. Построение математической или сетевой модели.
3. Существующие метод решения…………………
4. Конкретный метод решения………………………
5. Решение задачи………………………………………
5.1. Решение задачи без применения ЭВМ………
5.2. Блок-схема задачи…………………………………
5.3.Программа……………………………………………
5.4. Решение задачи на ЭВМ…………………………
ЗАКЛЮЧЕНИЕ……………………………………………
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ……
Математическое программирование представляет собой математическую дисциплину, занимающиеся изучением экстремальных задач и разработкой методов их решения.
В общем виде математическая постановка экстремальной задачи состоит в определении наибольшего значения целой функции f (x1,x2, ……., xn) при условии gi (x1,x2, ……., xn) ≤ b1 (i = 1,m), где f и gi - заданные функции a * bi – некоторые действительные числа. В зависимости от свойств функции f и gi математическое программирование можно рассматривать как ряд самостоятельных дисциплин. Занимающиеся изучением и разработкой методов решения определенных классов задач.
Прежде всего, задачи математического программирования делятся на задачи линейного и нелинейного программирования. При этом если все функции
f и gi линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функции нелинейная, то соответствующая задача является задачей нелинейного программирования.
Наиболее изученным разделом математического программирования является линейное программирование. Для решения задач линейного программирования разработан целый ряд эффективных методов, алгоритмов и программ. Среди задач линейного программирования наиболее глубоко изучены задачи выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве.
Отдельным классами задач математического программирования являются задачи целочисленного, параметрического и дробно-линейного программирования.
В задачах целочисленного программирования неизвестные могут принимать только целочисленные значения. В задачах параметрического программирования целевая функция или функции, определяющие область возможных изменений переменных, либо то и другое зависят от некоторых параметров.
В задачах дробно-линейного программирования целевая функция представляет собой отношения двух линейных функций, а функции определяющие область возможных изменений переменных, также являются линейным. Выделяют отдельные классы задач стохастического к динамического программирования.
Если в целевой функции или в функциях, определяющих область возможных изменений переменных, содержатся случайные величины, то какая задача относится к задаче стохастического программирования.
Задача, процесс нахождения решения которой является многоэтапным, относится к задаче динамического программирования.
опубликован в
Одновременно с развитием линейного программирования большое внимание уделялось задачам нелинейного программирования, в которых либо целевая функция, либо ограничения, либо и то и друге нелинейны. В
методы решения узкого класса задач нелинейного программирования.
При исследовании экономических процессов в большинстве случаев имеют место задачи нелинейного программирования, аппроксимация их линейными задачами вызвана только тем, что последние хорошо изучены и для них разработаны алгоритмы решения. Даже простейшая транспортная задача принимает нелинейный вид, если стоимость перевозки единицы груза зависит от его общего количества.
Таким образом, динамическое программирование определяется как математическая теория отыскания оптимального решения многоэтапных задач.
Динамическое программирование как самостоятельная наука сформировалось в пятидесятых годах нашего века. Большой вклад в ее развитие внес американский математик Р. Беллман. Дальнейшее развитие динамическое программирование получило в трудах зарубежных ученых Дрейфуса, Робертса, Ланге, Кара, Хоува и др. В настоящее время оно в основном развивается в направлении приложений к различного рода многоэтапным процессам.
Мне было выдано задание, цель которого состоит в следующем: Составить программу для решения задачи обработки деталей методом Джонсона.
1 СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ
Для обработки 16 деталей имеется два станка, каждая деталь должна пройти обработки сначала на первом станке, а затем на втором со следующими данными о времени на каждом станке.
| Станок/Деталь | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 1 | 15 | 14 | 12 | 20 | 25 | 5 | 9 | 30 | 8 | 13 | 23 | 31 | 24 | 35 | 36 | 19 |
| 2 | 23 | 18 | 10 | 17 | 8 | 40 | 16 | 20 | 12 | 15 | 25 | 32 | 19 | 16 | 20 | 38 |
Найти оптимальный план обработки всех деталей. Решить задачу используя алгоритм Джонсона.
Цель задачи:
Составление программы для расписания обработки деталей на двух станках.
Решение:
Пусть время измеряется в некоторых условных единицах, при которых все tik являются целыми числами. Введем неотрицательные переменные xik указывающие
В этих условных единицах «дату» начало обработки х-й детали на i-й, каждая может поступить на обработку в i-м станке только после того, как обработка детали, поступивший первой, будет закончена.
Это условие можно выразить соотношениями
xik
≥ xij
+
tij
;
или
xij
≥ xik
+
xik
Xsk
≥ xik
+
tik
Целевая функция z=t, которую необходимо минимизировать будет выражать собой общее время завершения всех работ. Величина t связана с переменными задачи соотношениями:
t
≥ xik
+
tik
Рассмотрим задачу целочисленного программирования, в которой целевая функция и органы линейны. В таких задачах переменные могут принимать только целые числа значения.
Рассмотрим задачу:
F
=
Σ
cij
+
xj
=>
max
xi
≥ 0
xi
–
целые числа
j
=
(1,
n
),
i
= (1,
m
)
При решении этой задачи симплекс методом могут оказаться как дробные, так и целые значения управления переменных.
Чтобы получить целочисленное решение нужно использовать метод Гомори, который состоит в следующем:
1. Находим решение задачи обычным симплекс методом без учета целочислености переменных.
2. После нахождения оптимального плана задачи просматриваем столбец. P0 , или среди чисел этого столбца нет дробных. То найденый план является оптимальным планом задачи целочисленного программирования. Если в аптимальном плане задачи в столбце В имеются дробные числа, то к системе ограничения добавляют неравенства вида
1. Σ f (aj *) xj ≥ f (bi *)
aj * и bi * это преобразованные исходные величины aj * bi * значений которых, берутся из последней таблицы.
3. Используя двойственный симплекс метод, находим решения двойственной задачи полученной из основной задачи в результате присоединения к ней дополнительного ограничения.
4. Если в найденном плане задачи есть дробные, то процесс решения повторяем второго пункта.
КОНКРЕТНЫЙ МЕТОД РЕШЕНИЯ
Задача теории расписания, или календарного планирования.
Для обработки n (k = 1, …… n) деталей иметься m (i = 1, ……. m) станков. Каждая деталь должна пройти обработку в некоторой последовательности на всех станках. Задано время tik обработки k-й деталей на i-м станке (некоторые tik = 0, если k-я деталь не обрабатывается на i-м станке). При этом необходимо выполнить следующие условия:
1) На одном станке единовременно может обрабатываться только одна деталь;
2) Для каждой детали указан определенный порядок обработки;
3) Производственные операции неделимые, т.е. начавшаяся на определенном станке обработка детали должна быть закончена не прерываясь.
Составить модель задачи по определению оптимального порядка обработки деталей, минимизирующего общее время выполнения всех работ.
Условия (2.1) можно свести к обычным ограничениям с помощью введения альтернативных переменных yiyk, принимающих значения 0 или 1. Введем некоторую постоянную T, заведомо большую общей даты выполнения всех работ.
Тогда альтернативные условия (2.1) равносильны следующей системе неравенств
(
T
+
tik
)
yijk
+
Xij
≥
Xjr
+
tjr
(4.1)
(
T
+
tik
)(1-
yijk
)+
Xjj
≥
Xjr
+
tjr
(4.2)
При yijk=0 получаем из (
Таким образом, если j-я деталь поступает на обработку на i-й станок после k-й, то yijk=0, а если до k-й, то yijk=1. Следовательно, для каждого i и любых двух деталей (I и k) необходимо, чтобы из двух переменных yijk и yikj одна равнялась нулю и другая – единице. Этого можно добиться, введя дополнительные ограничения
yijk
+
yikj
=1 (4.3)
которые вместе с условиями неотрицательности и целочислености обеспечат выполнения указанного требования.
Теперь можем сформулировать окончательно следующую модель целочисленного программирования: минимизировать z=t при условиях (2.2), (4.1), (4.2), (4.3), условиях неотрицательности и целочислености переменных хik, yijk и t.
Хотя полученная модель и может принципиально служить для решения задачи методами целочисленного программирования, но практически расчеты оказываются чрезвычайно громоздкими. Поэтому для решения задач календарного планирования используются иные, так называемые комбинаторные методы.
1) располагают данные
tik
в двух строках таблицы;
2) находят среди всех
tik
наименьшее;
3) если
min
{
tik
}=
t
2
k
0
, то
k
0
-
ю
деталь помещают на последнее место;
4) если оказывается несколько равных минимальных чисел, то выбирают деталь с меньшим номером . Если
min
{
tik
}=
tik
2
=
t
2
k
0
, то
k
0
-
ю деталь помещают первой
;
5)после выполнения
n
. 2-4 вычеркивают
k
0
-й столбец и продолжают ту же процедуру с оставшимися 2
n
-2 величинами
tik
, начиная с
n
, 2.
РЕШЕНИЕ ЗАДАЧИ
5.1
Решение задачи без применения ЭВМ
Задание:
Для обработки 16 деталей имеется два станка, каждая деталь должна пройти обработки сначала на первом станке, а затем на втором со следующими данными о времени на каждом станке.
| Станок/Деталь | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 1 | 15 | 14 | 12 | 20 | 25 | 5 | 9 | 30 | 8 | 13 | 23 | 31 | 24 | 35 | 36 | 19 |
| 2 | 23 | 18 | 10 | 17 | 8 | 40 | 16 | 20 | 12 | 15 | 25 | 32 | 19 | 16 | 20 | 38 |
Найти оптимальный план обработки всех деталей. Решить задачу, используя алгоритм Джонсона.
Решение задачи:
| | 6 | 9 | 7 | 10 | 2 | 1 | 16 | 11 | 12 | 15 | 8 | 13 | 4 | 14 | 3 | 5 |
| 1 | 5 | 8 | 9 | 13 | 14 | 15 | 19 | 23 | 31 | 36 | 30 | 24 | 20 | 35 | 12 | 25 |
| 2 | 40 | 12 | 16 | 15 | 18 | 23 | 38 | 25 | 32 | 20 | 20 | 19 | 17 | 16 | 10 | 8 |
Ответ:
В минимальном времени обработки на двух станках = 319 единиц.
Время простоя второго станка = 5.
Чистое время = 314
2
Блок-схема задачи
3
Программа
Решение задачи не ЭВМ
КЛЮЧЕНИЕ
Мне было предложено решить задачу по минимизации времени обработки деталей поочередно на двух станках. Вследствие решения данной задачи я изучил алгоритм Джонсона. Суть данного метода заключается в следующем: нужно расположить детали в такой последовательности, чтобы минимизировать время обработки деталей поочередно на двух станках и минимизировать простой второго станка.
Разработанная мною программа может работать для подсчета времени обработки шестнадцати деталей на двух станках и подсчета простоя второго станка.
1. Кузнецов Ю.Н.
Математическое программирование. Учебное пособие для вузов. М, «Высшая школа», 1976г.
2. Хазанова Л.Э. Математическое Моделирование в экономике: Учебное пособие. М.: Издательство Век, 1998год.
