4. Технология решения задач линейного программирования с помощью Поиска решений в среде excel

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

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

Поиск решения позволяет анализировать задачи трех типов:

• линейные (все зависимости между переменными задачи линейны);

• нелинейные (между переменными задачи существует хотя бы одна непропорциональная зависимость);

• целочисленные (результаты решения должны быть целыми числами).

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

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

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

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

Ограничение — это значение ячейки, которое должно находиться в определенных пределах или удовлетворять целевым критериям. Ограничения могут налагаться, как на целевую ячейку, так и на изменяемые ячейки. Для одной модели могут быть определены по два ограничения для каждой изменяемой ячейки (верхний и нижний пределы), а также до 100 дополнительных. Как пра­вило, ограничения накладываются путем использования опера­торов сравнения: <=, >=, =. Ограничения целочисленности целесообразно применять в случаях, когда используемая в задаче величина или искомый результат должны принимать одно из двух значений - "Да" или "Нет"(0 или 1), либо когда дробные значения результатов недопустимы (например, при расчете числа объектов инвестиции, служащих, машин, станков и т.д.).

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

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

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

После завершения поиска решения MS EXCEL предлагает три варианта продолжения работы:

• сохранить полученное решение или восстановить исходные значения на рабочем листе;

• сохранить полученное решение в виде именованного сценария;

• просмотреть один из встроенных отчетов о ходе решения.

ВНИМАНИЕ!!! Прежде, чем запускать инструмент ПОИСК решения, необходимо его включить. Для этого нажмите на кнопку Office (находится в левом верхнем углу MS Excel), затем нажмите на кнопку Параметры Excel. В списке слева выберите пункт Надстройки. Из списка Надстройки выберите пункт Поиск решения и нажмите на кнопку перейти. В появившемся диалоговом окне выберите Поиск решения и нажмите ОК)

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

В диалоговом окне Поиск решения есть три основных параметра:

• Установить целевую ячейку

• Изменяя ячейки

• Ограничения

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

Второй важный параметр средства Поиск решения — это параметр Изменяя ячейки. Изменяемые ячейки — это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в це­левой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования. Они не должны содержать формул, и изменение их значений должно отражаться на изменении резуль­тата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек.

Третий параметр, который нужно вводить, для Поиска решения – это ограничения.

Для решения задачи необходимо:

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

1. Ввести исходные данные.

2. Ввести зависимость для целевой функции

3. Ввести зависимости для ограничений.

Запустить Поиск решений.

4. Назначение целевой функции (установить целевую ячейку).

5. Ввод ограничений.

6. Ввод параметров для решения ЗЛП.

Рассмотрим технологию решения используя условия Примера 2.4.1. (Задача о костюмах).

Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человеко-день трудозатрат. На мужской костюм - 3,5 м шерсти, 0,5 м лавсана и 1 человеко-день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человеко-дней трудозатрат. Tребуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского - 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

Сформулируем экономико-математическую модель задачи.

Введем следующие обозначения: х₁ - число женских костюмов; x₂ - число мужских костюмов.

Прибыль от реализации женских костюмов составляет 10х₁, а от реализации мужских 20х₂, т.е. необходимо максимизировать целевую функцию

f(x) = 10´ х₁ + 20´ х₂ -> max.

Ограничения задачи имеют вид:

х₁ + х₂ £ 150 - ограничение по труду

2х₁ + 0.5 х₂ £ 240 - ограничение по лавсану

х₁ + 3.5 х₂ £ 350 - ограничение по шерсти

х_{2 ³} 60 - ограничение по костюмам

х₁ ³ 0

Решение.