Математическое программирование.

 

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

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

В 1820 году Фурье и затем, через сто двадцать семь лет, но более подробно, в 1947 году Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач линейного программирования.

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

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

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, относят к 1930-м годам. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман — математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя, и Канторович — советский академик, лауреат Нобелевской премии (1975), сформулировавший ряд задач линейного программирования и предложивший в 1939 году метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

В 1931 году венгерский математик Б. Эгервари рассмотрел математичес-кую постановку и предложил решение задач линейного программирования, имеющую название «проблема выбора», метод решения получил название «венгерского метода».

Л. Канторовичем совместно с М. К. Гавуриным в 1949 году был тщательно разработан так называемый метод потенциалов, который применяется при реше-нии определенного класса задач получивших название «транспортные задачи» и широко применяемый в логистике.

В последующих работах Л. Канторовича, В. Немчинова, В. В. Новожилова, А. Л. Лурье, А. Брудно, С. Аганбегяна, Д. Б. Юдина, Е. Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных инженерных и экономических проблем.

Методам линейного программирования было посвящено очень много работ и зарубежных учёных.

Так например в 1941 году Ф. Л. Хитчкок осуществил свою оригинальную постановку транспортной задачи.

Самый распространенный метод решения задач линейного программирования — симплекс-метод — был опубликован в 1949 году Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования за рубежом получили в работах Куна, А. Таккера, Гасса (Saul. I. Gass), Чарнеса (Charnes A.), Била (Beale E. M.) и др.

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

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

Кроме того начиная с 1955 года было опубликовано много работ, посвя-щенных квадратическому программированию (работы Била, Баранкина и Дорфмана (Dorfman R.),Франка (Frank M.) и Вольфа (Wolfe P.), Марковица и др.). В работах Денниса (Dennis J. B.), Розена (Rosen J. B.) и Зонтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования.

Естественно, что в настоящее время для эффективного применения методов математического программирования и решения задач на компьютерах разработаны алгебраические языки моделирования, представителями которыми являются AMPL и LINGO.

В процессе проектирования ставится обычно задача определения наилучших, в некотором смысле, структуры или значений параметров объектов. Такая задача называется оптимизационной. Если оптимизация связана с расчётом оптимальных значений параметров при заданной структуре объекта, то она называется параметрической оптимизацией. Задача выбора оптимальной структуры является структурной оптимизацией (например задача о смесях).

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

1. Допустимое множество — множество;

2. Целевую функцию — отображение;

3. Критерий поиска (max или min).

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

Если допустимое множество определенно, то такая задача называется - задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.

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

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

· Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.

· Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.

Существующие в настоящее время методы поиска можно условно разбить на три большие группы:

1. детерминированные;

2. случайные (стохастические);

3. комбинированные.

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

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

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

· В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:

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

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

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

· прямые методы, требующие только вычислений целевой функции в точках приближений;

· методы первого порядка: требуют вычисления первых частных производных функции;

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

Помимо того, оптимизационные методы делятся на следующие группы:

· аналитические методы (например, метод множителей Лагранжа и условия Каруша – Куна - Таккера);

· численные методы;

· графические методы.

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

· задачи дискретного программирования (или задачи комбинаторной оптимизации) — если X конечно или счётно;

· задачи целочисленного программирования — если X является подмножеством множества целых чисел;

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

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

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

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

Способ нахождения экстремума полностью определяется классом задачи. Но перед тем как получить математическую модель, обязательно нужно выполнить 4 этапа моделирования:

· Определение границ системы оптимизации

· Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается

· Выбор управляемых переменных

· «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)

· Определение ограничений на управляемые переменные (равенства и/или неравенства)

· Выбор числового критерия оптимизации (например, показателя эффективности)

· Создаём целевую функцию

 

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

Общая задача линейного программирования имеет вид:

Рисунок 23.

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

Графический метод решения ОЗЛП (основной задачи линейного программирования) основан на следующих утверждениях.

Система ограничений ОЗЛП геометрически представляет собой выпуклый многоугольник или выпуклую многоугольную область как пересечение полуплоскостей - геометрических образов неравенств системы.

Целевая функция Z = c₁x₁ + c₂x₂ геометрически изображает семейство параллельных прямых, перпендикулярных вектору нормали N(с₁,с₂). Эти прямые называются линиями уровня.

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

Теорема. При перемещении линии уровня в направлении вектора нормали N значение целевой функции возрастает, в противоположном направлении - убывает.

Алгоритм графического метода решения ОЗЛП выглядит так:

1. В системе координат нужно построить прямые по уравнениям, соответствующим каждому неравенству системы ограничений;

2. Надо найти полуплоскость решения каждого неравенства системы (обозначить стрелками). Для определения полуплоскости необходимо произвольно выбрать любую контрольную точку, не лежащую на данной прямой. Далее надо подставить ее координаты в систему ограничений. Если неравенство выполняется, то нужно выбрать полуплоскость, содержащую эту контрольную точку. Если же неравенство не выполняется нужно выбрать полуплоскость, не содержащую контрольную точку. В качестве контрольной точки рекомендуется выбирать точку с координатами (0;0);

3. найти многоугольник (многоугольную область) решений системы ограничений как пересечение полуплоскостей;

4. построить вектор нормали N. Начало вектора нормали в точке с координатами (0;0), конец вектора в точке с координатами (с₁, с₂);

5. через начало координат построить линию уровня, перпендикулярно к вектору нормали;

6. перемещать линию уровня параллельно самой себе по области решения в угловые точки, достигая max f при движении вектора N (min f при движении в противоположном направлении);

7. найти координаты точки max (min). Для этого необходимо решить систему уравнений прямых, которые пересекаются в этой точке или определить координаты по графику;

8. вычислить значение целевой функции в этой точке и получить ответ.