Метод перебора в excel

Обновлено: 07.07.2024

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

Взаимосвязь некоторых распределений в MS EXCEL

Рассмотрим взаимосвязь Биномиального распределения, распределения Пуассона, Нормального распределения и Гипергеометрического распределения. Определим условия, когда возможна аппроксимация одного распределения другим, приведем примеры и графики.

Перестановки с повторениями: Комбинаторика в MS EXCEL

Подсчитаем в MS EXCEL количество перестановок с повторениями из n элементов. С помощью формул выведем на лист все варианты таких перестановок (английский перевод термина: permutations of multisets).

Сочетания с повторениями: Комбинаторика в MS EXCEL

Подсчитаем в MS EXCEL количество Сочетаний с повторениями из n по k (выборка с возвращением). Также с помощью формул выведем на лист соответствующие варианты Сочетаний (английский перевод термина: combinations with …

Разрезка на мерные длины

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

Размещения без повторений: Комбинаторика в MS EXCEL

Подсчитаем в MS EXCEL количество Размещений из n по k и с помощью формул выведем на лист соответствующие варианты размещений (английский перевод термина: partial permutation или sequence without repetition).

Перестановки без повторений: Комбинаторика в MS EXCEL

Подсчитаем в MS EXCEL количество перестановок из n элементов. С помощью формул выведем на лист все варианты перестановок (английский перевод термина: permutation).

Размещения c повторениями: Комбинаторика в MS EXCEL

Подсчитаем в MS EXCEL количество Размещений с повторениями из n по k (выборка с возвращением). Также с помощью формул выведем на лист соответствующие варианты Размещений (английский перевод термина: sequence with …

Комбинаторика в MS EXCEL

Обзорная статья, в которой приведены основные функции MS EXCEL для вычисления количества перестановок, сочетаний и размещений. Рассмотрены варианты комбинаций без повторений и с повторениями (выборка с возвращением).

Комбинации элементов из нескольких множеств: Комбинаторика в MS EXCEL

Пусть имеется несколько множеств — , , , количество элементов в которых может быть различно. Требуется составить все возможные комбинации элементов …

Сочетания без повторений: Комбинаторика в MS EXCEL

Подсчитаем в MS EXCEL количество сочетаний из n элементов по k. С помощью формул выведем на лист все варианты сочетаний (английский перевод термина: Combinations without repetition).

При решении экономических и финансовых задач достаточно часто решение задачи приобретает вид математической модели (формулы), построенной на основе выявленных связей между изучаемыми элементами явления (результативного показателя) и самим явлением в целом. Изменяя составляющие элементы, можно проводить анализ изменения явления в целом. Таким образом, изучаются свойства и значения функции (явления) в тех или иных условиях. Этот анализ позволяет проводить инструмент MS Excel Подбор параметра. Рассмотрим возможности его применения на конкретных примерах.

Нахождение значения аргумента функции, соответствующего определённому значению функции

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

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

Значение в ячейке С1 представляет собой среднее арифметическое значение в ячейках А1 и В1:

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

Безусловно, можно самостоятельно путём перебора значений в ячейке А1 достичь необходимый результат. Однако, в целях минимизации затрат времени следует воспользоваться функцией Подбор параметра.

Для этого необходимо:

1) выполнить команду Подбор параметра из меню Данные > Анализ "что-если".

В результате появится запрос Подбор параметра:

2) в поле Установить в ячейке ввести ссылку или имя ячейки, содержащую формулу, для которой следует подобрать параметр. Автоматически в поле Установить в ячейке отображается имя ячейки, которая была активной на момент выполнения команды Подбор параметра. Кнопка свёртывания окна диалога, расположенная справа от поля, позволяет временно убрать диалоговое окно с экрана, чтобы было удобнее выделить диапазон на листе. Выделив диапазон, следует нажать кнопку для вывода на экран диалогового окна.

3) в поле Значение ввести число, которое должно возвращать формула с искомым значением параметра. Например, 855.

4) в поле Изменяя значение ячейки указать ссылку на ячейку, содержащую параметр, значение которого требуется подобрать для получения требуемого результата. На эту ячейку прямо или косвенно должна ссылаться формула, содержащаяся в ячейке, адрес которой указан в поле Установить в ячейке. В нашем случае это А1.

В итоге диалоговое окно примет следующий вид:

5) нажать кнопку ОК для закрытия диалогового окна. После выполнения этого действия появляется запрос Результат подбора параметра, а искомое значение параметра отображается в ячейке А1:

Использование функции Подбор параметра для нахождения значения аргумента функции при изменении вида ее графика

Допустим, что для решения поставленной задачи нам предстоит проанализировать построенный в Ms Excel график функции y = 3x-5 в диапазоне аргумента от –3 до 6.

Для этого следует:

3\dot А1-5

1) в ячейки А1-А10 ввести значения от –3 до 6 с шагом 1; в ячейку В1 – ввести формулу и путём перетаскивания маркера заполнения скопировать эту формулу на ячейки В2-В10. В результате соответствующий участок листа примет следующий вид:

2) выделив диапазон В1-В10, выберите тип диаграммы "График" на вкладке Вставить в группе Диаграммы.

3) На вкладке Макет в группе Подписи нажмите кнопку Подписи данных, а затем выберите нужный параметр отображения.

4) На вкладке Конструктор в группе Данные нажмите Выбрать данные.

5) В появившемся окне Выбор источника данных выберите Подписи горизонтальной оси. Задайте диапазон подписей оси диапазон А1-А10.

В результате должен быть построен график функции:

Далее предположим, что необходимо узнать значение аргумента данной функции, при котором значение самой функции будет равно 0.

Чтобы решить эту задачу с помощью построенного графика и функции Подбор параметра необходимо:

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

а затем выделить щелчком сам маркер

2) в меню Данные > Анализ выбрать функцию Поиск решения

3) если значение маркера данных получено из формулы, появится диалоговое окно Подбор параметра:

4) в поле Оптимизировать целевую функцию отображается ссылка на ячейку, содержащую формулу, в поле Значения – требуемая величина. Так, в данном случае следует указать ячейку В6 и значение "0" соответственно и нажать кнопку ОК.

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

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

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

y=2\cdot x^<2></p> <p>Поиск решения позволяет находить одно значение аргумента, соответствующее заданному значению функции (например, 0). Однако часто функция может принимать одно значение при нескольких значениях аргументов. То есть уравнение может иметь несколько корней. Например, функция -9
может принимать значение 0 при двух значениях аргументов.

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

Так, если попытаться решить указанное выше уравнение с помощью Ms Excel и встроенной в него функции Подбор параметра, то исходные данные можно представить в следующем виде:

Выполнив команду Подбор параметра из меню Данные > Анализ "Что-если", необходимо заполнить поля диалогового окна следующим образом:

В результате найденным корнем уравнения будет значение 2,121343 в ячейке А4 (рис. 11. рис. 11.14).

y=2\cdot x^<2></p> <p>Однако, это не единственный корень. В этом можно убедиться, решив уравнение или построив график функции -9
.

Для построения графика следует:

  1. в ячейки С4-С24 ввести значения от –10 до 10 с шагом 1; в ячейку D4 – ввести формулу 2*C4*C4-9 и путём перетаскивания маркера заполнения заполнить этой формулой ячейки D5-D24 ;
  2. выделив диапазон D4-D24 , выбрать тип диаграммы График в меню Вставка > Диаграммы;
  3. На вкладке Конструктор в группе Данные нажмите Выбрать данные.
  4. В появившемся окне Выбор источника данных выберите Подписи горизонтальной оси. Задайте диапазон подписей оси диапазон С4-С24.

В результате должен быть построен график функции:

2\cdot x^<2></p> <p>Из графика видно, что уравнение -9=0
имеет 2 корня, к тому же эти корни примерно равны –2 и 2. Одни корень 2,121343 нам уже известен.

Для поиска второго корня можно поступить двояко, используя пункт А или Б методических указаний ниже:

А. Изменим значение, например, в ячейке С12 (более близкое к ожидаемому корню). Выделим ячейку D12 и выполним команду Подбор параметра из меню Данные > Анализ "Что-если". Заполним поля запроса:

и после щелчка по кнопке ОК в ячейке С12 получим значение второго корня -2,12125:

Б. Построим график функции в интервале от -10 до 10.

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

Сделаем активной ячейку D11 со значением функции, равным 9 и в меню Данные > Анализ "что-если" выберем Подбор параметра. Заполним поле Изменяя значение ячейки запроса:

и щелкнув по кнопке ОК, в ячейке С11 получим значение второго корня -2,1213207:

Следует обратить внимание, что значения корня, полученные в п.А и п.Б имеют несущественное отличие. Это вызвано следующим обстоятельством. По умолчанию команда Подбор параметра прекращает итерационные вычисления, когда выполняется 100 итераций, либо при получении результата, который находится в пределах 0,001 от заданного целевого значения. Если нужна большая точность, можно изменить используемые по умолчанию параметры командой Параметры меню Файл > Формулы. Затем на вкладке Параметры вычислений в поле Предельное число итераций введите значение больше 100, а в поле Относительная погрешность – значение меньше 0,001.

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

Задание

Решить уравнение с использованием инструмента Excel Подбор параметра двумя способами:

  1. подбором аргумента для конкретного значения функции;
  2. посредством изменения графика функции.

Удостовериться с помощью построения графика в количестве корней уравнения. Определить все корни.

adjust0.jpg

Не очень частый, но и не экзотический случай. На моих тренингах такой вопрос задавали не один и не два раза :) Суть в том, что мы имеем конечный набор каких-то чисел, из которых надо выбрать те, что дадут в сумме заданное значение.

В реальной жизни эта задача может выглядеть по-разному.

  • Например, мы выгрузили из интернет-банка все платежи, которые поступили на наш счет за последний месяц. Один из клиентов разбивает сумму своего платежа на несколько отдельных счетов и платит частями. Мы знаем общую сумму оплаты и количество счетов, но не знаем их сумм. Надо подобрать те суммы в истории платежей, которые дадут в общем заданное значение.
  • У нас есть несколько рулонов стали (линолеума, бумаги. ), из которых надо подобрать под заказ те, что дадут заданную длину.
  • Блэкджек или в народе "очко". Надо набрать карты суммарной стоимостью максимально близкой к 21 баллу, но не превысить этот порог.

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

Давайте рассмотрим несколько способов решения такой задачи в Excel.

Способ 1. Надстройка Поиск решения (Solver)

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

  • в Excel 2007 и новее зайти Файл - Параметры Excel - Надстройки - Перейти (File - Excel Options - Add-ins - Go)
  • в Excel 2003 и старше - открыть меню Сервис - Надстройки (Tools - Add-ins)

и установить соответствующий флажок. Тогда на вкладке или в меню Данные (Data) появится нужная нам команда.

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

adjust1.jpg

  • Диапазон A1:A20 содержит наши числа, из которых мы будем выбирать нужные, чтобы "вписаться" в заданную сумму.
  • Диапазон В1:B20 будет своего рода набором переключателей, т.е. будет содержать нули или единички, показывая, отбираем мы данное число в выборку или нет.
  • В ячейке E2 стоит обычная автосумма всех единичек по столбцу B, подсчитывающая кол-во выбранных чисел.
  • В ячейке E3 с помощью функции СУММПРОИЗВ (SUMPRODUCT) считается сумма попарных произведений ячеек из столбцов А и B (то есть A1*B1+A2*B2+A3*B3+. ). Фактически, здесь подсчитывается сумма чисел из столбца А, отобранных единичками из столбца В.
  • В розовую ячейку E4 пользователь вводит желаемую сумму для подбора.
  • В ячейке E5 вычисляется абсолютное по модулю значение погрешности подбора с целью ее будущей минимизации.
  • Все желтых ячейках Е8:E17 хотелось бы получить список отобранных чисел, т.е. тех чисел из столбца А, напротив которых в столбце В есть единички. Для этого необходимо выделить сразу все (!) желтые ячейки и в них ввести вот такую формулу массива:

=ЕСЛИОШИБКА(ИНДЕКС($A$1:$A$20;НАИМЕНЬШИЙ(ЕСЛИ(B1:B20=1;СТРОКА(B1:B20);"");СТРОКА()-СТРОКА($E$8)+1));"")

=IFERROR(INDEX($A$1:$A$20;SMALL(IF(B1:B20=1;ROW(B1:B20);"");ROW()-ROW($E$8)+1));"")

После ввода формулы ее необходимо ввести не как обычную формулу, а как формулу массива, т.е. нажать не Enter, а Ctrl+Shift+Enter. Похожая формула используется в примере о ВПР, выдающей сразу все найденные значения (а не только первое).

Теперь перейдем на вкладку (или в меню) Данные и запустим инструмент Поиск решения (Data - Solver):

adjust4.jpg

В открывшемся окне необходимо:

  • Задать как целевую функцию (Target Cell) - ячейку вычисления погрешности подбора E5. Чуть ниже выбрать опцию - Минимум, т.к. мы хотим подобрать числа под заданную сумму с минимальной (а лучше даже нулевой) погрешностью.
  • В качестве изменяемых ячеек переменных (Changing cells) задать диапазон столбца переключателей B1:B20.
  • С помощью кнопки Добавить (Add) создать дополнительное условие на то, что ячейки диапазона B1:B20 должны быть бинарными (т.е. содержать только 0 или 1):

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

adjust3.jpg

Теперь можно либо оставить найденное решение подбора (Сохранить найденное решение), либо откатиться к прежним значениям (Восстановить исходные значения).

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

Найденные комбинации можно сохранять виде сценариев (кнопка Сохранить сценарий), чтобы вернуться к нем позднее с помощью команды Данные - Анализ "что-если" - Диспетчер сценариев (Data - What-If Analysis - Scenario Manager):

adjust7.jpg

И весьма удобно будет вывести все найденные решения, сохраненные в виде сценариев, в одной сравнительной таблице с помощью кнопки Отчет (Summary):

adjust8.jpg

Способ 2. Макрос подбора

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

adjust9.jpg

Для использования макроса нажмите сочетание Alt+F11, в открывшемся окне редактора Visual Basic вставьте новый модуль через меню Insert - Module и скопируйте туда этот код:

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

Рассмотрим задачу коммивояжера (англ. Travelling Salesman Problem, TSP) заключающуюся в отыскании самого короткого маршрута, проходящего через заданные города по одному разу с последующим возвратом в исходный город (также рассмотрим вариант без возврата).

Задача

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

Решение

Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера, лист 5 городов ).



Расстояния рассчитаем с помощью формулы: = КОРЕНЬ((ИНДЕКС($C$7:$D$11;$F7+1;1)-ИНДЕКС($C$7:$D$11;G$6+1;1))^2 +(ИНДЕКС($C$7:$D$11;$F7+1;2)-ИНДЕКС($C$7:$D$11;G$6+1;2))^2)


Теперь создадим модель для Поиска решения .


Совет : Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .

Переменные (выделено зеленым) . В качестве переменных модели следует взять номера городов. Так как начальная и конечная точка известны (Город0), то переменных будет 4. Ограничения (выделено синим) . Необходимо, чтобы номера городов не повторялись. Это означает, что количество уникальных (неповторяющихся) номеров городов должно быть равно 4. Для этого используется формула для подсчета уникальных значений : = СУММПРОИЗВ(1/СЧЁТЕСЛИ(B16:B19;B16:B19))

Целевая функция (выделено красным) . Длина маршрута должна быть минимальной.


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

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

Найденное Решение

Поиск решения найдет (должен найти) самый короткий маршрут, т.е. последовательность 0-1-4-2-3-0 (или обратную).


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

Совет . Таблицы перебора перестановок от 1 до 5, от 1 до 6, … от 1 до 9 можно найти в этой статье Перебор всех возможных Перестановок в MS EXCEL .

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


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

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

В файле примера также приведено решение задачи для замкнутого и незамкнутого маршрута посещения 9 городов. Решения найдены с помощью Эволюционного метода со следующими параметрами: Целочисленная оптимальность 0%, Использовать автоматическое масштабирование, Скорость изменения варьировалась 0,25-0,5; Размер совокупности варьировался 10-50. Оба решения проверены с помощью таблиц перебора всех маршрутов (см. таблицы перебора перестановок ). Если при первом прогоне Поиска решения не удавалось найти оптимальное решение, то он запускался повторно, при этом 1 или 2 параметра изменялись. После второго прогона оптимальное решение, как правило, было найдено.



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

Читайте также: