Элементы линейного программирования Параметрическое линейное программирование

Высшая математика в экономике

Элементы оптимального управления

Нелинейное программирование

Общая постановка задачи

Математическая модель задачи нелинейного программирования в общем виде формулируется следующим образом: найти вектор  = (х1, x2, …, xn), удовлетворяющий системе ограничений

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

где xj — переменные, j = ; L, f, gi — заданные функции от n переменных, bi — фиксированные значения.

Нелинейное программирование применяется при прогнозировании промышленного производства, управлении товарными ресурсами, планировании обслуживания и ремонта оборудования и т.д.

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

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

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

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

Графический метод

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

Задача с линейной целевой функцией и нелинейной системой ограничений

Пример 1. Найти глобальные экстремумы функции

при ограничениях:

Решение. Область допустимых решений — часть окружности с радиусом 4, которая расположена в первой четверти (рис. 28.1).

Линиями уровня целевой функции являются параллельные прямые с угловым коэффициентом, равным -2. Глобальный минимум достигается в точке O (0, 0), глобальный максимум — в точке А касания линии уровня и окружности. Проведем через точку А прямую, перпендикулярную линии уровня. Прямая проходит через начало координат, имеет угловой коэффициент 1/2 и уравнение x2 = 1/2х1.

Решаем систему

откуда находим х1 = 8/5, x2 = 4/5, L = 16/5 + 4/5 = 4.

Ответ. Глобальный минимум, равный нулю, достигается в точке O (0, 0), глобальный максимум, равный 4, — в точке А(8/5, 4/5).

Задача с нелинейной целевой функцией и линейной системой ограничений

Пример 2. Найти глобальные экстремумы функции

при ограничениях:

Решение. Область допустимых решений — OABD (рис. 28.2). Линиями уровня будут окружности с центром в

точке O1. Максимальное значение целевая функция имеет в точке D(9, 0), минимальное — в точке O1 (2, 3). Поэтому

Ответ. Глобальный максимум, равный 58, достигается в точке D (9, 0), глобальный минимум, равный нулю, — в точке O1 (2, 3).

Пример 3. Найти глобальные экстремумы функции

при ограничениях:

Решение. Область допустимых решений — OABD (рис. 28.3). Линии уровня представляют собой окружности с центром в точке O1 (6, 3). Глобальный максимум находится в точке O (0, 0) как самой удаленной от точки O1. Глобальный минимум расположен в точке Е, находящейся на пересечении прямой 3x1 + 2x2 = 15 и перпендикуляра к этой прямой, проведенного из точки O1.

Найдем координаты точки Е: так как угловой коэффициент прямой 3x1 + 2x2 = 15 равен -3/2, то угловой коэффициент перпендикуляра O1Е равен 2/3. Из уравнения прямой, проходящей через данную точку О2 с угловым коэффициентом 2/3, получим

Решая систему

находим координаты точки Е: х1 = 51/13, x2 = 21/13, при этом L(Е) = 1053/169.

Координаты точки Е можно найти следующим образом: дифференцируя выражение (x1 — 6)2 + (x2 - 3)2 как неявную функцию по x1, получим

Приравниваем полученное значение к тангенсу угла наклона прямой 3x1 + 2x2 = 15:

Решаем систему уравнений

получим координаты точки Е: х1 = 51/13, x2 = 21/13.

Ответ. Глобальный максимум, равный 52, находится в точке O (0, 0). Глобальный минимум, равный 1053/169, находится в точке E (51/13, 21/13).

Задача с нелинейной целевой функцией и нелинейной системой ограничений

Пример 4. Найти глобальные экстремумы функции

при ограничениях:

Решение. Областью допустимых решений является окружность с радиусом 4, расположенная в первой четверти (рис. 28.4). Линиями уровня будут окружности с центром в точке O1 (2, l).

Глобальный минимум достигается в точке O1. Глобальный максимум — в точке А (0, 4), при этом

Ответ. Глобальныи минимум, равный нулю, достигается в точке O1 (2, l), глобальный максимум, равный 13, находится в точке А (0, 4).

Пример 5. Найти глобальные экстремумы

при ограничениях:

Решение. Область допустимых решений не является выпуклой и состоит из двух частей (рис. 28.5). Линиями уровня являются окружности с центром в точке O (0, 0).

Найдем координаты точек А и В, решая систему

Получим А (1, 4), В (4, 1). В этих точках функция имеет глобальные минимумы, равные 17. Найдем координаты точек D и Е, решая системы

откуда получаем D (2/3, 6) и L(D) = 328/9, E (7, 4/7) и L(E) = 2417/49.

Ответ. Целевая функция имеет два глобальных минимума, равных 17, в точках А (1, 4) и B (4, 1), глобальный максимум, равный 2417/49, достигается в точке E (7, 4/7).

Общая схема исследования функций

  Процесс исследования функции состоит из нескольких этапов. Для наиболее полного представления о поведении функции и характере ее графика необходимо отыскать:

Область существования функции.

Это понятие включает в себя и область значений и область определения функции.

Точки разрыва. (Если они имеются).

Интервалы возрастания и убывания.

Точки максимума и минимума.

Максимальное и минимальное значение функции на ее области определения.

Области выпуклости и вогнутости.

Точки перегиба.(Если они имеются).

Асимптоты.(Если они имеются).

Построение графика.

Применение этой схемы рассмотрим на примере.

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

Метод множителей Лагранжа

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

Пример. Исследовать на сходимость ряд .

Так как   всегда, то очевидно, что .

При этом известно, что общегармонический ряд  при a=3>1 сходится, то в соответствии с признаком Вейерштрасса исследуемый ряд равномерно сходится и притом в любом интервале.

 Пример. Исследовать на сходимость ряд .

На отрезке [-1,1] выполняется неравенство  т.е. по признаку Вейерштрасса на этом отрезке исследуемый ряд сходится, а на интервалах (-µ, -1) È (1, µ) расходится

Свойства равномерно сходящихся рядов.

 1) Теорема о непрерывности суммы ряда.

 Если члены ряда  - непрерывные на отрезке [a,b] функции и ряд сходится равномерно, то и его сумма S(x) есть непрерывная функция на отрезке [a,b].


Элементы системы массового обслуживания