Использование информационных технологий при решении задач нелинейной оптимизации

Использование информационных технологий при решении задач нелинейной оптимизации

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

Пример 5.

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

                                               Таблица 2.3. Параметры задачи.

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

 тыс. руб. для сырья 1 и  тыс. руб. для сырья 2, где  - затраты сырья на производство продукции. Стоимость одного часа трудозатрат определяется зависимостью , где  - затраты времени на производство продукции.

Вопросы:

Сколько продукта 1 и 2 следует производить для того, чтобы обеспечить максимальную прибыль?

Какова максимальная прибыль?

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

                  

Проведем решение данной задачи в Excel. На начальном этапе подготовим форму для решения задачи на рабочем листе следующего вида:

Рис. 2.6. Данные для решения примера 5.

Отведем для искомых значений объемов выпуска продукции ячейки B8, C8, для расхода соответствующих ресурсов (включая трудозатраты) – ячейки B3, B4, B5. В данные ячейки необходимо ввести функции

=3*B8+5*C8

=4*B8+6*C8  и

=14*B8+12*C8

соответственно.

Численные значения ограничений по ресурсам внесем в ячейки C3, C4, C5. В ячейку E10 введем формулу для целевой функции: =11*B8+16*C8+0,1*B8^2+0,12*C8^2+0,22*B8*C8.

Решение задачи производится с помощью Поиска решения Excel. Изменяемыми ячейками будут, очевидно, ячейки B8, C8; целевая ячейка устанавливается равной максимальному значению; используются следующие ограничения: $B$3<=$C$3, $B$4<=$C$4, $B$5<=$C$5. Следует иметь в виду, что в связи с нелинейностью данной задачи необходимо в окне Параметры поиска решения отключить опцию Линейная модель (это замечание относится к решению всех задач, приведенных в данном разделе). В результате запуска Поиска решения получим ответ:  и значение максимальной прибыли 507.407 тыс. руб.

Пример 6.

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

Требуется найти такие объемы производства продукции, при которых прибыль максимальна.

Значения параметров задачи приводятся в нижеследующей таблице.

При заданных значениях параметров целевая функция имеет вид

,

или

.

Ограничения по ресурсам имеют вид

или

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

Решение. 

Заполним рабочий лист по аналогии с Рис 2.7.

Рис. 2.7. Данные для решения примера 6.

В ячейки B3¸B5 введем формулы-ограничения, в ячейку E8 – формулу для целевой функции. Дополнительное ограничение – на целочисленность переменных . После запуска Поиска решения получим ответ: .

Пример 7.

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

В качестве целевой функции принимаем

,

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

Решение проведем для трех случаев, соответствующих 1) отсутствию каких-либо ограничений на координаты , 2) необходимости размещения обслуживающего объекта на некотором прямолинейном отрезке (например, объект может быть расположен лишь на отдельном небольшом участке улицы), 3) расположению объекта в пределах некоторого круга заданного радиуса. Ограничимся случаем трех обслуживаемых объектов

Первый случай. Отсутствуют какие-либо ограничения на координаты .

Решение. Введем данные на рабочий лист в соответствии с приводимым ниже рисунком.

         В качестве изменяемых ячеек выберем B10, B11; в качестве целевой ячейки - ячейку E11 и введем в нее формулу

=J6*КОРЕНЬ((B10-A6)^2+(B11-B6)^2)+K6*КОРЕНЬ((B10-D6)^2+(B11-E6)^2)+L6*КОРЕНЬ((B10-G6)^2+(B11-H6)^2).

Рис. 2.8. Данные для решения задачи о расположении объекта (без ограничений).

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

Второй случай. Координаты  принадлежат некоторому отрезку прямой линии, задаваемой уравнением 

                             

(в данном примере мы используем значения ).

Решение. Введем данные на рабочий лист в соответствии с приводимым ниже рисунком.

Очевидно, формула для целевой функции (ячейка E12) остается неизменной.

Рис. 2.9. Данные для решения задачи о расположении объекта (координаты объекта лежат на отрезке прямой линии).

Единственным отличием от предыдущего случая является необходимость ввода дополнительного ограничения в ячейку B13; в ячейку B13 вводится формула

 =B9-B15*B8

и в окне диалога Поиск решения вводится ограничение

          $B$13=$B$16.

Ответ: оптимальное значение целевой функции  составляет 13,6843.

Третий случай. Координаты  лежат внутри некоторой окружности радиуса  (мы полагаем ). Данный случай может соответствовать, например, ситуации, когда необходимо разместить некоторый объект вблизи некоторого населенного пункта.

Решение. Введем данные на рабочий лист в соответствии с приводимым ниже рисунком.

Рис. 2.10. Данные для решения задачи о расположении объекта (координаты объекта локализованы в пределах круга определенного радиуса).

Целевая функция располагается в ячейке E11, искомые координаты объекта будут располагаться в ячейках B7, B8. В ячейку B12 введем функцию = B7^2+B8^2. Введем ограничение $B$12<=$C$11, учитывающее то обстоятельство, что объект не должен располагаться вне круга заданного радиуса. Поиск решения дает ответ  целевая функция .

Пример 8. Формирование оптимального портфеля ценных бумаг

Требуется сформировать портфель минимального риска из двух видов ценных бумаг – “АРТ” с эффективностью 12% и риском 21,1 и “ВЕРМ” с эффективностью 5,1% и риском 8,3 при условии, что обеспечивается доходность портфеля не менее 8,9%. Коэффициент корреляции  равен 0,18.

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

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

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

 – доходность (эффективность) портфеля ценных бумаг, рассчитываемая по формуле:

                                         

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

где  – коэффициент корреляции доходов между i-м и j-м активом;  - риски отдельных видов ценных бумаг.

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

Решение. В случае всего двух видов активов формула для расчета риска упрощается и приобретает вид

                   .

         Введем данные на рабочий лист в соответствии с Рис. 2.11.

Рис. 2.11. Данные для решения задачи о минимизации риска портфеля ценных бумаг.

Формулу для расчета  введем в ячейку С6; формулу для значения доходности портфеля – в ячейку С7 (=СУММ(12*A3+5,1*B3)). Формулу для целевой функции

=КОРЕНЬ((A5*A3)^2+2*A3*B3*A5*B5*C5+(B5*B3)^2) - в ячейку E5.

Используемые ограничения

Значение (ячейка C6) должно равняться единице.

Значение доходности портфеля ценных бумаг  (ячейка C7) должно быть не менее 8,9.

.

Ответ . Минимальный риск при этом составляет .

Контрольные вопросы к теме:

1. Экономическая суть методов оптимизации

2. Определите задачи математического программирования

3. Какие задачи называют задачами линейного программирования

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

4. Динамическое программирование

5. Стохастическое программирование

6. Определение целевой функции

7. Построение математической модели оптимизационной задачи

8. Нелинейные модели оптимизации

9. Методы решения задач нелинейной оптимизации