Содержание
- 2. Лекция 4 Методы математического программирования при автоматизации конструирования ЭА 1 Основные классы задач математического программирования. Линейное
- 3. Вопрос 1 Основные классы задач математического программирования. Линейное программирование в ИТАП
- 4. Основные классы задач математического программирования 1. Класс линейного программирования 2. Класс нелинейного программирования 3. Класс целочисленного
- 5. Линейное программирование Математическая формулировка: определить такие значения переменных X*, удовлетворяющих системе ограничений, при которой достигается экстремум
- 6. Прикладные задачи линейного программирования Задача о назначениях частный случай транспортной задачи, который используется при проектировании ЭА
- 7. Задача о назначениях Пусть имеется n вакантных видов работ, на которые претендует n работников, причем на
- 8. Задача о назначениях Определим матрицу где Необходимо максимизировать функцию F При ограничениях (на каждом j-м виде
- 9. Задача о назначениях Требование целочисленности переменных Xji, усложняет решение задачи. Однако доказано, что в задаче о
- 10. Симплекс-метод осуществляется направленное движение по опорным планам до получения оптимального решения Алгоритм: 1) По определенному правилу
- 11. Симплекс-метод Алгоритм: Для решения задачи линейного программирования этим методом необходимо, чтобы ее математическая модель была задана
- 12. Венгерский метод Разработал венгерский математик Е. Эгервари задолго до возникновения теории линейного программирования ограничения 1. Задачи
- 13. Венгерский метод Основан на трансформации системы независимых нулей. Систему нулевых элементов матрицы, обладающую тем свойством, что
- 14. Венгерский метод. Алгоритм 1. Подготовительный этап Для каждого из столбцов j исходной матрицы Сij эффективности отыскивается
- 15. Венгерский метод. Алгоритм в каждой строке матрицы С* отыскивается минимальный элемент ti, который вычитается из всех
- 16. Венгерский метод. Алгоритм Образуем первоначальную систему независимых нулей. С этой целью отыскиваем и помечаем звездочкой произвольный
- 17. Венгерский метод. Алгоритм 2. Подсчитываем число независимых нулей (k) полученной матрицы 3. Если k = n,
- 18. Венгерский метод. Алгоритм 7. Формируем новые невыделенные нули. Для этого среди невыделенных элементов матрицы С* выбираем
- 19. Венгерский метод. Алгоритм Для этого, начиная с нуля со штрихом, в одной строке с которым нет
- 20. Венгерский метод. Алгоритм 11. Меняем знаки у нулей в построенной цепочке, причем звездочки уничтожаем, а штрихи
- 21. Венгерский метод. Пример Задана исходная матрица эффективности где Ai ‑ рабочие; Вi ‑ различные виды работ.
- 22. Венгерский метод. Пример Подготовительный этап. Отыскиваем максимальные элементы в каждом из столбцов матрицы С Вычитаем каждый
- 23. Венгерский метод. Пример Подготовительный этап. Отыскиваем минимальные элементы в каждой из строк матрицы С*: A1 =0,
- 24. Венгерский метод. Пример Образуем первоначальную систему независимых нулей, отмечая их звездочками: Первая итерация. Подсчитываем число независимых
- 25. Венгерский метод. Пример Просматриваем нули первого столбца. Нуль на месте C31 выделять нельзя, так как он
- 26. Венгерский метод. Пример Построение цепочки нулей начинаем с последнего выделенного нуля со штрихом. Такой нуль находится
- 27. Венгерский метод. Пример Подсчитываем число независимых нулей (со звездочками). Так как k = 4 = n,
- 28. Венгерский метод. Пример Наложив этот план на значения исходной матрицы эффективности С, получим соответствующее значение целевой
- 29. Вопрос 2 Нелинейное программирование в ИТАП
- 30. Нелинейное программирование Математическая формулировка: определить такие значения переменных X* = {x*1, x*2, ..., х*n}, удовлетворяющие системе
- 31. Нелинейное программирование. Прикладные задачи Задача выбора оптимальных параметров технологического процесса В нелинейном программировании существует несколько методов
- 32. Вопрос 3 Целочисленное программирование в ИТАП
- 33. Целочисленное программирование все или часть переменных принимают только целочисленные значения Математическая формулировка: В общем виде задача
- 34. Целочисленное программирование
- 35. 1 Метод отсечения заключается в последовательном добавлении к исходной задаче линейных ограничений, которым удовлетворяют все целочисленные
- 36. 2 Комбинаторный метод решение задачи сводится к направленному перебору. Наиболее известными из этой группы являются метод
- 37. 3 Приближенный метод используются при решении задач большой размерности, для которых точные методы малоэффективны. Наиболее известным
- 38. 4 Метод статистической оптимизации (случайного поиска ) При использовании метода случайного поиска (метод Монте-Карло) производят случайный
- 39. Прикладные задачи • задача о назначениях, • задача о кратчайшем пути через n точек (задача о
- 40. Вопрос 4 Динамическое программирование в ИТАП
- 41. Динамическое программирование Процесс поиска решения разбивается на отдельные этапы (шаги). На каждом шаге принимается одно из
- 42. Динамическое программирование. Пример Определить кратчайший путь между точками X1 и X2, соединенными сложной сетью (рис.). Длина
- 43. Динамическое программирование. Решение 1. Разобьем весь процесс поиска на этапы. 2. Сначала найдем кратчайшие пути, соединяющие
- 44. Динамическое программирование. Решение Математически в примере решается следующее выражение: где Q – управляющий оператор, с помощью
- 45. Динамическое программирование Динамическое программирование является универсальным методом отыскания глобального экстремума в любых математических моделях, для которых
- 46. Вопросы по прочитанному материалу?
- 48. Скачать презентацию