Линейное программирование - наука о методах исследования и нахождения наибольшего или наименьшего значений линейной (целевой) функции при наличии линейных ограничений. Термин "программирование" понимается в смысле "планирования". Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации.
Развитие компьютерной техники, совершенствование информационных технологий, распространение пакетов прикладных программ позволили сделать доступными и наглядными современные методы решения математических задач широкому кругу пользователей, освободив от проведения трудоемких расчетов.
Опыт преподавания показывает необходимость использования в рамках дисциплины исследования операций табличного процессора MS Excel [1] и систем компьютерной математики, в частности системы MathCAD [2], [3], главными достоинствами которой является то, что она проста в изучении и использовании, позволяет одновременно с расчетами создавать документы в общепринятом виде.
Рассмотрим пример решения задач линейного программирования в Excel.
Задача. Найти наименьшее значение функции L = 3x + 2у при ограничениях.
Для того чтобы решить данную задачу в табличном процессоре Microsoft Excel, необходимо выполнить следующие действия:
1. Ввести условие задачи: а) создать экранную форму для ввода условия задачи; b) ввести исходные данные в экранную форму; с) ввести ограничения в экранную форму.
В ячейку D6, в которой будет отображаться значение функции L = 3х + 2у, необходимо ввести формулу (=СУММПРОИЗВ(В$3:С$3;В6:С6), по которой это значение будет рассчитано.
В ячейки D10, D11, D12 ввести формулы (=СУММПРОИЗВ(В$3:С$3;В10:С10), =СУММПРОИЗВ(В$3:С$3;В11:С11), =СУММПРОИЗВ(В$3:С$3;В12:С12)), соответствующие левым частям ограничений.
2. Решить задачу. Дальнейшие действия производятся в окне "Поиск решения", которое вызывается из меню "Сервис", а в Microsoft Excel-2007 вызывается из меню "Данные".
В поле "Изменяя ячейки" вписать адреса $В$3:$С$3. Необходимые адреса можно вносить в поле "Изменяя ячейки" автоматическим путем выделения мышью соответствующих ячеек переменных. С помощью кнопки "Добавить" задать ограничения для допустимых значений переменных. С помощью кнопки "Параметры" заполнить некоторые поля окна "Параметры поиска решения".
Путем нажатия кнопки "Выполнить" из окна "Поиск решения" запустить задачу на решение, после чего на экране появляется окно "Результаты поиска решения".
Для получения ответа (значений переменных, функции и левых частей ограничений) нажать кнопку "ОК". После этого в экранной форме появляется оптимальное решение задачи.
Решение задач линейного программирования в MathCAD
Система MathCAD позволяет упростить решения задач линейного программирования, используя при этом основные функции Maximize и Minimize.
Рассмотрим порядок выполнения решения задачи линейного программирования в системе MathCAD с системой ограничений двух или трех переменных.
1. Установить режим автоматических вычислений.
2. Определить целевую функцию как функцию трех переменных.
3. Задать начальные приближения для всех переменных.
4. Ввести ключевое слово Given.
5. Ввести выражения из системы ограничений и условия неотрицательности переменных. Для ввода знаков >, <, = использовать панель инструментов Булевый.
6. Задать вектор-столбец, элементы которого - переменные х1, х2, х3. Ввести знак присваивания и функцию Maximize(f, x1,x2,x3) - для решения задачи линейного программирования на максимум, или Minimize(f, x1,x2,x3) - для решения задачи линейного программирования на минимум.
7. Еще раз ввести вектор-столбец с переменными x1, x2, x3, нажать знак равенства и будет получено оптимальное решение.
8. Вычислить значение целевой функции в точке экстремума.
9. Оформить документ и сохранить его в файле.
Рассмотрим пример: Найти наибольшее значение функции L = x1 + 3х2 + 3x3 при ограничениях.
Решение: в системе MathCAD решение выглядит так:
Рассмотрим порядок выполнения решения задачи линейного программирования в системе MathCAD с системой ограничений больше трех переменных.
1. Установить режим автоматических вычислений.
2. Определить целевую функцию как функцию четырех переменных.
3. Ввести матрицу коэффициентов системы неравенств с помощью панели инструментов Матрицы.
4. Ввести вектор коэффициентов правой части системы неравенств также с помощью панели инструментов Матрицы.
5. Ввести начальное значение хотя бы одного искомого параметра.
6. Ввести ключевое слово Given.
7. Ввести систему неравенств в матричном виде: М·х,у.
8. Ввести граничные условия: х ? 0.
9. Ввести имя искомого вектора оптимальных параметров, например xopt. Ввести знак присваивания и функцию Maximize(f, x) - для решения задачи линейного программирования на максимум, или Minimize(f, x) - для решения задачи линейного программирования на минимум.
10. Ввести искомые оптимальные значения xopt, нажать знак равенства и будет получено оптимальное решение.
11. Вычислить значение целевой функции в точке экстремума f(xopt).
12. Оформить документ и сохранить его в файле.
Рассмотрим пример. Найти наибольшее значение функции L = 40x1 + 50x2 + 30x3 + 20x4 при ограничениях.
Постепенно у обучаемых сформируются устойчивые навыки использования встроенных функций, визуализации полученных результатов в ТП MS Excel, системе MathCAD, которые будут востребованы в профессиональной деятельности.
Список литературы
- Капустин Е.И. Решение некоторых классов математических задач в программе Excel. URL://exponenta.ru/educat/systemat/kapustin/003.asp/.
- Кудрявцев Е.М. MathCAD-2000. М.: ДМК Пресс, 2001. С. 576.
- Кузнецова Л.Г. Системы компьютерной математики / Учебное пособие. Омск, 2003. С. 108.