Модели и алгоритмы оптимизации загрузки ресурсов в условиях мелкосерийного производства

• Автор: Ильина, Татьяна Романовна
• Шифр специальности: 05.13.06
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Красноярск
• Количество страниц: 149 с. : ил

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. Формализация и исследования задач оптимизации загрузки ресурсов мелкосерийного производства при нерегулярном поступлении заказов
1.1. Экономикоматематическая модель задачи распределения производственной программы предприятия по плановым
периодам

1.2. Задачи формирования производственной программы при

мелкосерийном производстве

1.3. Задачи формирования оптимальной производственной

программы

ГЛАВА 2. Математический аппарат

2.1. Свойства пространства булевых переменных

2.2. Частичный порядок и Фмножества в В2П
ГЛАВА 3. Оптимизация унимодальных псевдобулевых функций
3.1. Унимодальная монотонная псевдобулевая функция и ее свойства
3.2. Оптимизация разнозначных унимодальных монотонных
псевдобулевых функций
3.3. Алгоритм оптимизации монотонных унимодальных
псевдобулевых функций с множествами постоянства
3.4. Оценка сверху эффективности алгоритма 2
3.5. Оценка в среднем эффективности алгоритма 2
ГЛАВА 4. Оптимизация полимодальных локально монотонных
псевдобулевых функций
4.1. Полимодальная локально структурно монотонная функция
и ее свойства
4.2. Алгоритм оптимизации полимоданлюй локально строго
монотонной псевдобулевой функции
4.3. Алгоритм оптимизации полимодальной локально монотонной
псевдобулевой функции с множествами постоянства
4.4. Эффективность алгоритмов глобальной оптимизации
ГЛАВА 5. Практическая реализация моделей и алгоритмов
5.1. Алгоритмы прямого локального поиска для задач оптимизации 2 функционалов с булевыми переменными 5.2. Генетические алгоритмы как генераторы начальных точек
для мультистарта локального поиска 5.3. Программная система решения задач оптимизации загрузки
ресурсов при мелкосерийных нерегулярных заказах 5.4. Результаты применения разработанного математического
и алгоритмического обеспечения при решении практических задач
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Третье поднаправление включает методы описания ограничений на целочисленность в такой форме, которая позволила бы применять обычные методы математического программирования Основным путем здесь является использование метола штрафных функций с введением штрафов за нарушение целочисленности. Решение, получаемой после введения функции штрафа задачи нелинейного программирования, является оптимальным или, по крайней мере, допустимым. Все три направления позволяют работать с частными случаями задач целочисленного программирования и не могут быть расширены на случай неявного задания целевой функции. Кроме того, получаемые задачи нецелочисленного программирования приобретают такую сложную структуру, что многие достоинства методов непрерывной оптимизации превращаются в недостатки и преимущества данных подходов становятся весьма сомнительными с точки зрения практики. Методы, ориентированные на применение теории управления динамическими системами и соответствующих алгоритмов. Такими задачами, например, являются задачи теории расписаний. Последние задачи могут быть приведены к статической модели целочисленного программирования. Однако решение данных задач с использованием последней модели при больших размерностях встречает существенные трудности. Построение динамической модели и использование определенной алгоритмической реализации принципа максимума позволяет в значительной мере преодолеть эти трудности и получить достаточно эффективную процедуру решения []. Данные методы требуют явного задания целевой функции и ограничений. Третье направление включает большую группу методов и алгоритмов, в которых в тех или иных формах реализуется один из основных принципов конструирования алгоритмов, характерных для задач выбора на дискретных множествах - принцип последовательного сужения множества альтернатив. Данная группа в теории дискретного программирования является наиболее обширной и в ее рамках появляются все новые и новые разновидности методов и алгоритмов. Здесь можно выделить три основных класса методов и алгоритмов. Первый класс охватывает разнообразные комбинаторные методы и алгоритмы дискретной оптимизации. К ним относятся все алгоритмы последовательного сужения конечного множества альтернатив, при реализации которых оптимальное решение определяется в результате полного или неполного (целенаправленного, неявного) перебора альтернатив или (и) элементов их составляющих. Большинство комбинаторных алгоритмов может применяться как на основе предварительного представления задачи моделью целочисленного программирования, так и непосредственно для решения задачи на комбинаторной структуре. В литературе можно встретить несколько схем сужения множества альтернатив, охватывающих несколько видов комбинаторных алгоритмов. Оптимизационная схема B. C. Михале-вича, введенная под названием метода последовательного анализа вариантов (последовательного исключения возможностей) [, , ], включает как частные случаи схемы методов динамического программирования и ветвей и границ. Для ряда комбинаторных алгоритмов общая оптимизационная схема вводится под названием поиска с возвратом []. Описанные алгоритмы могут быть применены в некоторых случаях для решения практических задач, но при условии, что удастся представить целевые функции в нужном виде и доказать наличие у них соответствующих свойств. Например, для применения метода последовательного анализа вариантов необходимо уметь вычислять оценку значения целевой функции по части объектных переменных, а не по всем, и, кроме того, доказать свойство монотонной рскурсивности этой функции, что представляется весьма затруднительным в случае ее алгоритмического задания. Для вычисления нижних оценок в алгоритме ветвей и границ обычно применяется релаксация, т е. Ко второму классу отнесем методы и алгоритмы, реализующие идею предварительного расширения множества допустимых альтернатив, позволяющего представить его описание в удобном для нахождения экстремума виде, и последующего сужения этого множества с использованием последовательно определяемых на каждом шаге сужения решений. В данном классе в свою очередь можно выделить два основных метода. Первый метод, предложенный Р. Гомори в г.