- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Линейное программирование презентация
Содержание
- 1. Линейное программирование
- 2. Примеры задач линейного программирования
- 3. Для изготовления двух видов продукции
- 4. Изучение рынка сбыта показало, что объем выпуска
- 5. Решение Введем переменные Задача
- 6. Решение Ограничения Задача о
- 7. Математическая модель Задача о распределении ресурсов
- 8. В дневной рацион питания цыплят включают
- 9. Решение Введем переменные Задача
- 10. Решение Ограничения Задача о
- 11. Математическая модель Задача о рационе (о диете)
- 12. Основные понятия
- 13. Термин линейное программирование линейное означает: ищется экстремальное
- 14. Задача линейного программирования в общем виде (ЗЛП)
- 15. Каноническая задача линейного программирования
- 16. Каноническая задача линейного программирования В канонической задаче
- 17. В канонической задаче: 1) целевая функция →
- 18. В канонической задаче: 1) целевая функция →
- 19. В канонической задаче: 1) целевая функция →
- 20. В канонической задаче: 1) целевая функция →
- 21. Теоретическое обоснование Теорема Если целевая функция принимает
- 22. Решение достигается в вершине
- 23. Графический метод решения
- 24. Графическое решение
- 25. Графическое решение Алгоритм решения Построить на плоскости
- 26. Задача о распределении ресурсов
- 27. Задача о распределении ресурсов С – оптимальный план
- 28. Задача о распределении ресурсов Нахождение С Координаты
- 29. Симплекс-метод Симплекс ─ n-мерный многогранник
- 30. Основные теоретические сведения Система линейных уравнений ─
- 31. Основные теоретические сведения Базисное решение ─ решение
- 32. Основная теорема ЛП Если каноническая задача линейного
- 33. Пример
- 34. Пример Опорный план:
- 35. Пример Проверка оптимальности Приведение задачи к специальному
- 36. Пример Увеличиваем
- 37. Пример Проверка оптимальности Приведение задачи к специальному
- 38. Пример Табличная запись решения I
- 39. Пример Табличная запись решения II
- 40. Пример Табличная запись решения III
- 41. Специальная задача ЛП Базисные переменные Свободные переменные
- 42. Симплексная таблица Опорное решение
- 43. Алгоритм симплекс-метода Подготовительный этап 1. Приведение к
- 44. Алгоритм симплекс-метода Основной этап 1. Проверка оптимальности
- 45. Алгоритм симплекс-метода Основной этап 3.Выбор ведущего столбца
- 46. Алгоритм симплекс-метода Основной этап 5. Замена базисной
- 47. Алгоритм симплекс-метода Основной этап 7. Преобразование ведущей
- 48. Алгоритм симплекс-метода Основной этап 8. Преобразование остальных элементов таблицы по правилу прямоугольника Новое значение
- 49. Алгоритм симплекс-метода Основной этап
- 50. Пример (распределении ресурсов) Каноническая форма задачи: Она же ─ специальная! Исходная модель
- 51. Пример (распределении ресурсов) Симплекс-таблица Задача разрешима План не оптимальный
- 52. Пример (распределении ресурсов) Симплекс-таблица Ведущий элемент Преобразованная таблица План не оптимальный Задача разрешима
- 53. Пример (распределении ресурсов) Симплекс-таблица Ведущий элемент Преобразованная таблица План оптимальный!
Слайд 3
Для изготовления двух видов продукции
А и В используют три вида
Задача о распределении ресурсов
Слайд 4Изучение рынка сбыта показало, что объем выпуска изделий А не должен
Задача о распределении ресурсов
Необходимо составить такой план производства продукции, при котором выручка от ее реализации будет максимальной
Слайд 5
Решение
Введем переменные
Задача о распределении ресурсов
х1 – число единиц продукции А,
х2 – число единиц продукции В, запланированных к производству
Выручка:
Цель:
Слайд 6
Решение
Ограничения
Задача о распределении ресурсов
1) Условие неотрицательности:
2) На запас сырья 1:
3)
4) На запас сырья 3:
5) Соотношение между 1 и 2:
Слайд 8
В дневной рацион питания цыплят включают два продукта П1 и П2.
Стоимость 1 ед. продукта П1 составляет 2 ден. ед., а продукта П2 – 4 ден. ед.
Задача о рационе (о диете)
Определить оптимальный рацион питания, стоимость которого будет наименьшей
Слайд 9
Решение
Введем переменные
Задача о рационе (о диете)
х1 – число единиц продукта
х2 – число единиц продукта П2, входящего в дневной рацион
Стоимость дневного рациона :
Цель:
Слайд 10
Решение
Ограничения
Задача о рационе (о диете)
1) Условие неотрицательности:
2) Ограничение на максимальное
3) Ограничения на минимальное содержание питательных веществ:
Слайд 13Термин линейное программирование
линейное означает: ищется экстремальное значение (min или max) линейной
Линейное программирование (ЛП) — это метод оптимизации моделей, в которых целевые функции и ограничения линейны
Терминология
Слайд 14Задача линейного программирования в общем виде (ЗЛП) – это задача о
Общая задача линейного программирования
Допустимый план – любой элемент допустимого множества
Оптимальный план – допустимый план, являющийся решением ЗЛП
Слайд 16Каноническая задача линейного программирования
В канонической задаче ЛП (КЗЛП):
1) находится максимум целевой
2) все ограничения имеют вид уравнений
3) все переменные неотрицательны
Слайд 17В канонической задаче:
1) целевая функция → max
2) все ограничения - уравнения
3)
Целевая функция F → min
Сведение общей ЗЛП к канонической
Решение. Переходим к (-F) → max (переходим к противоположной функции)
Слайд 18В канонической задаче:
1) целевая функция → max
2) все ограничения - уравнения
3)
Сведение общей ЗЛП к канонической
В ограничениях есть неравенство
a1x1+a2x2 ≥ b
Решение. Вводим новую переменную х3 ≥ 0: a1x1+a2x2 - х3 = b
Слайд 19В канонической задаче:
1) целевая функция → max
2) все ограничения - уравнения
3)
Сведение общей ЗЛП к канонической
Есть не положительные переменные
Решение.
Слайд 20В канонической задаче:
1) целевая функция → max
2) все ограничения - уравнения
3)
Сведение общей ЗЛП к канонической
Вывод
Каждую задачу линейного программирования можно привести к канонической форме
Слайд 21Теоретическое обоснование
Теорема
Если целевая функция принимает максимальное значение в некоторой точке допустимого
Вывод
Оптимальное решение следует искать в вершинах допустимого множества
Слайд 22Решение достигается в вершине
Целевая
функция не ограничена
Бесконечное
множество
решений
Варианты решения ЗЛП
Слайд 25Графическое решение
Алгоритм решения
Построить на плоскости допустимое множество
Найти градиент целевой функции
Найти оптимальный план
Построить прямую – линию уровня целевой функции
Слайд 28Задача о распределении ресурсов
Нахождение С
Координаты С – из системы:
Ответ: С(3;2)
Оптимальное значение
Оптимальный
Слайд 30Основные теоретические сведения
Система линейных уравнений ─ система с базисом, если в
Базисная переменная уравнения: входит в уравнение с коэффициентом +1 и отсутствует
в остальных уравнениях системы
Остальные переменные свободные
Специальная задача ЛП ─ каноническая задача ЛП, в которой:
все правые части
уравнений неотрицательны;
система уравнений ─
система с базисом;
в целевой функции
нет базисных переменных
Слайд 31Основные теоретические сведения
Базисное решение ─ решение системы, соответствующее нулевым значениям свободных
Опорный план ─ базисное решение, удовлетворяющее условию неотрицательности.
Опорный план (решение) ─ вершина допустимого множества.
Слайд 32Основная теорема ЛП
Если каноническая задача линейного программирования разрешима, то её оптимальный
Симплекс-метод ─ метод перебора опорных решений.
Слайд 34Пример
Опорный план:
Значение целевой функции
План не оптимальный!
Увеличиваем
Слайд 35Пример
Проверка оптимальности
Приведение задачи к специальному виду:
Выражение целевой функции через свободные переменные
План
Слайд 37Пример
Проверка оптимальности
Приведение задачи к специальному виду:
Выражение целевой функции через свободные переменные
Слайд 38Пример
Табличная запись решения
I этап
1. Самое маленькое отрицательное число в
2. Самое маленькое отношение свободного члена к положительному числу в столбце
Слайд 39Пример
Табличная запись решения
II этап
1. Самое маленькое отрицательное число в
2. Самое маленькое отношение свободного члена к положительному числу в столбце
Слайд 43Алгоритм симплекс-метода
Подготовительный этап
1. Приведение к каноническому виду
2. Приведение к специальному виду
3.
Слайд 44Алгоритм симплекс-метода
Основной этап
1. Проверка оптимальности (все ли числа в последней строке
2. Проверка на неразрешимость (есть ли столбец со всеми отрицательными числами)
Слайд 45Алгоритм симплекс-метода
Основной этап
3.Выбор ведущего столбца (по наименьшему отрицательному числу в последней
4.Выбор ведущей строки (по наименьшему отношению свободных членов к положительным числам ведущего столбца)
Ведущий элемент
Ведущий элемент
Слайд 46Алгоритм симплекс-метода
Основной этап
5. Замена базисной переменной: переменная ведущего столбца становится базисной,
6. Преобразование ведущего элемента: вместо него записывается его обратная величина
Слайд 47Алгоритм симплекс-метода
Основной этап
7. Преобразование ведущей строки: делим на ведущий элемент все
8. Преобразование ведущего столбца: делим на ведущий элемент со знаком минус все остальные элементы
Слайд 48Алгоритм симплекс-метода
Основной этап
8. Преобразование остальных элементов таблицы по правилу прямоугольника
Новое
Слайд 50Пример (распределении ресурсов)
Каноническая форма задачи:
Она же ─ специальная!
Исходная модель
Слайд 52Пример (распределении ресурсов)
Симплекс-таблица
Ведущий элемент
Преобразованная таблица
План не оптимальный
Задача разрешима
Слайд 53Пример (распределении ресурсов)
Симплекс-таблица
Ведущий элемент
Преобразованная таблица
План оптимальный!
