Задание 1. Решить линейную оптимизационную задачу.

ЛАБОРАТОРНАЯ РАБОТА № 4

ТАБЛИЧНЫЙ Микропроцессор MS EXCEL.

ПОИСК Хороших РЕШЕНИЙ

Цель работы:изучить способности утилиты «Поиск решения» ТП MS Excel на примере решения оптимизационных задач: оптимизации производственной программки, оптимизации плана перевозок.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Посреди оптимизационных задач экономики и управления созданием более известны задачки линейного программирования, в каких максимизируемая (минимизируемая) функция F(X) является Задание 1. Решить линейную оптимизационную задачу. линейной, а ограничения Gзадаются линейными неравенствами.

Общая форма записи модели задачки линейного программирования имеет вид:

мотивированная функция (ЦФ):

,

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

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

Это так именуемая утилита “Поиск решения” (см. рис Задание 1. Решить линейную оптимизационную задачу.. 4.1). Прокомментируем некие нюансы работы с этой утилитой.

Рис.4.1– Окно утилиты Поиск решения

Разыскиваемые переменные - ячейки рабочего листа Excel - именуются регулируемыми ячейками.

Мотивированная функция F(x1, x2, … , xn), именуемая время от времени просто целью, должна задаваться в виде формулы в ячейке рабочего листа. Эта формула может содержать функции, определенные юзером, и должна Задание 1. Решить линейную оптимизационную задачу. зависеть (ссылаться) от регулируемых ячеек. В момент постановки задачки определяется, что делать с мотивированной функцией. Вероятен выбор 1-го из вариантов:

Ø отыскать максимум мотивированной функции F(x1, x2, … , xn);

Ø отыскать минимум мотивированной функции F(x1, x2, … , xn);

Ø достигнуть того, чтоб мотивированная функция F(x1, x2, … , xn) имела фиксированное значение: F Задание 1. Решить линейную оптимизационную задачу.(x1, x2, … , xn) = a (см. рис. 4.2).

Рис.4.2 – Определение мотивированной функции в окне утилиты «Поиск решения»

Функции G(x1, x2, … , xn) именуются ограничениями. Их можно задать как в виде равенств, так и неравенств.

На регулируемые ячейки (разыскиваемые характеристики – x1, x2, … , xn) можно наложить дополнительные ограничения: неотрицательности и/либо целочисленности Задание 1. Решить линейную оптимизационную задачу., тогда решение ищется в области положительных и/либо целых чисел (см. рис.4.3).



Рис. 4.1 – Определение ограничений

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

Управление диалоговым окном поиска решения осуществляется последующим образом (см. рис. 4.1).

Установить Задание 1. Решить линейную оптимизационную задачу. мотивированную ячейку

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

Равной

Служит для выбора варианта оптимизации значения мотивированной ячейки (максимизация, минимизация либо подбор данного числа). Чтоб установить число, нужно ввести его в поле Задание 1. Решить линейную оптимизационную задачу..

Изменяя ячейки

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

Ограничения

Служит для отображения перечня граничных критерий намеченной цели.

Выполнить

Служит для пуска Задание 1. Решить линейную оптимизационную задачу. поиска решения намеченной цели.

Закрыть

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

Характеристики

Служит для отображения диалогового окна Характеристики поиска решения, в каком можно загрузить либо сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения.

Вернуть

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

Диалоговое окно "Характеристики поиска решения"

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

Рис.4.2 – Диалоговое окно "Характеристики поиска решения"

Наибольшее время

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

Предельное число итераций

Служит для управления временем решения задачки методом ограничения Задание 1. Решить линейную оптимизационную задачу. числа промежных вычислений. В поле можно ввести значение, не превышающее 32767; значение 100, применяемое по дефлоту, подходит для решения большинства обычных задач.

Относительная погрешность

Служит для задания точности, с которой определяется соответствие ячейки мотивированному значению либо приближение к обозначенным границам. Поле должно содержать десятичную дробь от 0 (нуля) до 1. Чем больше десятичных символов Задание 1. Решить линейную оптимизационную задачу. в задаваемом числе, тем выше точность — к примеру, число 0,0001 представлено с более высочайшей точностью, чем 0,01.

Допустимое отклонение

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

Сходимость

Когда относительное изменение значения в мотивированной ячейке Задание 1. Решить линейную оптимизационную задачу. за последние 5 итераций становится меньше числа, обозначенного в поле Сходимость, поиск прекращается. Сходимость применяется только к нелинейным задачкам, условием служит дробь из интервала от 0 (нуля) до 1. Наилучшую сходимость охарактеризовывает большее количество десятичных символов — к примеру, 0,0001 соответствует наименьшему относительному изменению по сопоставлению с 0,01. Наилучшая сходимость просит больше времени на поиск Задание 1. Решить линейную оптимизационную задачу. рационального решения.

Линейная модель

Служит для ускорения поиска решения линейной задачки оптимизации.

Демонстрировать результаты итераций

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

Автоматическое масштабирование

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

Неотрицательные значения

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

Оценка

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

Линейная – служит для использования линейной экстраполяции Задание 1. Решить линейную оптимизационную задачу. повдоль касательного вектора.

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

Разности

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

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

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

Способ поиска

Служит для выбора метода оптимизации — способ Ньютона либо сопряженных градиентов — для указания направления поиска.

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

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

Утилита «

Поиск решения» позволяет представлять результаты в виде 3-х отчетов: Результаты, Устойчивость и Пределы.

Для генерации 1-го либо нескольких отчетов выделяются их наименования в окне диалога Поисковые результаты решения.

Отчет по стойкости содержит информацию о том, как мотивированная ячейка чувствительна к изменениям ограничений и переменных Задание 1. Решить линейную оптимизационную задачу.. Этот отчет имеет два раздела: один для изменяемых ячеек, а 2-ой для ограничений. Раздел для изменяемых ячеек содержит значение нормированного градиента, которое указывает, как целая ячейка реагирует на повышение значения в соответственной изменяемой ячейке на одну единицу. Схожим образом множитель Лагранжа в разделе для ограничений указывает, как мотивированная ячейка Задание 1. Решить линейную оптимизационную задачу. реагирует на повышение соответственного значения ограничения на одну единицу.

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

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

ПРАКТИЧЕСКАЯ ЧАСТЬ

Задание 1. Решить линейную оптимизационную задачку.


zadachi-zanyatiya-usvoit-morfologicheskie-substrati-dlya-razvitiya-hirurgicheskih-oslozhnenij-saharnogo-diabeta.html
zadachi-znakomstvo-detej-so-shkoloj-i-professiej-uchitelya-sozdanie-predmetno-razvivayushej-sredi-dlya-oznakomleniya-vospitannikov-so-shkoloj-didakticheskie-i-syuzhetno-rolevie-igri.html
zadachi.html