Решение задачи о расписании обработки деталей СГРК.КП.П-41.21.ПЗ

Министерство  образования и науки Республики Казахстан

Семипалатинский геологоразведочный колледж 
 
 
 
 
 
 
 

Курсовой  проект 

Тема: Решение задачи о расписании обработки деталей  

СГРК.КП.П-41.21.ПЗ 
 
 
 
 
 

                               Руководитель: Н.Ю. Толпегина

                                                       «________»____________2008г

                               Нормоконтролер: З.Н. Берекболова

                               «________»________________________2008г 

                               Разработала студентка: А.Н. Подвязная

                                                   группа П-41 
 
 
 
 
 
 
 
 

г. Семей

2008г. 

     СОДЕРЖАНИЕ

Введение…………………………………………………..

Общая часть…………………………………………….

1. Содержательная постановка задачи…………

2. Построение математической  или сетевой модели.

3. Существующие метод  решения…………………

4. Конкретный метод  решения………………………

5. Решение задачи………………………………………

   5.1. Решение задачи без применения ЭВМ………

   5.2. Блок-схема задачи…………………………………

  5.3.Программа……………………………………………

  5.4. Решение задачи на ЭВМ…………………………

ЗАКЛЮЧЕНИЕ……………………………………………

СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ……

                                                        
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ 

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

     В общем виде математическая постановка экстремальной задачи состоит в  определении наибольшего значения целой функции f (x₁,x₂, ……., x_n) при условии g_i (x₁,x₂, ……., x_n) ≤ b₁ (i = 1,m), где f и g_i   - заданные функции a * b_i – некоторые действительные числа. В зависимости от свойств функции f и g_i математическое программирование можно рассматривать как ряд самостоятельных дисциплин. Занимающиеся изучением и разработкой методов решения определенных классов задач.

     Прежде  всего, задачи математического программирования делятся на задачи линейного и  нелинейного программирования. При  этом если все функции 

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

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

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

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

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

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

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

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

      Методам линейного  программирования посвящено много  работ зарубежных и, прежде всего  американских ученых. В 1941 г. Хичкок поставил транспортную задачу. Основной метод  решения задач линейного программирования – симплекс метод – был 

опубликован в 1949 г. Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Форда, Фалкерсона, Куна, Лемке, Гаусса, Чарнеса, Била и др. В настоящее время методы линейного программирования развиваются главным образом в направлении выявления конкретных экономических задач, к решению которых оно может быть применено, а так же по пути создания более удобных алгоритмов для решения задач на электронно-вычислительных машинах.

     Одновременно  с развитием линейного программирования большое внимание уделялось задачам нелинейного программирования, в которых либо целевая функция, либо ограничения, либо и то и друге нелинейны. В 1951 г. Была опубликована работа Куна и Таккера, в которой приведены необходимые и достаточные условия оптимальности для решения нелинейных задач. Эта работа послужила основой для последующих исследований в области нелинейного программирования. Чарнес и Лемке (1954 г.) рассмотрели приближенный метод решения задач с сепарабельными выпуклыми функциями цели и линейными ограничениями. Начиная с 1955 г. опубликовано  много работ, посвященных квадратическому программированию (работы Била, Баранкина и Дорфмана, Франка и Вольфа, Марковича, Хилдрета и др.). 

       В работах  Дениса Розена и Зойтендейка   разработаны Градиентные методы  решения задач нелинейного программирования. В настоящее время известны

     методы  решения узкого класса задач нелинейного  программирования. 

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

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

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

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

ОБЩАЯ ЧАСТЬ

1 СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ 

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

 
 

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

       
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ 

Цель  задачи:

Составление программы для расписания обработки  деталей на двух станках. 

Решение:

Пусть время измеряется в некоторых  условных единицах, при которых все  t_ik являются целыми числами. Введем неотрицательные переменные x_ik  указывающие     

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

Это условие  можно выразить соотношениями 
 

                       x_ik  ≥   x_{ij +} t_{ij  ;    или}     x_ij  ≥ x_{ik  +} x_ik 

Условие 2), согласно которому некоторая k-я деталь должна сначала обрабатываться на i-м станке, а затем на s-м, можно выразить соотношением

 

                         X_sk  ≥   x_{ik +} t_ik   

Целевая функция z=t, которую необходимо минимизировать будет выражать собой общее время завершения всех работ. Величина t связана с переменными задачи соотношениями:

                        

                             t ≥ x_{ik +} t_ik 

                
 

3 ДИСКРЕТНОЕ ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ 

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

     Рассмотрим  задачу: