УДК 519.8
© ФГБОУ ВПО НовГУ им. Ярослава Мудрого, 2013 © Голик Ф. В., 2013 |
Введение
Теория линейного программирования (ЛП) широко применяется при решении экономических задач, оптимизации производственных процессов и во многих других прикладных областях деятельности. Методы решения хорошо известны и могут быть реализованы как «ручным» счетом, так и с использованием специализированных компьютерных программ.
Программа MS Excel, установленная практически на каждом персональном компьютере, позволяет решать оптимизационные задачи, в том числе и задачи линейного программирования. Настоящее пособие является инструкцией по решению задач ЛП средствами Excel.
Содержание пособия, за исключением небольшой редакторской правки, полностью повторяет материал, опубликованный на сайте http://edu.nstu.ru/courses/mo_tpr/
Настройка MS Excel
Для решения задач линейного программирования (ЛП) в Excel необходимо иметь надстройку «Поиск решения». Если в меню Сервис нет такого пункта, то установите пакет «Поиск решения». Для этого запустите «Сервис»- «Надстройки». В открывшемся окне выберите надстройку «Поиск решения» (рис. 1). После этого пункт «Поиск решения» появится в меню Сервис.
В Офисе 2007 чтобы «добраться» окна «Надстройки» нужно сделать следующее: кнопка меню «Файл» — «Параметры Excel»- «Надстройки» — «Перейти» и получаем окно надстроек, которое в более ранних версиях можно было получить сразу из меню «Сервис». Надстройка «Поиск решения» появится в меню «Данные».
Рис.1. Окно Надстройки
Подготовка листа с исходными данными
Пример 1.
Пусть необходимо решить задачу ЛП:
На рис.2 дано изображение окончательно оформленного листа с исходными данными, подготовленными для расчета.
Рис.2. Лист с исходными данными
Порядок заполнения листа.
1) Задаем область под переменные:
—для нашего примера под x1 и x2 отведем ячейки B7 и C7 соответственно (рис. 2). В эти ячейки можно занести начальные значения переменных. В соседние ячейки можно ввести наименование переменной (см. ячейка A7).
2) Задаем первое ограничение:
-в ячейки B4 и C4 заносим коэффициенты ограничения a1j, т.е. коэффициенты первого ограничения при соответствующих переменных.
-в ячейку E4 заносим свободный член b1 равный 2.
-в D4 задаем формулу вычисления левой части: =B4*B7+C4*C7
3) Аналогично задаем остальные ограничения
4) Задаем целевую функцию. В ячейку D2 заносим формулу вычисления целевой функции: =4*B7+2*C7
Установка данных для пакета «Поиск решения»
Запускаем пакет «Поиск решения». В открывшемся окне задаем данные для решения задачи (рис. 3):
Рис.3. Данные для запуска Поиска решения
- в поле «Изменяя ячейки» — диапазон ячеек, отведенный под переменные;
- в поле «Установить целевую ячейку» — адрес ячейки, в которой вычисляется ЦФ;
- выбрать тип ЦФ — к максимуму или минимуму;
- ввести ограничения в нижней части окна. Для того, что бы ввести каждое новое ограничение, необходимо нажать кнопку «Добавить». В открывшемся окне (рис. 4) в первом поле задается ячейка, в которой вычисляется левая часть ограничения — $D$4, во втором поле – знак ограничения, в третьем поле – адрес ячейки со свободным членом.
Рис. 4. Ввод ограничений
После того как введены все данные, устанавливаем настройки пакета «Поиск решения», нажав кнопку «Параметры». В открывшемся окне устанавливаем параметры Линейная модель и Неотрицательные значения так, как показано на рис. 5. Это связано с тем, что класс решаемой задачи линейное программирование, а также все переменные неотрицательные.
И, наконец, запускаем решение задачи нажатием кнопки «Выполнить» в окне «Поиск решения» (рис. 3).
Рис. 5. Установка параметров расчета