Лекция 1 Математическое программирование
Математическое программирование – это область математики, разработанная теории и численные методы, решением многомерных, экстремальных задач с ограничениями.
Арифметические операции выполняет компьютер, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.
Функцию, экстремальное значение которой необходимо найти в условиях экономических возможностей, называют целевой или показателем эффективности (критерий оптимальности).
Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи – это отражение оригиналов в виде функций, уравнений, неравенств и др. математических объектов. Модель задачи математического программирования включает в себя:
совокупность неизвестных величин х=(х1,х2,..,хn), их называют планом задачи.
Целевую функцию (показатель эффективности, критерий оптимальности). Целевая функция позволяет выбирать наилучший вариант из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение Z=Z(x).
Условие или систему ограничений, которая накладывается на неизвестные величины. Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, а также из необходимости удовлетворения насущных потребностей из условий производительных и технологических процессов.
Ограниченными является не только материальные, финансовые и трудовые ресурсы, таковыми могут быть возможности технологического, технического и в целом научного потенциала, нередко потребности превышают возможности их удовлетворения. Совокупность ограничений, записанных в виде уравнений и неравенств, образует область допустимых решений (область экономических возможностей).
Li(x1...xn) , {<….>}bi , где i=1,…,m.
Из этих экономических или физических соображений на план задачи или некоторые его компоненты, как правило, накладывается условие отрицательности. Так же иногда на план задачи накладывается условие целочисленности. План задачи, удовлетворяющий системе ограничений, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным.
Из этих экономических или физических соображений на план задачи или некоторые его компоненты, как правило, накладывается условие отрицательности. Так же иногда на план задачи накладывается условие целочисленности. План задачи, удовлетворяющий системе ограничений, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным.
х i => 0 , Z(x*) = Z*(оптимальный план)
Классификация методов математического программирования.
В зависимости от особенностей целевой функции, а также функций, задающей ограничения, задача математического программирования делится на ряд типов:
1. Если целевая функция и функции системы ограничений, если они линейные относительно входящих неизвестных xi ,то такой раздел называется линейным. Методы и модели линейного программирования широко используются при оптимизации процессов во всех областях народного хозяйства. При разработке производственной программы предприятия, при определении наилучшего ассортимента выпускаемой продукции, задачах перспективного, текущего и оперативного планирования. Особенно широкое применение методов и моделей линейного программирования получили при решении экономии ресурсов производственно-транспортных и др. задач. Начало линейного программирования положил Канторович.
2. Если в задаче математического программирования целевая функция или одна из функций системы ограничений не линейна, то такой раздел называется нелинейным. Методы нелинейного программирования используются при расчете экономически-выгодных партий запуска деталей в производство при распределении ограниченных ресурсов, размеров запасов, размещения производительных сил.
3. Если на все или некоторые переменные накладывается условия дискретности, например, целочисленности, также задачи рассматриваются в дискретном программировании. Методами целочисленного программирования решаются задачи с логическими условиями, с разрывной целевой функцией. Это задачи о контейнерных перевозках, о маршрутизации, о расширении производственно-складской структур.
Z( x )=∑ Zj (xj ) – аддитивный вид
Z( x )= П Z j(x j ) – мультипликативный
При таком представлении целевой функции процесс выработки решений имеет многошаговый характер, параметры целевой функции или системы ограничения изменяются во времени, также задачи решаются методами динамического программирования. Методами динамического программирования могут решаться задачи планирования, управления производства, поставками и запасами, в условиях изменения спроса, распределение ограниченных ресурсов, в частности, размещение капитальных вложений, замена оборудования. В перечисленных моделях математического программирования предполагается, что вся информация о протекаемых процессах заранее известна и достоверна. Также методы называются детерминированными. Или методы обоснования решений в условиях определенности.
Если параметры, входящие в функцию цели или ограничения задачи являются случайными, недостоверными или если приходится принимать решения в условиях риска неполной или недостоверной информации, то говорят о проблеме стохастической оптимизации, а раздел называют стохастическим программированием. К нему относятся модели и методы выработки решений в условиях конфликтных ситуаций. В условиях неполной информации (экстремальной оценки), либо в условиях риска.
Позднее появились другие типы задач, учитывая специфику целевой функции и систему ограничений, в связи с чем возникли параметрическая.
К математическому программированию относятся методы экстремальных задач с бесконечным числом переменных.
Задачи математического программирования с одной целевой функцией решается методами скалярной оптимизации, однако в реальных задачах зачастую приходится учитывать несколько целевых функций. Также задачи относятся к векторной оптимизации. Задачи многокритериального подхода.