Презентации по Математике

Методы решения оптимизационных задач
Методы решения оптимизационных задач
Введение Примеры дискретных оптимизационных задач задача о кратчайшем пути: Пусть имеется несколько городов и известны попарные расстояния между соседними городами. При этом два города считаются соседними, если есть дорога, их соединяющая, и не проходящая через какой-либо другой город. Требуется найти кратчайший путь между некоторой парой городов; задача оптимального назначения: Пусть имеется n станков и n деталей, каждую деталь можно обрабатывать на любом станке, но время обработки детали на одном станке может отличаться от времени ее обработки на другом. Пусть эти времена для каждой пары «станок — деталь» заданы. Требуется так организовать производство деталей, т.е. разместить их по станкам, чтобы суммарное время работы было наименьшим ; задача коммивояжера Путешественник хочет объехать n городов, побывав в каждом ровно по одному разу, и вернуться в исходный, затратив при этом минимальную сумму на поездку. Затраты па поездку складываются из затрат на переезды между парами городов, а эти затраты заранее известны. В каждой задаче имеется лишь конечное число вариантов, из которых требуется осуществить выбор (путей между городами, способов распределения деталей по станкам, маршрутов передвижения путешественника). Каждому варианту выбора сопоставлена некоторая числовая характеристика (длина пути, суммарное время работы, стоимость поездки). Требуется выбрать вариант, числовая характеристика которого достигает экстремума. Методы решения подобных задач полный перебор (поочередно пересмотреть все варианты и выбрать требуемый); дискретная оптимизация. Общие свойства дискретных оптимизационных задач
Продолжить чтение