Множитель лагранжа в excel

Множитель лагранжа в excel

Задача нелинейного программирования ставится как задача нахождения оптимума определенной целевой функции при выполнении условий:

, ,

где , — параметры, , — ограничения, — количество параметров, — количество ограничений. Целевая функция или ограничение есть нелинейная функция

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

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

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

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

. (1.29)

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

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

Следует отметить, что в подавляющем большинстве практиче­ских задач оптимизации существует только один оптимум.

Решение задачи НЛП (реализация модели нелинейной оптимизации) средствами Excel отличается от решения ЗЛП следующим:

§ назначаются начальные значения искомых переменных , так, чтобы ЦФ в начальной точке не была равна нулю:

0;

§ в диалоговом окне Поиск решения в режиме Параметры не надо вводить флажок Линейная модель.

В Excel на каждой итерации вычисляется величина относительного приращения целевой функции

(1.30)

Оптимум считается достигнутым, если выполняется условие

,

где — относительная погрешность, назначаемая при решении задачи (режим Параметры).

Пример 4. Через точку провести плоскость, образующую с плоскостями координат тетраэдр наименьшего объема.

Решение.

Переменные — отрезки, которая плоскость отсекает на осях координат.

Целевая функция- объем тетраэдра, который надо минимизировать:

Ограничение на переменные накладывает задание точки :

Рабочий лист Excel может быть подготовлен в виде, представленном на рис. 1.22., формулы этого листа приведены в ячейках DЗ:D4.

Рисунок.1.22. Исходные данные, условия и полученное решение задачи

Ответ. Реализуя решение приведенной задачи средствами Excel (рис. 1.6.1), получим величины отрезков, при которых достигается оптимум . Объем тетраэдра равен .

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

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

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

Назва Программа Поиск решений
Дата конвертації 09.07.2013
Розмір 81.79 Kb.
Тип Программа

mir.zavantag.com > Математика > Программа

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

Программа ^ Поиск решений (в оригинале Excel Solver) – дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных та нелинейных задач оптимизации, используется с 1991 года.

Разработчик программы ^ Solver компания Frontline System уже давно специализируется на разработке мощных и удобных способов оптимизации, встроенных в среду популярных табличных процессоров разнообразных фирм-производителей (MS Excel Solver, Adobe Quattro Pro, Lotus 1-2-3).

Высокая эффективность их применения объясняется интеграциею программы оптимизации и табличного бизнес-документа. Благодаря мировой популярности табличного процессора MS Excel встроенная в его среду программа Solver есть наиболее распространенным инструментом для поиска оптимальных решений в сфере современного бизнеса.

По умолчанию в Excel надстройка Поиск решения отключена. Чтобы активизировать ее в Excel 2007, щелкните значок Кнопка Microsoft Office , щелкните Параметры Excel , а затем выберите категорию Надстройки . В поле Управление выберите значение Надстройки Excel и нажмите кнопку Перейти . В поле Доступные надстройки установите флажок рядом с пунктом Поиск решения и нажмите кнопку ОК .

В Excel 2003 и ниже выберите команду Сервис/Надстройки , в появившемся диалоговом окне Надстройки установите флажок Поиск решения и щелкните на кнопке ОК. Если вслед за этим на экране появится диалоговое окно с предложением подтвердить ваши намерения, щелкните на кнопке Да. (Возможно, вам понадобится установочный компакт-диск Office).

Процедура поиска решения

1. Создайте таблицу с формулами, которые устанавливают связи между ячейками.

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

— В Excel 2007 Данные/Анализ/Поиск решения ;

— В Excel 2003 и ниже Сервис > Поиск решения. Поле Установить целевую ячейку открывшегося диалогового окна надстройки ^ Поиск решения будет содержать адрес целевой ячейки.

3. Установите переключатели Равной, задающие значение целевой ячейки, – максимальному значению, минимальному значению или значению. В последнем случае введите значение в поле справа.

4. Укажите в поле Изменяя ячейки, в каких ячейках программа должна изменять значения в поисках оптимального результата.

5. Создайте ограничения в списке Ограничения. Для этого щелкните на кнопке Добавить и в диалоговом окне Добавление ограничения определите ограничение.

6. Щелкните на кнопке Параметры, и в появившемся окне установите переключатель Неотрицательные значения (если переменные должны быть позитивными числами), Линейная модель (если задача, которую вы решаете, относится к линейным моделям)

7. Щелкнув на кнопке Выполнить, запустите процесс поиска решения.

8. Когда появится диалоговое окно Результаты поиска решения, выберите переключатель Сохранить найденное решение или Восстановить исходные значения.

9. Щелкните на кнопке ОК.

^ Параметры средства Поиск решения

Максимальное время –служит для ограничения времени, отпущенного на поиск решения задачи. В этом поле можно ввести время в секундах, не превышающее 32 767 (примерно девять часов); значение 100, используемое по умолчанию, вполне приемлемо для решения большинства простых задач.

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

Относительная погрешность – определяет точность вычислений. Чем меньше значение этого параметра, тем выше точность вычислений.

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

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

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

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

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

Показывать результаты итераций – приостанавливает поиск решения для просмотра результатов отдельных итераций.

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

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

Оценка линейная – выберите этот переключатель для работы с линейной моделью.

Оценка квадратичная – выберите этот переключатель для работы с нелинейной моделью.

Разности прямые – используется в большинстве задач, где скорость изменения ограничений относительно невысока. Увеличивает скорость работы средства Поиск решения.

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

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

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

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

Отчеты бывают трех типов:

  • по результатам
  • по устойчивости
  • по пределам

Тип выбирается по окончании поиска решений в диалоговом окне Результаты поиска решений в списке Отчеты. Можно выбрать сразу два или три типа с помощью мыши при нажатой клавиши . Каждый отчет будет создан на отдельном рабочем листе.
^ Отчет по результатам.

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

^ 1 – начальное значение целевой функции при начальном опорном плане (3);

2 – максимальное или минимальное значение (в зависимости от задачи) целевой функции. В нашем случае – 168,57 д. ед.;

^ 3 – начальный опорный план;

4 – оптимальный план задачи. В нашем случае, чтобы получить максимальную выручку в размере 168,37 д. ед., нужно производить 57,14 единиц товара А и 71,43 единиц товара Б (понятно, что товар должен быть в целых единицах, но если бы мы задали такой параметр, то не получили отчеты, которые нужны для анализа и улучшение полученных результатов);

^ 5 – показывает количество использованных ресурсов на производство при оптимальном плане;

6 – формулы ограничений;

7 – показывает влияние ограничений на конечный результат. Если статус «связанное», тогда данное ограничение влияет на полученный план, если «не связан» – значит не влияет. В нашем случае ресурс 1 и 4 имеют статус «не связан» – это значит, что эти ресурсы не ограничивают возможности в производстве, что не скажешь про ресурс 2 и 3, которые использованы полностью;

^ 8 – разница между имеющимся в наличие количеством ресурсов и использованных при полученном плане.

Отчет по устойчивости

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

^ 1 – оптимальный план задачи. В нашем случае, чтобы получить максимальную выручку в размере 168,37 д. ед., нужно производить 57,14 единиц товара А и 71,43 единиц товара Б;

2 – нормированная стоимость касается неизвестных плана. Это неудачный перевод с оригинала reduced cost, которую можно было перевести, как «цена, которая уменьшает (целевую функцию)». Этот показатель, как изменится оптимальное значение ЦФ при выпуске продукции, которой нету в оптимальном плане. Например, если нормированная стоимость товара А была бы -3 (хотя в нашем случае это 0), то принудительный выпуск 2 единиц товара А, которых нету в оптимальном плане привел к уменьшению Дохода на 2•3=6 и составлял бы 168,57-6= 162, 57 д. ед.

^ 3 – коэффициенты ЦФ;

4, 5 – границы изменений значений коэффициентов ЦФ при условии, что количество оптимальной продукции (план) не изменится. Например, если целевой коэффициент товара А (КА) равен 1,15 (цена за 1 единицу товара), то изменяя его в рамках 1,15-0,43 0,72 ^ 6 – количество использованных ресурсов;

7 – теневая цена(в нелинейной модели это множитель Лагранжа) касается ограничений, то есть, определенное значение указывает на «ценность» ограниченного ресурса в сравнении с другими ресурсами. Этот показатель указывает как изменится оптимальное значение ЦФ (Доход) при изменении запасов ресурсов на 1 единицу. Например, если увеличить запас ресурса 3 на 10 единиц, то доход увеличится на 10•0,61=6,1 и будет составлять 168,57+6,1=174,67 д. ед.

^ 8 – запасы ресурсов;

9, 10 – задают диапазон для 8, в котором действует теневая цена 7 (аналогично 4, 5). Например, диапазон ресурса 3: 200 ^ 1 – значение ЦФ (Доход);

2 – оптимальный план задачи;

3 – наименьшее значения, которое может принять неизвестное (в нашем случае количество товара А и Б имеет Нижний предел 0, поскольку мы в Параметрах Поиска решений отметили Неотрицательные значения);

4 – это значение, которое будет в целевой ячейке (Доход), если неизвестное будит равно Нижнему пределу;

5 – это наибольшее значение, которое может содержать неизвестные, чтобы получить максимальную ЦФ;

Рис.э.3. Фрагмент электронных таблиц Excel в режиме отображения данных.

Рис.э.4. Диалоговое окно надстройки «Поиск решения» при поиске оптимального решения.

Рис.э.4. Диалоговое окно надстройки «Поиск решения» при поиске оптимального решения.

Рис э.5. Фрагмент электронных таблиц Excel с отчетом по устойчивости

Экономическая интерпретация множителей Лагранжа

Множитель Лагранжа – это двойственная переменная. Как и в линейном программировании, она показывает, на сколько изменится ЦФ при изменении правой части ограничений на единицу.

В рассмотренном примере . Следует ожидать, что при увеличении суммарного объема производимой продукции с 150 до 151 доход уменьшится на 20.

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

.

Решим эту задачу в MS Excel (надстройка «Поиск решения»).

Рис.э.6. Фрагмент электронных таблиц MS Excel в режиме отображения данных.

Стационарная точка ,

Приращение функции -20,67 оказалось больше по модулю, чем ожидаемое приращение -20. Это объясняется нелинейностью целевой функции и тем, что множитель Лагранжа отражает приращение функции только при бесконечно малом приращении аргумента.

Иллюстрация полученного решения в MS Excel.

Чтобы проиллюстрировать полученное решение диаграммами с помощью линий уровня, затабулируем соответствующие функции (рис.э.7). Основную идея -описать решение кв.ур-я. Соответствующая диаграмма приведена на рис.*.10. Эта диаграмма является упрощенным вариантом рис.э.2. Точка соответствующая оптимальным значениям выделена. В ней линия уровня, соответствующая уровню =14 700 и линия равных объемов С=150 касаются и следовательно градиенты коллинеарны. Стрелки градиентов при самостоятельном решении можно нанести любым способом, в т.ч. вручную. На эту диаграмму нанести значения приближений к решению, полученные мтодом приведенного градиента.

Рис.э.7. Фрагмент электронных таблиц Excel в режиме отображения данных. Табулирование целевой функций для построения линий уровня.

Рис.э.8. Фрагмент электронных таблиц Excel в режиме отображения формул. Табулирование целевой функций для построения линий уровня.

Чтобы построить семейство линий уровня или , при разных С заметим, что линии уровня — вложенные (концентрические) эллипсы.

Рассмотрим процесс построения линии при С =1000. Необходимо построить таблицу значений .Для этого явно выразим через , используя соотношение или

Последнее соотношение следует рассматривать как квадратное уравнение относительно : , где . Значения с находится в интервале B15:B58. Значения дискриминанта находится в интервале C15:C58. Квадратное уравнение (при положительном дискриминанте) имеет два корня, это обеспечивает задание верхней и нижней ветвей эллипса. Первый корень находится в интервале D15:D58. Второй корень находится в интервале E15:E58. Построение диаграммы, у которой значения абсциссы лежит в интервале А15:А58, а ординаты в интервале D15:D58, обеспечивает вывод верхней дуги эллипса. Построение диаграммы, у которой значения абсциссы лежит в интервале А15:А58 , а ординаты в интервале E15:E58, обеспечивает вывод нижней дуги эллипса, Другие лини уровня строятся аналогично.

Рис.э.9. Линии уровня целевой функции и равного объема.

Рис.э.10. Линии уровня целевой функции и равного объема. Маркеры треугольники показывают значения приближений к решению, полученные методом приведенного градиента.

Ссылка на основную публикацию
Миграция с exchange на яндекс почту
Если у вас на другом сервисе есть настроенная корпоративная почта, вы можете перенести её на «Mail.ru для бизнеса», используя миграцию....
Лучшие производители шкафов купе в москве рейтинг
*Обзор лучших по мнению редакции expertology.ru. О критериях отбора. Данный материал носит субъективный характер, не является рекламой и не служит...
Магазины дискаунтеры в россии список
Как закончили 2018 год десять крупнейших розничных ретейлеров РФ? Какая сеть растет быстрее всех? Почему гипермаркеты умирают, а «жесткие дискаунтеры»...
Множитель лагранжа в excel
Задача нелинейного программирования ставится как задача нахождения оптимума определенной целевой функции при выполнении условий: , , где , — параметры,...
Adblock detector