Система компьютерной математики MAPLE. Поиск оптимальных решений

[pic 1]

ЛАБОРАТОРНАЯ РАБОТА № 9

СИСТЕМА КОМПЬЮТЕРНОЙ МАТЕМАТИКИ MAPLE.

ПОИСК ОПТИМАЛЬНЫХ РЕШЕНИЙ

[pic 2]

Цель работы: приобрести практические навыки решения задач линейной и нелинейной оптимизации с помощью библиотек simplex и  Optimization СКМ MAPLE.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Библиотека Simplex 

Если требуется найти переменные, при которых линейная функция многих переменных имеет максимум (или минимум) при выполнении определенных ограничений, заданных в виде линейных равенств или неравенств, то следует использовать симплекс-метод. Этот метод реализован в библиотеке simplex, содержащей алгоритм линейной оптимизации. Библиотека simplex, как и любая другая, подключается командой with. Подробнее с функциями этой библиотеки можно ознакомиться в справочной системе СКМ Maple.

Поиск максимума (минимума) функции  осуществляется командами maximize  (minimize), которые используются в следующем формате:

maximize(expr, opt1, opt2, ..., optn)

minimize(expr, opt1, opt2, ..., optn)

здесь

expr                  - алгебраическое выражение,

opt1, opt2, ..., optn – параметры оптимизации.

В качестве параметров оптимизации можно указывать в фигурных скобках ограничительную систему неравенств. Поскольку пакет simplex предназначен для решения задач линейной оптимизации, после его загрузки команды maximize и minimize меняют свое действие. Теперь эти команды выдают координаты точек, при которых заданная линейная функция имеет максимум или минимум. При этом допускается дополнительная опция для поиска только неотрицательных решений NONNEGATIVE.

Пример 9.1

При каких значениях переменных функция f(x,y,z)=-x+2y+3z имеет максимум, если требуется выполнение условий x+2y-3z<=4, 5x-6y+7z<=8, 9x+10z<=11, а все переменные неотрицательные?

Сеанс работы в Maple:

>restart: with(simplex);

>f:=-x+2*y+3*z; # Целевая функция

[pic 3]

>ogran:={x+2*y-3*z<=4, 5*x-6*y+7*z<=8, 9*x+10*z<=11}: # Ограничения

>maximize(f, ogran, NONNEGATIVE); # Поиск решения в данном случае максимизация функции 

[pic 4]

СКМ MAPLE выдает ответ в самой точной форме – символьной, более точной, чем любой из численных методов. Однако, если желателен ответ в виде числа с плавающей точкой,  то его можно найти в конце символьных вычислений. Для этой цели можно использовать функцию evalf(expr, n).

> rez:=evalf(rez,3);

[pic 5]

Максимум функции при заданной системе ограничений можно определить с помощью функции subs(x=a, expr), которая подставит вычисленные значения переменных x, y и z (rez) в функцию f.

> F:=subs(rez,f);

[pic 6]

Таким образом, максимальное значение, равное 10,6, в условиях заданной системы ограничений функция F принимает при значениях неизвестных x=0, y=3.65, z=1.1.

Библиотека Optimization

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

• линейного программирования LPSolve;
• квадратического программирования QPSolve;
• нелинейного программирования NLPSolve;
• среднеквадратического отклонения LSSolve.

ПРАКТИЧЕСКАЯ ЧАСТЬ

Задание 1. Решить задачу линейного программирования, используя библиотеку  simplex   и библиотеку  Optimization.

Фирма производит три вида продукции (A, B, C), для выпуска каждого требуется определенное время обработки на всех четырех устройствах.

Рассчитать оптимальный план производства, если допустимое время работы на устройствах  I, II, III, IV составляет соответственно 84, 42, 21 и 42 часа.

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

...