Лекция 1 Математическое программирование
Математическое программирование – это область математики, разработанная теории и численные методы, решением многомерных, экстремальных задач с ограничениями.
Арифметические операции выполняет компьютер, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.
Функцию, экстремальное значение которой необходимо найти в условиях экономических возможностей, называют целевой или показателем эффективности (критерий оптимальности).
Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи – это отражение оригиналов в виде функций, уравнений, неравенств и др. математических объектов. Модель задачи математического программирования включает в себя:
- совокупность неизвестных величин х=(х1,х2. хn), их называют планом задачи.
- Целевую функцию (показатель эффективности, критерий оптимальности). Целевая функция позволяет выбирать наилучший вариант из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение Z=Z(x).
- Условие или систему ограничений, которая накладывается на неизвестные величины. Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, а также из необходимости удовлетворения насущных потребностей из условий производительных и технологических процессов.
Ограниченными является не только материальные, финансовые и трудовые ресурсы, таковыми могут быть возможности технологического, технического и в целом научного потенциала, нередко потребности превышают возможности их удовлетворения. Совокупность ограничений, записанных в виде уравнений и неравенств, образует область допустимых решений (область экономических возможностей).
Из этих экономических или физических соображений на план задачи или некоторые его компоненты, как правило, накладывается условие отрицательности. Так же иногда на план задачи накладывается условие целочисленности. План задачи, удовлетворяющий системе ограничений, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным.
Из этих экономических или физических соображений на план задачи или некоторые его компоненты, как правило, накладывается условие отрицательности. Так же иногда на план задачи накладывается условие целочисленности. План задачи, удовлетворяющий системе ограничений, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным.
х i => 0 , Z(x*) = Z*(оптимальный план)
Классификация методов математического программирования.
В зависимости от особенностей целевой функции, а также функций, задающей ограничения, задача математического программирования делится на ряд типов:
1. Если целевая функция и функции системы ограничений, если они линейные относительно входящих неизвестных xi ,то такой раздел называется линейным. Методы и модели линейного программирования широко используются при оптимизации процессов во всех областях народного хозяйства. При разработке производственной программы предприятия, при определении наилучшего ассортимента выпускаемой продукции, задачах перспективного, текущего и оперативного планирования. Особенно широкое применение методов и моделей линейного программирования получили при решении экономии ресурсов производственно-транспортных и др. задач. Начало линейного программирования положил Канторович.
2. Если в задаче математического программирования целевая функция или одна из функций системы ограничений не линейна, то такой раздел называется нелинейным. Методы нелинейного программирования используются при расчете экономически-выгодных партий запуска деталей в производство при распределении ограниченных ресурсов, размеров запасов, размещения производительных сил.
3. Если на все или некоторые переменные накладывается условия дискретности, например, целочисленности, также задачи рассматриваются в дискретном программировании. Методами целочисленного программирования решаются задачи с логическими условиями, с разрывной целевой функцией. Это задачи о контейнерных перевозках, о маршрутизации, о расширении производственно-складской структур.
Z( x )=∑ Zj (xj ) – аддитивный вид
Z( x )= П Z j(x j ) – мультипликативный
При таком представлении целевой функции процесс выработки решений имеет многошаговый характер, параметры целевой функции или системы ограничения изменяются во времени, также задачи решаются методами динамического программирования. Методами динамического программирования могут решаться задачи планирования, управления производства, поставками и запасами, в условиях изменения спроса, распределение ограниченных ресурсов, в частности, размещение капитальных вложений, замена оборудования. В перечисленных моделях математического программирования предполагается, что вся информация о протекаемых процессах заранее известна и достоверна. Также методы называются детерминированными. Или методы обоснования решений в условиях определенности.
Если параметры, входящие в функцию цели или ограничения задачи являются случайными, недостоверными или если приходится принимать решения в условиях риска неполной или недостоверной информации, то говорят о проблеме стохастической оптимизации, а раздел называют стохастическим программированием. К нему относятся модели и методы выработки решений в условиях конфликтных ситуаций. В условиях неполной информации (экстремальной оценки), либо в условиях риска.
Позднее появились другие типы задач, учитывая специфику целевой функции и систему ограничений, в связи с чем возникли параметрическая.
К математическому программированию относятся методы экстремальных задач с бесконечным числом переменных.
Задачи математического программирования с одной целевой функцией решается методами скалярной оптимизации, однако в реальных задачах зачастую приходится учитывать несколько целевых функций. Также задачи относятся к векторной оптимизации. Задачи многокритериального подхода.
Большая Энциклопедия Нефти и Газа
Теория математического программирования включает в себя метод неопределенных множителей Лагранжа и является естественным продолжением и развитием этого метода. В задачах линейного программирования функция цели и ограничения линейны относительно своих аргументов. Рассмотрим два примера задач линейного программирования. [1]
Теория математического программирования стала интенсивно разрабатываться с 40 — х годов нашего столетия, чему в немалой степени содействовало появление и быстрое совершенствование электронной вычислительной техники. [2]
В теории математического программирования важную роль играет теорема Фаркаша, которая будет доказана в конце этого параграфа. Предварительно мы установим некоторые вспомогательные понятия и факты, имеющие, впрочем, и самостоятельное значение. [3]
В теории математического программирования важную роль играет следующая теорема. [4]
В теории математического программирования убедительно показывается, что оптимальному решению соответствует одна из вершин многоугольника допустимых планов, а именно та, для которой общая производительность окажется максимальной. В нашем случае это вершина С. [5]
Наиболее разработанным разделом теории математического программирования является линейное программирование, которое позволяет рассматривать задачу отыскания максимума ( или минимума) линейной функции при наличии ограничений в виде линейных неравенств или уравнений. Эта задача формулируется в общем виде следующим образом. [6]
Эта книга содержит основные положения теории математического программирования и численные методы решения соответствующих экстремальных задач. [7]
В последующих параграфах этой главы рассматриваются основы теории математического программирования : доказываются теоремы существования локальных экстремумов и теоремы существования решений задач математического программирования. [8]
С другой стороны, необходимо использовать максимум того, что создано в теории математического программирования и теории оптимального управления. [9]
Общие методы нахождения экстремума функции при наличии ограничений разрабатываются областью математики, называемой теорией математического программирования . [10]
Книга имеет своей целью дать представление о моделях в математическом программировании; дать основы теории математического программирования и предлагает читателю изложение основных методов решения задач математического программирования. [11]
В качестве основной модели распределения годовой программы по плановым периодам используются различные варианты задач теории математического программирования . В последние годы получено решение задач с учетом длительности производственного цикла изготовления изделий. Это позволило значительно повысить степень адекватности разрабатываемых моделей реальным производственным условиям, когда цикл изготовления деталей, сборочных единиц превышает один календарный период и выходит за его пределы. Использование этих моделей на практике наиболее перспективно. [12]
Постановка задач оптимального синтеза сигналов показывает, что отыскивают экстремум функции или функционала, в том числе и при наличии различных ограничений. Методы решения экстремальных задач разрабатываются в теории математического программирования , их решают, как правило, с учетом того, в каких цепях будут циркулировать сигналы. [13]
Рассмотренные постановки задач оптимального синтеза сигналов показывают, что эти задачи являются задачами на отыскание экстремума функции или функционала, в том числе и при наличии ограничений различного характера. Методы решения таких экстремальных задач разрабатываются в теории математического программирования . Задачи решают, как правило, с учетом того, в каких цепях будут циркулировать синтезируемые сигналы. [14]
Рассмотренные примеры не охватывают всех направлений синтеза сигналов. В теории информации и передачи сигналов изучают и задачи неоптимального синтеза, которые пока еще не решаются регулярными методами теории математического программирования . [15]