--PAGE_BREAK--3.Ввод и редактирование ограничений
Диалоговые окна изменения и добавления ограничений одинаковы, рис.2.
В поле Ссылка на ячейку вводится адрес или имя ячейки или диапазона, на значения которых накладываются ограничения.
Выберите из раскрывающегося списка условный оператор, который необходимо разместить между ссылкой и её ограничением. Это знаки операторов: не более, не менее, равно и т. д.
В поле Ограничения введите число, формулу или имя ячейки или диапазона содержащих или вычисляющих ограничивающие значения.
Чтобы приступить к набору нового условия, нажмите кнопку Добавить.
Чтобы вернуться в диалоговое окно Поиск решения, нажмите кнопкуОК.
Условные операторы целого и двоичного типа можно применять только при наложении ограничений на изменяемые ячейки.
Рис.2.Диалоговое окноИзменение ограничения.
4. Настройка параметров алгоритма и программы
Настройка параметров алгоритма и программы производится в диалоговом окне Параметры поиска решения, рис. 3.
В окне устанавливаются ограничения на время решения задач, выбираются алгоритмы, задаётся точность решения, предоставляется возможность для сохранения вариантов модели и их последующей загрузки. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач.
Рис. 3. Диалоговое окноПараметры поиска решения.
Поле Максимальное время служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах) не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства лабораторных работ.
Поле Предельное число итераций служит для управления временем решения задачи, путём ограничения числа промежуточных вычислений. В поле можно ввести время (в секундах) не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.
При достижении отведённого временного интервала или при выполнении отведённого числа итераций, на экране появляется диалоговое окно Текущее состояние поиска решения.
Поле Относительная погрешность служит для задания точности (допустимой погрешности), с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 (нуля) до1. Низкая точность соответствует введённому числу, содержащему меньшее количество десятичных знаков, чем число, используемое по умолчанию, например, 0,0001. Высокая точность увеличит время, которое требуется для того, чтобы сошёлся процесс оптимизации. Чем меньше введённое число, тем выше точность результатов.
Поле Допустимое отклонение служит для задания допуска на отклонение от оптимального решения, если множество значений влияющей ячейки ограничено множеством целых чисел. При указании большого допуска поиск решения заканчивается быстрее.
Поле Сходимость результатов поиска решения применяется только к нелинейным задачам. Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается. Условием сходимости служит дробь из интервала от 0 (нуля) до 1. Лучшую сходимость характеризует большее количество десятичных знаков, например, 0,0001 – это меньшее относительное изменение, чем 0,01. Чем меньше его значение, тем выше точность результатов. Лучшая сходимость требует больше времени на поиск оптимального решения.
Флажок Линейная модель служит для ускорения поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи.
Флажок Неотрицательные значения позволяет установить нулевую нижнею границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна Добавить ограничение.
Флажок Автоматическое масштабирование служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине, например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.
Флажок Показывать результаты итераций служит для приостановки поиска решения для просмотра результатов отдельных итераций.
Кнопки Оценки служат для указания метода экстраполяции (линейная или квадратичная), используемого для получения исходных оценок значений переменных в каждом одномерном поиске.
Линейная служит для использования линейной экстраполяции вдоль касательного вектора.
Квадратичная служит для использования квадратичной экстраполяции, которая даёт лучшие результаты при решении нелинейных задач.
Кнопки Разности (производные) служат для указания метода численного дифференцирования (прямые или центральные производные), который используется для вычисления частных производных целевых и ограничивающихся функций.
Прямые используется для гладких непрерывных функций.
Центральные используется для функций, имеющих разрывную производную. Не смотря на то, что данный способ требует больше вычислений, он может помочь при получении итогового сообщения о том, что процедура поиска решения не может улучшить текущий набор влияющих ячеек.
Кнопки Метод поиска служат для выбора алгоритма оптимизации (метод Ньютона или сопряжённых градиентов).
Кнопка Ньютона служит для реализации квазиньютоновского метода, в котором запрашивается больше памяти, но выполняется меньше итераций, чем в методе сопряжённых градиентов. Здесь вычисляются частные производные второго порядка.
Кнопка Сопряжённых градиентов служит для реализации метода сопряжённых градиентов, в котором запрашивается меньше памяти, но выполняется больше итераций, чем в методе Ньютона. Данный метод следует использовать, если задача достаточно велика и необходимо экономить память, а также если итерации дают слишком малое отличие в последовательных приближениях.
Для решения линейных задач используются алгоритмы симплексного метода. Для решения целочисленных задач используется метод ветвей и границ.
Команда Сохранить модель служит для отображения на экране диалогового окна Сохранить модель, в котором можно задать ссылку на область ячеек, предназначенную для хранения модели оптимизации. Данный вариант предусмотрен для хранения на листе более одной модели оптимизации. Первая модель сохраняется автоматически.
Команда Загрузить модель служит для отображения на экране диалогового окна Загрузить модель, в котором можно задать ссылку на область ячеек, содержащих загружаемую модель.
продолжение
--PAGE_BREAK--Сохранение и загрузка модели
1. Сохранение модели оптимизации
В меню Сервис выберите команду Поиск решения. Нажмите кнопкуПараметры. Нажмите кнопку Сохранить модель. Появляется окно Сохранить модель, рис. 4. В поле Задайте область модели введите ссылку на верхнюю ячейку столбца, в котором хотите разместить модель оптимизации.
Рис. 4. Диалоговое окноСохранить модель.
Значения элементов управления диалоговых окон Поиск решения и Параметры поиска решения записываются на лист. Чтобы использовать на листе несколько моделей оптимизации, нужно сохранить их в разных диапазонах (столбцах).
Предлагаемый диапазон содержит ячейку для каждого ограничения, а также ещё три ячейки. Можно также ввести ссылку только на верхнюю ячейку столбца, в котором следует сохранить модель.
Диалоговое окно Загрузить модель используется для задания ссылки на область загружаемой модели оптимизации. Ссылка должна адресовать область модели целиком, недостаточно указать только первую ячейку.
2. Загрузка модели оптимизации
Перед тем как использовать данную процедуру, необходимо сохранить хотя бы одну модель.
1 В меню Сервис выберите команду Поиск решения.
2. Нажмите кнопкуПараметры.
3. Нажмите кнопкуЗагрузить модель. Появляется окно, аналогичное окнуСохранить модель.
4. Введите ссылку на область модели.
Диалоговое окно Загрузить модель используется для задания ссылки на область загружаемой (ранее сохранённой) модели оптимизации. Ссылка должна адресовать область модели целиком не достаточно указать только первую ячейку.
Вычисления и результаты решения задачи Для запуска оптимизатора нажмите кнопку Выполнитьв окне Поиск решения. Программа начинает работать, в строке сообщений (слева внизу листа) появляется сообщение Постановка задачи…Ваша таблица с моделью и параметрами алгоритма автоматически приводится к стандартам постановки задач математического программирования. Это преимущество Excel. В других пакетах Вам пришлось бы оторваться от экономической сути задачи и заниматься формальной математической постановкой задачи. После этапа постановки решается задача. Чтобы прервать поиск решения, нажмите клавишу ESC. MicrosoftExcelпересчитает лист с учётом найденных значений влияющих ячеек. По окончании счёта появляется диалоговое окно Результаты поиска решения,рис. 5.
Рис. 5. Диалоговое окноРезультаты поиска решения.
Нажав соответствующую кнопку можно сохранить найденное решение во влияющих ячейках модели или восстановить исходные значения.
Поле Тип отчёта служит для указания типа отчёта, размещаемого на отдельном листе книги.
Отчёт Результаты используется для создания отчёта, состоящего из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях.
Отчёт Устойчивость используется для создания отчёта, содержащего сведения о чувствительности решения к малым изменениям в формуле модели или в формулах ограничений. Такой отчёт не создаётся для моделей, значения в которых ограничены множеством целых чисел. В случае нелинейных моделей отчёт содержит данные для градиентов и множителей Лагранжа. В отчёт по нелинейным моделям включаются ограниченные затраты, фиктивные цены, а также диапазоны ограничений.
Отчёт Пределы используется для создания отчёта, состоящего из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчёт не создаётся для моделей, значения в которых ограничены множеством целых чисел. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно верхним пределом называется наибольшее значение.
К сожалению, эти отчёты очень неудобны. Они перегружены плохо читаемыми абсолютными ссылками со знаками доллара. Желает лучшего и перевод с английского на русский.
Кнопка Сохранить сценарий служит для отображения диалогового окна Сохранение сценария, в котором можно сохранить сценарий решения задачи, чтобы использовать его в дальнейшем с помощью диспетчера сценариев MicrosoftExcel. В поле Название сценария введите имя сценария. Чтобы создать сценарий, не сохраняя найденное решение и не отображая результатов на листе, сохраните сценарий в диалоговом окне Результаты поиска решения, а затем выберите Восстановить исходные значения.
Просмотр промежуточных результатов поиска решения
Режим пошагового решения задач используется при отладке моделей.
В диалоговом окне Поиск решения нажмите кнопку Параметры.
Чтобы получить возможность просмотра текущих значений влияющих ячеек каждой итерации, установите флажокПоказывать результаты итераций, нажмите кнопку ОК, а затем кнопкуВыполнить.
На экране появится диалоговое окно Текущее состояние поиска решения, рис. 6, а влияющие ячейки листа изменят свои значения.
Чтобы остановить поиск решения и вывести на экран диалоговое окно Результаты поиска решения, нажмите кнопку Стоп.
Рис.6. Диалоговое окноТекущее состояние поиска решения.
Чтобы выполнить следующую итерацию и просмотреть её результаты,нажмите кнопку Продолжить.
продолжение
--PAGE_BREAK--Возникающие проблемы и сообщения процедуры поиска решения
Оптимальное решение не найдено
Поиск решения может остановиться до достижения оптимального решения по следующим причинам.
Пользователь прервал процесс поиска.
Команда Показывать результаты итераций в диалоговом окне Параметры поиска решения выбрана перед Выполнить.
Пользователь нажал кнопкуСтоп в режиме пошагового выполнения итераций, по истечении времени, отведённого на работу процедуры, или после выполнения заданного числа итераций.
Установлен флажок Линейная модель в диалоговом окне Параметры поиска решения, в то время как решаемая задача не линейна.
Значение, заданное в поле Установить целевую диалогового окна Поиск решения, неограниченно увеличивается или уменьшается. Необходимо уменьшить значения полей Максимальное время или Итерации в диалоговом окне Параметры поиска решения.
В случае задач, значения в которых ограничены множеством целых чисел, необходимо уменьшить значение в поле Допустимое отклонение диалогового окна Параметры поиска решения, что позволит найти лучшее решение.
В случае нелинейных задач необходимо уменьшить значение в поле Сходимость диалогового окна Параметры поиска решения, что позволит продолжать поиск решения, когда значение в целевой ячейке изменяется медленно.
Если значения влияющих ячеек или значения влияющей и целевой ячеек различаются на несколько порядков, необходимо установить флажок Автоматическое масштабирование в диалоговом окне Параметры поиска решения. Внесите нужные изменения и запустите процедуру поиска решения снова.
Если найденное решение нелинейной задачи существенно отличается от ожидаемого результата, запустите процедуру поиска решения с другими начальными значениями влияющих ячеек. Если задать такие значения влияющих ячеек, которые близко расположены от экстремальной точки целевой функции, можно значительно сократить время поиска решения.
Итоговые сообщения процедуры поиска решения
1. Если поиск решения успешно завершён, в диалоговом окне Результаты поиска решения выводится одно из следующих сообщений.
Решение найдено. Все ограничения и условия оптимальности выполнены.
Все ограничения соблюдены с установленной точностью и найдено заданное значение целевой ячейки.
Поиск свёлся к текущему решению. Все ограничения выполнены.
Относительное изменение значения в целевой ячейке за последние пять итераций стало меньше установленного значения параметра Сходимость в диалоговом окне Параметры поиска решения. Чтобы найти более точное решение, установите меньшее значение параметра Сходимость, но это займёт больше времени.
2. Если поиск не может найти оптимальное решение, в диалоговом окне Результаты поиска решения выводится одно из следующих сообщений.
Поиск не может улучшить текущее решение. Все ограничения выполнены.
В процессе поиска решения нельзя найти такой набор значений влияющих ячеек, который был бы лучше текущего решения. Приблизительное решение найдено, но либо дальнейшее уточнение невозможно, либо заданная погрешность слишком высока. Измените погрешность на меньшее число и запустите процедуру поиска решения снова.
3. Поиск остановлен (истекло заданное на поиск время).
Время, отпущенное на решение задачи, исчерпано, но достичь удовлетворительного решения не удалось. Чтобы при следующем запуске процедуры поиска решения не повторять выполненные вычисления, установите переключатель Сохранить найденное решение или Сохранить сценарий.
4. Поиск остановлен (достигнуто максимальное число итераций).
Произведено разрешённое число итераций, но достичь удовлетворительного решения не удалось. Увеличение числа итераций может помочь, однако следует рассмотреть результаты, чтобы понять причины остановки. Чтобы при следующем запуске процедуры поиска решения не повторять выполненные вычисления установите переключатель Сохранить найденное решение или Сохранить сценарий.
5. Значения целевой ячейки не сходятся.
Значение целевой ячейки неограниченно увеличивается (или уменьшается), даже если все ограничения соблюдены.Возможно, следует в задаче снять одно ограничение или сразу несколько, или наложить дополнительные ограничения. Изучите процесс расхождения решения, проверьте ограничения и запустите задачу снова. Например, в задаче об оптимальных портфелях банков, если не наложить ограничение на портфель привлечения ресурсов, то банк как аферист будет занимать деньги до бесконечности.
6. Поиск не может найти подходящее решение.
В процессе поиска решения нельзя сделать итерацию, которая удовлетворяла бы всем ограничениям при заданной точности. Вероятно, ограничения противоречивы. Исследуйте лист на предмет возможных ошибок в формулах ограничений или в выборе ограничений.
7. Поиск остановлен по требованию пользователя.
Нажата кнопка Стоп в диалоговом окне Текущее состояние поиска решения после прерывания поиска решения в процессе выполнения итераций.
8. Условия для линейной модели не удовлетворяются.
Установлен флажок Линейная модель, однако итоговый пересчёт порождает такие значения, которые не согласуются с линейной моделью. Это означает, что решение недействительно для данных формул листа. Чтобы проверить линейность задачи, установите флажок Автоматическое масштабирование и повторно запустите задачу. Если это сообщение опять появится на экране, снимите флажок Линейная модель и снова запустите задачу.
9. При поиске решения обнаружено ошибочное значение в целевой ячейке или в ячейке ограничения.
При пересчёте значений ячеек обнаружена ошибка в одной формуле или в нескольких сразу. Найдите целевую ячейку или ячейку ограничения, порождающие ошибку, и измените их формулы так, чтобы они возвращали подходящее числовое значение.
Набрано неверное имя или формула в окне Добавить ограничение или окне Изменить ограничение или в поле Ограничения были заданы целое или двоичное ограничение. Чтобы ограничить значения ячейки множеством целых чисел, выберите оператор целого ограничения в списке условных операторов. Чтобы установить двоичное ограничение, выберите оператор для двоичного ограничения.
10. Мало памяти для решения задачи.
Система не смогла выделить память, необходимую для поиска решения. Закройте некоторые файлы или приложения, и попытайтесь снова выполнить процедуру поиска решения.
продолжение
--PAGE_BREAK--Примеры выполнения задач
ПРИМЕР № 1
Для изготовления четырёх видов продукции используют три вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице.
Какое количество продукции каждого вида должно изготовляться, чтобы доход от реализации был максимальным?
Тип сырья
Нормы расхода сырья на одно изделие
Запасы сырья
А
Б
В
Г
I
1
2
1
0
18
II
1
1
2
1
30
III
1
3
3
2
40
ЦЕНА ИЗДЕЛИЯ
12
7
18
10
Решение
1. Формулировка математической модели задачи:
· переменные для решения задачи: x
1 – суточный объём изготовления продукции А, x
2 – суточный объём изготовления продукции Б, x
3 – суточный объём изготовления продукции В, x
4 – суточный объём изготовления продукции Г;
· определение функции цели (критерия оптимизации). Суммарная суточная прибыль от изготовления всех видов продукции равна:
F=12*x1 +7*x2 +18*x3 +10*x4,
поэтому цель состоит в том, чтобы среди всех допустимых значений x1, x2, x3, x4 найти такие, которые максимизируют суммарную прибыль от изготовления продуктов F:
F=12*x1 +7*x2 +18*x3 +10*x4 max;
· ограничения на переменные:
1. объём производства продукции не может быть отрицательным, т. е.
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0;
2. расход исходного продукта для изготовления всех видов продукции не может превосходить максимально возможного запаса данного исходного продукта, т. е.
1*x1 +2*x2 +1*x3 +0*x4 ≤ 18,
1*x1 +1*x2 +2*x3 +1*x4 ≤ 30,
1*x1 +3*x2 +3*x3 +2*x4 ≤ 40,
Таким образом, получаем следующую математическую модель задачи:
· Найти максимум следующей функции:
F=12*x1 +7*x2 +18*x3 +10*x4 max;
· При ограничениях вида:
1*x1 +2*x2 +1*x3 +0*x4 ≤ 18,
1*x1 +1*x2 +2*x3 +1*x4 ≤ 30,
1*x1 +3*x2 +3*x3 +2*x4 ≤ 40,
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0;
2. Подготовка листа рабочей книги
MS
Excel для вычислений – на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рис. 7. Переменные задачи x1, x2, x3, x4 находятся соответственно в C3, С4, С5, С6. Целевая функция находится в ячейке С8 и содержит формулу:
=12*C3+7*C4+18*C5+10*C6
Ограничения на задачу учтены в ячейках С10: С12.
3. Работа с надстройкой Поиск решения – воспользовавшись командой Сервис | Поиск решения, вводим необходимые данные для рассматриваемой задачи (установка данных в окне Поиск решения приведена на рис. 8). Результат работы по поиску решения помещён на рис. 9 – 14.
Рис. 7. Рабочий лист
MS
Excelдля решения задачи.
Рис. 8. Установка необходимых параметров задачив окне Поиск решения.
Рис.9. Результаты расчёта надстройки Поиск решения.
продолжение
--PAGE_BREAK--