Учебное пособие по курсу «Математика»

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

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

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

Решить задачу нелинейного программирования – означает найти такие значения управляющих переменных, которые удовлетворяют системе ограничений и в то же время доставляют максимум или минимум целевой функции. Однако, для задач нелинейного программирования, в отличие от линейных задач, не существует единого, универсального метода решения. В зависимости от вида целевой функции и ограничений разработано лишь несколько специальных методов решения, к которым относятся графический метод, метод множителей Лагранжа и некоторые другие.
3.4.1. Графический метод решения задач нелинейного программирования
В задаче нелинейного программирования в общей ее постановке система ограничений определяет в n – мерном пространстве некоторую область, которая является областью допустимых решений задачи. Аналогично задачам линейного программирования, задачи нелинейного программирования можно решать графически, когда целевая функция и система ограничений содержат только две управляющие переменные, а ограничения представляют собой неравенства.

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

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

Шаг 1. На плоскости строят область допустимых решений, определяемую ограничениями. Если она пуста, т.е. если ограничения несовместны, то задача не имеет решений. В противном случае переходят к шагу 2.

Шаг 2. Строят линию уровня целевой функции: , где C – некоторая константа. Переходят к шагу 3.

Шаг 3. Определяют направление возрастания (при задаче на максимум) или убывания (при задаче на минимум) целевой функции посредством вычисления координат и построения вектора градиента целевой функции.

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

Шаг 5. Определяют значения координат для точки, найденной на шаге 4, а также значение целевой функции в этой точке, т.е. при найденных значениях координат этой точки.
ПРИМЕР: Найдите графическим методом оптимальные решения задачи нелинейного программирования, заданной математической моделью вида:


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

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


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


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

Для минимума целевой функции, аналогично в точке А имеем: для прямой – линии уровня целевой функции и для касательной к гиперболе. Приравнивая найденные выражения, получим: и подставив найденное значение в уравнение гиперболы, получим: . Поэтому оптимальное решение для задачи на минимум целевой функции будет иметь следующий вид: .
3.4.2. Метод множителей Лагранжа
Пусть требуется решить задачу нелинейного программирования, заданную математической моделью в каноническом виде:

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

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

Шаг 1. Составляют функцию Лагранжа:
,

где переменные называются множителями Лагранжа.

Шаг 2. Находят частные производные функции Лагранжа по всем переменным и приравнивают их к нулю:

Шаг 3. Решают систему уравнений, полученную на шаге 2, и находят стационарные точки, т.е. точки, в которых функция F (и, следовательно, исходя из структуры функции F, целевая функция f) может иметь экстремум.

Шаг 4. Проверяют полученные на шаге 3 стационарные точки на наличие в них экстремума и находят экстремальное значение целевой функции задачи в найденной точке условного (в смысле не глобального) экстремума.
ПРИМЕР: Фирма реализует автомобили двумя способами: через магазин и через торговых агентов. При реализации автомобилей через магазин расходы на реализацию составляют: условных единиц, а при продаже автомобилей через торговых агентов расходы составляют условных единиц. Найти оптимальный способ реализации автомобилей, обеспечивающий минимум суммарных расходов, если общее число автомобилей, предназначенных для продажи, составляет 200 штук.

Очевидно, что математическая модель задачи будет иметь вид:

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

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

Решив эту систему, получим: и . Этим значениям управляющих переменных соответствует значение целевой функции, равное: .

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

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

Рекомендуемая литература по теме 3.4: [3, 5].
ВОПРОСЫ:

1. 
   Для решения каких экономических задач чаще всего применяются нелинейные математические модели?
   

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

3. 
   В каком виде должна быть записана математическая модель задачи нелинейного программирования для решения ее методом множителей Лагранжа?
   

4. 
   В чем заключается основная идея метода множителей Лагранжа?
   

ТЕМА 3.5. Динамическое программирование

Динамическое программирование – один из разделов оптимального программирования, в котором процесс принятия решения и управления обычно разбивается на отдельные этапы (или шаги).

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

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

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

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

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

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

Процедура построения оптимального управления методами динамического программирования распадается на две основных стадии: предварительную и окончательную.

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

На окончательной стадии для каждого шага определяется окончательное (безусловное) оптимальное управление.

Условная оптимизация производится по шагам, в обратном порядке, т.е. от последнего шага к первому, в то время как безусловная оптимизация – также по шагам, но от первого шага к последнему.
Рассмотрим основные экономические задачи, которые решаются методами динамического программирования.
3.5.1. Оптимальное распределение ресурсов.
Пусть имеется некоторое количество ресурсов х, которое нужно распределить между n различными предприятиями, объектами и т.п. так, чтобы получить максимальную суммарную эффективность от выбранного способа распределения.

Если ввести обозначения: – количество ресурсов, выделенных му предприятию; – функция полезности, т.е. величина дохода от использования ресурса полученного –ым предприятием; – наибольший доход, который можно получить при использовании ресурсов x от первых k различных предприятий, то математическую модель данной задачи можно записать в виде:

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

Для максимизации суммарного дохода от k-го и первых способов необходимо выбрать величину таким образом, чтобы выполнялись соотношения вида:

Таким образом, получены рекуррентные соотношения, позволяющие решить поставленную задачу оптимального распределения ресурсов методами динамического программирования.
3.5.2. Оптимальное распределение инвестиций.
Инвестор выделяет средства в размере D условных единиц, которые должны быть распределены между m предприятиями. Каждое –ое предприятие при инвестировании в него средств x приносит прибыль в размере: условных единиц, . Нужно выбрать оптимальное распределение инвестиций между предприятиями, обеспечивающее максимальную суммарную прибыль.

Заметив, что выигрышем W в данной задаче является суммарная прибыль, приносимая всеми m предприятиями, приступим к последовательному изложению алгоритма решения данной задачи методами динамического программирования.

1. 
   Определение числа шагов. Число шагов m равно числу предприятий, в которые осуществляется инвестирование.
   
2. 
   Определение состояний системы. Состояние системы на каждом шаге характеризуется количеством средств s, имеющихся в наличии перед данным шагом, причем: .
   
3. 
   Выбор шаговых управлений. Управлением на –ом шаге является количество средств, инвестируемых в –ое предприятие.
   
4. 
   Функция выигрыша на –ом шаге: – это прибыль, которую приносит –ое предприятие при инвестировании в него средств , так, чтобы: .
   
5. 
   Определение функции перехода системы в новое состояние: . Т.е., если на –ом шаге система находилась в состоянии s, а выбрано управление x, то на –ом шаге система будет находиться в состоянии , или, если в наличии имеются средства в размере s условных единиц, и в –ое предприятие инвестируется x условных единиц, то для дальнейшего инвестирования остается только условных единиц.
   
6. 
   Составление функционального уравнения для :
   

.

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

7. 
   Составление основного функционального уравнения.
   

.
Поясним последнее уравнение. Пусть перед –ым шагом у инвестора остались средства в размере s условных единиц. Тогда x условных единиц он может вложить в –ое предприятие, при этом оно принесет доход в размере а оставшиеся условных единиц – в остальные предприятия с –го до m-го. Условный оптимальный выигрыш от такого вложения составит: . Оптимальным будет то условное управление x, при котором сумма в фигурных скобках будет максимальной.
ПРИМЕР: Торговая фирма располагает 5 автолавками, которые могут быть направлены в воскресный день в три населенных пункта. Считается, что товарооборот фирмы зависит от количества и ассортимента направляемых товаров и определяется только числом посланных в тот или иной населенный пункт автомашин. Среднее значение товарооборота в условных единицах в каждом из населенных пунктов задано в таблице. Найдите оптимальную стратегию фирмы в распределении автолавок по населенным пунктам, максимизирующую общий (суммарный) товарооборот.

1	15	12	18
2	24	20	23
3	30	31	29
4	37	38	36
5	41	42	39

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

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

1	1	18	0	18	–	–
2	2	23	1	30	–	–
3	3	29	2	38	–	–
4	4	36	3	49	–	–
5	5	39	4	56	1	64

Для второго шага функциональное уравнение имеет вид:


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

0	1	0	18	18
1	0	12	0	12

Откуда следует: и поэтому: . Заносим эти результаты в расчетную таблицу и продолжаем расчет.
Для s = 2 имеем:

0	2	0	23	23
1	1	12	18	30
2	0	20	0	20

Откуда заключаем, что: и . Заносим эти результаты в расчетную таблицу и продолжаем расчет.


Для s = 3 получим:

0	3	0	29	29
1	2	12	23	35
2	1	20	18	38
3	0	31	0	31

Следовательно: и . Заносим эти результаты в таблицу и продолжаем расчет.

Совершенно аналогично для s = 4 имеем:

Откуда следует: и . Заносим полученные значения в расчетную таблицу и продолжаем условную оптимизацию для второго шага.

Для s = 5 получим:
,

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

Переходим к условной оптимизации для первого шага . Очевидно, что перед первым шагом состояние системы известно: s = 5 (в распоряжении фирмы находятся все пять автолавок, которые только предстоит распределять), поэтому условная оптимизация на этом шаге проводится только для состояния s = 5.
Итак, для и получим:

0	5	0	56	56
1	4	15	49	64
2	3	24	38	62
3	2	30	30	60
4	1	37	18	55
5	0	41	0	41

Следовательно: и . И эти результаты заносим в таблицу.

Итак, расчетная таблица заполнена, и условная оптимизация закончена. Из этой таблицы следует, что оптимальный товарооборот, принесенный оптимальным распределением автолавок по населенным пунктам, равен 64, т.е.:

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

Итак, для получения максимального товарооборота, равного 64, фирме следует: в первый населенный пункт направить 1 автолавку, во второй населенный пункт – 3 автолавки и в третий населенный пункт – 1 автолавку.

Рекомендуемая литература по теме 3.5: [3, 5, 10].
ВОПРОСЫ:

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

2. 
   Что является шагом при решении задач по распределению инвестиций?
   

3. 
   Какие два крупных этапа содержит алгоритм решения задач по распределению инвестиций?
   

4. 
   Что является целевой функцией в математической модели задачи по распределению инвестиций?