Методы математического программирования используют

Общая характеристика методов математического программирования

Методы математического программирования относятся к численным методам поиска оптимальных решений, которые позволяют найти решение только для конкретных значений параметров. Такими методами являются методы линейного, нелинейного дискретного, стохастического и динамического программирования.

Если функции эффективности и ограничения линейны, а операция одноэтапная, то можно применить один из методов линейного программирования. Данные методы используют одну и ту же идею: задается некоторое неоптимальное решение (начальный план), а затем оптимальное решение находится путем изменения начального плана в направлении приближения к оптимальному. Линейное программирование является в настоящее время наиболее разработанной ветвью математического программирования.

При нелинейном характере хотя бы одного компонента математической модели (целевой функции или ограничений) применяют методы нелинейного программирования. Общих методов этого типа пока не существует, за исключением случая квадратичной зависимости между критерием и параметрами при линейных ограничениях.

Некоторые математические модели могут содержать условие дискретности значений параметров (например, по своей физической сущности параметры должны быть только целыми числами). Решение таких задач осуществляется с применением методов дискретного (целочисленного) программирования.

Отыскание решений в операциях, которые носят многоэтапный характер, проводится с применением метода динамического программирования. Его сущность состоит в том, что оптимальное решение отыскивается не за все этапы одновременно, а последовательно, от этапа к этапу. Идея оптимизации управления на каждом отдельном этапе использовалась давно, но без учета будущего. При динамическом программировании оптимизация каждого этапа проводится с учетом всех последующих этапов.

Если операция носит случайный характер и приходится иметь дело со случайными величинами и функциями, то для ее исследования используются методы стохастического программирования.

Методы решения задач линейного программирования

Эти методы используются для решения однокритериальных задач оптимизации, целевая функция которых отвечает условиям детерминированности и линейности, а на значения переменных накладываются линейные ограничения. Линейность предполагает наличие двух свойств: пропорциональности и аддитивности. Пропорциональность означает, что вклад каждой

переменной в целевую функцию прямо пропорционален величине этой переменной, а аддитивность заключается в представлении целевой функции в виде суммы вкладов от различных переменных.

К особенностям использования данных методов относится то, что оптимальному решению всегда соответствует одна из экстремальных точек пространства решений (это является следствием такого важного свойства задач линейного программирования, как выпуклость пространства решений).

Поэтому вычислительная схема представляет собой упорядоченный процесс перехода от исходной экстремальной точки к некоторой смежной экстремальной точке, продолжающийся до тех пор, пока существуют точки с лучшим (большим или меньшим) значением целевой функции.

Основным методом решения задач линейного программирования является симплекс-метод и его модификации, ориентированные на особенности решаемых задач (см. [6.9; 6.55; 6.57]).

Источник

Лекция 1 Математическое программирование

Математическое программирование – это область математики, разработанная теории и численные методы, решением многомерных, экстремальных задач с ограничениями.

Арифметические операции выполняет компьютер, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.

Функцию, экстремальное значение которой необходимо найти в условиях экономических возможностей, называют целевой или показателем эффективности (критерий оптимальности).

Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи – это отражение оригиналов в виде функций, уравнений, неравенств и др. математических объектов. Модель задачи математического программирования включает в себя:

1. совокупность неизвестных величин х=(х₁,х₂. х_n), их называют планом задачи.
2. Целевую функцию (показатель эффективности, критерий оптимальности). Целевая функция позволяет выбирать наилучший вариант из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение Z=Z(x).
3. Условие или систему ограничений, которая накладывается на неизвестные величины. Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, а также из необходимости удовлетворения насущных потребностей из условий производительных и технологических процессов.

Ограниченными является не только материальные, финансовые и трудовые ресурсы, таковыми могут быть возможности технологического, технического и в целом научного потенциала, нередко потребности превышают возможности их удовлетворения. Совокупность ограничений, записанных в виде уравнений и неравенств, образует область допустимых решений (область экономических возможностей).

Из этих экономических или физических соображений на план задачи или некоторые его компоненты, как правило, накладывается условие отрицательности. Так же иногда на план задачи накладывается условие целочисленности. План задачи, удовлетворяющий системе ограничений, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным.

Из этих экономических или физических соображений на план задачи или некоторые его компоненты, как правило, накладывается условие отрицательности. Так же иногда на план задачи накладывается условие целочисленности. План задачи, удовлетворяющий системе ограничений, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным.

х _i => 0 , Z(x*) = Z*(оптимальный план)

Классификация методов математического программирования.

В зависимости от особенностей целевой функции, а также функций, задающей ограничения, задача математического программирования делится на ряд типов:

1. Если целевая функция и функции системы ограничений, если они линейные относительно входящих неизвестных x_i ,то такой раздел называется линейным. Методы и модели линейного программирования широко используются при оптимизации процессов во всех областях народного хозяйства. При разработке производственной программы предприятия, при определении наилучшего ассортимента выпускаемой продукции, задачах перспективного, текущего и оперативного планирования. Особенно широкое применение методов и моделей линейного программирования получили при решении экономии ресурсов производственно-транспортных и др. задач. Начало линейного программирования положил Канторович.

2. Если в задаче математического программирования целевая функция или одна из функций системы ограничений не линейна, то такой раздел называется нелинейным. Методы нелинейного программирования используются при расчете экономически-выгодных партий запуска деталей в производство при распределении ограниченных ресурсов, размеров запасов, размещения производительных сил.

3. Если на все или некоторые переменные накладывается условия дискретности, например, целочисленности, также задачи рассматриваются в дискретном программировании. Методами целочисленного программирования решаются задачи с логическими условиями, с разрывной целевой функцией. Это задачи о контейнерных перевозках, о маршрутизации, о расширении производственно-складской структур.

Z( x )=∑ Z_j (x_j ) – аддитивный вид

Z( x )= П Z _j(x _j ) – мультипликативный

При таком представлении целевой функции процесс выработки решений имеет многошаговый характер, параметры целевой функции или системы ограничения изменяются во времени, также задачи решаются методами динамического программирования. Методами динамического программирования могут решаться задачи планирования, управления производства, поставками и запасами, в условиях изменения спроса, распределение ограниченных ресурсов, в частности, размещение капитальных вложений, замена оборудования. В перечисленных моделях математического программирования предполагается, что вся информация о протекаемых процессах заранее известна и достоверна. Также методы называются детерминированными. Или методы обоснования решений в условиях определенности.

Если параметры, входящие в функцию цели или ограничения задачи являются случайными, недостоверными или если приходится принимать решения в условиях риска неполной или недостоверной информации, то говорят о проблеме стохастической оптимизации, а раздел называют стохастическим программированием. К нему относятся модели и методы выработки решений в условиях конфликтных ситуаций. В условиях неполной информации (экстремальной оценки), либо в условиях риска.

Позднее появились другие типы задач, учитывая специфику целевой функции и систему ограничений, в связи с чем возникли параметрическая.

К математическому программированию относятся методы экстремальных задач с бесконечным числом переменных.

Задачи математического программирования с одной целевой функцией решается методами скалярной оптимизации, однако в реальных задачах зачастую приходится учитывать несколько целевых функций. Также задачи относятся к векторной оптимизации. Задачи многокритериального подхода.

Источник

§ 3. Классификация методов математического программирования.

Математическое программирование предполагает построение алгоритмов решения задач оптимизации (задач оптимального планирования) . В зависимости от свойств целевой функции и ограничений математическое программирование подразделяестся на: линейное; нелинейное (нелинейное при линейных ограничениях: выпуклое; сепарабельное; квадратичное; геометрическое). Это разделение неслучайно. Оно определяется отсутствием универсальных методов решения задач нелинейного программи­рования, для которого разработаны лишь эффективные методы решения отдельных классов задач. Задачи оптимизации связаны с вопросами эффективного использования или распределения ограниченных ресурсов для достижения желаемых целей. Характерной чертой задач оптимизации является большое число реше­ний, удовлетворяющих условиям задачи. Выбор конкретного решения, как «наилучшего», зависит от функции цели (показатель качества, критерий оптимальности, функция качества, критерий эффективности и т.д. — си­нонимы). Задача, допускающая лишь одно решение_, не требует оптимиза­ции.

В общем плане, существующие методы математического программирова­ния подразделяются на аналитические и численные

Аналитические методы включают в себя классические методы дифференциального и вариационного исчисления. Эти методы за­ключаются

в определении экстремума функции f(х) путем нахож­дения тех значений х, которые обращают в нуль производные f(х) по х (здесь х n-мерный вектор). В случае поиска экстремума при наличии ограничений применяются такие методы, как метод множителей Лагранжа и метод ограниченных вариаций. Однако для решения больших задач чаще всего приме­нение аналитических методов невозможно.

Численные методы используют предшествующую информацию для построения улучшенных решений задачи при помощи итерационных процедур. Численные методы применяются для решения задач, ко­торые не могут быть решены аналитически. Численные методы включают методы регулярного (т.е. равномерного) и слу­чайного поиска. Задача поиска заключается в определении пос­ледовательности воздействий, доставляющих максимум или мини­мум заданному целевому функционалу.

Решение задач оптимизации численными методами представляет собой два этапа:

Первый этап — сбор информации об объекте;

Алгоритм сбора информации должен быть

1. прост;

1. должен обеспечивать процедуру решения наиболее полной информацией об объекте;
2. должен учитывать априорную информацию, полученную ранее, т.е. иметь возможность самообучаться.

Источник