Решение задач линейного программирования

Цель: изучение методики составления экономико-математических моделей задач линейного программирования (ЛП) и технологии решения задач ЛП с помощью надстройки Поиск решения в среде MS Excel.

5.1 Решение задач ЛП с помощью надстройки Поиск решения в среде MS Excel

Поиск решения – это надстройка Ехсel, которая позволяет решать оптимизационные задачи. Для загрузки этой надстройки при работе в MS Excel 2003 необходимо выбрать команду Сервис → Надстройки и установить флажок для надстройки Поиск решения. При работе в MS Excel 2007 следует выбрать команду Office – Параметры Excel – Надстройки – Управление: надстройки Ехсel – Перейти и установить флажок для надстройки Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то необходимо с помощью программы-установки Ехсel (или Office) установить надстройку Поиск решения.

Далее приведен пример решения в MS Excel задачи ЛП [1, 2].

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

Таблица 5.1 – Исходные данные

Тип ресурсов, т	Конфеты «Зубр»	Конфеты «Мишка»	Конфеты «Зайка»	Конфеты «Белочка»	Общий объем ресурсов, т
Какао		1,5
Орехи		0,5	0,5
Сахар
Прибыль от реализации одной тонны конфет, тыс. д. е.

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

Далее необходимо ввести исходные данные задачи на лист Excel так, как показано на рисунке 5.1. В экранной форме на рисунке 5.1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка в Excel.

Рисунок 5.1 – Экранная форма для ввода условий задачи

Дальнейшие действия производятся в окне «Поиск решения», которое вызывается из меню «Сервис» (рисунок 5.2).

Для ввода адреса ячейки значения целевой функции необходимо поставить курсор в ячейку окна «Поиск решения», а затем указать нажатием левой клавиши мыши на листе Excel адрес целевой ячейки $Е$7.

В поле «Изменяя ячейки» указываются адреса $B$3:$D$3 для хранения значений искомых переменных задачи .

Рисунок 5.2 – Окно «Поиск решения» задачи

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

рисунке 5.2) и в окне «Параметры поиска решения» установить флажки «Линейная модель» и «Неотрицательные значения». Установка флажка «Линейная модель» указывает на то, что решается задача ЛП. Установка флажка «Неотрицательные значения» обеспечивает выполнение условий неотрицательности искомых переменных .

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

Рис.5.3 – Окно "Параметры поиска решения"

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

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

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

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

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

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

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

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

Полученное решение задачи представлено на рисунке 5.4.

Рисунок 5.4 – Полученное решение задачи

Оптимальное решение (оптимальный план производства конфетной фабрики): 6 т конфет «Зубр», 17,33 т конфет «Мишка». При этом достигается максимальная прибыль 358 тыс. д. е.

Иногда при решении задач могут появляться сообщения, представленные на рис. 5.5 и 5.6. Такие сообщения свидетельствуют не о характере оптимального решения задачи, а о том, что при вводе условий задачи в Excel могли быть допущены ошибки, не позволяющие Excel найти оптимальное решение, которое в действительности существует. Поэтому, прежде чем делать вывод о принципиальной невозможности нахождения оптимального решения задачи, ответьте на вопросы из таблицы 5.1.

Рис.5.5 – Сообщение при несовместной системе ограничений задачи

Рис.5.6 – Сообщение при неограниченности целевой функции в требуемом направлении

Таблица 5.1 – Список вопросов, позволяющих выявить ошибки ввода условия задачи в Excel