Использование Microsoft Excel для решения задач линейного программирования

Задача запускается на решение в окне "Поиск решения". Но предварительно для установления конкретных параметров решения задач оптимизации определенного класса необходимо нажать кнопку "Параметры" и заполнить некоторые поля окна "Параметры поиска решения" (рис. 7).

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

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

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

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

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

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

Подтвердите установленные параметры нажатием кнопки "OK".

Запуск задачи на решение

Запуск задачи на решение производится из окна "Поиск решения" путем нажатия кнопки "Выполнить".

После запуска на решение задачи ЛП на экране появляется окно "Результаты поиска решения" с сообщением об успешном решении задачи.

Рис. 13 Сообщение об успешном решении задачи

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

Если при заполнении полей окна "Поиск решения" были допущены ошибки, не позволяющие Excel применить симплекс-метод для решения задачи или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено. Иногда слишком малое значение параметра "Относительная погрешность" не позволяет найти оптимальное решение. Для исправления этой ситуации увеличивайте погрешность поразрядно, например от 0,000001 до 0,00001 и т.д.

В окне "Результаты поиска решения" представлены названия трех типов отчетов: "Результаты", "Устойчивость", "Пределы". Они необходимы при анализе полученного решения на чувствительность. Для получения же ответа (значений переменных, ЦФ и левых частей ограничений) прямо в экранной форме просто нажмите кнопку "OK". После этого в экранной форме появляется оптимальное решение задачи (рис. 9).

Рис. 14 Экранная форма задачи после получения решения

2.3 Решение задачи распределения ресурсов предприятия при помощи электронной таблицы

Рассмотрим решение задачи распределения ресурсов предприятия при помощи электронной таблицы.

Данная задача в классической постановке имеет следующий вид [1]. Известно, что номенклатура выпускаемой некоторым предприятием продукции состоит из n наименований. Обозначим через a_ij количество ресурса i-гo вида (i = 1, 2,..., m), необходимое для производства единицы продукции j-го вида (j = 1, 2,..., n), через b_i - объемы имеющихся ресурсов (i = 1, 2,..., m). Пусть c_j - прибыль, получаемая предприятием при изготовлении и реализации единицы j-го вида продукции, A_j и В_j - заданные нижняя и верхняя границы по объему выпуска продукции j-го вида.

Требуется составить такой план выпуска продукции х = (x₁, х₂,..., х_n), где x_j -- объем выпускаемой продукции j-го вида, который был бы технологически осуществим по имеющимся ресурсам всех видов, удовлетворял бы заданным ограничениям на выпуск каждого вида продукции и в то же время приносил бы наибольшую общую прибыль предприятию.

Математическая модель рассматриваемой задачи имеет вид:

Здесь запись (2.1) означает, что надо найти наибольшую общую прибыль предприятия; формула (2.2) задает технологические ограничения на производство; формула (2.3) -- ограничения на объемы отдельных видов выпускаемой продукции.

Пример.

Некоторое предприятие производит продукцию 5 видов, используя комплектующие детали 7 наименований А, В, С, D, Е, F, G. Запасы предприятия ограничены некоторым количеством комплектующих деталей. Известно, сколько требуется комплектующих деталей для производства единицы продукции каждого вида и прибыль от производства единицы продукции каждого вида. Определить, сколько требуется произвести продукции каждого вида, чтобы обеспечить предприятию наибольшую прибыль.

Данные по производству приведены в таблице.

Математическая модель рассматриваемой задачи

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

Возможный вид исходных данных представлен на рис.1. блок ячеек B1:B5 содержит начальный план, в данном случае произвольно взятый набор (1, 0, 0, 0, 0); ячейка В6 - оптимизируемую (целевую) функцию; блоки А10:А16 и С10:С16 служат для выражения ограничений ,накладываемых на значение аргументов целевой функции. Ячейки А1:А6, А9 и В10:В16 исходной области используются для хранения текста иллюстративно поясняющего характера.

Рис. 15 Фрагмент рабочего листа Excel с исходными данными для расчетов

Для задания параметров поиска решения необходимо вызвать диалоговое окно Поиск решения. В этом окне следует задать целевую ячейку B6, содержащую оптимизируемую функцию, вид оптимизации - максимальное значение .диапазон ячеек, содержащих варьируемые параметры B1:B5 и ограничения на целевую функцию.

Рис. 16 Установки окна Поиск решения для задачи распределения ресурсов

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

Рис. 17 Окно Добавление ограничения

В данном случае для решения поставленной задачи следует указать следующие ограничения:

$A$10<=$C$10

$A$11<=$C$11

$A$12<=$C$12

$A$13<=$C$13

$A$14<=$C$14

$A$15<=$C$15

$A$16<=$C$16

$B$1:$B$5=целое

$B$1:$B$5>=0

Найденный в результате выполнения поиска решения оптимальный план (2, 1, 6, 3, 3) представлен в диапазоне ячеек B1:B5 рис.4. При этом целевая функция приняла решение 40; были выполнены все заданные условиями задачи ограничения.

Рис. 18 Фрагмент листа Excel с полученными в результате поиска решения данными

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

ЗАКЛЮЧЕНИЕ

Использование возможностей Microsoft Excel упрощает выполнение различных вычислений. Он демонстрирует решение задач линейного программирования.

Можно сделать вывод, что использование дополнения Excel Solver позволяет найти решения для задач линейного программирования. Решение не занимает много времени, и результаты отображаются в ясном, легко читаемом формате.

Удобство использования MS Excel для решения задач линейного программирования выглядит следующим образом:

* Создание временной таблицы, ее можно использовать для таких задач, как изменение только исходного типа данных;

* все необходимое для решения проблемы формулы, уже представленной в MS Excel;

* Решение проблемы занимает в несколько раз меньше времени, чем ее собственное решение;

* Точность решения намного выше, чем вручную, и ошибки минимизируются.

Единственным недостатком решения задач линейного программирования с использованием MS Excel может быть: отсутствие полного решения, т. е. Поиск решений немедленно дает готовый ответ и не отображает все вычисления, которые в принципе не являются целью решения проблема.

Размещено на Allbest.ru