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

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

1. или 2.

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

К необходимости решать задачу математического программирования (ЗМП) приводят:

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

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

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

4. Проблема оптимального плани­рования финансов и др.

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

На рис. 8.28 – 8.30 в трехмерной системе координат построены модели следующих видов

Модель ЗЛП: рис . 8.26.

Модель ЗНП: рис. 8.29.

Модель ЗНП: рис. 8.30.

Н а первом рис. 8.28 пред­ставлена геометрическая интерпретация ЗЛП, в которой требуется найти максимальное значение линейной функции , изо­бра­жаю­щей плоскость, ограниченную линейными неравенствами, также изобража­ющими плос­кости, расположенные верти­кально.

На рис. 8.29 дана геометрическая интерпретация ЗНП, в которой нелинейной частью является исследуемая на максимум функция, представляющая парабо­лоид вращения .

Наконец, на рис. 8.30 нелинейность ЗНП представлена функцией ограничения Это цилиндроид с плос­кос­тью внутри, на которой требуется обна­ру­жить максимальное значение . Часть цилин­дроида вырезана для улучшения обзора.

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

Разработаны различные методы решения ЗМП, например, симплекс-метод. Их изучением занимается экономико-математическая дисциплина «Исследова­ние операций», которая следует за линейной алгеброй и целиком опирается на пройденный материал..

Вопросы для повторения.

1. Сформулировать определение экстремума функции нескольких переменных.

2. Привести необходимые условия локального экстремума.

3. Сформулировать теорему об исследовании на локальный экстремум по угловым минорам.

4. Дать определение условного экстремума.

5. Дать геометрическую интерпретацию необходимых условий условного экстремума.

6. Описать метод Лагранжа по исследованию функции на условный экстремум.

7. Что такое окаймленный гессиан?

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

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

1 Дисконт – от англ. discount – скидка