68013

Поиск решения

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-09-17

991 KB

6 чел.

Поиск решения

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

Формулировка задачи

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

а) определить, каковы переменные модели;

б) выбрать целевую функцию;

в) задать ограничения, которым должны удовлетворять переменные.

При подготовке рабочего листа к решению задачи нужно:

  1.  отвести диапазон ячеек для хранения переменных величин;
  2.  в отдельную ячейку ввести функцию цели. Функция цели всегда зависит от переменных, поэтому в ячейке с целевой функцией будут использованы ссылки на ячейки, где хранятся переменные;
  3.  подготовить значения и формулы для задания ограничений. Поскольку ограничения накладываются на переменные, то в формулах для задания ограничений будут использованы ссылки на ячейки, где хранятся переменные.

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

После построения математической модели можно обратиться к средству Поиск решения. Для этого нужно воспользоваться командой Tools|Solver – Сервис|Поиск решения. (Если эта команда недоступна, то сначала нужно выполнить следующую последовательность действий: вызвать диалоговое окно Надстройки с помощью команды Tools|Add-Ins – Сервис|Надстройки и установить флажок Solver Add-in – Поиск решения.) На экране появится окно диалога Поиск решения (рис. 1).

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

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

Список Ограничения представляет все ограничения, накладываемые на переменные. Чтобы добавить ограничение, нужно воспользоваться кнопкой Добавить. На экране появится диалоговое окно (рис. 2).

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

Кнопка Добавить позволит задать несколько ограничений, кнопка ОК добавляет ограничение и закрывает это окно.

Кнопка Изменить диалогового окна Поиск решения позволяет модифицировать выделенное в списке Ограничения ограничение. При этом на экране появится диалоговое окно Добавление ограничение
(рис. 2) с уже заполненными элементами управления.

Кнопка Удалить диалогового окна Поиск решения позволяет удалить выделенное ограничение.

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

Параметры поиска решения

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

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

Таблица 1. Параметры поиска решения

Название

Описание

Поле Максимальное время

Определяет время, отпускаемое на решение задачи

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

Позволяет ограничить число промежуточных вычислений 

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

Задает точность выполнения ограничений. Чем ближе значение к 1, тем ниже точность

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

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

Поле Сходимость

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

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

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

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

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

Флажок Показывать результаты итераций

Может быть использован для просмотра процесса нахождения решения

Группы Оценки, Разности, Метод поиска

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

Примеры задач

Транспортная задача

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

Заводы

Производство цемента (т/сут)

Стоимость перевозки 1т цемента, руб.

Комбинат 1

Комбинат 2

Комбинат 3

1

40

10

15

25

2

60

20

30

30

Потребности
в цементе

50

20

30

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

Решение. В качестве неизвестных величин выступают объемы перевозок. Пусть xij объем перевозки цемента с iго завода на jй комбинат, pij  стоимость перевозки 1т цемента с iго завода на jй комбинат. Тогда функция цели представляет собой суммарные транспортные расходы:. Эту функцию надо минимизировать.

Неизвестные в данной задаче должны удовлетворять следующим ограничениям.

  1.  Объемы перевозок не могут быть отрицательными, т.е. .
  2.  Весь цемент с заводов должен быть вывезен. Пусть аi  объем производства цемента на i-ом заводе. Тогда это ограничение выглядит следующим образом: .
  3.  Потребности всех комбинатов в цементе должны быть удовлетворены. Если за bj обозначить потребность в цементе j-го комбината, то это условие может быть записано так: .

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

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

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

Замечание. В рассмотренном примере задача является сбалансированной: суммарный объем произведенной продукции равен суммарному объему потребности в ней. Поэтому в этой модели не надо учитывать издержки, связанные со складированием (при перепроизводстве) или с недопоставками (при дефиците). В противном случае в модель нужно было бы ввести:

(в случае перепроизводства) фиктивный комбинат, стоимость перевозок единицы продукции в который будет равна стоимости складирования, а потребности в продукции объемам складирования излишков продукции на заводах;

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


 

А также другие работы, которые могут Вас заинтересовать

21500. Интенсивная терапия травматического и ожогового шока 146 KB
  Определение патогенез шока. Но он всегда проявляется расстройствами кровообращения на тканевом уровне в виде кризиса микроциркуляции и эти нарушения косвенно отражаются на клинических проявлениях шока. Характерным для шока является возрастание активности симпатоадреналовой системы что проявляется тахикардией но иногда высокая симпатоадреналовая активность может быть завуалирована действием основного фактора гистамина при анафилактическом шоке сердечной блокады в результате повреждения проводящей системы тампонады перикарда.
21501. ИНФЕКЦИОННЫЕ ОСЛОЖНЕНИЯ У ПОСТРАДАВШИХ С ТЯЖЕЛОЙ МЕХАНИЧЕСКОЙ ТРАВМОЙ И БОЛЬНЫХ ХИРУРГИЧЕСКОГО ПРОФИЛЯ (Антибактериальная профилактика и химиотерапия) 116.5 KB
  Успехи достигнутые современной хирургией и в частности хирургией повреждений позволили существенно снизить вероятность развития инфекционных осложнений связанных с первичной контаминацией раны. Этиологическая структура возбудителей инфекционных осложнений Структура возбудителей инфекционных осложнений определяется следующими основными факторами: эволюцией микроорганизмов и приобретением ими резистентности к антибактериальным препаратам; путями передачи возбудителя Изменения структуры возбудителей инфекционных осложнений у пострадавших с...
21502. ИНФУЗИОННО-ТРАНСФУЗИОННАЯ ТЕРАПИЯ ПРИ КРИТИЧЕС 24.5 KB
  Влияние инфузионной терапии на организм. Методы и техника проведения инфузионной терапии. Техническое обеспечение инфузионной терапии. Осложнения инфузионной терапии.
21503. Инфузионно-трансфузионная терапия при критических состояниях 136 KB
  Ее развитие определялось прежде всего уровнем научных разработок по изучению электролитного состава крови для поддержания ионного равновесия плазмы придания ей коллоидных и питательных свойств и создания в конечном итоге оптимальных по составу кровезамещающих растворов пригодных для терапии тех или иных заболеваний. Поэтому в это время появляются ряд новых препаратов созданных на основе солевых растворов с добавлением гомогенной или обработанной физическими или химическими методами гетерогенной плазмы крови жидкость Петрова сыворотка...
21504. Коррекция нарушений водно-солевого обмена 263 KB
  Скорость внутривенного введения К не более 20 ммоль ч 1 г КCl соответствует 136 ммоль К; при более быстром введении возникает опасность остановки сердца. Концентрация Na в плазме крови становится выше 147 ммоль л точно отражает дефицит свободной воды.массу тела кг 142 где сNaпл концентрация Na в плазме крови больного ммоль л; 142 концентрация Na в плазме крови ммоль л в норме; 06 60 содержание всей воды в организме по отношению к массе телал. Изотоническая дегидратация означает истинный дефицит Na в организме так как...
21505. ИНЖЕНЕРНО-ТЕХНИЧЕСКОЕ И МЕТРОЛОГИЧЕСКОЕ ОБЕСПЕЧЕНИЕ СРЕДСТВ ИЗМЕРЕНИЙ АППАРАТОВ ИСКУССТВЕННОЙ ВЕНТИЛЯЦИИ ЛЕГКИХ И ИНГАЛЯЦИОННОГО НАРКОЗА 183 KB
  ЦЕЛЕВОЕ НАЗНАЧЕНИЕ ЛЕКЦИИ: представить данные свидетельствующие значимость проблемы инженернотехнического и метрологического обеспечения средств измерений аппаратов ИВЛ ИН; ознакомить слушателей с необходимостью срочного решения проблемы в лечебных учреждениях; представить основные пути совершенствования инженернотехнического и метрологического обеспечения средств измерений аппаратов ИВЛ ИН; ознакомить с протоколом действий €œМетрологической проверки средств измерений аппаратов ИВЛ ИН. Состояние инженернотехнического и...
21506. Структурно-функциональные связи легких, воздухоносных путей и паренхимы легких 226 KB
  Структурнофункциональные связи легких воздухоносных путей и паренхимы легких 1.1 Структура воздухоносных путей паренхимы легких Механика дыхания Распределение вентиляции 2. Легочное кровообращение и его отношение к вентиляции Легочное кровообращение Вентиляционноперфузионные отношения Обмен газов и их транспорт Обмен газов в легких Транспорт газов к периферическим тканям и в обратном направлении Регуляция дыхания Основная функция легких обмен газов: поглощение кислорода из окружающей среды удаление из организма двуокиси кислорода....
21507. РЕСПИРАТОРНЫЙ ДИСТРЕСС-СИНДРОМ ВЗРОСЛЫХ 366 KB
  Этиология РДСВ.Petti описал РДСВ ARDSкак синдром острой дыхательной недостаточности характеризуемой некардиогенным отеком легких с тяжелой гипоксемией вызываемой интрапульмональным шунтированием справа налево с вторичным ателектазированием и заполнением воздушного пространства отечной жидкостью. О распостранености РДСВ дают представления следующие данные: в США частота распостранения РДСВ составляет 06 1000при этом летальность на 150000 случаев РДСВ приблизительно равна 5060 в то же время WebsterCohen и...