12 Лабораторная работа № 7 Постановка задачи и оптимизация модели с помощью процедуры поиска решения

Учебная цель: постановка задачи и ее решение в Microsoft Excel 2010,. с использованием надстройки Поиск решения

Справочно-информационный материал

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

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

Для запуска процедуры MS Excel 2010 на вкладке Данные в группе Анализ следует выбрать команду Поиск решения (Solver). Если эта команда отсутствует, то на вкладке Файл выберите команду Параметры, а затем — категорию Надстройки. Затем в поле Управление выберите значение Надстройки Excel и нажмите кнопку Перейти. В появившемся окне в поле Доступные надстройки установите флажок рядом с пунктом Поиск решения и нажмите кнопку ОК.

В окно Поиск решения (Solver) в поле Установить целевую ячейку (Set Target Cell) следует ввести ссылку на ячейку или имя конечной ячейки. Конечная ячейка должна содержать формулу.

Затем надо выполнить одно из следующих действий:

• чтобы максимизировать значение конечной ячейки путем изменения значений влияющих ячеек, установить переключатель (Egual To) в положение максимальному значению (Max);

• чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек, установить переключатель (Egual To) в положение минимальному значению (Min);

• чтобы установить значение в конечной ячейке равным некоторому числу, установить переключатель (Egual To) в положение по значению (Value of) и ввести в соответствующее поле требуемое число.

Далее в поле Изменяя ячейки (By Changing Cells) ввести имена или ссылки на изменяемые ячейки, разделяя их запятыми. Изменяемые ячейки должны быть прямо или косвенно связаны с конечной ячейкой. Допускается задание до 200 изменяемых ячеек. Чтобы автоматически найти все ячейки, влияющие на формулу модели, следует нажать на кнопку Предположить (Guess).

Потом в поле Ограничения (Subject to the Constraints) ввести все ограничения, накладываемые на поиск решения. Для добавления ограничений в разделе Ограничения диалогового окна Поиск решения следует нажать на кнопку Добавить (Add). В поле Ссылка на ячейку (Cell Reference) ввести адрес или имя ячейки, на значение которой накладываются ограничения. Затем выбрать из раскрывающегося списка условный оператор (<=, =, >=, цел (int) или двоич (bin)), который должен располагаться между ссылкой, и ограничение. Если выбрано цел (int), в поле Ограничение появится значение целое (integer). Если выбрано двоич (bin), в поле Ограничение появится двоичное (binary). В поле Ограничение следует ввести либо число, либо ссылку на ячейку или ее имя, либо формулу. Затем выполнить одно из следующих действий:

• чтобы принять ограничение и приступить к вводу нового, нажать на кнопку Добавить (Add).

• чтобы принять ограничение и вернуться в диалоговое окно Поиск решения, нажать на кнопку OK.

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

В окне Поиск решения нажатием кнопки Параметры можно сделать некоторые установки. Так, например, флажок Линейная модель (Assume Linear Model) в диалоговом окне Параметры поиска решения (Solver Options) позволяет задать любое количество ограничений. При решении нелинейных задач на значения изменяемых ячеек можно наложить более 100 ограничений в дополнение к целочисленным ограничениям на переменные. Чтобы узнать о назначении полей ввода этого окна, следует нажать на кнопку Справка (Help).

Для изменения или удаления ограничений в списке Ограничения (Subject to the Constraints) диалогового окна Поиск решения следует выделить ограничение, затем выбрать команду Изменить (Change) и внести изменения, либо нажать на кнопку Удалить (Delete).

В завершение надо нажать на кнопку Выполнить (Solve) и в появившемся окне:

• чтобы сохранить найденное решение на листе, выбрать в диалоговом окне Результаты поиска решения (Solver Results) вариант Сохранить найденное решение (Keep Solver Solution);

• чтобы восстановить исходные данные, выбрать вариант Восстановить исходные значения (Restore Original Values).

Рассмотрим в качестве примера следующую задачу.

Фирма производит две модели A и В сборных книжных полок. Их производство ограничено наличием сырья и временем машинной обработки. Для каждого изделия модели A требуется 3 м² досок, а для изделия модели В – 4 м² . Фирма может получать от своих поставщиков до 1700 м² досок в неделю. Для каждого изделия модели А требуется 12 мин. машинного времени, а для изделия модели В – 30 мин. В неделю можно использовать 160 ч машинного времени. Сколько изделий каждой модели следует выпускать фирме в неделю, если каждое изделие модели А приносит 2 долл. прибыли, а каждое изделие модели В – 4 долл. прибыли?

Решение. Составим математическую модель.

Обозначим:

х – количество изделий модели А, выпускаемых в течение недели,

у – количество изделий модели В.

Прибыль от этих изделий равна 2х+4у долл. Эту прибыль нужно максимизировать. Функция, для которой ищется экстремум (максимум или минимум), носит название целевой функции. Беспредельному увеличению количества изделий препятствуют ограничения. Ограничено количество материала для полок, отсюда неравенство 3х+4у<=1700. Ограничено машинное время на изготовление полок.

На изделие А уходит 0,2 часа, на изделие В – 0,5 часа, а всего не более 160 ч, поэтому 0,2х+0,5у <=160.

Кроме того, количество изделий – неотрицательное число, поэтому х>=0, у>=0.

В формализованном виде эта задача оптимизации записывается так:

	Теперь решим эту задачу в Excel. Введем в ячейки рабочего листа информацию согласно рис.1. В ячейки В2 и В3 введем значение 0.
Будем считать, что ячейка В2- это переменная х, а В3 – у. Введем в ячейки В6, В9 и В10 следующие формулы: 2*В2+4*В3, 3*В2+4*В3 и в 0,2*В2+0,5*В3. В столбец С формулы можно занести как комментарий.

Произведем поиск решения.

	A	B	C	D
1	Переменные
2	Изделие А	0	х
3	Изделие В	0	у
4
5	Целевая функция
6	Прибыль, руб	0	=2*х+4*у
7
8	Ограничения
9	Материал	0	=3*х+4*у	<=1700
10	Время изготовления	0	=0,2*х+0,5*у	<=160

Рис. 1. Макет таблицы для ввода переменных, формул и ограничений

Выделим ячейку, в которой вычисляется целевая функция, и вызовем режим меню Сервис®Поиск решения (Solver). В диалоговом окне (см. рис. 2) в поле ввода Установить целевую ячейку (Set Target Cell) уже содержится адрес ячейки с целевой функцией $В$6. Установим переключатель (Egual To) в значение максимум (Max). Перейдем к полю ввода: Изменяя ячейки (By Changing Cells). В нашем случае достаточно щелкнуть кнопку Предложить (Guess) и в поле ввода появится адрес блока $В$2:$В$3.

Рис.2. Диалоговое окно Поиск решения

Перейдем к вводу ограничений. Щелкнем кнопку Добавить (Add). Появится диалоговое окно Добавление ограничения (Add Constraint). В поле ввода Ссылка на ячейку (Cell Reference) укажем $B$9. Правее расположен раскрывающийся список с условными операторами. Выберем условие <=. В поле ввода Ограничение (Constraint) введем число 1700. Не выходя из этого диалогового окна, щелкнем по кнопке Добавить (Add) и введем ограничение $B$10<=160. Ввод ограничений закончен, поэтому нажмем на кнопку ОК и вновь окажемся в диалоговом окне Поиск решения (Solver). В нем будут отображаться следующие ограничения: $B$10<=160, $B$9<=1700. С помощью кнопок Изменить (Change) и Удалить (Delete) можно изменить или стереть введенные значения.

Нажмем на кнопку Параметры (Options) и окажемся в диалоговом окне Параметры поиска решения (Solver Options). Менять ничего не будем, только установим два флажка: Линейная модель (Assume Linear Model) и Неотрицательные значения (Assume Non-Negative) для переменных х и у. Щелкнем по кнопке ОК и окажемся в исходном окне.

Задача оптимизации полностью готова. Нажмем на кнопку Выполнить (Solve). Появится диалоговое окно Результаты поиска решения (Solver Results) с сообщением Решение найдено (Solver found Solution). Все ограничения и условия оптимальности выполнены. На выбор предлагаются варианты: Сохранить найденное решение (Keep Solver Solution) или Восстановить исходные значения (Restore Original Values). Выберем первое. При этом в таблице произойдут следующие изменения (см. рис.3.). В ячейки, соответствующие х и у, автоматически подставятся оптимальные значения.

	A	B	C	D
1	Переменные
2	Изделие А	300	х
3	Изделие В	200	у
4
5	Целевая функция
6	Прибыль, руб	1400	=2*х+4*у
7
8	Ограничения
9	Материал	1700	=3*х+4*у	<=1700
10	Время изготовления	160	=0,2*х+0,5*у	<=160

Рис. 3.. Таблица с результатами поиска решения

Таким образом, согласно произведенным расчетам изделие А нужно выпускать в количестве 300 штук в неделю, а изделие В – 200 штук. При этом прибыль составит 1400 долларов.

Порядок выполнения работы

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

ПРИЛОЖЕНИЕ

Варианты заданий

Вариант 1.

Предприятие выпускает 3 модели телевизоров, причем каждая модель производится на отдельной технологической линии. Суточный объем производства первой линии – 30 изделий, второй линии – 25 изделий, третьей линии – 48 изделий. При производстве телевизоров используются однотипные элементы. Максимальный суточный запас используемых элементов равен 500 единицам. Составить такой суточный план производства телевизоров, при котором прибыль от их реализации будет максимальной. Прибыль на единицу продукции и расход элементов на один телевизор приведены в таблице:

Модель телевизора	Прибыль на ед. продукции в руб.	Расход элементов на один телевизор
I	120	8
II	150	6
III	180	9