Решение оптимизационных задач с помощью электронных таблиц

Многие из вас в большей или меньшей степени знакомы с электронными таблицами Excel. Тем не менее необходимо дать определения терминов, наиболее часто встречающихся в этой книге. Данный подход облегчит восприятие материала и позволит сосредоточиться на описании практических приемов для решения конкретных задач.

Ячейка

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

Адрес

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

Ссылка

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

Приложение Excel имеет мощную надстройку «Поиск решения». Она предназначена для поиска оптимального значения (минимума или максимума) заданной функции, которую называют целевой, при наличии некоторых ограничений на варьируемые параметры. Например, при покупке продуктов на рынке ограничениями могут быть: список продуктов, которые надо купить; имеющиеся в наличии деньги; время нахождения на рынке; вес купленных продуктов, который мы можем унести. Целевая функция, наверное, почти у всех будет одинакова: минимум истраченных на покупку денег. Пример целевой функции, для которой мы всегда ищем максимальное значение, наблюдается в задаче трудоустройства. Человек всегда ищет работу с максимальной зарплатой, но при наличии целого ряда ограничений: образование, стаж предыдущей работы, возраст и т.п.

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

Изначально надстройка «Поиск решения» не видна в меню и ее необходимо активировать с помощью меню Файл–Параметры–Надстройки (поставить «галочку» напротив меню «Поиск решений»»). Теперь решить оптимизационные задачи можно обратившись к вкладке «Данные»-«Поиск решений».

Чтобы надстройка работала правильно мы должны указать ей:

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

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

· Ограничения. Их значения также следует разместить в ячейках на листе Excel, а в надстройке прописать их адреса и выбрать знаки (<, =, > и т.п.).

Рассмотрим пример простой оптимизации, чтобы разобраться где и что мы должны указать для правильной работы надстройки. Для этого зададим простейшую целевую функцию Y=Х^2 на листе Excel и построим ее график. Ее минимум очевиден, он равен 0 и при этом единственный аргумент тоже будет равен 0.

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

После этого можно сохранить найденное решение.

Теперь потренируемся задавать ограничения. Например, потребуем, чтобы аргумент был не менее 7. Для этого в поле ограничений (через кнопку «Добавить») укажем адрес аргумента (А20) и адрес конкретного ограничения (С20). В ячейку А20 занесем адрес изменяемой ячейки (А17).

Метод ОПГ – метод обобщенного понижающего градиента (или приведенного градиента). Основная идея метода ОПГ состоит в том, чтобы сократить размерность задачи путем исключения зависимых (базисных) переменных и применить метод приведенного градиента для определения направления спуска и в качестве критерия при установлении оптимальности.

Теперь результат работы надстройки будет уже другим.

Литература.

1) Банди Б Основы линейного программирования, 1989г.

2) Муртаф Б. Современное линейное программирование, 1984г.

3) Хамухин А.А.Решение оптимизационных задач в среде Microsoft Excel.