Решение задач линейного программирования в табличном процессоре MS Excel

Для решения задач ЛП в Excel имеется надстройка Поиск решения, которая вызывается щелчком по вкладке ленты «Данные».

Если на вкладке «Данные» отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите из контекстного меню команду Настройка панели быстрого доступа => Надстройки => Пакет анализа => кнопка Перейти и активизируйте надстройку Поиск решения. Если же этой надстройки нет в диалоговом окне «Надстройки», то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения.

После выбора команды Поиск решения появится диалоговое окно «Поиск решения».

Алгоритм решения задач ЛП в MS Excel 2007

Шаг 1. Ввести условие задачи:

1) создать экранную форму для ввода условия задачи и ввести исходные данные (коэффициенты целевой функции, коэффициенты при переменных в ограничениях, правые части ограничений);

2) ввести зависимости из математической модели в экранную форму (формулу для расчета целевой функции, формулы для расчета значений левых частей ограничений);

3) задать целевую функцию (в окне «Поиск решения»): целевую ячейку, направление оптимизации целевой функции;

4) ввести ограничения (в окне «Поиск решения»): ячейки со значениями переменных, соотношения между правыми и левыми частями ограничений.

Шаг 2. Решить задачу:

1) установить параметры решения задачи (в окне «Поиск решения»);

2) запустить задачу на решение (в окне «Поиск решения»);

3) выбрать формат вывода решения (в окне «Результаты поиска решения»).

Рассмотрим использование данного пакета для решения конкретного примера.

Пример 7. Предприятие имеет в своем распоряжении определенное количество ресурсов: труд, сырье и оборудование. Ресурсы трех видов - рабочая сила, сырье и оборудование, имеются в количестве соответственно 80 чел.-дн., 480 кг и 130 станков. Предприятие может выпускать изделия четырех видов: электропечь, электрокамин, колонка и электроутюг. Доход от единицы каждого вида изделия соответственно составляет 3, 4, 3 и 1 тыс. руб. Количество единиц каждого ресурса, необходимое для производства одного изделия каждого вида, представлено в таблице 2.13.

Таблица 2.13

Ресурс	Расход ресурса на производство 1 ед. продукции	Наличие ресурса
электропечь	электрокамин	колонка	утюг
Труд, чел.-дн.
Сырье, кг
Оборудование, станки

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

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

х₁ - количество электропечей, шт.;

х₂ - количество электрокаминов, шт.;

х₃ - количество колонок, шт.;

х₄ - количество утюгов, шт.

Рассмотрим алгоритм решения задачи.

Шаг 1. Ввод исходных данных:

1) создание экранной формы и ввод в нее условия задачи.

Экранная форма для ввода условий задачи вместе с введенными в нее исходными данными представлена на рис. 2.1.

2) ввод зависимостей из математической модели в экранную форму:

а) зависимость для целевой функции. В ячейку F6, в которой будет отображаться значение целевой функции, необходимо ввести формулу, по которой это значение будет рассчитано:

Рисунок 2.1 – Экранная форма задачи

Используя обозначения соответствующих ячеек в Excel, эту формулу для расчета целевой функции можно записать как сумму произведений каждой из ячеек, отведенных для значений переменных задачи (В3, С3, D3, Е3), на соответствующую ячейку, отведенную для коэффициентов целевой функции (ЦФ) (В6, С6, D6, Е6), т.е. необходимо в ячейку F6 вставить функцию СУММПРОИЗВ. В диалоговом окне Аргументы функции в строку Массив 1 ввести B3:E3, в строку Массив 2 ввести B6:E6. Массив 1 будет использоваться при вводе зависимостей для ограничений, поэтому на этот массив надо сделать абсолютную ссылку (рис. 2.2). После этого в целевой ячейке появится 0 (нулевое значение).

Рисунок 2.2 – Окно «Аргументы функции»!!!!!!!!!!!!!!!!!!!!!!!

б) зависимости для левых частей ограничений. Левые части ограничений задачи представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (В10, С10, D10, E10 – ограничение 1; В11, С11, D11, E11 – ограничение 2; В12, С12, D12, E12 – ограничение 3). Формулы, соответствующие левым частям ограничений, представлены в таблице 2.14.

Таблица 2.14

Левая часть ограничения	Формула Excel
или В10×В3+С10×С3+D10×D3+Е10×Е3	=СУММПРОИЗВ(B$3:E$3;B10:E10)
или В11×В3+С11×С3+D11×D3+Е11×Е3	=СУММПРОИЗВ(B$3:E$3;B11:E11)
или В12×В3+С12×С3+D12×D3+Е12×Е3	=СУММПРОИЗВ(B$3:E$3;B12:E12)

На экране в полях F10, F11 и F12 появится 0 (рис. 2.3).

Рисунок 2.3 – Экранная форма после ввода всех необходимых формул

в) проверка правильности введения формул. Для проверки правильности введенных формул производите поочередно двойное нажатие левой клавиши мыши при указании на ячейки с формулами. При этом на экране рамкой будут выделяться ячейки, используемые в формуле (рис. 2.4);

Рисунок 2.4 – Проверка правильности введения формулы в целевую ячейку

3) задание ЦФ. Дальнейшие действия производятся в окне «Поиск решения» (рис. 2.5):

а) поставьте курсор в поле «Установить целевую ячейку»;

б) введите адрес целевой ячейки $F$6;

в) введите направление оптимизации ЦФ, щелкнув один раз левой клавишей мыши по селекторной кнопке «максимальному значению»;

Рисунок 2.5. - Окно «Поиск решения»

4) ввод ограничений:

а) задание ячеек переменных. В окно «Поиск решения» (рис. 2.5) в поле «Изменяя ячейки» введите адреса $В$3:$Е$3.

В поле «Изменяя ячейки» указываются ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке.

б) задание ограничений. Нажмите кнопку Добавить в окне «Поиск решения». Появляется диалоговое окно «Добавление ограничения» (рис. 2.6). В поле «Ссылка на ячейку» введите адрес ячейки левой части конкретного ограничения, например $F$10. В соответствии с условием задачи выберите необходимый знак, например «<=». В поле «Ограничение» введите адрес ячейки правой части рассматриваемого ограничения, например, $Н$10.

Рисунок 2.6 – Окно «Добавление ограничения»

Аналогично введите остальные ограничения: $F$11<=$H$11, $F$12<=$H$12. После введения последнего ограничения нажать на кнопку ОК. На экране появится диалоговое окно «Поиск решения» с введенными условиями (рис. 2.7).

Рисунок 2.7 - Окно «Поиск решения» после ввода всех необходимых данных

Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений, то это делают, щелкнув по кнопкам Изменить или Удалить.

Шаг 2. Решение задачи:

1) установка параметров решения задачи. Задача запускается на решение в окне «Поиск решения», но предварительно, для установления конкретных параметров решения задач оптимизации определенного класса, необходимо нажать на кнопку Параметры и заполнить некоторые поля окна «Параметры поиска решения» (рис. 2.8).

Рисунок 2.8 – Параметры поиска решения, подходящие для большинства задач ЛП

Параметр «Максимальное время» служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32767 с (более 9 ч).

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

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

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

Параметр «Сходимость» применяется только при решении нелинейных задач.

Установка флажка «Линейная модель» обеспечивает ускорение поиска решения линейной задачи за счет применения симплекс-метода;

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

2) запуск задачи на решение. Запуск задачи на решение производится из окна «Поиск решения» путем нажатия на кнопку Выполнить. После запуска на решение задачи ЛП на экране появляется окно «Результаты поиска решения» с сообщением о найденном решении (рис. 2.9).

Рисунок 2.9 – Сообщение об успешном решении задачи

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

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

В окне «Результаты поиска решения» представлены названия трех типов отчетов: Результаты, Устойчивость, Пределы. Они необходимы при анализе полученного решения на чувствительность. Для получения ответа (значений переменных, целевой функции и левых частей ограничений) прямо в экранной форме нажмите на кнопку ОК. После этого в экранной форме появляется оптимальное решение задачи (рис. 2.10).

Рисунок 2.10 – Экранная форма после получения решения

Анализ оптимального решения с использованием MS Excel

Excel позволяет представить результаты поиска решения в форме отчета. Существует три типа таких отчетов:

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

2. Устойчивость. Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений.

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

Для того чтобы получить отчеты для анализа оптимального решения, необходимо в окошке «Результаты поиска решения» добавить типы отчетов: Результаты, Устойчивость, Пределы (рис. 2.9).

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

Рисунок 2.11 – Отчет по результатам

Для ограничений в столбце «Формула» приведены зависимости, которые были введены в диалоговое окно «Поиск решения»; в столбце «Разница» показано количество неиспользованного ресурса. Если ресурс используется полностью, то в столбце «Статус» указывается «связанное» (дефицитный ресурс); При неполном использовании ресурса в этом столбце указывается «не связанное» (недефицитный ресурс).

Отчет по устойчивости выводится в следующей форме (рис. 2.12).

Рисунок 2.12 – Отчет по устойчивости

В первой таблице этого отчета выводится следующая информация:

- в первых двух столбцах перечислены ячейки, в которых вычисляются значения переменных, и их имена;

- в столбце «Результ. значение» - найденное оптимальное решение;

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

- в столбце «Целевой коэффициент» - коэффициенты целевой функции;

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

Во второй таблице (рис. 2.12) выводится следующая информация:

- в первых двух столбцах перечислены ячейки, в которых вычисляются левые части ограничений, и их имена;

- в столбце «Результ. значение» - значения левых частей ограничений (для ограничений на ресурсы - их использованное количество, для граничных условий - значение переменных в оптимальном плане);

- в столбце «Теневая цена» - двойственные оценки, показывающие, на какую величину изменится целевая функция при увеличении на 1 ед. правой части ограничения, тогда как остальные данные неизменны (в частности, при добавлении единицы соответствующего ресурса). Теневаяцена - это максимальная цена, которую стоит платить за дополнительное количество дефицитного ресурса, чтобы его приобретение было выгодным;

- в столбце «Ограничение. Правая часть» - правые части ограничений;

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

В последней симплексной таблице оценочные коэффициенты D_j дополнительных переменных – это «Теневая цена»; оценки D_j основных переменных – это «Нормир. стоимость».

Отчет по пределам изменений представлен на рис. 2.13.

Рис. 2.13 – Отчет по пределам

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

Дата добавления: 2014-10-22