Материал: 4758

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

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

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

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

Рис. 5. диалоговое окно Параметры поиска Поле Допустимое отклонение служит для задания допуска на

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

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

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

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

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

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

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

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

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

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

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

Задание 2. Проверить установку параметров поиска решения Вашей задачи и при необходимости изменить их.

Окно диалога "Результаты поиска решения"

Поиск решения осуществляется при нажатии кнопки Выполнить окна Поиск решения. На рис. 6 показаны результаты решения задачи оптимизации плана выпуска продукции для условий примера, приведенного на рис. 1.

Рис. 6. Результаты решения задачи оптимизации.

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

При повторном обращении к диалоговому окну Поиск решения и нажатии кнопки Восстановить будут восстановлены все параметры поиска решения и выделения ячеек.

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

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

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

Рис. 7. Окно итогового сообщения о результатах поиска решения. Кнопка Сохранить сценарий служит для отображения окна диалога

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

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

Результаты поиска решения:

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

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

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

Задание 3. Найти оптимальное решение сформулированной задачи, просмотреть его, и восстановить исходные значения задачи. Вновь получить оптимальное решение. Сохранить его с одновременным выводом на отдельных листах Ехсеl всех типов отчетов о поиске решения. Сохранить под выбранным именем книгу Ехсеl с результатами работы.

Итоговые сообщения процедуры поиска решения

Если поиск решения успешно закончен, в окне диалога Результаты поиска решения выводится одно из следующих сообщений:

• Решение найдено. Все ограничения и условия оптимальности выполнены. Все ограничения соблюдены с установленной точностью и найдено заданное значение целевой ячейки.

• Поиск свелся к текущему решению. Все ограничения выполнены.

Значение целевой ячейки не менялось в течение последних пяти итераций.

Решение, возможно, найдено или итеративный процесс улучшает решение очень медленно.

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

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

•Поиск остановлен (истекло заданное на поиск время). Время,

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

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

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

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

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

•Поиск не может найти подходящего решения. В процессе поиска

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

•Поиск остановлен по требованию пользователя. Нажата кнопка Стоп в

окне диалога Текущее состояние поиска решения после прерывания поиска решения или в процессе пошагового выполнения итераций.

•Условия для линейной модели не удовлетворяются. Установлен флажок

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

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

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

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

Содержание отчета по лабораторной работе

1)Постановка задачи.

2)Таблица исходных данных.

3)Таблица результатов расчета.

4)Анализ полученных результатов и выводы.

Практическая работа № 3 (6 ч.)

Решение транспортных задач средствами табличного редактора Excel

Тема работы: Формулировка транспортной задачи и построение ее математической модели. Понятие открытой и закрытой транспортной задачи и ее математическая модель.

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

Содержание работы и порядок ее выполнения

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

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

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

Формулировка транспортной задачи и построение ее математической

модели

Транспортная задача (ТЗ) является частным случаем ЗЛП и формулируется следующим образом: пусть имеются т пунктов отправления (ПО) А1, А2, ..., Ат, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2, ..., ат единиц. Имеются n пунктов назначения (ПН), В1, В2,..., Вn, подавших соответственно заявки на b1, b2, ... , bп единиц груза.