Содержание
- 2. Метод перебора (метод равномерного поиска, перебор по сетке) — простейший из методов поиска значений действительно-значных функций
- 3. Методы перебора Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа
- 4. Методы перебора Самым известным из методов направленного перебора является метод ветвей и границ (branch&bound algorithm). Впервые
- 5. Методы перебора Методы направленного перебора предполагают аппроксимацию или разбиение задачи смешанной дискретной оптимизации на несколько подзадач,
- 6. Практическое применение алгоритмов направленного перебора
- 7. Линейное программирование — область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или
- 8. Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования. Симплекс-метод был
- 9. Сущность метода Симплекс-метод – универсальный метод решения задач линейного программирования. Суть метода: целенаправленный перебор решений, соответствующих
- 10. Сущность метода Метод применим к любой задаче линейного программирования в канонической форме: Количество неизвестных (n) в
- 11. Основные этапы решения задачи симплекс-методом Приведение задачи к каноническому виду. Приведение задачи к допустимому виду (выделение
- 12. 1. Приведение задачи к каноническому виду Для приведения задачи к каноническому виду необходимо добавить в каждое
- 13. 2. Приведение задачи к допустимому виду Для того, чтобы привести систему уравнений к допустимому виду, необходимо
- 14. 2. Приведение задачи к допустимому виду Неизвестные, которые выражаются через остальные неизвестные, называются базисными, а весь
- 15. 2. Преобразование целевой функции Далее необходимо преобразовать целевую функцию, исключив из нее базисные переменные. Для исключения
- 16. 2. Преобразование целевой функции Получим: или где .
- 17. 3. Нахождение первого допустимого базисного решения Приравняем свободные переменные к нулю и найдем значения базисных переменных.
- 18. 3. Основная теорема симплекс-метода Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное
- 19. 4. Проверка решения на оптимальность Допустимое базисное решение системы ограничений является оптимальным реше-нием задачи линейного программирования
- 20. 5. Поиск другого допустимого базисного решения Если полученное допустимое базисное решение системы ограничений не является оптимальным,
- 21. Основные этапы решения задачи симплекс-методом Приведение задачи к каноническому виду. Приведение задачи к допустимому виду (выделение
- 22. Симплекс-таблица Пусть задача приведена к виду:
- 23. Симплекс-таблица: развернутый вариант
- 24. Симплекс-таблица: сокращенный вариант
- 25. Симплекс-таблица: алгоритм решения 1. Просматривается последняя строка таблицы, среди коэффициентов этой строки (исключая столбец свободных членов)
- 26. Симплекс-таблица: алгоритм решения 2. Столбец таблицы, соответствующий выбранному отрицательному коэффици-енту в последней строке называется ключевым. В
- 27. Симплекс-таблица: алгоритм решения 3. Среди положительных коэффициентов ключевого столбца выбирается тот, для которого абсолютная величина отношения
- 28. Симплекс-таблица: алгоритм решения 4. Базисная переменная, отвечающая строке ключевого элемента, должна быть переведена в разряд свободных,
- 29. Симплекс-таблица: алгоритм решения 4а) в обозначениях строк и столбцов переменная, вводимая в базис и переменная, выводимая
- 30. Симплекс-таблица: алгоритм решения 4д) все остальные элементы таблицы, включая строку оценок и столбец свободных членов, пересчитываем
- 31. Симплекс-таблица: алгоритм решения 5. Новая симплекс-таблица отвечает новому допустимому базисному решению. Проверяем новое решение на оптимальность,
- 32. Пример Для производства четырех видов изделий A1 , A2 , A3 , A4 завод должен использовать
- 33. Пример Математическая модель задачи: .
- 34. Пример Приведение задачи к каноническому виду: Примем за базисные переменные x5, x6, x7. Тогда первое опорное
- 35. Пример. 1 шаг симплекс-метода, развернутая таблица.
- 36. Пример. 1 шаг симплекс-метода, сокращенная таблица.
- 37. Пример. 1 шаг симплекс-метода Базисное решение (0; 0; 0; 0; 1000; 600; 150). Поиск ключевой строки:
- 38. Пример. 2 шаг симплекс-метода.
- 39. Пример. 2 шаг симплекс-метода Базисное решение (150; 0; 0; 0; 250; 0; 0). Определение ключевой строки:
- 40. Пример. 3 шаг симплекс-метода.
- 41. Пример. 3 шаг симплекс-метода Базисное решение (150; 0; 0; 0; 250; 0; 0). Определение ключевой строки:
- 42. Пример. 4 шаг симплекс-метода.
- 44. Скачать презентацию