Слайд 1
Структура задач и положения линейного программирования
Презентация
Презентация на тему «Структура задач и положения линейного программирования»
10 слайдов · сгенерирована в Презентоше — бесплатном генераторе презентаций
Слайд 2
Общая постановка
Линейное программирование изучает задачи, в которых нужно найти максимум или минимум линейной целевой функции при линейных ограничениях и неотрицательных переменных. Такая модель включает три элемента: целевую функцию, систему ограничений и область допустимых решений. Например, в канонической форме ограничения задаются равенствами, а в основной форме могут содержать неравенства.
Слайд 3
Целевая функция
Целевая функция показывает, какой результат требуется улучшить, например прибыль, затраты или расход ресурсов. Для задачи с переменными \(x_1, x_2, \dots, x_n\) она записывается как линейная комбинация с коэффициентами \(c_1, c_2, \dots, c_n\). В экономических задачах именно эта функция позволяет сравнивать разные планы по одному численному критерию.
Слайд 4
Область допустимых решений
Допустимым называют решение, которое удовлетворяет всем ограничениям задачи. Множество таких решений образует область допустимых решений, внутри которой и ищут оптимальный план. Если область пустая, задача не имеет решения, а если целевая функция не ограничена, оптимум не существует.
Слайд 5
Базисные решения
Для симплекс-метода особенно важны базисные допустимые решения, так как именно среди них обычно ищется оптимум. Они соответствуют вершинам многогранника допустимых решений и позволяют последовательно переходить от одного плана к другому. В типичной задаче с \(m\) уравнениями выбирают \(m\) базисных переменных, а остальные приравнивают нулю.
Слайд 6
Симплекс-алгоритм
Симплекс-алгоритм начинается с нахождения начального базисного допустимого решения и построения симплекс-таблицы. Затем выполняют последовательные преобразования, переводя задачу от одного плана к другому с более выгодным значением целевой функции. Переходы продолжаются до тех пор, пока не будет найден оптимальный план или не выяснится, что решения нет.
Слайд 7
Симплекс-таблица
Симплекс-таблица позволяет удобно записывать коэффициенты ограничений, свободные члены и параметры целевой функции. В ней видно, какие переменные входят в базис, а какие остаются свободными. После каждого шага таблица пересчитывается, чтобы отразить новый базисный план и проверить его качество.
Слайд 8
Критерий оптимальности
Критерий оптимальности показывает, можно ли улучшить текущий базисный допустимый план. Для задачи максимизации в строке оценок не должно оставаться положительных улучшений, а для задачи минимизации — отрицательных, в зависимости от принятой формы записи. Если критерий выполнен, текущий план считается оптимальным и дальнейшее улучшение не требуется.
Слайд 9
Выбор переменной
Если план не оптимален, выбирают переменную, которая должна войти в базис и улучшить значение целевой функции. Обычно это переменная с наилучшей оценкой в строке критериев, потому что именно она дает наиболее выгодное направление изменения плана. Затем определяют переменную, которая выйдет из базиса, чтобы сохранить допустимость решения.
Слайд 10
Заключение
Линейное программирование сводит практические задачи к поиску оптимума линейной функции при системе ограничений. Симплекс-алгоритм решает такие задачи поэтапно, проверяя критерий оптимальности и улучшая неоптимальный базисный допустимый план. Его эффективность основана на переходе между вершинами области допустимых решений и строгом контроле допустимости на каждом шаге.
Нужна такая же презентация, но по своей теме?
Презентоша сгенерирует презентацию по любой теме за минуту — бесплатно.
Создать презентациюРазделы:Программирование и ИТ