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

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

Задачи этого раздела делят на две категории: прямые и обратные. Решение прямых задач исследования операций составляет предмет математического моделирования, а решение обратных задач – предмет математического программирования. Слово «программирование» здесь следует понимать в смысле планирования решения задачи, но не разработки программ для ЭВМ.

При математическом моделировании определяют выходные характеристики системы при заданных параметрах системы и входных воздействиях.

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

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

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

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

Исторически сложилась следующая терминология для описания задач математического программирования.

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

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

Таким образом, задачей математического программирования является определение на заданном комплексе условий таких значений параметров x_i, при

которых целевая функция принимает максимальное или минимальное значение:

, (29)

где - вектор переменных.

Если целевая функция Zлинейно зависит от элементов решения x₁, x₂, … x_n

и ограничения, накладываемые на эти элементы, представляют собой линейные

неравенства или равенства относительно x₁, x₂, … x_n,то имеет место линейное программирование. Решение такой задачи не представляет затруднений, методы решений хорошо разработаны, имеются стандартные программы. Однако в случае целочисленного программирования, когда значения искомых переменных должны быть целыми числами, решение существенно затрудняется.

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

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

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

Дата добавления: 2014-01-06