Математические методы теории оптимизации. Понятие экстремальных задач, примеры. Основные понятия лп.

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

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

(1) требуется определить max (min) f(x_i..x_n), при условии:

(*) g_i(x_i…x_n) {;=;}b_i

(**) x_j0 jn, где

– f(x_i…x_n) – показатель качества решений (целевая функция) и.

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

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

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

1. Задача (1) является неразрешимой, если она не имеет решения. Это возможно в случае, когда целевая функция не ограничена на допустимом множестве решений. Решить экстремальную задачу – найти ее оптимальное решение, либо установить ее неразрешимость.

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

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

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

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

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