Функция в excel: поиск решения

Методы решения

Задача коммивояжёра относится к классу NP-трудных и не известен алгоритм,
который позволет гарантировано её решить за полиномиальное по числу городов
N время T ~ Nk, k=const.
Тем не менее, для «обозримого» количества городов существует множество способов решения:

1. Точные методы не только находят некоторое решение, но и при окончании своей работы
доказывают, что это решение — наилучшее. Отметим следующие из них:

• Полный перебор перестановок N-1
  чисел (стартовый город фиксирован). Практически бесполезен при N > 15.
• Направленный поиск с возвратами —
  перебор вариантов «вокруг» некоторого решения с отсечением путей, имеющих длину большую, чем лучший к текущему моменту путь.
• Метод ветвей и границ — наиболее эффективный из известных метод отсечения «неперспективных» узлов, за счёт анализа матрицы расстояний.
  При поиске оптимального решения строится бинарное дерево (в каждом узле порождаются 2 ветви: коммивояжёр
  идёт в некоторый город или не идёт в него).
• Линейное программирование применяется для минимизации (с ограничениями)
  линейной формы d·x, где
  x
  — искомый бинарный вектор размерности

N(N-1)/2, компоненты которого x_i
равны 1 или , в зависимости от того, входит i-е ребро в путь или нет.
Вектор d (той же размерности) равен длинам рёбер.

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

• Жадный алгоритм при выборе очередного города берёт ближайший не посещённый до этого город.
• Метод шнурка — геометрическая вариация жадного алгоритма, в которой города охватываются
  замкнутым контуром. Он постепенно растягивается, стараясь пройти через все города, минимальным образов увеличив свою
  длину.
• Скользящий перебор переставляет местами города из небольшой части пути.
  Затем такое «окно перебора» скользит вдоль всего пути. Метод имеет различные вариации и оказывается эффективным
  способом улучшения решения, найденного предыдущими двумя эвристическими методами.

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

• Метод отжига в котором происходят перестановки городов
  с постепенно «затухающей» интенсивностью. При этом постоянно сохраняется наилучшее найденное решение.
• Генетический алгоритм — более «продвинутый» вариант, при котором
  создаётся большое количество различных путей. Они постоянно «мутируют» и «скрещиваются» друг с другом,
  обмениваясь отдельным участками.

Описательная статистика на базе Пакета анализа данных Excel

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

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

в Excel 2003: дать команду Сервис -> Надстройки и поставить галочку напротив Пакета анализа. Теперь в меню Сервис появится команда Анализ данных.

• в Excel 2007:щелкнуть по кнопке Офис, далее по кнопе Параметры Excel, выбрать Надстройки, в нижней части окна в поле Управления выбрать Надстройки Excel, щелкнуть по кнопке Перейти, поставить галочку напротив Пакета анализаю На вкладке Данные в группе Анализ появится команда Анализ данных
• При выполнении команды Анализ данных вызывается диалоговое окно Анализ данных, в котором выбирается режим Описательная статистика (рис. 23); в одноименном диалоговом окне задаются установки:

рис. Диалоговое окно режима Описательная статистика.

Параметры диалогового окна «Описательная статистика» имеют следующий смысл.

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

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

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

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

К-ый наибольший – порядковый номер наибольшего после максимального значения. Установить флажок, если в выходную таблицу необходимо включить строку для k-го наибольшего значения для каждого диапазона данных. В соответствующем окне ввести число k. Если k равно 1, эта строка будет содержать максимум из набора данных.

К-ый наименьший – порядковый номер наименьшего после минимального значения. Установить флажок, если в выходную таблицу необходимо включить строку для k-го наименьшего значения для каждого диапазона данных. В соответствующем окне ввести число k. Если k равно 1, эта строка будет содержать минимум из набора данных.

Левый столбец содержит метки статистических данных; правый столбец содержит статистические данные.

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

Для изменения места вывода результатов можно установить переключатель Новый рабочий лист, чтобы открыть новый лист и вставить результаты, начиная с ячейки A1.

Можно ввести имя нового листа в поле, расположенном напротив соответствующего положения переключателя.

Если установить переключатель Новая книга, то открывается новая книга, и результаты вставляются в ячейку A1 на первом листе в этой книге.

Итоговая статистика – полный вывод показателей описательной статистики.

Для его определения надо установить флажок, если в выходном диапазоне необходимо получить по одному полю для каждого из следующих видов статистических данных: Среднее, Стандартная ошибка (среднего), Медиана, Мода, Стандартное отклонение, Дисперсия выборки, Эксцесс, Асимметричность, Интервал, Минимум, Максимум, Сумма, Счет, Наибольшее (#), Наименьшее (#), Уровень надежности.

Обзор и возможности функции

Надстройка «Поиск решений» — специфическая возможность Excel 2007, 2010, 2013, 2016, которая предназначена для работы с формулой при наличии определённых условий. Описать её логику можно следуя принципу «что если?». То есть, просчитать изменение конечной ячейки при условии изменения других. Хотя и звучит это сложно, но описать данный принцип удобнее на конкретном примере: как будет изменяться остаток средств в конце месяца, если изменить разные статьи расходов.

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

Скрипт

Для работы скрипта нам понадобятся такие переменные:

• Массив, где мы будем хранить все просчитанные маршруты.
• Порядковый номер текущего маршрута. Как только обрабатываем очередной маршрут, будем увеличивать номер на единицу, чтобы сохранить новый маршрут под новым номером.
• Переменная, где хранится самый короткий путь. Чтобы уже на первом шаге у нас было с чем сравнивать длину маршрута, поместим в неё заведомо большое число, например, 10 000 километров. Как только мы найдём путь короче (а мы найдём), заменим его новым минимальным расстоянием.
• Номер самого короткого маршрута. С его помощью мы вытащим из массива со всеми маршрутами самый короткий из них.

Соберём скрипт. Читайте комментарии:

Решение уравнений

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

Допустим, имеем уравнение: 15x+18x=46. Записываем его левую часть, как формулу, в одну из ячеек. Как и для любой формулы в Экселе, перед уравнением ставим знак «=». Но, при этом, вместо знака x устанавливаем адрес ячейки, куда будет выводиться результат искомого значения.

В нашем случае, формулу мы запишем в C2, а искомое значение будет выводиться в B2. Таким образом, запись в ячейке C2 будет иметь следующий вид: «=15*B2+18*B2».

Запускаем функцию тем же способом, как было описано выше, то есть, нажав на кнопку «Анализ «что если»» на ленте», и перейдя по пункту «Подбор параметра…».

В открывшемся окне подбора параметра, в поле «Установить в ячейке» указываем адрес, по которому мы записали уравнение (C2). В поле «Значение» вписываем число 45, так как мы помним, что уравнение выглядит следующим образом: 15x+18x=46. В поле «Изменяя значения ячейки» мы указываем адрес, куда будет выводиться значение x, то есть, собственно, решение уравнения (B2). После того, как мы ввели эти данные, жмем на кнопку «OK».

Как видим, программа Microsoft Excel успешно решила уравнение. Значение x будет равно 1,39 в периоде.

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

Некоторые настройки Поиска решения

Метод решения
Рассмотренная выше модель является линейной, т.е. целевая функция (M – общий вес, который может быть максимален) выражена следующим уравнением M=a1*x1+a2*x2, где x1 и x2 – это переменные модели (количество коробок и ящиков), а1 и а2 – их веса. В линейной модели ограничения также должны быть линейными функциями от переменных. В нашем случае ограничение по объему V=b1*x1+b2*x2 также выражается линейной зависимостью. Очевидно, что другое ограничение — Максимальное количество тары (n) – также линейно x1+x2 Линейные задачи обычно решаются с помощью Симплекс метода. Выбрав этот метод решения в окне Поиска решения
можно также проверить на линейность саму модель. В случае нелинейной модели Вы получите следующее сообщение:

В этом случае необходимо выбрать метод для решения нелинейной задачи. Примеры нелинейных зависимостей: V=b1*x1*x1; V=b1*x1^0,9; V=b1*x1*x2, где x – переменная, а V – целевая функция.

Кнопки Добавить, Изменить, Удалить
Эти кнопки позволяют добавлять, изменять и удалять ограничения модели.

Кнопка Сбросить
Чтобы удалить все настройки Поиска решения
нажмите кнопку Сбросить
– диалоговое окно очистится.

Загрузить/ Сохранить,
Сохранить
Параметры
Загрузить/ Сохранить
Загрузить

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

Принимая во внимание вычислений в MS EXCEL, рекомендуется, чтобы эти диапазоны варьирования были значительно выше точности вычисления (она обычно устанавливается от 0,001 до 0,000001). Как правило, данные в модели нормируют так, чтобы диапазоны варьирования целевой функции и переменных были в пределах 0,1 – 100 000

Конечно, все зависит от конкретной модели, но если ваши переменные изменяются более чем на 5-6 порядков, то возможно следует «загрубить» модель, например, с помощью операции логарифмирования.

Надстройка Excel «Поиск решения» – это аналитический инструмент, который позволяет нам быстро и легко определить, когда и какой результат мы получим при определенных условиях. Возможности инструмента поиска решения намного выше, чем может предоставить «подбор параметра » в Excel.

Основные отличия между поиском решения и подбором параметра:

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

Настройка «Поиска решений» для таблицы

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

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

Для «Изменяя ячейки переменных» укажите область данных, куда могут вноситься изменения

В моем случае это будут довложения для каждого счета.

Теперь обратите внимание на «В соответствии с ограничениями». У нас есть ограничения, поэтому нужно указать их, чтобы программа понимала, какие значения может использовать и к какому результату ей стремиться

Нажмите «Добавить», чтобы создать первое ограничение.

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

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

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

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

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

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

Я ставил цель показать вам, как работает программа «Поиск решения» в Microsoft Excel, чтобы вы узнали, как можно автоматически найти оптимальные значения для большой таблицы, избегая ручной переборки значений. Надеюсь, все объяснения и примеры были вам понятны, и теперь вы освоили еще одну очень удобную функцию, упрощающую взаимодействие с электронными таблицами, созданными в Экселе.