Этап. Создание математической модели задачи
Тема 2. РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ МЕТОДОМ ПОИСКА РЕШЕНИЯ
Цель работы:научиться использовать табличный процессор Excel для решения задач оптимизации.
Содержание работы:
1. Создание математической модели задачи ЛП.
2. Создание формы для ввода условий задачи, ввод в неё исходных данных и зависимостей из математической модели.
3. Ввод целевой ячейки, изменяемых ячеек и ограничений в окно Поиск решения из меню Сервис.
4. Задание параметров поиска и решение задачи.
Порядок выполнения работы:
1. Изучить методические указания.
2. Выполнить задания.
3. Оформить отчет и ответить на контрольные вопросы.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
К классу задач линейного программирования (ЛП) относятся такие задачи однокритериальной оптимизации, в которых переменные являются непрерывными и неотрицательными, целевая функция является линейной функцией своих аргументов, а ограничения могут быть представлены в форме линейных неравенств и равенств.
Задача линейного программирования в общем случае формулируется следующим образом:
Определить максимум (минимум) целевой функции F max(min) при заданной системе ограничений (2) и граничных условий (3):
Fmax(min) =A1*X1+A2*X2+...+An*Xn (1)
{B11*X1+B12*X2+...+B1n*Xn<=C1
{B21*X1+B22*X2+...+B2n*Xn<=C2 (2)
{Bn1*X1+Bn2*X2+...+Bnn*Xn<=Cn
Xi>=0, i=1, ..., n (3)
Надстройка Поиск решения является инструментом оптимизации. С помощью этой надстройки можно найти оптимальное или заданное значение некоторой ячейки путем подбора значений нескольких ячеек, удовлетворив нескольким граничным условиям.
Целевая ячейка – это ячейка, для которой нужно найти максимальное, минимальное или заданное значения.
Изменяемые ячейки – это ячейки, от которых зависит значение целевой ячейки. Целевая ячейка должна содержать формулу, прямо или косвенно зависящую от изменяемых ячеек. Поиск решения подбирает значения изменяемых ячеек до тех пор, пока не будет найдено решение.
Ограничение – это условие, накладываемое на некоторую ячейку. Ограничения могут быть наложены на любые ячейки таблицы, включая целевую ячейку и изменяемые ячейки.
Чтобы запустить процедуру поиска решения, надо:
1. В меню Данные выбрать команду Поиск решения. Откроется диалоговое окно Поиск решения (рис. 6.1).
Рисунок 6.1 – Диалоговое окно Поиск решения
2. В поле Установить целевую ячейку ввести ссылку на ячейку, в которой нужно получить максимальное, минимальное или заданное значения.
3. В поле Изменяя ячейки ввести ссылки на изменяемые ячейки. (Если щелкнуть по кнопке Предположить, то Поиск решения самостоятельно определит изменяемые ячейки).
4. Для задания ограничений щелкнуть по кнопке Добавить.
5. В открывшемся диалоговом окне следует: (Рис. 6.2)
§ в поле Ссылка на ячейку ввести ссылку на ячейку, содержащую формулу, которая определяет ограничение; формула должна прямо или косвенно зависеть от одной или нескольких изменяемых ячеек;
§ во втором поле выбрать оператор ограничения (>,<,= и т.д.);
§ в поле Ограничение ввести значение ограничения.
6. Для задания следующего ограничения щелкнуть по кнопке Добавить и повторить операции пункта 5.
7. Когда все ограничения будут заданы, щелкнуть по кнопке ОК, чтобы вернуться в диалоговое окно Поиск решения.
Рисунок 6.2 – Диалоговое окно Добавление ограничения
8. Изменять и удалять ограничения можно с помощью кнопок Изменить и Удалить.
9. С помощью кнопки Параметры можно задать: максимальное время решения; предельное число итераций; относительную погрешность; допустимое отклонение; сходимость; метод поиска.
Если известно, что решаемая задача линейная (т.е. зависимости между переменными линейны), то следует включить режим Линейная модель: процесс решения значительно ускорится.
Для возврата в диалоговое окно Поиск решения щелкнуть по кнопке ОК.
Для инициализации процедуры поиска решения щелкнуть по кнопке Выполнить. Полученные результаты будут выведены на рабочий лист.
После завершения процедуры решения в диалоговом окне Результаты поиска решения можно выполнить один из следующих вариантов:
· сохранить найденное решение или восстановить исходные значения на рабочем листе;
· сохранить параметры поиска решения в виде модели;
· сохранить решение в виде сценария;
· просмотреть любой из встроенных отчетов.
Текущие установочные параметры для поиска решения можно сохранить в виде модели. Для этого надо в диалоговом окне Параметры поиска решения щелкнуть по кнопке Сохранить модель и указать на рабочем листе область для сохранения модели (можно указать только верхнюю ячейку области).
При сохранении модели запоминаются целевая ячейка, изменяемые ячейки, ограничения и параметры поиска решения.
Чтобы впоследствии загрузить модель, надо щелкнуть по кнопке Загрузить модель в диалоговом окне Параметры поиска решения. (Диалоговое окно Параметры поиска решения открывается при щелчке по кнопке Параметры в диалоговом окне команды Данные > Поиск решения).
Найденные решения (значения изменяемыхячеек) можно сохранить в качестве сценария. Для этого нужно:
1. В диалоговом окне Результаты поиска решения выбрать Сохранить сценарий.
В поле Название сценария ввести имя сценария. Просмотреть сценарии можно с помощью команды Данные > Работа с данными >Анализ что-если> Диспетчер сценариев > Сценарии.
С помощью программы Поиск решения можно создать три типа отчетов по результатам, полученным при успешном завершении процедуры решения.
Каждый отчет создается на отдельном листе текущей рабочей книги.
Для создания отчета надо в диалоговом окне Результаты поиска решения выбрать нужный тип отчета в поле Тип отчета. Можно выбрать сразу несколько типов (при выделении нескольких строк используется клавиша <Ctrl>).
Типы отчетов:
Результаты – отчет содержит целевую ячейку, список изменяемых ячеек, их исходные и конечные значения, ограничения и сведения о них.
Устойчивость – отчет содержит сведения о степени зависимости модели от изменений величин, входящих в формулы, применяемые в задаче (формулы модели и формулы ограничений).
Пределы – выводится целевая ячейка и ее значение, а также список изменяемых ячеек, их значений, нижних и верхних пределов и целевых результатов.
Рассмотрим применение процессора Excel для решения ЗЛП на примерах.
Задача 1. Планирование производства
Модель линейного программирования дает возможность определить наиболее выгодную производственную программу выпуска нескольких видов продукции при заданных ограничениях на ресурсы.
МП выпускает товары Х1,Х2,Х3,Х4, получая от реализации каждого прибыль в 60,70,120,130 руб. соответственно. Затраты на производство приведены в таблице.
| Затраты | X1 | X2 | X3 | X4 | Всего |
| Трудовые | |||||
| Сырьевые | |||||
| Финансы |
Определить:
1) Максимум прибыли в зависимости от оптимального распределения затрат.
2) Минимум ресурсов, необходимых для получения максимальной прибыли.
Решение задачи средствами Excel состоит из 4 этапов:
1. Создание математической модели задачи ЛП.
2. Создание формы для ввода условий задачи, ввод в неё исходных данных и зависимостей из математической модели.
3. Ввод данных из формы в окно Excel Поиск решения из меню Данные.
4. Задание параметров поиска и решение задачи.
этап. Создание математической модели задачи
Составим математическую модель процесса по описанию задачи:
60Х1+70Х2+120Х3+130Х4 = Fmax – целевая функция прибыли.
{Х1+Х2+Х3+Х4 <= 16
{6Х1+5Х2+4Х3+Х4 <= 110 – ограничения модели
{4Х1+6Х2+10Х3+13Х4 <= 100
Хj >=0 – граничные условия модели, так как количество производимых товаров не может быть отрицательной величиной.
Для решения данной задачи c помощью программы MS Excel создадим новую книгу с именем Линейное программирование и изменим имя ее первого рабочего листа на Задача о производстве.
Этап. Создание формы
а) Составление формы в виде:
| A | B | C | D | E | F | G | H | |
| Переменная | X1 | X2 | X3 | X4 | Формула | Знак | Св.член | |
| Значение | ||||||||
| Коэф. ЦФ | =СУММПРОИЗВ (В$2:Е$2;В3:Е3) | Max | ||||||
| Трудовые | =СУММПРОИЗВ (В$2:Е$2;В4:Е4) | <= | ||||||
| Сырьевые | =СУММПРОИЗВ (В$2:Е$2;В5:Е5) | <= | ||||||
| Финансы | =СУММПРОИЗВ (В$2:Е$2;В6:Е6) | <= |
б) Запись в ячейки В3:Е3 коэффициентов целевой функции F (1), в В4:Е6 коэффициентов из системы ограничений (2) и в ячейки Н4:Н6 – свободных членов из системы (2).
в) Ввод формул с помощью fx – Мастера функций.
Для ввода формулы в целевую ячейку (целевой функции): щелкнуть левой клавишей мыши по ячейке F3, затем по значку Мастера функций fx на панели инструментов, в появившемся окне "Мастер функций, Шаг 1" выбрать категорию "Математические", далее выбрать функцию СУММПРОИЗВ, нажать клавишу ОК, в окне "Мастер функций Шаг 2" в поле Массив 1 ввести с клавиатуры В2:Е2 (ячейки, в которых будут варьироваться Х1..Х4), в поле Массив 2 ввести В3:Е3 (коэффициенты целевой функции ЦФ).
Примечание. Можно вводить В2:Е2 не с клавиатуры, а поставить курсор в окно Массив 1, а затем протащить курсор при нажатой левой клавише мыши по ячейкам В2:Е2, имена ячеек сами запишутся в окно. Аналогично поступить с полем Массив 2.
Нажать клавишу ОК, в ячейку F3 запишется формула 60Х1+70Х2+120Х3+ 130Х4 в виде СУММПРОИЗВ(В2:Е2;В3:Е3).
Чтобы не вводить формулы в другие ячейки, необходимо изменить тип адресации для ячеек В2:Е2 с относительной на абсолютную $B$2:$E$2, установив курсор перед нужным адресом B2и нажав функциональную клавишу F4, затем повторить эти действия для адреса E2. Формула примет следующий вид:
СУММПРОИЗВ($В$2:$Е$2;В3:Е3)
После внесенных изменений необходимо скопировать формулу в ячейки F4:F6 c помощью маркера заполнения. Для этого необходимо выделить ячейку F3, содержащую нужную формулу, установить указатель мыши на черный квадратик в правом нижнем углу ячейки (он примет форму черного крестика) и протащить с помощью левой кнопки мыши на весь требуемый диапазон.
В результате копирования мы увидим следующие формулы:
– в ячейке F4 – СУММПРОИЗВ($В$2:$Е$2;В4:Е4),
– в ячейке F5 – СУММПРОИЗВ($В$2:$Е$2;В5:Е5),
– в ячейке F6 – СУММПРОИЗВ($В$2:$Е$2;В6:Е6).