- •Министерство образования Украины
- •Лазорин Анатолий Иванович
- •Лабораторная работа.
- •Тема: Распределительные задачи
- •Задача о назначении
- •(Экстремальная задача комбинаторного вида)
- •2.2. Общие положения
- •2.1. Постановка задачи.
- •2.2. Построение математической модели и критерий оптимизации.
- •2.3.Алгоритм метода решения – решение венгерским методом.
- •З. Подготовка и расчет контрольного примера.
- •3.1.Исходные данные и постановка задачи.
- •3.3. Построение исходной таблицы и расчет.
- •4. Подготовка и расчет варианта задания.
- •5. Отчет должен содержать.
- •6.Список используемых источников.
- •Лабораторная работа. Транспортная задача линейного программирования
- •1. Постановка задачи.
- •2. Математическая формулировка задачи.
- •3 Методы определения начального опорного плана.
- •3.1 Метод северо-западного (с-з) угла
- •3.2 Метод наименьшей стоимости.
- •3.3 Метод Фогеля.
- •4 Нахождение оптимального решения транспортной задачи методом потенциалов.
- •5. Решение транспортных задач при помощи программы "Transpo"
- •Введение исходных данных по запросам программы
- •7. Последовательность выполнения работы.
- •8. Состав отчета к лабораторной работе.
- •Лабораторная работа. Тема Задачи линейного программирования
- •Графический метод решения задач лп.
- •Симплексный метод решения задач лп.
- •Для этого в случае необходимости задача (1.1) поиска минимума сводится к задаче на поиск максимума (1.7) путем изменения знаков коэффициентов Сj
- •Правило прямоугольника
- •Пример. Решить задачу лп:
- •Метод искусственного базиса.
- •Поэтому новая таблица имеет четыре строки и шесть столбцов:
- •Лабораторная работа. Тема: Задачи упорядочения и согласования. Алгоритм Джонсона.
- •2.Общие положения
- •2.1.Постановка задачи.
- •2.2Построение математической модели и критерий оптимизации.
- •Таким образом требуется определить такую последовательность обработки, при которой
- •Например, пусть имеем порядок обработки изделий на 1-ой машине
- •3.Подготовка и расчёт контрольного примера.
- •Пример составления таблицы значений времени обработки для 3-х машин:
- •4.Подготовка и расчёт варианта задания .
- •4.2. Исходные данные контрольного примера.
- •5.Отчёт должен содержать.
- •6.Список используемых источников.
- •Лабораторная работа Задачи управления запасами. Управление запасами при случайном спросе.
- •2.Общие положения.
- •2.1.Постановка задачи и основные особенности.
- •2.2.Построение математической модели и критерий оптимизации.
- •2.3.Алгорим метода решения.
- •3.Подготовка и расчёт контрольного примера.
- •Вычисленное значение
- •4. Подготовка и расчет варианта задания.
- •5. Отчет должен содержать :
- •6. Список используемых источников
- •Лабораторная работа Тема: Состязательные задачи.
- •2.Общие положения.
- •2.1 Постановка задачи и краткие теоретические положения.
- •2.2 Построение математической модели и критерий оптимизации.
- •3.Подготовка и расчёт контрольного примера.
- •3.1 Исходные данные и постановка задачи.
- •3.2.Построение математической модели и критерия оптимизации.
- •3.3.Снижение размерности игровой матрицы и анализ на наличие седловой точки.
- •3.4.Поиск оптимального решения.
- •3.3.Анализ вариантов исследований.
- •4.Подготовка и расчёт варианта задания.
- •5.Отчёт должен содержать.
- •6.Список используемых источников.
- •Лабораторная работа. Тема: Задачи массового обслуживания Задача анализа и синтеза детерминированной одноканальной замкнутой системы массового обслуживания с ожиданием
- •Краткая характеристика объекта.
- •2.Постанавка задачи. Постановку задачи разделим на две части. В первой части выполним анализ заданной смо и расчет ее характеристик, а во второй – определим оптимальную структуру системы.
- •Очередь
- •3.Основные положения расчетов.
- •4.Построение и исследование математической модели смо.
- •Первое слагаемое критерия обозначить:
- •5.Подготовка и расчет контрольного примера.
- •6.Подготовка и расчет варианта задания.
- •7. Отчет по работе должен содержать:
- •Содержание
Лабораторная работа. Тема: Задачи упорядочения и согласования. Алгоритм Джонсона.
1.Цель работы: Приобретение практических навыков применения теоретических положений, формализации и решения задач упорядочения оптимальной последовательности выполнения различных операций.
2.Общие положения
2.1.Постановка задачи.
В задачах упорядочения и согласования определяются оптимальные последовательности обработки изделий, массивов информации, наилучших маршрутов движения, т.е. процессов, состоящих из комплекса взаимосвязанных операций (работ, событий, экспериментов) чётко разграниченных по продолжительности выполнения, по ресурсам, затрачиваемым на операции, а также с целью оценки операций наиболее важных согласно целевой функции. Один из методов решения таких задач - алгоритм Джонсона, применяется для нахождения оптимальной последовательности порядка обслуживания m требований на 2-х пунктах обслуживания. При этом каждое из требований должно пройти сначала на первом пункте, затем - на втором. Продолжительности обслуживания требований различные. Примером может служить обработка деталей на двух многооперационных станках или на двух технологических линиях. Если, например, для двух пунктов обслуживания (станков) и m = 6 требований (операций, изделий) применить метод прямого перебора, то будет m! = 720 возможных вариантов.
Пусть имеется m изделий, каждое из которых должно быть обработано на двух машинах. Известны время обработки каждого изделия на каждой машине. Требуется выбрать такой порядок обработки изделий, при котором суммарное время обработки изделий будет минимальным (или минимальное суммарное время простоя машин).
2.2Построение математической модели и критерий оптимизации.
Основные ограничения задачи состоят в следующем:
время перехода изделия от одной машины к другой незначительно и им можно пренебречь;
каждое изделие обрабатывается в определённом технологическом порядке;
каждое обслуживание должно быть полным (завершено) прежде, чем начнётся следующее.
Оптимизируемый параметр - время обработки, т.е.суммарное время обработки изделий должно быть минимальным.
Критерий оптимизации.
Тобр = tij + tnij min , (2.1)
где tij - время обработки изделия на i-ой машине, tnij - время простоя i-ого станка, а также сумма tij - время обработки изделий на i-ом станке известно, то минимизация относится к сумме tnij.
Таким образом требуется определить такую последовательность обработки, при которой
Тпр = tij min (2.2)
Например, пусть имеем порядок обработки изделий на 1-ой машине
Р1=(t11, t12,......, t1m)
и на 2-ой машине:
Р2=(t21, t22,......, t2m),
тогда порядок Р1 будет лучше порядка Р2, если Тпр1< Тпр2
Графический процесс обработки изделий на двух машинах имеет вид:
Рис.2.1
2.3Алгоритм метода решения (Джонсона) включает следующие этапы:
2.3.1.записываются tij -продолжительности обработки в две строки (колонки),т.к. i=2, по соответствующим машинам и по порядку обслуживания;
2.3.2.просматривают все продолжительности обработки изделий и находят среди них наименьшую;
2.3.3.анализ и перестановка изделий; если это изделие относится к первой машине, то его надо переставить на первое место, а если ко второй - то переставить на последнее место порядка обслуживания. При наличии одинаковых минимальных элементов в обеих строчках (колонках), то указанную перестановку делают одновременно. Если же одинаковые элементы (минимальные) оказываются в обеих строках (колонках) на одном порядковом номере, то перестановку делают по 1-ой машине (на 1-ое место).Если же одинаковые минимальные элементы оказываются в первой (второй) строке, то на первое (последнее) место становится изделие, которому соответствует элемент с меньшей длительностью второй (первой) строки;
2.3.4.преставленные номера изделий из дальнейшего рассмотрения исключают и возвращаются к п.п.2.3.2;
2.3.5.в результате получают оптимальную последовательность обработки изделий на двух машинах;
графически определяется время простоя и работы второй машины Тобр, которое будет минимальным из всех возможных вариантов.
2.4.возможно применение алгоритма Джонсона для решения задачи упорядочения для трёх машин или трёхэтапного обслуживания. Это возможно в следующем случае:
минимальное время обработки изделия на первой машине больше или равно максимальному времени обработки изделия на второй обработки изделия на второй машине:
min{tij}>=max{tij} (2.3)
j=1,...,m j=1,...,m
минимальное время обработки изделия на третьей машине больше или равно максимальному времени обработок на второй машине:
min{t3j}>=max{tij} (2.4)
j=1,...,m j=1,...,m
Далее составляется новая таблица для суммы (t1j+t2j) вместо t1j или (t2j+t3j) вместо t2j и к ней применяется алгоритм Джонсона (п.п.2.3).