Решение задач нелинейного программирования средствами Excel

 

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

 в Excel реализовано 2 метода: метод Ньютона и метод сопряженных градиентов Флетчера-Ривса. Выбор метода осуществляется в окнеПараметры поиска решения. В качестве критерия останова в Excel используется условие . Значение  вводитсяв окне Параметры поиска решения в строке Относительная погрешность.

Для решения задач условной оптимизации

                        

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

1. Все ограничения –неравенства преобразуются в ограничения- равенства.

Таким образом, задача принимает вид

2. Полученная задача переписывается с помощью функции Лагранжа

 

,

где  - двойственные переменные (множители Лагранжа).

3. Рассматривается система уравнений, линейная относительно  :

Находится решение этой системы - вектор , где координаты  выражены через : .

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

5. Ее решение   берется в качестве решения исходной задачи.

Решение задачи нелинейного программирования рассмотрим на следующем примере. Пусть требуется определить размеры бака a,b,h, стоимость которого не должна превышать C_зад так, чтобы его объем V был максимальным. 

 

                                                               h

 

 

                                                                     b        

                                         a              

Объем бака V=abh

Полная поверхность S=2(ab)+2(a+b)h=2(ab+(a+b)h)

Принимаем, что стоимость материала C=kS,

где k-стоимость единицы площади материала.

В результате получим C=2k(ab+(a+b)h)

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

Для решения задачи принимаем следующие значения: k= 10 руб/м²,

С_зад=100 руб.

Тогда математическая модель примет вид:

Решим данную задачу с использованием средств EXCEL.

Решение задачи нелинейного программирования отличается от решения задачи линейного программирования следующим:

· назначаются начальные значения искомых переменных x_j⁰

· в окне Параметры поиска решения не надо вводить Линейная модель.

Начальные значения x_j⁰ желательно назначать близкими к ожидаемым оптимальным значениям, что ускорит решение задачи. Обязательным является требование к целевой функции, которая в начальной точке должна быть не равна нулю (иначе возможно деление на ноль при вычислении Df_k ).

Необходимо сделать форму для ввода условий задачи, в которую далее вводятся

· зависимости для объема и стоимости (ячейки С8, С9);

· начальные значения x_j⁰ (ячейки В3, С3, D3). В данном случае в качестве начальных значений выбираются единичные;

· значение правой части ограничения (ячейка E9). 

В ячейках, в которых будет представлен результат (B3:D3), перед решением задачи надо назначить число знаков после запятой. В нашем примере назначаем в ячейках 2 знака после запятой.

Далее вызывается программа Поиск решения и в появившемся диалоговом окне вводится ячейка для целевой функции (С8), направление поиска (максимизация), изменяемые ячейки (B3:D3). Затем выбирается пункт Добавить и в появившемся окне Добавление ограничений вводятся ограничения B3>=B4; C3>=C4; D3>=D4, C9<=E9. После ввода всех ограничений в окне поиска решения выбирается команда Параметры иосуществляется переход в диалоговое окно Параметры поиска решения. В нем назначаются параметры поиска решения. Выберем в качестве метода решения безусловных задач метод сопряженных градиентов, параметры точности можно оставить без изменения.              После ввода всех исходных данных и параметров производится решение задачи. Результаты решения представлены в таблице

 

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

В первой таблице приводятся значения для переменных:

· результат решения задачи

· нормированный градиент - величина, приводимая при выборе некоторых методов в диалоговом окне Параметры поиска решения.

Во второй таблице приводятся значения для ограничений:

· величина стоимости

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

Для задач линейного программирования можно произвести также параметрический анализ, решая их при различных значениях параметров. Алгоритм выполнения параметрических расчетов аналогичен схеме, рассмотренной при решении задач линейного программирования, поэтому в данном разделе разбираться не будет. В таблице приведен итоговый сценарий, построенный в результате решения рассматриваемой задачи нелинейного программирования при различных значениях стоимости: 100, 200, 300, 400, 500.

           

ЗАДАНИЯ ДЛЯ ЛАБОРАТОРНОГО ПРАКТИКУМА

 

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

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

 

Поезда